Area based long pathfinder optimization

[Sylvain Gadrat]

Hello,

I am a programmer and I recently discovered that playing with 0.A.D's pathfinding logic on my spare time is incredibly fun. While experimenting I thought about a way that can sligthly improve the pathfinder cpu usage and memory consumption. So I'll use this topic to outline the idea, feedback about progresses and get some ideas from you.

Disclaimer:

I am not expert (actually, not experienced at all) regarding 0.A.D's internals, pathfinding theories nor video games programming in general. I do it to play dolls with units on my spare time. I have not a lot of spare time. 0.A.D needs more impacting optimizations than this one, long pathinder is not a bottleneck. So, I can't ensure to finish, polish and maintain any code related to this idea.

For a global view of the pathfinding logic, you can read this post. I will only work on long pathfinder here.

Currently the long pathfinder is tile based. It splits the map in a grid of little squares (called tiles). Each tile holds passability information ("this tile is passable by infantry", "this tile is not passable by boats",...) and a cost class ("it is sand", "it is grass",...). With such a grid, when the pathfinder is asked to compute a path from point A to point B, it can run A* on the grid, considering each tile.

The optimization idea is to group identical tiles (same passability and cost class) into biggest squares named areas.

The first optimization with areas is the memory usage. With the grid we hold passability and cost information (2 bytes) for each tile. With areas, we need such information only once per area but we also need to store position and size (in my current implementation, 8 bytes) of each area, for a total of 10 bytes per area. Hoping there is at least an average of 5 tiles per area, it is an improvement. This "optimization" needs to be confirmed by experimentation, since in worst case (only areas containing an unique tile on the map), it takes five times more memory.

Memory consumption in diagram's example :

10x10 map = 100 tiles

11 areas

grid = 100 tiles * 2 bytes = 200 bytes

areas = 11 areas * 10 bytes = 110 bytes

Memory consumption in worst case (10x10 map) :

10x10 map = 100 tiles

worst case = 1 area per tile = 100 areas

grid = 100 tiles * 2 bytes = 200 bytes

areas = 100 areas * 10 bytes = 1000 bytes

Note that areas' memory consumption is not directly bound to the map's size, but to the design of the map. A giant map of flat sand can be discretized with 10 bytes but, unlike the grid, we never know how much memory will be used before processing the map.

The most interesting optimization is the cpu usage and the resulting path's smoothing. It is grouped, because while using less cpu, we will prefer straight lines to stairs (removing a fixme from the code).

The basic idea is that once a unit is in a passable area, it can go anywhere in this area without getting stuck. More, an area is homogeneous in movement's cost. With these both hypotheses, moving inside an area is really trivial, we just follow a straight line from origin to destination, the cost of the move is the length of the line multiplied by the cost of moving in the area. So we can limit the A* to only considering tiles that are needed to go from one area to another.

Of course it is interesting only if areas are bigger than 2x2 tiles since only inner tiles are skipped by A*. So, bigger areas are, less memory and cpu are needed to compute path.

To conclude this huge post : this solution is not a big deal, in fact it can be a real disaster in terms of memory usage. It is a poor attempt to mix ideas from navigation meshes and the tiles based current implementation. The good side is that it does not require to modify heavily the pathfinder, just changing the way data are hold and add a little smartness to get neighbours of a tile. Talking about navigation meshes, anyone could point me to a good article ? I only found some explaining that we can do all that we want at no cpu/ram cost, but nothing explaining how to do

[ribez]

hi,

i'm not a programmer, so excuse me if i will say a foolish thing.

Is it possible using a mix of the two techniques, so area is used only if it represents at least 5 tiles, otherwise tiles approach will be used?

[Rasunadon]

Good idea but 5 tiles minimum is false. You are using squares so it is at least 9 tiles. Maybe rectangles would work too?

[Wijitmaker]

Hi Sylvain. It looks like Philip is about to post, so I'll leave the technical analysis for him From a non-programmer point of view, I could see this working well in a static environment, but 0 A.D.'s world is very dynamic with entities moving, new buildings being constructed, trees being cut down... etc. I'm not sure how difficult it would be to update the areas?

