[PATCH] Incremental update of pathfinder's passability grid

[Sylvain Gadrat]

When there is changes of the terrain or passability obstructions on the map, the pathfinder has to update a tile based representation of the world. This grid of tiles is needed by the long pathfinder to compute speedily long range paths.

Currently, when the pathfinder need to update its grid, it recompute the full grid instead of taking care only about regions that are modified. It is a little waste of time.

Since the grid is easy to compute there is nothing worrying for now but it can become harmful when we will try to optimize the pathfinder. Optimizations will need to have a way to reprocess only modified tiles because it is basically done by precomputing more than the tile grid.

This ticket is related to some "TODOs" in the simulation code that can be found

• in CCmpPathfinder::HandleMessage()
• in CCmpPathfinder::UpdateGrid()
• in CCmpObstructionManager::Rasterize()

[Sylvain Gadrat]

Note that terrain and obstructions are handled separately.

To do incremental updates of the terrain, it appears that it is possible to store i0, j0, i1 and j1 values when the pathfinder receives a "MT_TerrainChanged" event. It will can then use stored values to update only needed regions.

About obstructions handling it is interesting. It is split in two functions. Rasterise() from the obstruction manager computes a grid of obstructions, which is then merged in pathfinder's passability grid by UpdateGrid(). Rasterise() completely clean the grid, then write obstruction information from a list of entities present on the map.

In the attached patch, I implement the incremental update by storing a history of recently removed entities in the obstruction manager. So instead of cleaning the entire grid, it can only reset tiles from removed ones since the last call to Rasterise(). The pathfinder attach a little observer to the grid, so it can know the list of modified tiles to improve the merging step in UpdateGrid().

For performances, it makes Rasterise() slower and UpdateGrid() faster, so it has a negligible impact. Note that performances can be largely improved by using the history system for added, moved and removed entities instead of just for removed ones. Before optimizing, I would like to know your point of view. Is there something I do the wrong way ? Not compliant with your coding habits ?...

[Sylvain Gadrat]

First try to implement incremental updates, diff from the revision r10023

[Sylvain Gadrat]

Oops, miss attachement of "diffupdate.patch", the good one is "pathfinder-incremental-grid-update.patch"

Sorry

[Sylvain Gadrat]

Here is a new version of the patch, greatly improving performances.

There is two changes. A minor one : we now keep the grid observer into CCmpPathfinder's members. And a major one : we keep an history of all obstruction manager's modifications instead of just removals.

About the minor one, there is nothing special. Keeping the observer as a member allow us to avoid recreating it for each Rasterise() call. It impact performance by avoiding of recreating the observer's vector and it's huge number of elements. This change alone make the patch to obtain performances negligibly higher than the unpatched version instead of negligibly lower.

About the major change, it was harder than expected. We cannot simply store an history for added shapes, then reset tiles of removed shapes and set tiles of added shapes when we have to rasterise. This is trivial to do from the previous patch, but since a tile can be obstructed by two or more shape (think about two trees on the same tile), when we reset a tile, we need to be sure there is nothing obstructing it, including shapes that are not in the history.

So, the idea to successfully implement the history for all modifications. We keep in history all modified shapes, don't care if added or removed. We keep up to date a map permitting speed access to shapes that can impact obstructions information of a tile (using the tile's coordinates). So, to rasterise we can access a list of tiles to check for modification using the history, and process each of this tiles speedily, thanks to our new map.

[Sylvain Gadrat]

Improve performances, diff from the revision r10023

[historic_bruno]

What's the improvement in performance with the latest patch? How did you test, in Atlas?

[Sylvain Gadrat]

My test procedure :

1. I create two simulation's "comands.txt"
   1. A little one by playing against jubot on Oasis, rushing and winning the game speedily
   2. A big one by starting a game on Acropolis with 4 jubots and let it run (I trunk it to 20000 turns)
2. I build a reference version of pyrogenesis (svn plus my two added timers) and the one with the full patch applied.
3. I start "./pyrogenesis -replay=/path/to/commands.txt" for both comands.txt and both pyrogenesis version
4. I compare timers tc_Rasterize and tc_PathfinderUpdateGrid, which are respectively the time consumed by "Rasterise()" and "UpdateGrid() after rasterization"

Results :

version	comands.txt	tc_Rasterize	tc_PathfinderUpdateGrid
reference	little	68.0051 Mc	78.2193 Mc
incremental update	little	18.2494 Mc	21.0265 Mc
reference	big	44.7346 Gc	38.1679 Gc
incremental update	big	30.9104 Gc	8626.16 Mc

"incremental update" version reference to the second patch.

For the big comands.txt I ran pyrogenegis with "time", here the result :

• reference version : real 29m43.041s ; user 29m36.521s ; sys 0m05.760s
• incremental update version : real 29m02.272s ; user 28m52.380s ; sys 0m08.763s

