r/programming • • Sep 22 '20

I made Dijkstra's Path-finding visualization with dynamic wall addition. How's it?

https://youtu.be/3yUPeIayvfU
0 Upvotes

7 comments sorted by

2

u/CodingFiend Sep 27 '20

I have implemented a beads version of this program https://github.com/magicmouse/beads-examples/tree/master/Example%20-%20Pathfinder

It's very different looking code, as Beads has 2D arrays, but both programs are about the same length. Beads has one big advantage, zero external dependencies.

1

u/xX__NaN__Xx Sep 27 '20

Nice, it's really cool. 😃

Awesome

1

u/NiteLite Sep 22 '20

I believe that maybe the heuristic you have defined for estimated path distance might be flawed since it seems to perform more of a flood fill than an optimal A* pathfinding.

1

u/xX__NaN__Xx Sep 22 '20

I believe I mentioned it in the description, but since I had used squares for nodes I made the distance constant.

1

u/NiteLite Sep 22 '20

Ah, didn't see that.

If you implement the distance heuristic as something as simple as the taxicab distance, abs(x1 - x2) + abs(y1 - y2) between the start and the currently evaluated tile, you will see a lot more awesome behavior from the algorithm :)

A* just needs to know roughly the distance between the start and the current tile its working with.

1

u/CodingFiend Sep 23 '20

a cute little visualization. Very informative to see how algorithms execute. Would you be interested in a small paid project to port this to the Beads language, which is similar to python, but also quite different? www.beadslang.com has the reference manual, SDK. If so, please let me know.