Hi, I'm going through the course on AI at gameinstitute.com... They spend quite a lot of time talking about Dijkstra's algorithm, presenting not just one, but four different versions of the algorithm. Isn't A* better than Dijkstra's though? Maybe there is some situation where Dijkstra would be preferrable? If it's not that important I'll just skip reading all this material since I already am very familiar with the basic Dijkstra's algorithm since I studied it in college. Thanks roos

If you want to find the shortest path between A and B then A* is a good choice.

If you want to find the closest occurence of an item, where there are many instances of that item on the map (like a health pack), then Dijkstra's is usually preferable (depending on the number of instances). This is because the algorithm explores all paths in an expanding fringe of nodes and stops when the first instance is found (one search), whereas if using A* to find the closest instance of an item you'd have to find the distance to each instance (several searches) and choose the shortest.

fup!

Cool, thanks a lot! I guess I'll go back and read that part more carefully :)

Btw, I just ordered your new book from Amazon half an hour ago, looks awesome, everyone on amazon's giving it 5 stars. I have your other book too, but I'm more excited about the new one since it seems to cover a lot of practical topics.

roos

:) cheers. I hope you enjoy it.

A related question. There's an article in GPG5 regarding using A* with multiple start and/or multiple end nodes. I haven't had a chance to test an implementation but if I remember right it says it is significantly superior than running multiple A*'s and I believe they said even better than a run of Dijkstra. Anyone played with such a method?

p.s. btw fup, love the book

I don't have a copy of GPG5 on me right now, but it makes sense. If you want to find a health pack you can run a modified version of A* that uses all the health packs as origins (put them initially on the open list with a cost of 0) and the character's position as destination. Everything else in A* is untouched. If I am thinking correctly this morning, that should result in a pretty efficient algorithm.

Dijkstra is still an important algorithm for searches in graphs were it is hard to come up with a heuristic. However, I wouldn't study the details of four versions of the algorithm if you already understand the basics.

A* is more appropriate when you have an idea of where your destination is relative to your starting node (eg that the destination is somewhere North/Up of the starting node and that you can follow some edge to reduce the distance in that direction). Dijkstra doesn't use any such information, it does a breadth-first search instead. That's why, as fup said, it's good for things like "find the closest X to this node."

It's also worth noting that A* really is just a variation of Dijkstra's, which is itself a variation of breadth first search, so I wouldn't consider learning Dijkstra's really thoroughly a waste of time. In this theory class I took we spent damn near a month on variations of depth and breadth first search. A good professor of mine explained to us that he thought of all the searching algorithms like this


add first node to the data structure
until data structure is empty
take a node out of the data structure
add adjacent nodes you haven't already visited to the data structure


If the data structure is a stack you have depth first search, if it's a queue you have breadth first, if it's a priority queue where each node's priority is it's distance from the start you have Dijkstra's, if it's a priority queue where each node's priority is it's distance from the start plus a hueristic then you have A*.

Of course the data structure makes a big difference like fup noted, but it's a nice way of looking at them.

I like the description by the AP above very much. R. Sedgewick had a similar description in the book "Algorithms in <insert programming language here>".

After looking at GPG5, the article gives exactly my suggestion to implement multiple sources. For multiple targets they consider using a number of stop nodes, not just one, but then the heuristic should be an estimate of the distance to the closest exit, which may not be trivial. For the "one source many targets" situation I think reversing the problem ("many sources one target") will usually work better.