The representation I chose was to store information regarding the connection of edges between cell vertices, as well as to be able to reference or store information regarding the edges of a given cell. So I required operations to be performed on either cells or nodes(vertices). Get/Set/Clear operations can be done on an edge basis (ie, connect an edge from this corner in the north direction) or on a cell basies (ie, set the north edge of this cell). Such a representation facilitates multiple methods of maze generation, and allows easy analysis of each cell to determine it's edges and select a pre-made room pattern corresponding to the edge pattern.
I also wanted to specify certain additional cell-based functionality useful for the depth-first random generation algorithim; specifically, the ability to flag a cell as visited.
I represent each node(vertex) as a single unsigned char, and store connectivity information in individual bits. Additionally, I represent each cell as a single uchar, and encode visited as a single bit. Has the advantage of compacting a maze into w*h + (w+1)*(h+1) bytes, where w,h are the dimensions of the maze in cells. So a 200x200 maze is represented in 80401 bytes. That's about as compact as I could make it without getting extremely weird with bit packing, and I will rarely if ever have occasion to use it for large mazes anyway since I am only building it as a basis for the level templating described in my previous post. And a templated level built on a maze of 200x200 cells would be huge, bewilderingly complex, and completely unnecessary.
I provide two methods of maze generation. The first is the wall-growth mechanism detailed in the original Accidental article. All node positions in the maze are compiled into a list then shuffled into random order. The list is then iterated, and at each location I check to see if the node is blocked, ie connected to any other node by an edge. A blocking condition halts wall building. If the node is not blocked, a random direction and wall length are determined, and the algorithm attempts to build a wall in that direction and up to that length. Again, blocked nodes halt wall building. The result is a maze comprised of many looping paths, wherein one can travel from one point to another by multiple paths.
The second generation method is a randomized recursive depth-first search of the maze. Starting at a random starting location, mark the cell as visited, then visit each of it's 4 neighbors in turn, random order. For each neighbor cell that has not been visited, knock down the wall between the two cells, then recurse with that neighbor cell as the current cell. This algorithm generates a 'perfect' maze, wherein there is exactly 1 path between any two randomly selected points. Creates a maze with lots of long, branching, twisting passages and dead ends.
These 2 images show the 2 algorithms in action, first the wall-growth technique, then the depth-first technique.
The maze header:
#ifndef MAZE_H#define MAZE_H#include struct CMazeNode{ unsigned char edges; void setEdge(unsigned char e){edges |= e;}; void clearEdge(unsigned char e){edges &= ~e;}; void clear(){edges=0;}; void set(){edges=15;}; bool getEdge(unsigned char e){return ((edges & e) != 0);}; bool isBlocked(){return (edges != 0);};};struct SNodeListElement{ unsigned int x, y; SNodeListElement(unsigned int X, unsigned int Y) : x(X), y(Y) {};};enum EEdgeMasks{ E_North=0x01, E_West=0x02, E_East=0x04, E_South=0x08, E_Visited=0x10};class CMaze{ public: CMaze(){nodes=0;cells=0;}; ~CMaze(){destroy();}; void init(unsigned int cw, unsigned int ch); void destroy(); unsigned int getCellWidth(){return cell_width;}; unsigned int getCellHeight(){return cell_height;}; unsigned int getNodeWidth(){return node_width;}; unsigned int getNodeHeight(){return node_height;}; // Node-based functions void setEdgeNode(unsigned int x, unsigned int y, unsigned char cm_edge); void clearEdgeNode(unsigned int x, unsigned int y, unsigned char cm_edge); bool isBlockedNode(unsigned int x, unsigned int y); bool getEdgeNode(unsigned int x, unsigned int y, unsigned char cm_edge); // Cell-based functions void setEdgeCell(unsigned int x, unsigned int y, unsigned char cm_edge); void clearEdgeCell(unsigned int x, unsigned int y, unsigned char cm_edge); bool getEdgeCell(unsigned x, unsigned y, unsigned char cm_edge); unsigned char getEdgePattern(unsigned int x, unsigned int y); // Spanning-tree based generation base functionality // Used by algorithms that generate based on some sort of // recursive or tree-based randomized search algorithm void setVisited(unsigned int x, unsigned int y); bool getVisited(unsigned int x, unsigned int y); void clearVisited(unsigned int x, unsigned int y); void setBackDirection(unsigned int x, unsigned int y, unsigned char dir); unsigned char getBackDirection(unsigned int x, unsigned int y); void clearBackDirection(unsigned int x, unsigned int y); // General functions void setAllEdges(); void clearAllEdges(); void setBorderEdges(); void clearAllCells(); // Clear back and visited for all cells void clear(){clearAllEdges(); clearAllCells(); setBorderEdges();}; // Generation functions void generateWallGrowthMaze(unsigned int min_wall, unsigned int max_wall); void generateDepthFirstMaze(); private: CMazeNode *nodes; unsigned char *cells; unsigned int cell_width, cell_height; // dimensions in cells unsigned int node_width, node_height; // dims in nodes void buildNodeList(std::vector &list); void shuffleNodeList(std::vector &list); unsigned char randomDir(); void buildMazeWall(unsigned int x, unsigned int y, unsigned char cm_dir, unsigned int len); void recurseDepthFirst(unsigned int x, unsigned int y);};#endifAnd the source:
#include "maze.h"#include #include #include // Helper functionsvoid CMaze::buildNodeList(std::vector &list){ // Populate a vector with (x,y) pairs for every node in the maze if(!nodes) return; // Not initialized unsigned int x,y; list.clear(); list.reserve(node_width*node_height); for(x=0; x { for(y=0; y { list.push_back(SNodeListElement(x,y)); } } shuffleNodeList(list); return;}void CMaze::shuffleNodeList(std::vector &list){ // Use our global random generator for predictable level regeneration /*unsigned int size=list.size(); if(size==0) return; unsigned int c; for(c=0; c { unsigned int rn; do { rn=g_randRange(0,size-1); } while(rn==c); SNodeListElement tmp=list[c]; list[c]=list[rn]; list[rn]=tmp; }*/ // algorithm defines a shuffle algorithm that operates on // iterators // std::random_shuffle(list.begin(), list.end()); // Or, we can pass our global g_randTarget as a functor std::random_shuffle(list.begin(), list.end(), g_randTarget);}void CMaze::init(unsigned int cw, unsigned int ch){ destroy(); if(cw==0 || ch==0) return; cell_width=cw; cell_height=ch; node_width=cw+1; node_height=ch+1; nodes=new CMazeNode[node_width * node_height]; cells=new unsigned char[cell_width*cell_height]; clearAllEdges(); clearAllCells();}void CMaze::destroy(){ if(nodes) { delete[] nodes; nodes=0; } if(cells) { delete[] cells; cells=0; }}// Node-based functions// setEdgeNode-- Connect an edge starting at x,y and extending one edge length in the// direction given by cm_edge.void CMaze::setEdgeNode(unsigned int x, unsigned int y, unsigned char cm_edge){ if(x>=node_width || y>=node_height) return; if(!nodes) return; nodes[y*node_width+x].setEdge(cm_edge); // Now, set other node unsigned char e; unsigned int nx, ny; if(cm_edge==E_North) { e=E_South; nx=x; ny=y-1; } else if(cm_edge==E_South) { e=E_North; nx=x; ny=y+1; } else if(cm_edge==E_East) { e=E_West; nx=x+1; ny=y; } else if(cm_edge==E_West) { e=E_East; nx=x-1; ny=y; } else return; if(nx>=node_width || ny>=node_height) return; nodes[ny*node_width+nx].setEdge(e);}// clearEdgeNode -- Remove an edge starting at x,y in direction cm_edgevoid CMaze::clearEdgeNode(unsigned int x, unsigned int y, unsigned char cm_edge){ if(x>=node_width || y>=node_height) return; if(!nodes) return; nodes[y*node_width+x].clearEdge(cm_edge); // Now, clear other node unsigned char e; unsigned int nx, ny; if(cm_edge==E_North) { e=E_South; nx=x; ny=y-1; } else if(cm_edge==E_South) { e=E_North; nx=x; ny=y+1; } else if(cm_edge==E_East) { e=E_West; nx=x+1; ny=y; } else if(cm_edge==E_West) { e=E_East; nx=x-1; ny=y; } else return; if(nx>=node_width || ny>=node_height) return; nodes[ny*node_width+nx].clearEdge(e);}// isBlockedNode -- Query a node to see if any edges connect to it;// this constitutes a 'blocking' condition for the wall-growth algorithmbool CMaze::isBlockedNode(unsigned int x, unsigned int y){ if(x>=node_width || y>=node_height) return false; if(!nodes) return false; return (nodes[y*node_width+x].isBlocked());}// getEdgeNode -- Determine if a node is connected to an edge extending in the given directionbool CMaze::getEdgeNode(unsigned int x, unsigned int y, unsigned char cm_edge){ if(x>=node_width || y>=node_height) return false; if(!nodes) return false; return (nodes[y*node_width+x].getEdge(cm_edge));}// Cell-based functions// setEdgeCell -- Set the edge of the given cell in the given directionvoid CMaze::setEdgeCell(unsigned int x, unsigned int y, unsigned char cm_edge){ if(x>=cell_width || y>=cell_height || !nodes) return; unsigned int nx, ny; unsigned char e; // Calculate one endpoint of edge if(cm_edge==E_North) { nx=x; ny=y; e=E_East; } else if(cm_edge==E_South) { nx=x; ny=y+1; e=E_East; } else if(cm_edge==E_East) { nx=x+1; ny=y; e=E_South; } else if(cm_edge==E_West) { nx=x; ny=y; e=E_South; } else return; setEdgeNode(nx, ny, e);}// clearEdgeCell -- Remove the given edge of the given cellvoid CMaze::clearEdgeCell(unsigned int x, unsigned int y, unsigned char cm_edge){ if(x>=cell_width || y>=cell_height || !nodes) return; unsigned int nx, ny; unsigned char e; // Calculate one endpoint of edge if(cm_edge==E_North) { nx=x; ny=y; e=E_East; } else if(cm_edge==E_South) { nx=x; ny=y+1; e=E_East; } else if(cm_edge==E_East) { nx=x+1; ny=y; e=E_South; } else if(cm_edge==E_West) { nx=x; ny=y; e=E_South; } else return; clearEdgeNode(nx, ny, e);}// getEdgeCell -- Query the given edge of the given cellbool CMaze::getEdgeCell(unsigned int x, unsigned int y, unsigned char cm_edge){ if(x>=cell_width || y>=cell_height || !nodes) return false; unsigned int nx, ny; unsigned char e; // Calculate one endpoint of edge if(cm_edge==E_North) { nx=x; ny=y; e=E_East; } else if(cm_edge==E_South) { nx=x; ny=y+1; e=E_East; } else if(cm_edge==E_East) { nx=x+1; ny=y; e=E_South; } else if(cm_edge==E_West) { nx=x; ny=y; e=E_South; } else return false; return getEdgeNode(nx, ny, e);}// getEdgePattern -- Compile an unsigned char value specifying the edge pattern of// the given cell. Classifies a cell based on it's open and closed edges into one of// sixteen categories.unsigned char CMaze::getEdgePattern(unsigned int x, unsigned int y){ unsigned char pattern=0; if(getEdgeCell(x,y,E_North)) pattern |= E_North; if(getEdgeCell(x,y,E_South)) pattern |= E_South; if(getEdgeCell(x,y,E_East)) pattern |= E_East; if(getEdgeCell(x,y,E_West)) pattern |= E_West; return pattern;}// General functions// setAllEdges -- Connect all edges between nodes in the entire mazevoid CMaze::setAllEdges(){ if(!nodes) return; unsigned int c; for(c=0; c { nodes[c].set(); }}// clearAllEdges -- Clear all edges between nodes in the entire mazevoid CMaze::clearAllEdges(){ if(!nodes) return; unsigned int c; for(c=0; c { nodes[c].clear(); }}// setBorderEdges -- Set the edges on the outside border of the mazevoid CMaze::setBorderEdges(){ if(!nodes) return; int c; // Set top and bottom edge for(c=0; c { setEdgeCell(c,0,E_North); setEdgeCell(c,cell_height-1,E_South); } // Set left and right edge for(c=0; c { setEdgeCell(0,c,E_West); setEdgeCell(cell_width-1,c,E_East); }}// setVisited -- Mark the given cell has 'visited'. Used by the depth-first generation algovoid CMaze::setVisited(unsigned int x, unsigned int y){ if(x>=cell_width || y>=cell_height || !cells) return; cells[y*cell_width+x] |= E_Visited;}// getVisited -- Check to see if the given cell has been visited alreadybool CMaze::getVisited(unsigned int x, unsigned int y){ if(x>=cell_width || y>=cell_height || !cells) return false; return (cells[y*cell_width+x] & E_Visited);}// clearVisited -- Clear the visited status of a cellvoid CMaze::clearVisited(unsigned int x, unsigned int y){ if(x>=cell_width || y>=cell_height || !cells) return; cells[y*cell_width+x] &= ~E_Visited;}void CMaze::setBackDirection(unsigned int x, unsigned int y, unsigned char dir){ if(x>=cell_width || y>=cell_height || !cells) return; cells[y*cell_width+x] |= dir;}unsigned char CMaze::getBackDirection(unsigned int x, unsigned int y){ if(x>=cell_width || y>=cell_height || !cells) return 0; return cells[y*cell_width+x] & 0x0F;}void CMaze::clearBackDirection(unsigned int x, unsigned int y){ if(x>=cell_width || y>=cell_height || !cells) return; cells[y*cell_width+x] &= ~0x0F;}// clearAllCells -- Clear the visited and other status flags of all cells in the mazevoid CMaze::clearAllCells(){ if(!cells) return; for(unsigned int c=0; c { cells[c]=0; }}// buildMazeWall -- The workhorse of the wall-growth algorithm. Given a starting location, a// direction, and a length, attempt to build a wall. Blocked nodes terminate wall buildingvoid CMaze::buildMazeWall(unsigned int x, unsigned int y, unsigned char dir, unsigned int len){ unsigned int wx=x, wy=y; unsigned int ox,oy; if(isBlockedNode(x,y)) return; unsigned int c; for(c=0; c { ox=wx; oy=wy; if(dir==1) wy-=1; if(dir==2) wx-=1; if(dir==4) wx+=1; if(dir==8) wy+=1; if(isBlockedNode(wx,wy)) { setEdgeNode(ox,oy,dir); return; } else { setEdgeNode(ox,oy,dir); } }}// randomDir -- Select one of the for random directionsunsigned char CMaze::randomDir(){ unsigned int roll=g_randRange(1,4); switch(roll) { case 1: return E_North; case 2: return E_West; case 3: return E_East; case 4: return E_South; };}// generateWallGrowthMaze -- Construct a maze using the wall-growth method.// The method works by accumulating all node coordinates into a list, shuffling the list, then iterating// through it. At each location, attempt to draw a wall of randomly determined length and direction.// Blocked nodes prevent wall building. This algorithm results in a maze that has lots of loops and// multiple paths between any two given points. The passed parameters min_wall and max_wall// determine the range of lengths of walls to be drawn. Walls may in reality turn out shorter// due to hitting a wall. Longer wall lengths result in longer straight passages.void CMaze::generateWallGrowthMaze(unsigned int min_wall, unsigned int max_wall){ if(!nodes) return; std::vector nlist; buildNodeList(nlist); unsigned int size=nlist.size(); if(size==0) return; unsigned int c; for(c=0; c { unsigned char d=randomDir(); unsigned int len=g_randRange(min_wall, max_wall); unsigned int x=nlist[c].x; unsigned int y=nlist[c].y; buildMazeWall(x,y,d,len); }}// recurseDepthFirst -- The workhorse of the depth-first tree-based generation algorithm// The function marks the current cell as visited, then shuffles the cell's 4 adjacent neighbors into// random order and calls itself for each cell in the list that has not already been visited. When// a cell's neighbor is visited, the edge between the two cells is knocked down, creating a passage.void CMaze::recurseDepthFirst(unsigned int x, unsigned int y){ // First, mark cell as visited setVisited(x,y); // Now, check each neighbor. If it hasn't been visited, knock down the // wall and recurse on that cell unsigned int cx,cy; unsigned char dirs[4]={E_North, E_South, E_East, E_West}; std::random_shuffle(dirs, dirs+4, g_randTarget); for(int c=0; c<4; ++c) { unsigned char d=dirs[c]; switch(d) { case E_North: cx=x; cy=y-1; break; case E_South: cx=x; cy=y+1; break; case E_East: cx=x+1; cy=y; break; case E_West: cx=x-1; cy=y; break; } if(cx { if(!getVisited(cx,cy)) { clearEdgeCell(x,y,d); recurseDepthFirst(cx,cy); } } }}// generateDepthFirstMaze -- Generates a maze using a randomized depth-first search of the maze// starting at a random location.// This algorithm generates a 'perfect' maze, in which there is exactly 1 path between any two randomly// selected cells.void CMaze::generateDepthFirstMaze(){ // First, select a random starting cell if(!nodes) return; unsigned int sx, sy; sx = g_randTarget(cell_width); sy = g_randTarget(cell_height); setAllEdges(); recurseDepthFirst(sx, sy);}For a given (x,y) cell location, once the maze is generated you can call a function, getEdgePattern, that will return an unsigned char value representing the pattern of edges belonging to that cell. If the north edge is represented by the value of 1, for example, and the south edge is represented by the value of 8, then a cell with the north and south edges closed and the east and west edges open would have the edge pattern of 10. The 4 cardinal directions are represented as bits to facilitate this process. This allows the level generation algorithm to query the maze for a value, and use that value to determine which pre-generated room pattern to copy into the level grid for a given layout graph node. With 4 cardinal directions, this classifies each cell of a maze into 1 of 16 categories, so 16 categories of room templates must be used. (rotation can cut down the work required here, by allowing the generation script to rotate patterns in 90 degree increments before copying into the level grid).
If you attempt to use the above class, you will get some errors. In my shuffling functions, I call std::random_shuffle with a custom random number generator that is part of my standard library package (vxnlib ftw!). The generator wraps up a mersenne twister from boost::random, and provides calls for performing real distribution number generation in the range of 0,1 or integer distribution in the range of 0,N. You can either replace the generator with one of your own in the random_shuffle calls, or use my hackish random stuff here:
#include #include #include #include #include #include boost::mt19937 global_mersenne;boost::uniform_real<> real_dist(0,1);boost::uniform_int<> int_dist(0, RAND_MAX);boost::variate_generator > uni_real(global_mersenne, real_dist);boost::variate_generator > uni_int(global_mersenne, int_dist);int g_randInt(){ // Return random int //return(rand()); return uni_int();}void g_setSeed(int Seed){ //srand(Seed); global_mersenne.seed(static_cast<unsigned int>(Seed));}void g_setSeedTime(){ //srand(time(0)); global_mersenne.seed(static_cast<unsigned int>(std::time(0)));}int g_randTarget(int Target){// Return rand up to, but not including, Target boost::uniform_int<> local_int_dist(0, Target-1); boost::variate_generator > local_uni_int(global_mersenne, local_int_dist); return local_uni_int();}float g_rand01(){// Return random from 0 to 1 inclusive return uni_real();}int g_randRange(int Low, int High){ // Return random from Low to High inclusive if(Low==High) return Low; int Range=High-Low + 1; int Result; Result=g_randTarget(Range); return(Low + Result);}int g_diceRoll(int Dice, int Sides){// Emulate dicerolling int Roll; int c; Roll=0; for(c=0;c Roll+=g_randRange(1,Sides); return Roll;}I created a couple of random number generators in the global namespace to make it easier to swap existing rand-based code with the new generators. Might not be the best approach, but it works for me. So sue me. If you want, you can just remove the function object parameter to random_shuffle, and the algorithm will default to using rand().
For visualization purposes, I merely iterate the edge graph, and draw horizontal or vertical lines in a bitmap depending on the edge connectivity of the nodes, then save the bitmap out to .tga format. It's a hacked up thingy, since it's not really part of the class and was only built for quick visualization purposes while testing and debugging. So I won't show it.
In days to come, I'll demonstrate how to use the generated maze as a level layout template, though the process here is simple enough.
Caveats: The class is a quick one, and my formal software engineering skills are nonexistent. There may be bugs, and there will certainly be better ways of doing things. I'm usually interested in hearing about them. But please try not to mire me in an endless recursion of finding better ways of doing things; I would rather move on to practical applications of things than sit around debating the merits of using std::map to represent a graph, and spending endless hours researching exactly how to do it. This method works well enough given the rigid constraints imposed by a graph living in the world of tile-based games.
