The contrast between the walls and the blue (explored) areas is too low.
When I press the round button to retry, the maze disappears. I'd like to see the same maze solved with different algorithm, or even see the same algorithm a few times. So my recommendation is to not errase the map, until the user press the button to make another map.
Very nice! My only suggestion would be to include Jump Point Search (JPS) [1], which can be an order of magnitude faster than A* search in grid map settings. JPS has also been extended to 3D grids for quadrotor path planning [2].
Am I missing something that this is doing something other than finding shortest paths? For example A* on an empty map should generate a diagonal path with almost no checks outside the paths immediate neighbors. But I get this: https://link.ekin.dev/OTW2xy
edit: Just wanted to add in case this is more of a frontend demo than a pathfinder demo, it does look beautiful and the search animation is more intuitive than similar demos I've seen. And runs fine on my phone.
It still doesn't feel like a DFS though. It's not picking the next node in a consistent order. I wouldn't expect gaps between the search.
This nerd-sniped me so I dug into the code, it's because it uses the non-recursive approach but it has an extra step of not adding neighbors to the stack if they've already been added previously. So you get this staggered line search because it avoids searching any tiles adjacent to a previously searched tile unless there are no other options. Decent optimization and still technically a DFS, it's just not the textbook example.
"Still technically a DFS" - No! The traditional textbook DFS visiting order has certain important properties. It's not just a "BFS" which uses stack and doesn't produce shortest path. There are more complex graph processing for finding strongly connected components, searching cutpoints and others which rely on proper DFS. Replacing DFS with this thing will result in completely wrong result. It is possible to implement a proper DFS non recursively, but it's a bit more trickier than just replacing queue with a stack in BFS.
If you form a spanning tree by noting which edges where used during DFS traversal of undirected graph, then all of the edges not used will connect a node with it's ancestor and there will be no cross edges. It doesn't matter if all you care is traversing the graph in any order and maybe checking which parts are connected, but it is important for some of the more complex graph algorithms built on top of DFS.
Maybe it does only horizontal and vertical steps. In that case it makes no difference, because the heuristic should always give you the Manhattan distance, which is equal for all options that don't overshoot the goal.
Yeah _0ffh's point makes sense on the path found. But even if it finds a path that is basically one horizontal one vertical line, it should still check the immediate neighbors only.
Building the maze takes too long. Maybe turn the play button into a fast-forward button when the maze is being built and solved.
The dark mode colors are pretty bad.
When you click and hold, it should turn every square the same color until you let go again. Right now it toggles every square you pass over, which is confusing.
When you move the start and end, it removes walls from the board.
Isn't Dijkstra the same as BFS?
Fast is not fast.
I think an inverted binary tree maze would be nice.
That's because demonstrating Dijkstra on a grid is as useful as demonstrating air resistance in vacuum. In a grid with only horizontal and vertical Dijkstra will produce same order as BFS (but more slowly). You could see some difference if you treated diagonal moves as having sqrt(2) length, but such distance metric is rarely useful. Either you simplify things by having grid and not allowing diagonal movement or treating them like like them length 1, or you allow free 2D movement at arbitrary angles with proper euclidean geometry and distances. Treating diagonal distances as sqrt(2) is worst of both approaches. You loose most of the simplification provided by grid and can't evaluate it in head or on a paper, but it still doesn't produce geometrically accurate results.
One case where Dijkstra on a grid would make sense if you treated entering and exiting certain cells as slower=longer distance. Might be useful if you modeled a game where certain cells contain difficult to traverse terrain like mountains or swamp.
Ye the colours aren't great - design skills have a long way to go ! Fixed the start and end nodes bug and will look into adding the fast forward button and inverted binary tree maze. Thanks for the ideas !
Very nice! This brings back memories. In the 90's sometime I found a GIF of a huge maze and I wanted to find the solution. Young coder me decided to write a program in VB to find the solution. Just went and grabbed a screen shot of it here: https://i.imgur.com/gRz5b01.png I can't remember how long it took it to solve it back then but it solves it now on modern hardware in about 3 seconds. Likely much better ways to do it now, I know nothing about path finding theory. This was just a simple recursive search.
I need to do more of these fun side projects like this just for the pure joy of it.
Nice stuff! However, when I try to drag the start/end points around the map it has an 'eraser' effect, deleting walls as it goes. Also you can try using black or darker gray for walls.
Thanks for highlighting that the start and end nodes aren't meant to be moved but I fixed it so that they can't be overridden by a wall. I also made the walls darker for the light theme so hopefully its a bit better !
The contrast between the walls and the blue (explored) areas is too low.
When I press the round button to retry, the maze disappears. I'd like to see the same maze solved with different algorithm, or even see the same algorithm a few times. So my recommendation is to not errase the map, until the user press the button to make another map.