[Sylvain Gadrat]

Cosmetic regarding coding conventions, diff from the revision r10175

[Sylvain Gadrat]

Version 3 is a very little update of the patch regarding code convention, mostly brackets moving. And tested merged in a more recent svn checkout.

[Philip Taylor]

(Finally got around to looking at this in some detail - sorry for taking far too long :-( )

With current SVN, 64-bit Linux, Pentium Dual-Core 2.16GHz, Gambia River, adding some TIMER blocks to measure each call:

• On first load, Rasterise is about 2.7msec, the rest of UpdateGrid is about 71msec. (That includes all the terrain computation so it's slow.)
• When constructing a building, Rasterise is about 2.7msec, UpdateGrid is about 1msec.

With the patch:

• On first load, Rasterise is about 4msec, UpdateGrid is about 70msec.
• When constructing a building, Rasterise is about 0.6msec, UpdateGrid is about 0.2msec.

The most common situation during gameplay will be buildings being built/destroyed, or trees being destroyed, and the pathfinder will run every turn, so the most important timing is Rasterise+UpdateGrid when only one or a few entities have changed since the last turn. When constructing a building in this test it only really needs to update about 4*4 tiles instead of 384*384, so in theory it could be up to 10,000x faster, but it's only about 5x faster with this patch.

But then I realised I was testing on a circular map, and tens of thousands of tiles are set to OUTOFBOUNDS each time. (That's less of a problem on square maps like Oasis since fewer tiles are out of bounds). If I just disable the out-of-bounds stuff entirely (rather than fixing it properly):

• When constructing a building, Rasterise is about 0.04msec, UpdateGrid is about 0.003msec.

So that's better, and easily fast enough.

I think my main concerns are memory usage and code complexity. On Gambia River, m_UnitInfluences has about 80K entries, with 8 bytes of data per entry plus a load of overhead for the std::multimap, so it's probably a couple of megabytes and not at all cache-friendly. There's already the approach used by GetObstructionsInRange to find shapes that might overlap a range of tiles, so I think it'd be better to reuse that (to simplify the code and to avoid wasting memory). Also, there might be performance costs that aren't measured, e.g. the cost of updating all the history data when a map is first loaded with thousands of entities, or the cost of the changes to Grid in other code that uses it (since adding the modify() call inside set() might stop it getting inlined nicely).

I tried a proof-of-concept patch of an alternative solution: instead of tracking exactly which tiles changed, just track the bounding box of the set of changed tiles. Use the existing subdivision thing to find shapes overlapping that rectangle, and recompute all the tiles within it. That seems to give similar performance in the house-building test (about 0.02msec for Rasterise on a slightly faster computer; I didn't integrate it with UpdateGrid but that should be straightforward). It'll process more tiles than in your patch, but in the common case it won't be many more, and the processing is much cheaper per tile (since there's no new data structures to update). I think it's significantly simpler (~100 lines of new code, vs ~400 in your patch, and I think the logic is more straightforward and less prone to bugs, though it'll need a little more complexity to efficiently handle multiple widely-separated obstruction changes per turn).

If the pathfinder is changed and UpdateGrid has to do a lot more work, it might matter that this alternative will process more tiles. But I think it probably won't matter - the new UpdateGrid will probably want to process large chunks of the map at once anyway (e.g. recompute a whole 8x8-tile chunk to find distances between the points on the edges, whenever a single tile inside that chunk has changed) (or e.g. use SSE to efficiently process a long row of tiles in 16-byte segments), so a list of a few large rectangles to recompute will be more appropriate than a list of many individual tiles. (This is largely speculation, though...)

So I think the question is: Does the approach in your patch have advantages over my patch? Yours is more complete and better tested, but I can spend some time making my one work properly if it seems a better approach, and I'd prefer to aim for whatever's best in the long term. Mine seems simpler (less code, less new data structures) and doesn't increase memory usage. Yours (if it removed duplicates from GridObserver::m_Modified) is more precise at finding the smallest set of changed tiles, but I'm not sure that's an important improvement over a rougher over-estimate of tiles given how UpdateGrid is probably faster at updating large chunks than single tiles. Am I misunderstanding or missing anything important here? (I expect I am but I'm not sure exactly what :-) )

[Philip Taylor]

incomplete proof-of-concept for alternative design

[Sylvain Gadrat]

I am agree with you on many points, notably :

• General : Having an exact list of modified tiles is not important at all, while the list contains all modified tiles and not a lot more.
• In my patch : The modification of Grid to accept observers is not really needed, basically I had to choose between observers on Grids or returning the list of updated tiles after rasterizing. I choose the one that makes it impossible to forget a rasterized tile in the list. So Rasterize() rasterize without taking care of remember the tile list, nor what kind of representation the pathfinder would expect.
• In my patch : Out of bound tiles are rasterized after each update and that's really bad. It could simply be optimized by not re-computing out of bound tiles at all if the history is used.

