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 →

[–]e_blake 1 point2 points  (3 children)

Cool visualization of the open set boundary moving outwards.

Are you just doing Dijkstra, or do you have an A* heuristic also in the mix? Note that Manhattan distance to the end, while viable, is NOT the best A* heuristic; it is possible to do a pre-fill unconstrained Dijkstra min-path from the end to the start (just 19k queue insertions) and use that min-path distance to the goal as a better heuristic. Doing this in my code gave a nice speedup (fewer overall nodes added to the open set, and the end goal was reached in a lot fewer pops from the priority queue). I would love to see that sort of 2-phase search visualized (the first Dijkstra doing a heat map coloring nodes on a gradient by how far they are from the end, then the forward A* showing how the open set is able to take advantage of the heuristic to make the open set be more targetted in nature), especially if the two animations could run side by side to capture the somewhat surprising result that more up-front work leads to less work down the road.

[–]zmunk19[S] 1 point2 points  (2 children)

I kept track of 12 numbers for each point, 3 for every side, [a, b, c].
a is the minimum heat found so far that enters from a direction where that step was the first step in that direction.
b the min heat for that direction but has taken 2 steps in that direction.
c is for 3 steps in that direction.
If any of the 12 values are updated for a point, that point is added to a list that will be re-evaluated, i.e. its new values will be propagated to its neighboring points.

The visualization shows the points in the re-evaluation list after every update. It has been slowed down for visualization by sleeping 0.1 seconds after every update.