Quick, no time to explain! Have a look at how a computer goes out of a maze in the demo!
And check out Github if you want to see the code.
Solving mazes is not a new topic, every computer science student heard about this topic at least once during their studies and most of them tried to implement a maze solver one way or another. However seeing a computer getting out of a maze is always a source of wonder and excitement to me. I know there is nothing magical in these maze solving algorithms but seeing them getting executed has always been some kind of a kink to me.
So last time I had a bit of free time I decided to make my own maze solver! It's nothing fancy: I'm not inventing a new algorithm nor am I looking for something extremely fast but I wanted it to be fun to watch.
So here is what I came up with.
I had two main goals in this project:
So I used p5.js again to create a grid of cells and destroy the walls between them to create ways. The web application allows to choose the classical backtracking solution as well as a recursive divisor generator. This is not fancy but this works.
However, doing some researched I also discovered that some cellular automata generate patterns looking like a maze, namely CA
B3/S1234 (meaning a cell is born if it has exactly 3 alive neighbors and it survives it is has respectively 1,2,3,4 or 5 and 1,2,3 or 4 alive neighbors). The web app also allows to select this generators and even though I had to cheat a bit (sometimes some walls need to be broken to have a valid maze) it was quite exciting to see CAs applied on mazes!
About the solvers so far I implemented four of them: