Forest And Pathing

[Chakakhan]

There is currently an issue with the pathing that allows units to get stuck in a forest. To make a long story short, it has to do with the long path finder and the short path finder having different ideas about what is a passable area and what is not. I did some play testing today on other systems and the behavior is pretty much the same for all the 3D RTS games I tried (AoE3, AoM, AoEo).

So in the picture above, from AoE3, the green arrows show where units can pass through and the red X's show where units cannot pass. The map designers were careful to make it visually clear where you could and couldn't pass and the system tolerances were designed along those same lines.

Pathfinding In 0 A.D.

Let me explain a few technical things about the way we "pathfind" and move units around the game world. 0 A.D. uses a "long path finder" to find the best path from the starting point to the requested destination (if one exists). It basically breaks up the terrain into a series of square "tiles" and then uses an algorithm (A* basically) to figure out a path to our destination at the tile level. It figures out if a tile is passable or not and if not it will rule out any path across that tile. It eventually finds a set of adjacent tiles that will take us from source to destination, or it fails and no path is returned. It then creates a set of waypoints along those tiles and saves that as a units long path. The long path doesn't worry about moving units, it only considers static objects. It is not useful to consider moving units at this level because it could take minutes to get to a destination and by then all the non-static units might have moved.

Then 0 A.D.'s short path finder finds a path to the first long path waypoint using a different algorithm. The short path algorithm doesn't navigate at the tile level like the long path finder, it navigates the best path based on looking at the objects in its way. It can consider other moving units and does so if it runs into an obstruction along its path (actually the unit just requests a new short path telling the algorithm to consider moving units). When it reaches the long path waypoint it was headed for it recalculates a new short path to the next waypoint along the long path. Once a unit reaches a long path waypoint it requests a new short path to the next long path waypoint and so on until eventually it reaches its final destination or it is blocked.

This is a simplification of the process as the algorithms have to account for changes to the game world. For example, what if a wall was built between the time a unit requested a long path and the time it reached the location of the wall. The wall now invalidates the units long path, so it has to recalculate a new long path. There are lots of other corner cases that must be considered as well (feel free to look at the code for the finer details ).

Now with that explanation, hopefully the image below will make some sense. This is part of a screenshot taken from 0 A.D. It is a forested area near the center of the map "Median Oasis". It is currently very easy to get units in a formation stuck in this area. I took this screenshot with the 0 A.D. developer option "pathfinder overlay" turned on (press shift+D to get the developer menu). This places a red box on all the tiles that the long path finder considers impassable. Take a look at the image below:

First off notice that it is not very clear from a players perspective which paths are passable and which are not. Look at the wide spot between the two trees just in front of the cavalry unit. As indicated by the red tiles, the long path finder does not consider that area passable.

Secondly notice that the area where the horse is located is completely surrounded by red impassable tiles.

Remember we calculate our path at the tile level in the long path finder, but the short path finder uses a different method. The short path finder uses the blue squares around the trees and the unit to see if there is enough room for a unit to pass through. In other words, if the square around the unit can be moved between the squares around two trees, the unit can pass between the two trees. So when using the short path finder we can easily pass through that wide opening directly in front of the cavalry unit. Under most circumstances a combination of long and short path finders gets the unit through that area without any problems. As far as I know a single unit will not get stuck going through the forest with the current version of the code in SVN (I tried to reproduce this for over an hour and could not).

Formations

Things get a bit more complicated when a unit is traveling in formation. When a unit is in formation it is following a proxy unit which actually holds the long path for the entire formation. So when you tell a formation to move it actually generates a long path for a placeholder or proxy object which represents the formation. All the units in the formation actually follow a particular point on this proxy object which represents the units target position in the formation. As the proxy object moves along the path to the destination the individual members of the formation will calculate their long and short paths to their target position on the proxy object many times along the way.

The differences between what the long and short path finder consider passable is what causes units to get stuck.

If a unit in a formation is in the open area where the cavalry unit is in the image above and both his long and short path need to be recalculated and the proxy object is already on the other side of the forest then we get stuck. The pathfinder tries to find a long path to the formation proxy and since he is in an area surrounded by impassable squares he can not calculate a new path and he is stuck.

That is the bug in the current code and we are looking at the best way to solve that problem in code.

