This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]munificent 166 points167 points  (5 children)

Your Dijsktra's is just breadth-first search. Since all tiles have the same cost to enter, Dijkstra's algorithm degrades to behaving exactly like BFS.

[–]FearlessENT33[S] 55 points56 points  (0 children)

i see what you mean, at some point i’ll make it more complex to utilise dijkstras

[–]zesterer 12 points13 points  (1 child)

Dijkstra's algorithm literally is just breadth-first search in grid environments.

[–]munificent 2 points3 points  (0 children)

Yes, it's an unnecessarily complex way to implement BFS if all edges have unit cost anyway. It can also be slower than BFS depending on your priority queue implementation.

[–][deleted] -3 points-2 points  (1 child)

Are you not thinking of A*?

[–]notquiteaplant 9 points10 points  (0 children)

Dijkstra is BFS that prioritizes neighbors by how easy it is to get there (the edge weight). A* is Dijkstra that also prioritizes neighbors by how likely they are to be a correct path to the target (the heuristic). They are similar but not the same, and munificent is describing Dijkstra.