Maze Generation in C++

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
{
public:
   // 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.
   Cell();
   
   // And this is the destructor. It removes it's self from the group, and
   // if the group ends up becoming empty, it deletes it.
   ~Cell();
   
   // 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);

private:
   // 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
{
public:
   // 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.
   ~Maze();
   
   // 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 ();

private:    
   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>

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

Cell::~Cell()
{
   group->erase(std::find(group->begin(), group->end(), this));
   
   if(!group->size())
      delete group;
}

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

void Cell::ApplyRules(unsigned int edge, Cell &cell)
{
   if(group != cell.group) // If we are in different groups. . .
   {
      std::vector *old_group = cell.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];
}

Maze::~Maze()
{
   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));

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

            break;
         }
      }
   }
}

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