It is also very important that we make it clear to both the player and the map designer what a passable area is. We need to decide on a clearance threshold and then we can adjust the code to match. Note that making this value really small slows down the algorithms. It should be something reasonable like in that first image from AoE3 I think.

Any feedback or ideas are welcome.

Cheers!

Note: I am brand new looking at this code, so Philip or anyone else please feel free to correct any bad technical assumptions I have made.

[k776]

Nicely written. I have a far better idea of how it works now.

Why can't the long path finder simply pick it's path based on the blue areas?

If performance is an issue, why not introduce a third path finder?

long = based on the tiles

medium = calculated for every 25% of the long path

short = calculated within the units LOS

The problem I still see with having a long path finder though is that units could walk many times more distance than they needed to if a line of trees had only a single hole.

Is there more advanced, faster algorithms that can be used?

[Chakakhan]

Why can't the long path finder simply pick it's path based on the blue areas?

I left out a lot of the edge case details in my description, size and clearance are actually part of the pathing consideration. The short and long path finder need to agree on what is passable and what is not. They currently don't always agree completely.

Performance is dramatically affected if you decrease the tile size (therefore increaseing the total number of tiles), so you can't just reduce the tile size to get higher resolution without taking a major performance hit.

If performance is an issue, why not introduce a third path finder?

long = based on the tiles

medium = calculated for every 25% of the long path

short = calculated within the units LOS

That is pretty close to what we have, what you are calling medium and short are both rolled into the short pathfinder.

The problem I still see with having a long path finder though is that units could walk many times more distance than they needed to if a line of trees had only a single hole.

Yep, that is certainly possible. It could be considered bad map design to create a map like that knowing that large groups of units roaming around is a part of this type of game. On the other hand it could be considered a strategic challenge as well. Either way I think it should be visually evident to the player what is going on.

Obviously we need to make some code adjustments. I just don't think we want to make a knee jerk change until we as a team have looked at this issue holistically and come to a consensus about what constitutes good game play. Because that is really what this is all about!

Is there more advanced, faster algorithms that can be used?

We are currently using the A* algorithm with lots of optimization for the long path finder and it is considered the best for this type of problem. There are lots of adjustments that can be made and lots of fine tuning. Its just a tough problem and it is very easy to fix one thing while breaking a dozen others if you aren't very careful. The current code is very well written and well designed so once we figure out the right solution, I don't think the changes will be that difficult.

[fcxSanya]

I don't saw our pathfinder code, but from your screenshot it looks like red tiles with only single tree inside can be considered as passable, because indeed unit can move through them. Can our code calculate passable/impassable tiles for long pathfinder more accurate ?

[Chakakhan]

I found a great quote from David Pottinger, the guy who was the technical lead on AoE2. It backs up my statements about cost and complexity:

It is interesting to note that Pottinger writes, "Pathfinding is one of the slowest things most RTS games do (e.g. Age of Empires 2 spends roughly 60 to 70% of simulation time doing pathfinding)." Having played AOE and AoE2, and being aware of the fairly small size of the maps (usually less than 100 x 100 tiles) I would have thought it would have been possible to pre-calculate paths and store them leaving the CPU time for other things.

He follows that up with a list of things to consider, the following is the first item on his list:

• Terrain analysis doesn't need to be exact. If you try to make it perfect, you'll either end up spending a lot of time tweaking heuristics or you'll have a lot of extra areas that really don't buy you anything.

The article summary is here: http://www.gilgamesh...es/page_29.html

I have a copy of it if you are interested let me know. In this article he talks briefly about terrain analysis for pathing and AI.

[ribez]

wow

this is why i love this game and this forum, because following the development process is very instructive and interesting, even for a non-programmer like me

[Ykkrosh]

If a unit in a formation is in the open area where the cavalry unit is in the image above and both his long and short path need to be recalculated and the proxy object is already on the other side of the forest then we get stuck. The pathfinder tries to find a long path to the formation proxy and since he is in an area surrounded by impassable squares he can not calculate a new path and he is stuck.

Hmm... I think the difference between in-formation and not-in-formation may just be an accident - I added the "Sort of hack" to CCmpUnitMotion::PathResult in the PATHSTATE_WAITING_REQUESTING_LONG state here, and I can't remember any reason why PATHSTATE_FOLLOWING_REQUESTING_LONG shouldn't be changed to do the same thing, so that it doesn't always abort when the long path has zero length, which might possibly help. (But it doesn't seem a totally robust solution so it would still be good to have a more proper way of handling forests so units don't often get stuck between impassable tiles in the first place.)

