We've drawn the maze and created entry and exit points, and now it's time to find a path or paths through it.
Breadth-first search, bfs, spreads out like a wave over the maze and can be used for finding the shortest path from one point to another in a graph.
With breadth-first search, you look at each neighbor of a point in the graph that is on the same level before moving on to the next level, which creates the wave effect.
The backtracking algorithm works incrementally to build each solution path, and would eventually find all solutions if you don't stop it earlier.
At each step of the path, this algorithm picks a random valid neighbor square to move to.
When it follows a path in the maze and finds a dead-end, it will backtrack to where it can continue building a solution from the last viable step.
In this animation you can see the backtracking when the path turns yellow.
Dijkstra / A*
Dijkstra's algorithm and the A* algorithm are both versions of breadth-first search, but the edges in the graph are weighted and in the case of A*, some kind of heuristic is used to help guide the search towards the target.
Dijkstra's algorithm can be used to find the shortest path from one vertex in a graph to another, as well as from one vertex to every other vertex.
It only works on graphs with positive edge weights. There are other algorithms for when there are negative edge weights, but we won't go there today.
The A* algorithm is similar to Dijkstra's algorithm but uses a heuristic to guide the path to the goal destination.
A heuristic could be anything depending on your goals, but often it is something like a distance equation.
For this solver, I gave each edge in the maze a weight based on how far it is from an exit, using the Manhattan distance, or L1 norm.
Here's the formula for that in Python.
abs(x1-x2) + abs(y1-y2)
At each step in the path, the algorithm looks at the options for the direction it could take next: forward, backwards, left or right, and picks the one that has the minimum distance to an exit.
If you compare this visualization with the earlier ones for breadth-first search or backtracking, it is more focused on guiding the path towards the exit, while the other two do not do anything to guide the path in a particular direction.
Thanks for reading!
All of the code used for this project is in Python.
I made the visualizations and animations in matplotlib.
Mazes are an interesting type of problem and are a great way to learn graph algorithms because you can use so many common graph algorithms to generate and solve a maze.
Here are some links if you want to read about mazes in general and their history.
D3 has a built-in force to detect circle collisions in force layouts, but what if you're working with rectangles? In this post we will go over how to detect and resolve collisions, and then adapt D3's built-in forceCollide to work on rectangles.
You can do a lot of interesting things with the Spotify API, like searching for artists and playlists, following and sharing them, and more. In this post we will access the API using Python to get featured playlists and associated artists and genres.
Pictograms have been around for a long time, and with good reason. They are interesting and engaging, and might even help your audience to remember the information better. In this post we will build a pictogram grid in D3.js.