Then, in my patch, I think the impact of observers is negligible on other parts of code that uses Grids since the default observer is NULL, so the set() will just skip modifying it. So the only impact will by the read of the pointer (and possibly one cache miss, next calls to set() should have it in cache) and evaluate the condition (and occasional branch prediction miss, but over a series of set(), always the same branch is taken). Finally if it cause problem, it can be handled by making a special Grid class (without observers being the normal, with being the special) and/or template stuff.

About you patch now.

If I understand well, a summary can be written as :

 * Keep in memory a big rectangle surrounding all modified shapes
 * When a shape is modified, enlarge the rectangle to continue surrounding all shapes
 * When rasterizing, rasterize only tiles under shapes in the rectangle

I think about two main issues

• When rasterizing, I maybe miss it but I didn't saw any handle of removed Shapes. The shape is no more in the map, so not returned by GetShapesInRange(). It is very possible that I miss something.
• line 452, the "XXX" comment that warns about breaking if used with multiple grids. It can theoretically be used like that. Rapidly searching, UpdateGrid() can delete its grid and reconstruct one if the terrain is resized. Actually, all the history stuff in my patch is here to avoid writing this "XXX" :) My patch should work with the same limitation if instead of history stuff, it retain a simple list for modified shapes.

And I agree that it could cause troubles if there is two modifications on opposite side of the map. More, it seems to be the most common scenario since players bases are typically on opposite sides of the map, and there is a lot of modifications around players bases.

And finally my opinion. I think the simpler is the better. Keeping in mind we don't have to optimize Rasterize() (whereas it is a good side effect) since it already take a little time and is not called often. Same idea with the actual UpdateGrid(). It is just important to be able to report changed areas, since it is a step needed before implementing more complex/powerful pathfinding mechanics doing more pre-computation on UpdateGrid().

[Philip Taylor]

I think the impact of observers is negligible on other parts of code that uses Grids since the default observer is NULL

To be specific, it can change the inner loop of code like

for (u16 j = 0; j < entityGrid.m_H; ++j)
  for (u16 i = 0; i < entityGrid.m_W; ++i)
    playerGrid.set(i, j, playerGrid.get(i, j) + entityGrid.get(i, j));

(assuming the compiler can't be certain the observer is NULL) from

0105BAC6 mov  ebx,dword ptr [ecx+eax]  
0105BAC9 add  dword ptr [eax],ebx  
0105BACB add  eax,4  
0105BACE dec  edx  
0105BACF jne  0105BAC6  

to

0008C610 mov  ecx,dword ptr [edi+esi]  
0008C613 add  dword ptr [esi],ecx  
0008C615 cmp  dword ptr [ebp-98h],0  
0008C61C je   0008C62E  
0008C61E mov  edx,dword ptr [ebp-58h]  
0008C621 mov  ecx,dword ptr [ebp-98h]  
0008C627 push edx  
0008C628 push ebx  
0008C629 call GridObserver::modifiy (9F010h)  
0008C62E inc  ebx  
0008C62F add  esi,4  
0008C632 dec  dword ptr [ebp-5Ch]  
0008C635 jne  0008C610  

which is basically what you said (plus extra register pressure so the loop counter is put on the stack). Anyway, not a big deal as long as we're aware of it.

• When rasterizing, I maybe miss it but I didn't saw any handle of removed Shapes. The shape is no more in the map, so not returned by GetShapesInRange(). It is very possible that I miss something.

RemoveShape will call MakeDirtyUnit and expand the dirty rectangle to include the area previously covered by that shape. Then Rasterise will reset the whole dirty rectangle to 0 and fill it with all the shapes that still exist, so any tile that was only covered by a recently-removed shape will end up as 0. So I think that's alright, unless I'm missing the problem.

• line 452, the "XXX" comment that warns about breaking if used with multiple grids. It can theoretically be used like that.

Yeah, I think it'd probably be sensible to just remove that theoretical possibility since I can't imagine why we'd ever need it and it adds complexity to either of these patches. (AI scripts reuse the pathfinder passability grid, but they don't need the raw obstruction data.)

And I agree that it could cause troubles if there is two modifications on opposite side of the map. More, it seems to be the most common scenario since players bases are typically on opposite sides of the map, and there is a lot of modifications around players bases.