Philip or anyone else please feel free to correct any bad technical assumptions I have made.

Everything looks right to me

Why can't the long path finder simply pick it's path based on the blue areas?

If performance is an issue, why not introduce a third path finder?

The long pathfinder approximates the map as tiles for performance, and also so it can account for variable movement costs across different tiles (e.g. prefer moving along roads rather than mountainsides - the short pathfinder has to ignore movement costs entirely since it's not tile-based). The difficulties (and/or bugs) come in the interactions between different pathfinders that have different levels of approximation, so adding a third pathfinder would add more interactions and likely make it more complex and more fragile.

I don't saw our pathfinder code, but from your screenshot it looks like red tiles with only single tree inside can be considered as passable, because indeed unit can move through them. Can our code calculate passable/impassable tiles for long pathfinder more accurate ?

It can never be perfectly accurate, since it varies depending on the size of the moving unit and since tiles are always an approximation - the impassability can either be an overapproximation (like it is now), where units will tend to avoid walking through gaps that they actually can fit through since they think the tiles are blocked, or an underapproximation, where units will think they can walk through a forest/wall/city/boulder-strewn-valley/etc until they're standing right next to it and then they suddenly realise they can't actually fit and they have no idea how to find an alternative path around the obstacle.

(Hmm... Currently the implementation (CCmpObstructionManager::Rasterise) considers a tile to be impassable if the central point of that tile is within an obstruction shape (the blue squares), so it's an underapproximation, but that's only for 'static shapes' (rotatable-rectangle things like buildings). For 'unit shapes' (more efficient but non-rotatable-circle things like trees) it considers a tile impassable if the obstruction shape overlaps any part of the tile, so that's more of an overapproximation. I'm not sure that discrepancy is intentional.)

[Chakakhan]

Hmm... I think the difference between in-formation and not-in-formation may just be an accident - I added the "Sort of hack" to CCmpUnitMotion::PathResult in the PATHSTATE_WAITING_REQUESTING_LONG state here, and I can't remember any reason why PATHSTATE_FOLLOWING_REQUESTING_LONG shouldn't be changed to do the same thing, so that it doesn't always abort when the long path has zero length, which might possibly help. (But it doesn't seem a totally robust solution so it would still be good to have a more proper way of handling forests so units don't often get stuck between impassable tiles in the first place.)

I made this change when researching and they don't get stuck.

(Hmm... Currently the implementation (CCmpObstructionManager::Rasterise) considers a tile to be impassable if the central point of that tile is within an obstruction shape (the blue squares), so it's an underapproximation, but that's only for 'static shapes' (rotatable-rectangle things like buildings). For 'unit shapes' (more efficient but non-rotatable-circle things like trees) it considers a tile impassable if the obstruction shape overlaps any part of the tile, so that's more of an overapproximation. I'm not sure that discrepancy is intentional.)

I think we should change this so that trees are treated similar to other static objects and see how it feels. If we make both of these changes I think we will be a lot less likely to have this type of issue. I will code this up and put up a patch for your review when I get home from work tonight (unless you have already done it )

[Ykkrosh]

I think we should change this so that trees are treated similar to other static objects and see how it feels.

Hmm, trees are 1.5m (3/8 of a tile) in radius, so if they're done exactly like static shapes then they'll often fall entirely between tile centers and won't block any tiles at all, so units will probably never choose to walk entirely around forests instead of through them. Maybe that's okay.

I doubt I'll have time to look at this myself, so please feel free to fix it . (Trees ought to remain as unit shapes instead of static shapes ((these names are kind of rubbish - they made a bit more sense when only units had unit shapes)) since that makes the short pathfinder a lot faster (because it can assume they're axis-aligned), so I think it should be fixed by changing the calculations in Rasterise.)

[Pureon]

Very nice introduction to the topic Chakakhan

[Chakakhan]

Hmm, trees are 1.5m (3/8 of a tile) in radius, so if they're done exactly like static shapes then they'll often fall entirely between tile centers and won't block any tiles at all, so units will probably never choose to walk entirely around forests instead of through them. Maybe that's okay.

