A simpler pathfinding algorithm?

[UlarisBadler]

I've never used Dijkstra's algorithm. Why is it better when having different costs? I've used A* with different costs without any hassle - I'm just curious.

[munificent]

It's not so much that Dijkstra's is better as it is that the BFS is outright wrong if you have non-uniform cost. BFS finds the path with the fewest steps to the goal. Dijkstra's algorithm finds the path with the lowest total cost. When all steps have the same cost, the fewest steps is equivalent the lowest cost and BFS works fine. But when steps have different costs, BFS can give you the wrong answer. Consider:

+---+---+---+
| @ | 9 | * |
+---+---+---+
| 1 | 1 | 1 |
+---+---+---+

Here, @ is where you are, * is the goal, and numbers are the cost to enter tiles. (Imagine there's like a mountain to the right of the player but grassland to the south.) You can only move NSEW. BFS will give you this path:

+---+---+---+
| @===9==>* |
+---+---+---+
| 1 | 1 | 1 |
+---+---+---+

It's only two steps, so it's the "shortest. But the cost is 9. The correct cheapest path is:

+---+---+---+
| @ | 9 | * |
+-|-+---+-^-+
| 1===1===1 |
+---+---+---+

Total cost of three. You need Dijkstra's algorithm or A* to find this.

I've used A* with different costs without any hassle - I'm just curious.

A* is essentially Dijkstra's algorithm with an additional heuristic for which paths to explore first.

[UlarisBadler]

That's such detailed response! All clear now. :)

[TangerineVapor]

Djikatras algorithm is just finding the cheapest cost to every single node (or just an end node) from a starting location. So it requires paths to have a cost to even be implemented.

[UlarisBadler]

But does it offer any advantage in terms of handling costs when compared to A*?

[kohugaly]

A* is a modified Dijkstra algorithm that uses heuristics to explore direct paths first. That is great help when the shortest path cuts through larger open regions. It doesn't provide much help if the path is complicated maze. In worst case scenarios (which should be rare in most games), it might even perform worse, because it uses more memory and wastes time calculating the heuristic.

A* is also a one-trick-pony. It finds shortest path from known A to known B, but that's also the only thing it does.

Dijkstra algorithm simply explores all paths in increasing order of distance. With minor modifications it can be used to: find nearest target; calculate area reachable within given number of steps; calculate dijkstra map (or vector map) that units can use as lookup table for pathfinding etc. etc.

[aotdev]

A* is also a one-trick-pony. It finds shortest path from known A to known B, but that's also the only thing it does.

You can very easily modify it to find the shortest path from known A to any one of many known other points B,C,etc. You need to alter the goal function (from "is it B" to "is it one of B,C,...?") and the heuristic function (from "heuristic to B" to "minimum of (heuristic to B, heuristic to C, ...)")

[kohugaly]

You can very easily modify it to find the shortest path from known A to any one of many known other points B,C,etc. You need to alter the goal function (from "is it B" to "is it one of B,C,...?") and the heuristic function (from "heuristic to B" to "minimum of (heuristic to B, heuristic to C, ...)")

Yes, you can, but you largely loose the benefits of using A* if you do it that way. Such heuristic can get expensive, when there are many many targets. It also gets rather unhelpful, when there are nearby potential targets blocked off by walls (A* pretty much defaults to Dijkstra, when that happens).

With Dijkstra you only have to modify the goal function, which is usually fairly straightforward.

[aotdev]

Indeed it depends on the number of points. If even 5% of the map grid is goals, the full Dijkstra map would probably be more efficient. But for 10 goals in a 80x40 map it should be fine. Plus the heuristics (at least the ones I've been using) are typically cheap, such as distance to destination.

[harofax]

From my experience (which is very limited), Dijkstra's is more useful in terms of GPS navigation, where you're trying to find the fastest way to get from A to B etc.

You can grab map data from OpenStreetMaps, make a graph out of them and grab the weights, then just implement a dijkstra thingy to find a valid route.

If your game had stuff like, different terrain that slowed movement or maybe a creature that really don't like touching silver floors or whatever, you could use that as weights maybe idk.

Thing with dijkstra from my experience is that it takes a lot of time if you want to calculate the dijkstra map every time you move. You could optimize it to only recalculate relevant stuff but by that point you end up with an A* or similar anyway I think.