A* owns them all ?
Author
Hey everybody !
I'm wondering - are there any other AI algorithms, other than A-Star, for path finding ?...
And if there are, what are their advantages/disadvantages comparing to the A* algorithm ?...
Thanks a lot in advance, Arie.
A* finds optimal (that means shortest) paths, if you don't need optimal paths there might very well be a faster algorithm.
Wikipedia about shortest paths
Wikipedia about shortest paths
Also, A* is made for finding a path to a specific goal. What if you want your bot to find a path to a health pack but theres many health packs throughout the level? It'd be inefficient to generate an A* to each of them to find the closest. Instead Dijkstra's is a better choice for this type of situation as it will find an optimal path to the first health pack it finds in the search, so in essence you get to find the closest cheapest healthpack to go to with 1 call to your Dijkstra path planner.
Here are a few:
http://www.red3d.com/breese/navigation.html
http://www.gameai.com/pathfinding.html
-Kirk
http://www.red3d.com/breese/navigation.html
http://www.gameai.com/pathfinding.html
-Kirk
A* is optimal, it is really I end of a series of search algorithm. You can see in the book from Russel and Norvig, Artificial Intelligence: a Modern Aproach.
Altough A* is optimal it is not complete, so it is a more IA search techniques.
Dijkstra is optimal and complete and is a more algorithm thing. And computes the distance from a node to all other's in the graph.
Altough A* is optimal it is not complete, so it is a more IA search techniques.
Dijkstra is optimal and complete and is a more algorithm thing. And computes the distance from a node to all other's in the graph.
It's not simply that A* is optimal... there are many other optimal search algorithms out there (in that they return the optimal path). What A* guarantees (and this is the kicker) is that it is optimally efficient, which means that not only does it guarantee to return the optimal path (under certain assumptions) but it also guarantees to expand fewer nodes in its search tree than any other algorithm.
Timkin
Timkin
The A* algorithm requires a distance heuristic (lower bound if I remember correctly). Most of the time this isn't a problem, but there are times when you can't provide one (e.g. a map with lots of wormholes?) so the other algorithms become more suitable.
If you remove the heuristic from the cost calculations, A* turns into Dijkstra. In my A* implementation I have a flag I can set to use the heuristic, so when looking for the nearest health kit for example, a heuristic is pointless if there are many of them, so Dijkstra would be preferred, planning for specific goals and I use A*
While A* is optimally efficient on a pure random access memory machine with limitless amount of memory, in reality it's not always the fastest algorithm for finding the optimal path, because it consumes so much memory. There are variations such as IDA* and SMA* which use less memory and are still optimally efficient on certain environments (not all, like A* is).
So, choosing A* is not always best bet. Sometimes you want less optimal paths, like others have mentioned, and sometimes the search space is such that SMA* has same speed complexity but lower memory usage complexity.
So, choosing A* is not always best bet. Sometimes you want less optimal paths, like others have mentioned, and sometimes the search space is such that SMA* has same speed complexity but lower memory usage complexity.
Quote:Original post by DrEvil
If you remove the heuristic from the cost calculations, A* turns into Dijkstra. In my A* implementation I have a flag I can set to use the heuristic, so when looking for the nearest health kit for example, a heuristic is pointless if there are many of them, so Dijkstra would be preferred, planning for specific goals and I use A*
Do you have some benchmarks of your implementation?
I'de be very interested in comparing performances.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
