hi, what are the pro''s and cons of the two mentioned algorithms? I know Dijkstra''s algorithm really well, and it seems to be fine for everything I need - yet I hear much much more talk about A* algorithms - Are they really much much better than Dijkstra''s algorithm?? Jack;

A* is basically built on Dijkstra''s algorithm. It''s essentially the same, but you try to predict the length of the remaining path when you calculate the value of a certain node. That way you don''t have to consider tiles/nodes/whatever you use that go in the opposite direction.
A* is thus a lot faster, however, if the predicted path length is longer than the actual remaining length you don''t necessarily get the optimal path. If the predicted path length is equal to or lower than the minimum remaining path length from the current node to the goal you will get an optimal path.
In fact, A* with a predicted path of length 0 is the same as Dijkstra''s algorithm.

cu,
Prefect

---
Sanity is the trademark of a weak mind.

cheers;

I suppose it comes into it''s own when using large networks... the examples I''ve made are only 40-100 nodes and a path can be found in around 1 millionth of a second...

Jack;

Well, like Prefect explains, A* is Dijkstra with a heuristic. Basically, a heuristic is "something" that you use to reduce the domain of search for a search algorithm.
It''s useful when the domain of search is getting huge. Like in a game of chess, you don''t really want to search for all possible movements, rather you''d like to look only the most interesting. And to evaluate how "intersting" a branching is, you use a heuristic. Well ... to look for the fastest path, it''s the same.

If you are happy with your actual search algorithm, you don''t need to worry too much. Just keep in mind that when your domain of search increase in size, you''ll have to opportunity to use a heuristic to fasten your operations, turning your dijkstra into a A* algorithm.

youpla :-P

I think it does matter which you use, it depends on the application you need it for. “Large networks of nodes” implies a large node-map, but doesn’t say how far apart your paths are from each other, (the number of nodes traveled through to get to your target), or whether it’s an irregular or regular grid.

I’m using A* for true 3D path finding where nodes in the map are not on a regular grid. If your system is the same I would say that A* is the only way to go. A* takes into account paths that cross each other and the distance that path took compared with the previous path through a node. If you have a non-regular grid this is important. On a regular grid, the shortest path is the one that reaches the goal first, (i.e. least amount of nodes traversed). With a true 3D node map, you may reach the goal in only a few nodes, but those nodes might be 1,000’s of co-ordinates apart. Another route that takes many more nodes to reach the destination may only be 100 units from the target.

There has been a lot of discussion on this forum and others about the merits on A* on regular grid node maps, I firmly believe that the extra work involved in A* compared with Dijkstra is unnecessary, unless your start and target nodes are extremely spaced apart. If you’re dealing with an irregular node map, like a true 3D world, then A* is the only way to go.



---Strange

Is that a recent Gamasutra article? There was the one about Midtown-Madness AI, but I haven''t seen any others recently...

I''ve written up an article for my website on the Dijkstra algorithm, so I was more interested in the general case - I might in the future be designing a game that''s 3D terrain based/flight sim - at which point there''d be 1000''s of nodes which probably wont be in a regular pattern....

Jack;

strangebreed: Dijkstra''s algorithm can take care of actual distances as well. Just use the sum of all links'' lengths instead of the number of links traversed.

cu,
Prefect

---
Sanity is the trademark of a weak mind.

Dijkstra''s algorithm is pretty much entirely distance based - that''s why it was designed for finding the shortest route; read through the pure mathematical version (which is where I learnt it from) and you''ll see what I mean...

Jack;