mazes

In last week’s grep blog I linked to a post on @gamasutra about algorithms for generating interesting mazes.  This weekend I was feeling inspired to finally get into some procgen coding, and I ended up creating a little Unity demo.  You can play it here in your browser:

After studying that maze article for a bit it didn’t take long to get the basic algorithm running, but initially I had no real ‘seed’ concept (my name for the grid coloring input used at the core of the algorithm).  I just had a hard-coded version of what the article calls a [2,0,2] grid coloring and totally random wall selection behavior.  From there I refactored it into a data structure so I could experiment with different seed types, but since it only supported single-cell tiles I couldn’t get anything really interesting out of it.

So I extended the seed structure to allow each tile to point to one other tile as its ‘parent’ tile.  Whenever the parent or child tile is evaluated in any part of the algorithm then the whole set of tiles is evaluated via a linked list.  To keep things simple I enforce some strict rules, like a child tile can only have one parent, and a parent tile cannot also be a child (e.g. limit of depth=1).

One fun part about how I implemented this in the data, is that the reference is stored as an offset of rows and columns.  This means that an edge tile of the seed can actually point outwards and link to tiles of adjacent seeds at generation time.  The two bottom seeds in the demo both take advantage of this, resulting in more complex and interesting output.

The article is very vague about the particulars of grid coloring, but after studying the examples I realized that as long as my seeds were square, and repeated in every direction, then I could guarantee that the requirements of the algorithm would always be met.  The four seeds in my demo were all derived from examples in the article, but now that I have a functional interface into the algorithm I think it would be fun to create a frontend for designing and testing seeds of all kinds.

I can’t really share the entire demo project source, since I would have to post the RZG source along with it, so instead I generated a doxygen page for the procgen algorithm.  I tore out all of my engine-related code, but you could probably just stick it in a MonoBehaviour and get it running without too much effort.  Enjoy!