# A* owns them all ?

This topic is 5122 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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.

##### Share on other sites
A* finds optimal (that means shortest) paths, if you don't need optimal paths there might very well be a faster algorithm.

##### Share on other sites
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.

##### Share on other sites
Here are a few:

http://www.gameai.com/pathfinding.html

-Kirk

##### Share on other sites
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.

##### Share on other sites
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

##### Share on other sites
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.

##### Share on other sites
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*

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by DrEvilIf 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.

1. 1
2. 2
Rutin
19
3. 3
khawk
18
4. 4
5. 5
A4L
11

• 12
• 16
• 26
• 10
• 44
• ### Forum Statistics

• Total Topics
633768
• Total Posts
3013748
×