Archived

This topic is now archived and is closed to further replies.

jollyjeffers

Dijkstra vs A* path finding...

Recommended Posts

jollyjeffers    1570
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;

Share this post


Link to post
Share on other sites
Prefect    373
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.

Share this post


Link to post
Share on other sites
jollyjeffers    1570
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;

Share this post


Link to post
Share on other sites
ahw    263
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

Share this post


Link to post
Share on other sites
strangebreed    122
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

Share this post


Link to post
Share on other sites
jollyjeffers    1570
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;

Share this post


Link to post
Share on other sites
Prefect    373
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.

Share this post


Link to post
Share on other sites
jollyjeffers    1570
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;

Share this post


Link to post
Share on other sites
strangebreed    122
You''re right, Dijkstra''s can be used easily with distance based path-finding. Distance and crossed paths however is inherent in A*, it''s a necessary part of the algorithm.

I just found it easier to implement an irregular grid in my A* code than a standard length or breadth first search.


---Strange

Share this post


Link to post
Share on other sites
jollyjeffers    1570
I read up on the Dijkstra algorithm in a maths book (I do this sort of thing in maths) - and it''s entirely distance related, I looked at Dijkstra''s algorithm on several computer science pages and they really really overcomplicate thing - I couldn''t understand them at all, but within 15 minutes reading my maths book I could do the algoithm off the top of my head...

Jack;

PS - Thanks for the URL..

Share this post


Link to post
Share on other sites