Automatic Maze Generation

When I was young, I really enjoyed mazes.  I got tired of the ones I could find.  So I started making my own.  I would use a mechanical pencil and fill an entire 8.5″x11″ piece of paper.  The mazes were always solvable.  I made sure of that.  They even started getting complicated.  I added gates that required keys and all sorts of stuff that was unenforceable on paper.

Fast forward 20 years, I had an idea for a game that would automatically generate mazes.  After getting to a good stopping point on GeoBlox, I decided to try my hand at something 3D.  I’m not even sure if automatic level generation is appropriate for a second game, but I expect to learn a bunch either way.

I developed a random search algorithm that would meander its way from start to finish on an open board.  Then I repurposed the algorithm to fill in the rest of the board.  Then I was left with a moderately significant problem: how do I fill in the walls between all of these paths?  The solution that I came with (which I already hate, but it sort of works) was to fill the board with small boxes that would get destroyed when they came in contact with a path segment.  The path segments, for testing purposes, were visible.  This would effectively destroy everything but the walls that I needed.

This “worked” but the player character (i.e. the capsule) was getting stuck on the walls.  I messed with the colliders a bit and determined that the problem is symptomatic of my creation-by-destruction method.  A friend who is also learning game development right now directed me to a short video on Spelunker, which uses a combination of automation and pre-made design to build levels.  This got me thinking that I should just create a bunch of prefab “rooms” and then link them together.  In the end, I think this will allow for much more flexibility in the future.  So, I’m only 2 days into this game and I’m already scrubbing everything I have.

But just for posterity, here’s version 0.1: Maze Raider (This is a working title…I’m not attached to it.)

Leave a Reply