I doubt I'll have time to look at this myself, so please feel free to fix it . (Trees ought to remain as unit shapes instead of static shapes ((these names are kind of rubbish - they made a bit more sense when only units had unit shapes)) since that makes the short pathfinder a lot faster (because it can assume they're axis-aligned), so I think it should be fixed by changing the calculations in Rasterise.)

Well, yea, trees are a little different aren't they.

Seems like we need a different algorithm for them, maybe one that handles small objects better. I don't think one tree should be able to obstruct an entire tile by itself. And if two trees are on the tile, but on the same side then they probably shouldn't block it either. But if there are two trees each on opposite sides of the tile then they probably should.

What if for trees (and other small objects) we broke the tile up into thirds or some other reasonable size and write the algorithm so that it is based on a small object intersecting more than one of the fractionalized tile areas? For example, if we broke the tile into thirds and we got a hit on the tile for two of the three we would mark it blocked for pathing. We would need a new way to specify this type of object so that we can differentiate it from the other unit types (we may already have some way to do this - maybe the non-moving flag or something?). Assuming we broke each tile into thirds, we loop through them for each unit and if we get a hit on a tile section, we see if another section of the tile is already hit and if so mark it blocked. That way we still only have to hit each tile once per tree.

Thoughts?

We should probably refactor those names at some point as that is a little confusing.

[Ykkrosh]

What if for trees (and other small objects) we broke the tile up into thirds or some other reasonable size and write the algorithm so that it is based on a small object intersecting more than one of the fractionalized tile areas?

Could maybe work - probably the easiest way is for Rasterise() to compute a high-res grid like it does now, then downsample to the tile resolution (with a threshold so a tile is impassable if >=50% of sub-cells are obstructed).

Or we could just increase the resolution of the pathfinder grid, maybe, and have 2x2 cells per terrain tile (instead of 1x1 like now). We need about 2 bytes per cell (for CCmpPathfinder's Grid<TerrainTile>), so a 512x512 map is still only 2MB at the increased resolution. (Or we could split it into a high-res passability grid with 1 bit per cell, plus one TerrainTile per tile, so it's 512KB+32KB). Then the tile-based A* can work over these higher-resolution cells, though we'd probably need some hierarchical-A* optimisations so it's faster at searching through the large empty spaces. Then our pathfinding cells will be a closer match to the size of our units and trees, and it won't be such a necessarily bad approximation.

[Chakakhan]

Well changing the resolution of the pathfinder grid might be the cleanest solution.

I probably should try both ways and see where I run into trouble with each one. Then we could also get an idea about the performance impact of each solution as well.

So with the rasterise change are you proposing that we process all unit type objects the same way or that we separate out tree/small objects and process them differently like I mentioned?

[Ykkrosh]

Then we could also get an idea about the performance impact of each solution as well.

I think Rasterise is called rarely so its cost shouldn't be particularly important (and it could be optimised significantly by only dirtying subregions of the grid when obstructions move, regardless of this change). The tile-based A* would have to increase its max steps by 4x to match the old behaviour, so it should be 4x slower in the worst case, but it's about the simplest possible A* so algorithmic improvements (which are needed anyway) should mitigate it. So I think it'll be hard to compare performance impact usefully now since we need optimisations that will totally change the performance later. Comparing how well they work in terms of implementation difficulties and path quality and unit stickiness sounds like it'd be pretty useful, though.

So with the rasterise change are you proposing that we process all unit type objects the same way or that we separate out tree/small objects and process them differently like I mentioned?

Might as well handle them all the same way, I think - that doesn't sound like it should be any more complex and it might result in better behaviour around static shapes like rocks and buildings.

[Chakakhan]

Sounds good, I will start on this tonight.

[historic_bruno]

I may be missing something obvious, but isn't it intended that units will always be able to pass through a forest, so trees should not even create an obstruction? (Except to siege units, if I remember correctly)

Forests are probably the most illustrative example of pathfinder bugs, but I'm not sure we should tailor the algorithms to them if the above is true.

Related: I think it would be nice if there was a higher terrain cost applied for passing through a forest, and most of the time units would want to go around if possible.

[kissofdeath]

I love the forums of 0 a.d. The posts are so well written, and give the reader a decent idea of the implementation.

Great job Kenny, excellent post.

[Chakakhan]

I may be missing something obvious, but isn't it intended that units will always be able to pass through a forest, so trees should not even create an obstruction? (Except to siege units, if I remember correctly)

