Hi everyone,

I'm trying to do some basic pathfinding with the A* algorithm for an rts game. I wondered, which is the right cell size to choose. My first idea was to set the cell size to width of the unit with the highest width in the game. Otherwise I would have to check nodes at the sides too, to see if the unit can pass.

For small units the cells can then maybe be divided in subcells, which will then be examined.

What do you think about this?

If you have any recommendations for articles/tutorials/books about this (not basic A*, but rather how to apply it for rts games), it would be very nice.

Thanks in advance!

I think a more natural way to do this is to consider each cell to represent the center of a unit, and the cell will have a property that is the maximum radius of a unit that can fit there.

I would experiment with different cell sizes and pick something as large as you can get away with.

I don't really understand this.

Do you want to make different cells with different sizes?


Could you please explain a bit more?

Thx in advance :-)

Forget cells. You are making a graph. Each node in the graph represents a location on the map. Two nodes are connected if they are adjacent on the map, without obstacles between them. Certain units are too large to be at certain locations, so if you want to use the same graph for units of different sizes, make the maximum radius of a unit that can fit in each location be a property of the location.

I would give each node/edge a "max radius" attribute, anything with a radius over that can then not use the edge/node. It would be fairly trivial to discard edges/nodes from your A* search based on the units radius. Generating the max radius attributes would be the hardest part.

Are you using a nav grid or a nav mesh? I've never tried a nav mesh but from what I've read of them they work well with units of varying sizes - might be worth looking into.

You have two basic options.

One is to build a waypoint graph as has been described; each node in your A* graph (not a grid) carries a radius that describes how large of a unit can pass through that node. Adjusting the A* algorithm to search only nodes with a minimum radius is trivial.

The other is to build a navigation mesh where you use polygons to represent pathable areas, select a sequence of polygons to travel across using A*, then use something like a local steering algorithm to actually move across each individual polygon.


Which works best depends a lot on your level geometry and how many units you want to be using. There's a good article here which includes additional resources in the discussion. Bottom line is that for an RTS a navmesh+steering approach is fairly standard due to the properties of most RTS maps.

Check out Chapter 8 in Programming Game AI by Example, it might help you.

You have two basic options.

One is to build a waypoint graph as has been described; each node in your A* graph (not a grid) carries a radius that describes how large of a unit can pass through that node. Adjusting the A* algorithm to search only nodes with a minimum radius is trivial.

The other is to build a navigation mesh where you use polygons to represent pathable areas, select a sequence of polygons to travel across using A*, then use something like a local steering algorithm to actually move across each individual polygon.

Grid-based approaches can work just as well They're simple to implement, don't suffer from high branching factor issues (like waypoints) and there's no need for local steering (like nav meshes). OTOH, you probably need to smooth the paths; using either post-processing or online via Any-angle A*.

Grid-based approaches can work just as well They're simple to implement, don't suffer from high branching factor issues (like waypoints) and there's no need for local steering (like nav meshes). OTOH, you probably need to smooth the paths; using either post-processing or online via Any-angle A*.

Very interesting article!

This probably can solve some of my pathfinding problems. I really like to do it with a grid, because it makes things very simple.

I think that unfortunately this will only work out with quadratic units, won't it?

And how would you implement collision avoidance on top of this? I think of something like before examining any node with A* I check if a move to this node would yield a collision with a not-moving unit and if so, the cell/node is treated as unpassable. Later when the path is executed the same checks are made before entering any node/cell.

This probably can solve some of my pathfinding problems. I really like to do it with a grid, because it makes things very simple.

I think that unfortunately this will only work out with quadratic units, won't it?

It will work as long as you use a square bounding box for your units. This constraint is similar to the circular bounding box constraint required by navigation meshes. You could probably use the annotated clearance values to reason about other types of bounding boxes (like rectangles) but you now need to figure out if there is enough room for the unit to turn and rotate. The article doesn't deal with that extension so the hard work is up to you ;)

And how would you implement collision avoidance on top of this? I think of something like before examining any node with A* I check if a move to this node would yield a collision with a not-moving unit and if so, the cell/node is treated as unpassable. Later when the path is executed the same checks are made before entering any node/cell.
[/quote]

You could use something like temporal reservations (see David Silver's 2005 article entitled Cooperative Pathfinding). The current state of the art has moved on a bit since then however: techniques like MAPP (see Wang and Botea 2009, 2011) scale better and (iirc) have lower memory requirements.