What is this all about
This project is about generating mazes and then seeing how robots with various solving algorithms progress through those mazes.
How are mazes generated
Mazes are being generated by one of the simplest algorithms called depth-first search. It produces "perfect mazes", which contain no loops.
What are robots
Robots differ in algorithms which drive them through the maze. Below is the complete list of currently available robot types with descriptions.
Vector 1
It is the most primitive robot. Each round it randomly chooses any available direction. Vector 1 has no memory.
Vector 5
This is the implementation of the algorithm, erroneously thought by many to be a sufficient method to solve a maze with a robot: choose a direction randomly, follow that direction until you encounter a wall, randomly choose another direction. Such an algorithm, however, is not a way to guarantee your robot will ever reach an exit. Vector 5 is here to demonstrate that.
Vector 9
Take Vector 5, add memory to it and you get a decent maze solver. Vector 9 chooses a direction randomly, follows it, if encounters a wall chooses another direction, but does not go back to where it has already been unless there is no other way to go. Following back its own trail, Vector 9 will search for a turn into unexplored territory and go for it. Guaranteed to find an exit in any perfect maze.
Gyro-5
Amnesia robot - each time it encounters a dead-end, Gyro-5 will loose all of its memory. A fun one to watch. Eventually will find an exit.
Gyro-5 Crusher
Crusher is a tough bot. It has the same memory problem (feature?) as Gyro-5, but if it accumulates level 10 or higher, it will crush a wall. Note, this little beast will cause irreversible damage to the maze, there will be no way to fix it but to generate a new one.
Gyro-10
This one is another maze solver. It actually uses the same depth-first search algorithm which is currently used to generate mazes themselves. Gyro-10 has a memory. It chooses a random direction and each step randomly chooses to go to any unexplored territory. If it gets to a dead-end, it will backtrack until it finds another unexplored passage. Guranteed method to find an exit in any perfect maze. Efficiency results on average are about the same as using Vector 9.
Clockbot
This robot has a clockwise priority in his decision making. First he tries to go West, if this is not available, he will go South, then East and only then choose to go North.
Deterministic algorithm, currently most efficient, usually outrunning Einstein-B, but at the very least getting the same result.
Clockbot WM
Clockbot without memory. This shows the importance of memory in robots with deterministic algorithms.
Einstein-B
The second smartest bot of the current collection after Clockbot, Einstein-B chooses passages which are geographically closer to the exit. This is also a deterministic algorithm, without any random decisions. On average, Einstein-B completes a maze visiting less cells than Vector 9 and Gyro-10.
I use Internet Explorer and when I click "Create robot" nothing happens.
Sorry, but Internet Explorer is not supported. It would be more correctly to say, though, that Internet Explorer does not support us by not supporting web standards. Use any other browser that does comply with HTML and JavaScript specifications, for example Mozilla Firefox.
And believe me, this is a practical decision - if I begin fixing everything for IE, it would take me half the time it took me to write the whole project without any guarantee it would work with future versions of IE. I think my time could be better spent doing something else.
Sometimes the robot would miss a cell or two and "jump".
The robot moves by executing a script that sends and receives data in real time. If the connection is not perfect, sometimes the robot will seem to jump.
Why if a maze is larger, Gyro-5 Crusher does not display numbers?
The text would be too small, so I decided to leave it out. Additionally, it was giving a visual artifact when the robot was moving.
Do you plan any interaction?
I do. It remains to be seen whether it would be a separate project or not. I do think that this project is pretty much self-contained and is a nice way to observe various maze solving algorithms as well as maze generation. So probably this is just the starting point for other maze projects.
What are you using to make this site?
PHP, MySQL, jQuery.