Maze Generation in C++

And now for some real geeky goodness…

Here’s a random maze generator class based on Kruskal’s algorithm for creating a minimum spanning tree. Of course I didn’t write this from scratch… It’s a cleaned up and modified version of some code I found here written by smart_idiot. At least I think that’s his page… This version creates a maze that is closed in on the bounding walls. If you add the missing cases to the switch statement in Update(), it will create a maze that “wraps”, where “exiting” an opening in one exterior wall will “enter” on the opposite side of the maze.

Yeah there is no drawing code so have fun. I did write a small application that will give a 3D walk through of the maze. I might post it some time… but the source is relatively large…

#ifndef _MAZE_H_
#define _MAZE_H_

#include <vector>

class Cell
   // This is the constructor for the Cell. As you can see, it starts off with
   // a new group containing a pointer to its self, and all the edges are set
   // to true, meaning there are walls up.
   // And this is the destructor. It removes it's self from the group, and
   // if the group ends up becoming empty, it deletes it.
   // Write about here I should have a copy constructor, and an assignment opperator.
   // The problem with that however is that if I do that, they should get new groups.
   // If they get new groups, they obviously aren't connected to anything. And if
   // they aren't connected to anything, there isn't much point in trying to make
   // a copy of them. So long story short, no trying to copy cells. And as a side
   // effect of this, Mazes too.
   // This applies the rules between two cells.
   void ApplyRules(unsigned int edge, Cell &neighbor);
   bool GetEdge (int index);

   // And the cells have edges. Four of them. Imagine that.
   bool Edge[4];
   // This is the most important part of the maze generator. Each cell belongs
   // to a group. In the beginning each cell has its own group. If 2 neighboring
   // cells are in different groups, they can connect, and in the process become
   // part of the same group. Thats pretty much all there is to it.
   std::vector *group;
   friend class Maze;

class Maze
   // This is the maze constructor. By default a maze is 32x32 cells, though you can use any size
   // you want, though 8x8 is the minumum.
   Maze(unsigned int w = 32, unsigned int h = 32);
   // This is the destructor, which is only here to destroy the cells and avoid a nasty memory leak.
   // This is a helper for finding a cell in the maze. You may choose a cell outside of the maze,
   // in which case it wraps back to the other side, though trying to look up a cell farther than
   // 2 maze lengths away will cause serious problems and probably a crash if x or y is negetive.
   Cell & At(int x, int y);
   // This function should be called repeatedly to construct the maze. The maze is done
   // when all the cells are in the same group, and hence the group size of any of the
   // cells is equal to width times height, but there currently isn't a check for it.
   void Update();
   unsigned int GetWidth ();
   unsigned int GetHeight ();
   bool MazeDone ();

   void Generate ();

   Cell *cells; // And now, back in the context of the Maze class, we have a pointer to some cells.
   unsigned int width, height; // Width and height of the maze.   

#endif //_MAZE_H_

#include "Maze.h"

#include <algorithm>

   group = new std::vector <cell*> (1, this);
   Edge[0] = Edge[1] = Edge[2] = Edge[3] = true;

   group->erase(std::find(group->begin(), group->end(), this));
      delete group;

bool Cell::GetEdge (int index)
   return Edge [index];

void Cell::ApplyRules(unsigned int edge, Cell &cell)
   if(group != // If we are in different groups. . .
      std::vector *old_group =; // Remember the old group so we can delete it later.
      // Change all the cells in that group to point to our group.
      for(std::vector::iterator c = old_group->begin(); c != old_group->end(); c++)
         (*c)->group = group;
      // Add them all to out group.
      group->insert(group->end(), old_group->begin(), old_group->end());
      // And finally destroy the old group.
      delete old_group;
      // All thats left to do now is hide the edges of the cells.
      Edge[edge] = false;
      cell.Edge[(edge + 2) % 4] = false;

Maze::Maze(unsigned int w, unsigned int h)
   width = w < 8 ? 8 : w;
   height = h < 8 ? 8 : h;
   cells = new Cell [width * height];

   delete [] cells;

unsigned int Maze::GetWidth()
   return width;

unsigned int Maze::GetHeight ()
   return height;

Cell & Maze::At(int x, int y)
   return cells[(x+width)%width + ((y+height)%height)*width];

bool Maze::MazeDone ()
   return (At (0,0).group->size () == width * height);

void Maze::Update()
   int edge;

   for(unsigned int y = 0; y < height; ++y)
      for(unsigned int x = 0; x < width; ++x)
         edge = 1 + rand () % 2;

         switch (edge)
         case 1:
            if (x + 1 < width)
               At (x, y).ApplyRules (edge, At(x+1, y));

         case 2:
            if (y + 1 < height)
               At (x, y).ApplyRules (edge, At(x, y+1));


void Maze::Generate ()
   while (!MazeDone ())
      Update ();

Related Posts