Well, not sure what the story on that is. I think there should be forest that are so dense that it makes a lot more sense to go around, especially an army with supplies and all that stuff. You would certainly have to make pathing exceptions if you wanted to make a dense forest passable, the obstacle code would have to handle trees in a special way - at a certain density, the trees are pathed differently. Otherwise you could pass through trees everywhere and thats not good. So one of the game designers will have to let us know what the desired goals are and then we can tell them how reasonable that is from a code perspective.

Forests are probably the most illustrative example of pathfinder bugs, but I'm not sure we should tailor the algorithms to them if the above is true.

As you say, forest make the problem more likely to occur and it is also very obvious when it happens there. The same things are happening in large battles, but its just not noticed as much because units are getting killed etc. Other things like lag and jerkiness become a much more obvious problem than bad pathing in that situation.

Solutions to performance problems are also being designed and mulled over as well. As Philip mentioned, the code is not using highly optimized versions of the algorithms yet. It's just better to get game play elements right before optimizing it too much. He has lots of ideas on how we can optimize the code once it is in a reasonable game play state.

Related: I think it would be nice if there was a higher terrain cost applied for passing through a forest, and most of the time units would want to go around if possible.

I totally agree with this!

[ribez]

what about ambush in forest? will it be possible with new implementation of pathfinding?

[Rasunadon]

Related: I think it would be nice if there was a higher terrain cost applied for passing through a forest, and most of the time units would want to go around if possible.

I think it should be so. Your soldiers should avoid forests if you tell them to move somewhere. They should go in the forest only after your direct command to go in it.

Green = forests, Blue = soldiers and their path, Red = where you tell them to move

[Chakakhan]

The changes will actually make it easier to navigate in the forest.

Ras, that could be achieved by making forested terrain very undesirable to the long pathfinder. This will be possible.

[Wijitmaker]

what about ambush in forest? will it be possible with new implementation of pathfinding?

This capability would indeed be welcomed for the Iberians:

"Hero" Aura: "Tactica Guerrilla": <(TAHK-tee-kah gay-REE-yah); means: guerrilla tactics> The Iberians were singularly well known for their use of guerrilla war tactics and the concept of fighting in this fashion came from them; the word itself being derived from medieval Spanish. Time and time again they sucked their enemies into ambuscades. Effect: The Hero and any units grouped with him are invisible to enemies when idle or moving. They will only become visible when performing an action, such as attacking an opponent. Furthermore, invisible units (like units concealed in forests) aren't considered when determining if a player has been wiped off the map.

Here are some other comments on forest terrains: http://trac.wildfiregames.com/wiki/XML%3A_Terrain

Attached is an old image too for what it is worth

The ranger unit in Battle for Middle Earth would be a good example of the behavior of Iberian units in the guerrilla use.

[Rasunadon]

Ambush and Iberians? Easy, all other nations have increased the cost of movement through forest terrain, Iberians not.

[kissofdeath]

I'm missing something about the path finding logic.

If the single cavalry unit is surrounded by red tiles (as shown in kenny's first post) and the short pathfinder uses the way points set by the long pathfinder, then how can the single cavalry unit even get out of the forest in the first place?

wouldn't the long pathfinder not return any way points, since it can't find a valid path from near those trees to outside the forest?

Or does the short pathfinder actually start moving the unit and hope to find a path when the long pathfinder doesn't return any way points?

[Chakakhan]

I'm missing something about the path finding logic.

If the single cavalry unit is surrounded by red tiles (as shown in kenny's first post) and the short pathfinder uses the way points set by the long pathfinder, then how can the single cavalry unit even get out of the forest in the first place?

wouldn't the long pathfinder not return any way points, since it can't find a valid path from near those trees to outside the forest?

Or does the short pathfinder actually start moving the unit and hope to find a path when the long pathfinder doesn't return any way points?

Good question!

If the long path finder can't find a path then we try with the short path finder. If the short path finder finds a path then we are good, if not we have problems. There was a bug in the code which was causing units to get stuck. If a unit was in formation and the long path finder failed then the short path finder didn't always run. That is fixed, but we are still looking at ways to improve pathing so that the default pathing code handles most issues and we avoid having to code too many special case solutions.

It is a lot less likely that you will get stuck with the latest updates, but there are a few conditions where bad pathing can happen because of the issues discussed above. I am currently working on a task to test a couple of solutions and see which one gives us better pathing.

Cheers!