Talking about navigation meshes, anyone could point me to a good article ?

Here are some articles:

http://www.ai-blog.net/archives/000152.html <= lots of links about halfway down the page

Here are some old articles:

http://www.gamasutra.com/view/feature/3096/toward_more_realistic_pathfinding.php

http://www.gamasutra.com/view/feature/3317/smart_move_intelligent_.php

http://www.gamasutra.com/view/feature/2738/evolving_pathfinding_algorithms_.php

http://www.gamasutra.com/view/feature/3137/profiling_data_analysis_.php?page=2

http://www.gamedev.net/page/reference/index.html/_/reference/programming/artificial-intelligence/pathfinding-and-searching/motion-planning-using-potential-fields-r1125

An additional resource is that we have had a former SSSI employee (Dan Higgins aka Major Glory) drop by the forums in the past and I'm sure he would be available to bounce some ideas off of. This was his last piece of advice to us:

What I'd suggest for pathfinding is the following:

1) Read my articles on pathfinding in AI Wisdom (3 in there) and my terrain analysis article in Game Programming Gems 3 (Sneak into Barnes & Noble, get a coffee and a chair. =)

2) First, and most importantly is the low-level pathfinder. Nail that down using some of the optimization techniques I discussed. Spliting over time is a big task, so just use an instantaneous path, but using some of the "beating memset" techniques for clearing the pathfinder for the next guy.

3) After that's great, and terrain analysis is in (see gems 3), use the terrain information to build a high-level pathfinding engine. Basically, put a grid over the terrain regions, then use a "graph" type of A*.. instead of 8 adjacencys, there are X number. One day, I'll write an article on this.. its long and complex, but is one of the keys to having hundreds of units pathfinding over long distances.

An idea of time: Took me a weekend to get pathfinding working... took me 9 months to optimize it to hard-core RTS level where pathfinding was never a performance issue. Again, you probably don't need it that optimized, just 100% reliable, never freezing the game, and applying a high-level system to even an instantaneous system will provide mega performance benifits.

[Ykkrosh]

I am a programmer and I recently discovered that playing with 0.A.D's pathfinding logic on my spare time is incredibly fun.

Sounds good . I think pathfinding is interesting since it's a fairly simple-to-define problem (find a good path between two points on a grid) but there's no perfect solution, and there's always some benefit in making it faster, so there's a huge range of alternative approaches and tradeoffs to explore.

While experimenting I thought about a way that can sligthly improve the pathfinder cpu usage and memory consumption.

I don't think memory usage is particularly important by itself - maps will rarely be more than maybe 512x512 tiles, and players have lots of RAM (>99% have at least 512MB, >95% have at least 1024MB, based on data from current users), so we can spend a few more bytes per tile without much worry. But speed is important, and memory usage is important in its indirect effect on speed due to cache usage - minimising the memory that the algorithm accesses is more relevant than minimising the total amount allocated.

The optimization idea is to group identical tiles (same passability and cost class) into biggest squares named areas.

This reminds me slightly of HAA* - have you seen that before? The hierarchy stuff is probably more important than the clearance stuff, though I suppose we should still ideally support some notion of clearance to cope better with formations or unusually large units (and/or smaller tile sizes). That article seems less similar now that I look at it again, but might still be an interesting thing to compare - it splits the map into a regular grid of clusters, then finds the important links between clusters and the distances between those link points inside the cluster, and does that for each passability class independently then merges redundant data at the end. That sounds like it may work more efficiently than your proposal if there is a high density of different passability/cost classes, since it can still use the same cluster size regardless of terrain complexity, though it has a higher cost for computing distances within a region and it looks like the implementation may be a bit more complex.

[Sylvain Gadrat]

Is it possible using a mix of the two techniques, so area is used only if it represents at least 5 tiles, otherwise tiles approach will be used?