Yeah, it seems important to handle that case efficiently. With the dirty-rectangle thing, it would probably store a list of dirty rectangles, and when adding a new one it'll check if it's intersecting an existing rectangle, in which case it'll expand the existing rectangle to include the new one, else it'll add the new one to the list. (A little bit like ShapeHistory, but storing axis-aligned bounding rectangles so it can coalesce nearby shapes (keeping the list small without needing a hardcoded limit like 10) and so it doesn't have to do any work converting the shapes into tiles later.)

And finally my opinion. I think the simpler is the better.

Hmm, do you mean a variation of my patch (with some added complexity so it actually works properly) or a variation of your patch (maybe simplified to only support a single grid or to use something like GetShapesInRange etc) or something else? :-)

Keeping in mind we don't have to optimize Rasterize() (whereas it is a good side effect) since it already take a little time and is not called often.

I think the current 3msec for Rasterize is long enough to be slightly concerning - I'd like to target a smooth 60fps (more out of idealism than a practical requirement), so there's 16msec per frame, in which case an occasional 3msec delay is nice to fix.

It is just important to be able to report changed areas, since it is a step needed before implementing more complex/powerful pathfinding mechanics doing more pre-computation on UpdateGrid().

So we'll have a pathfinder like ​this and only want to recompute a small number of the 4x4-tile blocks, instead of the entire map. Then I think it doesn't really matter whether we return a list of changed tiles or a list of larger dirty-rectangles? (since in either case the pathfinder will just convert it into a small list of blocks to update)

[Sylvain Gadrat]

RemoveShape will call MakeDirtyUnit and expand the dirty rectangle to include the area previously covered by that shape. Then Rasterise will reset the whole dirty rectangle to 0 and fill it with all the shapes that still exist, so any tile that was only covered by a recently-removed shape will end up as 0. So I think that's alright, unless I'm missing the problem.

I missed the reset of the big square, sorry.

Yeah, I think it'd probably be sensible to just remove that theoretical possibility since I can't imagine why we'd ever need it and it adds complexity to either of these patches. (AI scripts reuse the pathfinder passability grid, but they don't need the raw obstruction data.)

If it is possible to remove it, it could simplify our patches for sure. I presumed resizing the map was doable in atlas, and didn't want to break anything.

Yeah, it seems important to handle that case efficiently. With the dirty-rectangle thing, it would probably store a list of dirty rectangles, and when adding a new one it'll check if it's intersecting an existing rectangle, in which case it'll expand the existing rectangle to include the new one, else it'll add the new one to the list.

Good idea. Just to mention a corner case before being surprised : the new rectangle can overlap more than one existing ones.
Another idea : it could be possible segment the map into regions and having a dirty rectangle by region. It avoids intersecting rectangles an allow to define exactly how many distinct rectangles we want to handle. Just an idea, there is certainly corner cases.

Hmm, do you mean a variation of my patch or a variation of your patch or something else? :-)

I didn't knew which one to prefer. Now I think working from your version can be sensible. Short term, the memory usage of the big(s) square seems simpler to keep under control than a tile's list. Mid term it let tweak the balancing among the number of tiles unnecessarily dirtied, the computational cost and the memory usage (maximal number of distinct rectangles).

So we'll have a pathfinder like this and only want to recompute a small number of the 4x4-tile blocks, instead of the entire map. Then I think it doesn't really matter whether we return a list of changed tiles or a list of larger dirty-rectangles? (since in either case the pathfinder will just convert it into a small list of blocks to update)

We agree on the fact that the path finder will just have to know which part of the map changed and the information being reported as tiles or rectangles doesn't matter.

I disagree with "pathfinder will just convert it into a small list of blocks". It needs to recompute the passability grid before updating the blocks abstractions. This passability grid can serves as "the maze" for HPA* (and derivateds), so it need it to resolve edges costs and the final level of path refinement. I think that "pathfinder will use it to reconstruct dirty tiles of the passability grid and get a smallest list of blocks".

However good rectangles will ever be better than a tiles list with duplicate entries :)

[Kieran P]

Latest status: Waiting for Philip to finish the new path finder before working on performance tweaks around it.

[kanetaka]

I revived Philip's patch, to fit new pathfinder. ​https://github.com/kanetaka2014/0ad/commit/bd3bb7a6a24c372d9fa1eca7227a1eda85645362

[Itms]

In 16751:

New long-range pathfinder.

Based on Philip's work located at ​http://git.wildfiregames.com/gitweb/?p=0ad.git;a=shortlog;h=refs/heads/projects/philip/pathfinder
Includes code by wraitii, sanderd17 and kanetaka.

An updated version of docs/pathfinder.pdf describing the changes in detail will be committed ASAP.

Running update-workspaces is needed after this change.

Fixes #1756.
Fixes #930, #1259, #2908, #2960, #3097
Refs #1200, #1914, #1942, #2568, #2132, #2563

[elexis]

In r23361 by Vladislav:

Improves performance of Atlas terrain elevation by updating the only changed terrain.

Reviewed By: Itms
Comments By: Stan
Differential Revision: ​https://code.wildfiregames.com/D2557