Last month we were initially planning a 2D version of 3D Monster Maze but that would have taken too long.

This month we suffered from a horrible illness so we decided to skip the whole 'live action intense development' entirely. On the positive side, we spent far too long fiddling around with a little game which means 3D Monster Maze in 2D is now a reality!

And so, here is a breakdown of some of the more interesting parts.

To create a maze that is randomly generated, we will first need some walls. After a ponder or two and experimentations, I came up with the following layout of wall tiles.



What I came up with for each tile was a wall going directly through its center; which is probably the most efficient way of dealing with this.
However, we still need corners and T junctions along with some other bits so it looks more robust and complete.

This resulted in a layout that tries hard to only include each tile once whilst placing them in a natural setting. This makes it easy to draw any sort of walls over the top and give the game a bit of texture.

There are only two tiles that are duplicated in the layout. Here, I have marked them in red along with a chequered pattern that shows exactly where the tiles are. The red tiles and the blank tiles are never used.



Now we can draw some simple walls and produce a little maze. All well and good but randomizing it will make it a little more interesting, don't you think? After much head scratching, fiddling and guess work I came up with the following algorithm. Pay attention now.


1. Start with a maze full of single cells, ie. no cell is attached to any other cell.

2. Each cell is 2x2 characters of empty space surrounded by walls. (3x3 area per cell or 4x4 if you count the overlap.)

3. Go through each row and each column of cells and knock down a random number of walls in a straight line. This creates a basic shape for the maze.

4.The following three actions are then performed repeatedly.

i. Go through each cell and check that it has at least 2 missing walls, if it doesn't then randomly knock down walls until it does.

ii. Go through each cell and check if it has any corner pieces that have had all of their walls removed, if any corner does then randomly restore a wall. This prevents very small wall islands from forming.

iii. Finally make sure every cell is connected to every other cell. Build connected groups of cells and then randomly knock down a wall from each group until only one group remains.

5. Perform all the 3 checks until no new changes are made, at each point we may randomly break one of the previous constraints so this ensures that all 3 constraints are met simultaneously.


Here's an example of mazes created by this technique. As you can see, it makes for some rather pleasant Pacman-style mazes.



More images can be found at -> http://imgur.com/a/uxmvy

And of course the source code -> https://bitbucket.org/xixs/gamecakejam/src/tip/dmazed/lua/dmazed/cells.lua



Huzzah! We now have a maze for the game to take place in and it only took 10x longer than any other gamecakejam!