Comment by LorenPechtel

Thought here: If I'm reading this right the cache remains valid unless something is done to the world state. Thus how about dumping the cache when the world is altered, the separate thread simply sits there rebuilding the cache. If an object should move one unit but the cache isn't there simply note the movement but don't update it. Next time around when you find the entry in the cache you move it two units. Given the stated calculation times I would think the user would not see this.