Improve the RangeManager (and other components) spatial subdivision system

[wraitii]

One of the reasons why the game is slow in the later game is that our current implementation of Spatial Subdivisions isn't really clever, and leads to slowness (in particular because we need to sort and make unique keys in the queries).

We need to improve on that system. A quadtree was proposed and rejected, since it wasn't really more useful (it has the same uniqueness limitation in a basic implementation). So we need something else.

[wraitii]

Above patch changes the subdivision system slightly. All items are now unique, and stored only in one subdivision. If the half-size of their obstruction square is higher than the subdivision's size, they're stored in a general array, otherwise in the proper subdivision. When returning results, we return one subdivision more on each side to ensure that we do return all elements, and we then add the general array (I think I forgot that in the current patch).

In effect, this allows to remove the sorting and making unique non-sense that we were having before, which should be a little faster.
My implementation is also dynamic sized, a template (I changed the range manager to pass entity data pointers directly, for example, which might also be ever so slightly faster than the current system with entity maps where we need to access the entity data using the ID, or which might allow us to change entity maps to a faster system).

Needs some reviewing, I get a weird error where the game tries to malloc absurd amounts of memory (I had 92tb once) sometimes when appending vectors, I don't really get why.

(you'll notice I reuse a vector in the rangemanager to avoid too much fragmentation, it's currently preset to 12000 entities but that's a bit much).

NB: I haven't actually tested that this is faster. This needs to be done, too.

[wraitii]

Some numbers for 50000 entities, for each category the first occurence is my method and the second is redfox's. I have the same results for far fewer entities, which leads me to think my subdivision is faster, though not by a huge margin. The fact it's also dynamic makes me think it's a good direction.

time to add entities: 0.001506
time to add entities: 0.003451
time to query these entities: 0.000347
time to do stuff on those entities: 0.000175
time to query these entities: 0.008005
time to do stuff on those entities: 0.000225
time to move entities: 0.500477
time to move entities: 1.32654

[tom]

Well, this patch is really good, I hope you can provide a specific file to download, I'll pack you test them, thank you!

[sanderd17]

See also http://www.wildfiregames.com/forum/index.php?showtopic=18826 for a different approach to get rid of the uniqueness issue (not fixing the other issues with the current spacial code).

[wraitii]

In 15617:

Revert RedFox's changes to Spatial subdivisions in the simplest possible way (hopefully won't cause OOS, but at least we'll get reports). Fixes #2573, Refs #2430 . There probably are opportunities to remove more things.

[Itms]

The patch won't apply cleanly on SVN anymore, and we won't get it in for A18 anyways.

I'll take a look at it after the release (as I worked much with the range manager), if wraitii doesn't mind of course.

In the meantime, I put it out of our huge review queue ;-)

[Itms]

Here is a patch adding a new spatial subdivision class to the simulation. It is faster but less precise, so when performing range queries, we end up with more entities to process and the queries are slowed down a bit.

However the overall performance gain is good: on a non-visual replay the simulation update is at most 10 ms quicker with the patch, whereas ExecuteActiveQueries is at most 1 ms slower.

Once this is committed, I will look into the remaining use of the old spatial subdivision in the obstruction manager. For static elements, I think it is not worth using the new subdivision, but it might be possible to improve the old one for this specific use case.

[Itms]

Addressed style comments

[Itms]

In 16540:

Add a new spatial subdivision, based on an old patch by wraitii.

This subdivision is faster but less precise, so range queries get more entities and are a bit slower (up to 1ms approx.), but the overall gain on a simulation update is always positive and can reach 10ms per frame.

For now, this new subdivision is only used by the range manager, integrating it in the obstruction manager might be sensible.

Refs #2430

[Itms]

Leaving the ticket open for more enhancements wrt the obstruction manager.

I will most probably include said enhancements into the new pathfinder, so I'm adding the corresponding keyword too.

[Itms]

In 16544:

Some entities (like birds) can have negative positions without being marked as out-of-world.

Refs #2430

[kanetaka]

In CCmpRangeManager::Init(), m_Subdivision is reset by width and height. Index() is used there but yet m_ArrayWidth = 0 at that point so assertion fails. You should check member variables' initializing order.

[Itms]

Replying to kanetaka:

In CCmpRangeManager::Init(), m_Subdivision is reset by width and height. Index() is used there but yet m_ArrayWidth = 0 at that point so assertion fails. You should check member variables' initializing order.

This is already fixed in r16547...

[Itms]

After taking a look when working on pathfinding stuff, the standard spatial subdivision is more suited than the fast one for the obstruction manager.