Hmm, it can be possible by creating special areas containing a grid where uniform areas are inefficient. It can improve the worst case scenario, but it will be more complex to implement. So lets wait to see if such mix is needed before thinking of implementing it

Good idea but 5 tiles minimum is false. You are using squares so it is at least 9 tiles. Maybe rectangles would work too?

Talking about five tiles per area, I'd think of an average value obtained by : <number of tiles> divided by <number of areas>.

Sorry if it was not clear.

Rectangles should work very well, thanks to point that. My idea was that an area is useful only if it has a maximum of "inner tiles" (the skipped ones by A*). So, avoiding rectangles having a height or width of 2 tiles was a priority.

Writing (and re-reading) this post it appear clear that a rectangle is better than a lot of little square, to save some memory as to be able to take diagonal paths.

From a non-programmer point of view, I could see this working well in a static environment, but 0 A.D.'s world is very dynamic with entities moving, new buildings being constructed, trees being cut down... etc. I'm not sure how difficult it would be to update the areas?

To re-compute the entire map's areas, it is a little slower than to compute the grid version, but nothing worrying in theory, despite my current implementation lag on it I am confident than with some optimization it will be good enough.

If it is a real performance issue, when building or destroying something on the map, we could just re-compute impacted areas. It will not give a perfect result, but not far from very good in a really short time.

Here are some articles:

...

Here are some old articles:

...

Yeah thank you ! Some good readings for this week-end

I don't think memory usage is particularly important by itself - maps will rarely be more than maybe 512x512 tiles, and players have lots of RAM (>99% have at least 512MB, >95% have at least 1024MB, based on data from current users), so we can spend a few more bytes per tile without much worry. But speed is important, and memory usage is important in its indirect effect on speed due to cache usage - minimising the memory that the algorithm accesses is more relevant than minimising the total amount allocated.

My primary concern is the cpu time, but seeing that it can take five times more memory than the current implement scare me a little.

Good catch for minimizing cache failures. I didn't ever think about it, I'll try to remember and applying it cleverly.

This reminds me slightly of HAA* - have you seen that before? The hierarchy stuff is probably more important than the clearance stuff, though I suppose we should still ideally support some notion of clearance to cope better with formations or unusually large units (and/or smaller tile sizes).

Oh ! Very interesting ! Like I said, I have little to no experience, just knowing some concept (notably some of ones exposed in free entries of aigamedev ) and I had never heard about HAA* before. It sounds like I will try to implement that just after being happy with (or definitely trashing) the implementation of uniform areas. HAA* is more like a totally new algorithm whereas uniform areas are just an optimization of the existing one, it may be too hard for my first experience with 0.A.D's internals. Let it be the second experience.

If I understand well, in 0.A.D all units are at maximum 1 tile large (please correct me if I misunderstood). So clearance stuff is not needed. But I saw that you talked about reducing the tile's size. Such changes, without clearance stuff, could change the behavior of the pathfinder from always pessimist to often optimist. And an optimist long pathfinder could lead to units being stuck by a little group of trees, just large enough to make the short pathfinder give up, no ? Or worst, trying to shortcut through an impassable forest instead of moving around. I am sure I missed something, but else clearance is really important

[Sylvain Gadrat]

Ok, I succeed to implement a functional version, now I would like to profile it. Here are some questions about profiling.

I saw a macro named "PROFILE( xyz )" which seems to be perfect, except that results are not printed. Is there some documentation I missed that indicate how to have such stats printed ?

Is there a way to start 0.A.D without rendering ? I suspect it to disturb callgrind and sysprof and I focus on pathfinding, I don't really need rendering.

What's are your habits for profiling ? Your favourite tools ?...

[feneur]

Ok, I succeed to implement a functional version, now I would like to profile it. Here are some questions about profiling.

I saw a macro named "PROFILE( xyz )" which seems to be perfect, except that results are not printed. Is there some documentation I missed that indicate how to have such stats printed ?

Is there a way to start 0.A.D without rendering ? I suspect it to disturb callgrind and sysprof and I focus on pathfinding, I don't really need rendering.

What's are your habits for profiling ? Your favourite tools ?...

