Since I was a kid, I always been fascinated by mazes. Playing with them, on a sheet of paper or (even better) in a giant corn pasture maze is something great. Mazes are universal, you don't need written rules to play, you can play alone, make some speed-tests with friends, or making a lot of funny stuff.
Create a maze can be interesting, as you can do a lot of things with them. Of course, you can draw them by hand. It works, but when the size of the maze starts to be bigger, or if you don't have good drawing skills (like me!!), computers are here.
You can find tons of programs to create mazes on the net. But for me, my goal was to create something from scratch, by coding my own algorithms. In this Instructable, we will see first a simple algorithm to create mazes, a program example written in the Processing language and after that some clues to make funny stuff with them.
Thanks for reading, again please tell me the English mistakes!
Step 1: An Algorithm
I didn't have created this algorithm, I have discovered it in a book and I created a code from this. It’s not the only one maze generator algorithm, but this one was, for me, easier to convert in code.
Let's start with an array of cells. Each cell had four directions, linking to four cells. Each cell can be "visited" or "not visited".
The algorithm say:
- every cell is "not visited" when we start.
- you have walls in every direction, in every cell.
- select a cell
- choose a direction (left, right, up or down).
- check if the cell in the selected direction is visited or not.
- if not, move into the new cell, break the wall (remove it) and make the new cell visited.
- if the chosen cell in the chosen direction is already visited, select a new direction.
- if every cell around you is visited, move backward to the previous cell and start again to choose a random direction
- do these steps until every cell are visited.
The main conclusion of this algorithm is that the maze contains only one path, it means that you can reach every cells. It didn't have a defined start and end.
The pictures attached in this step are an example. I start with the cell 1, then 8, 9, 10, 3 and 2. In the cell 2, I don’t have any available cells here, so I move back in the cell 3. Here, I continue on the cell 4…
Step 2: Processing Code Example
This code was converted by be from my old QBasic DOS code. It is not very optimized, but it works. Simply set the size of the maze with the N and M variables (how many rows and columns.)
Warning: it seems to contain some bugs. I’m still working on it. If you want to make it faster, just comment (with “//”) the println and print lines to remove the debug notes.
The Processing software can be downloaded here.
Step 3: A Step Beyond !
The results are great, but we can do more. By starting the algorithm with cells already "visited" you can limit the maze into a given shape, to get great results!! This method was done in a work-in-progress VB application coded by me. A demo of a previous version can be seen here.
The software can export 2d files, save and restore “masks” (in bitmap), export POV-Ray code, STL files… but still contains a lot of bugs… :-(
I downloaded the Instructable logo, exported the black and white mask, and created this (almost hard) maze.
Step 4: What We Can Do / Custom DOOM Level
With the base of a 2D-maze, you can create a lot of things. You can export the lines to create a real maze using a CNC-router, you can 3D-print real objects. You can also edit the picture with Photoshop or similar software to add pictures, drawings and create fun games for kids. Great ideas are also on this site to make great objects.
I used a couple of development software to create randomly generated… Doom levels !! With these games, you can explore, visit (and shoot monsters !) in a 3d maze. The level walls are randomly generated, stuff and monsters are randomly placed.
This work was done by using:
- WadC ("Wad Compiler") : a great under rated software used to create the level with CODE. Yep, lines of code! Every walls, weapons, monsters and stuff is randomly generated. You can find this software here.
- BSP 5.1, to compile the WAD file and create the nodes and a specific tree in the level game file. More here.
- WinDEU 5.24 : The best GUI editor software. Used to clean the level and to solve some issues.A link seems to be here.
- Zdoom with Freedoom graphic pack. The original DOOM game was created by id-software, but the game engine is now in the public domain. I use Zdoom as an interpreter and Freedoom graphic pack.
This level is great in multi-player mode !
So, there are some ideas to create stuff from a 2D maze. And you, any ideas to transform a simple maze into something wonderful?
Thanks for reading !!