a* comparison question

Generally speaking, A* is considered to be the fastest. Antoher well know algorithm is Dijkstra, but usually, A* is the way to go.

yeah im just wanting to know what people tend to use and what good options there are out there.

A* is not necessarily the fastest... it completely depends on the domain. In general, since A* is optimally efficient, over most domains, A* will be as fast as comparable methods. For example, one problem that A* faces in large search trees is the cost of maintaining an ordering on the tree, both computationally and memory wise.

Cheers,

Timkin

Also if your searches doesnt have to be optimal you can do a lot of stuff that is faster than "pure" a*. For example you can do an initial search on a coarser version of your map and then use the result from that search to do a number of shorter searches on the real map.

When I do this using three search levels in a RTS i gain >20 times better performance than using pure a* while getting paths that are about 3-4% longer than optimal. Another good thing with this approach is that you dont have to calculate the whole path at once so the startup cost is >100 times less that of pure a* and also it handles changing terrain better (although changing terrain forces you to recalculate the coarser map levels).

Another possible way that I used before the above is to use the coarse search to improve the heuristic used in the real a* search. Using this method i could get 10x better performance (with 3-4% longer paths) than using a simple manhattan distance/d8 distance heuristic.

All the above numbers was on a 1024*1024 map using continuous tile costs with tile types taken from a real world map.

Isokron - when you make the coarser versions of the map, what happens if there was an unwalkable piece of terrain in the high resolution map being converted? Would that make the coarser piece of map unwalkable? Or perhaps you just average the terrain costs over the map grid area being sampled?

I have tried to use both the average value and the minimum value but none of those gives good results. So now i do something like

Startup:
1: Divide the map into coarse squares (16*16 normal tiles maybe, or several levels ie i currently use 8*8 and 64*64).
2: Select a point in each square close to the middle but not on a blocking piece of terrain.
3: Find the shortest path between each center point and its 8 neighbours
4: (optional) Recalculate what squares belongs to what center point based on shortest path instead of the squares.

Search time:
1: Find what center points the start and goal belongs to
2: Find a path between those (in the coarse map)
3: Now you have your path nicely subdivided into smaller ones
4: You cant however search from center point to center point but must rather throw away some tiles at the end of each path, how many is a tradeof between speed and path nicety. With 16*16 coarse squares you might want to throw away the last 20 tiles in each path. This can also lead to that its faster to search to every other center point rather than every one.

Well thats it basically, hope it made some sense. You might want to check out http://www-und.ida.liu.se/~stejo127/path.pdf although it was a few years since i wrote it.

I'd like to add some light on this subject, from my personal experience, in both RTS and FPS games.

A* is usually the way to go (in both cases), although IDA* is a good alternative. The most important things when dealing with A* is to optimize : 1. your world representation, 2. Memory consumption.

As for world-representation, splitting whole "world" into separate chunks is very important. This way many problems are solved : your agent has no knowledge of whole world, and the most important, you'll avoid the worst A* case - looking for a non-existing path all over the map. Essentially, pathfinder will be splitted into two (or more) parts, of which one is "high-level" which will find high-level path thru world-chunks, and the other is a low-level pathfinder which deals with paths inside each chunk. This is very important when dealing with large worlds. Your game will surely be much more responsive This way, you can have dozens of agents simultaniously pathfinding without hitting frame-rate significantly.

Memory is, also, very big issue, since A* is very memory-intensive algorithm! After writing my own custom A*-memory-manager pathfinder went thru the roof! Something like 10x faster and no memory-fragmentation (very important on consoles!)

So, A* is usually the best solution, but is it really the best one depends on two things : what are you trying to solve, and, ofcourse, how well it is implemeted


[edited by - NastyB on February 1, 2004 9:10:20 PM]

"Memory is, also, very big issue, since A* is very memory-intensive algorithm! After writing my own custom A*-memory-manager pathfinder went thru the roof! Something like 10x faster and no memory-fragmentation (very important on consoles!)"

I''d like to understand what you meant by that. sorry, it was not too clear too me. Are you talking about custom implementing the pathfinder''s memory allocation? If so, any tips? I have a working A* on my game, but it''s a tad slow, and i may have hundreds of simultaneous units calculating repetative paths (but not in real time at least).

thanks