Archived

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

Dijkstra vs A* path finding...

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
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
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
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
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
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
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
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
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