I don't know all the intricate details etc, but my guess is that the results are what is displayed when you press the F11 key, that does bring up profiler info in either case. (Shift+F11 to save current profiler data to "logs/profile.txt")

[Ykkrosh]

Oh ! Very interesting ! Like I said, I have little to no experience, just knowing some concept (notably some of ones exposed in free entries of aigamedev )

I think none of us really have any experience with this - we're all learning as we go along, which is what makes this fun . I implemented the game's current pathfinding code, but that was the first time I've ever done non-trivial pathfinding, so that (plus a random collection of articles I've noticed on the web) is the limit of my expertise, so I don't know what approaches will really work well

If I understand well, in 0.A.D all units are at maximum 1 tile large (please correct me if I misunderstood). So clearance stuff is not needed.

I think that's true (ignoring ships, which will be handled separately). But if you have 64 units in a phalanx formation, it might be nice if they picked paths that avoided going near obstacles that would cause the formation to break up, so clearance could perhaps be useful in that case. But that's probably an unnecessary complication

But I saw that you talked about reducing the tile's size. Such changes, without clearance stuff, could change the behavior of the pathfinder from always pessimist to often optimist.

Yeah - the current problem is that the tile grid is a poor approximation for the obstruction shapes of trees/rocks/buildings/etc, so units either get stuck or fail to find valid paths. Reducing the pathfinder tile size would allow it to be a better approximation. But we probably have units larger than half a tile, so clearance might be important for that. This is all kind of hypothetical though - we don't have any definite plans, and it would be good to keep things as simple as possible (but no simpler).

Here are some questions about profiling.

I wrote a wiki page - does that help?

[Sylvain Gadrat]

Thank you for the wiki page Philip, it is exactly information I needed.

So, I played a little more with the Area optimization. While I have to continue to tune performances to be sure, I begin to have serious doubts about de viability of the solution. Let me explain why.

First, I have to correct the second graph of my first post, the one showing tiles considered by the pathfinder.

It presented tiles that could be used by pathfinder but, in the example, only the ones used to compute the brown path impact on performances.

Heres the graph with only really used tiles :

The first goal of areas was to reduce the number of tiles considered by the pathfinder. Here we can see that in the example it will use 40 tiles with the current implementation versus 39 with areas. That's not really a big deal.

Actually, it is not an improvement at all.

With the tile based logic, A* process only direct neighbours of the current tile. So the distance between the current tile and the next one is one tile, simple and easy.

With area based logic, A* can process arbitrary tiles. So we have to compute the distance between the current tile and the next one. And computing the distance is not trivial.

Briefly, It seems that areas do not decrease a lot the complexity of the path finding problem, but make each node harder to compute.

In the next days I will :

1. Finish tweaking of areas and try a little to find a magical trick that solves above outlined problems.

2. Begin to think about implementing HAA* which seems interesting.

[Rasunadon]

If there are all tiles the same in one area why pathfinder needs to check all tiles around it and not only one (or two, entry and a exit one) from each area?

[Sylvain Gadrat]

That's because all tiles on the border of the area could be good exit point.

Considering a unit travaling on sand and grass at same cost, here a picture with two acceptable path (brown : common ; blue : to the last blue dot ; red : to the last red dot)

Both path tarvel from the same area to the same one, are going through the same ones, but dont exit but exit the big sand area from different points.

Maybe limiting transition between areas to only one point, generating a high level graph and runing some kind of Hierarchical A* could be a good enought approximation.

Edited August 6, 2011 by Sylvain Gadrat

[Wijitmaker]

I had another thought today on this reading the RMS map thread Michael posted about the problem of to many trees.

Would it be any advantage in having a second 'forest dynamic border' (unvisible to the player) that is based on trees? This could possible block out clumps of areas that the pathfinder could omit from it's long pathfinder calcuations? This would be a Boolean default property in the actors that 90% of the units in the game would be constrained by.

Dunno - not being a programmer, I'm purely conceptual. Just a thought, I have no idea if it would actually work in code