Opened 10 years ago
Closed 9 years ago
#2430 closed enhancement (fixed)
Improve the RangeManager (and other components) spatial subdivision system
Reported by: | wraitii | Owned by: | Itms |
---|---|---|---|
Priority: | Should Have | Milestone: | Alpha 19 |
Component: | UI & Simulation | Keywords: | |
Cc: | Patch: |
Description
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.
Attachments (2)
Change History (18)
by , 10 years ago
Attachment: | newSubdivision.patch added |
---|
comment:2 by , 10 years ago
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
comment:3 by , 10 years ago
Well, this patch is really good, I hope you can provide a specific file to download, I'll pack you test them, thank you! ==
comment:4 by , 10 years ago
Milestone: | Alpha 16 → Alpha 17 |
---|
comment:5 by , 10 years ago
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).
comment:7 by , 10 years ago
Milestone: | Alpha 17 → Alpha 18 |
---|
comment:8 by , 9 years ago
Keywords: | review quadtree removed |
---|---|
Milestone: | Alpha 18 → Alpha 19 |
Owner: | changed from | to
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 ;-)
comment:9 by , 9 years ago
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.
comment:10 by , 9 years ago
Keywords: | review added |
---|
comment:12 by , 9 years ago
Keywords: | pathfinding added; review patch removed |
---|---|
Summary: | [PATCH] Improve the RangeManager (and other components) spatial subdivision system → Improve the RangeManager (and other components) spatial subdivision system |
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.
follow-up: 15 comment:14 by , 9 years ago
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.
comment:15 by , 9 years ago
comment:16 by , 9 years ago
Keywords: | pathfinding removed |
---|---|
Resolution: | → fixed |
Status: | new → closed |
After taking a look when working on pathfinding stuff, the standard spatial subdivision is more suited than the fast one for the obstruction manager.
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.