logo sykohpath.com

				where code goes to die
			
	
blogblog

Maze Generation - Recursive Division

I've been in the mood to make a sort-of Gauntlet clone, so this weekend I decided to mess around with maze generation a little bit.  On Wikipedia, there's several algorithms to generate a maze, but only steps listed for the recursive one.  I wanted to make a maze setup with random-size corridors, so this is what I came up with.  This is in C++, and yes, I know it's not preferred to pass a 2d array into a function - use a vector instead.

xS/xE = x start / x end
yS/yE = y start / y end

The 2d world array:  int world[worldWidth][worldHeight]
REALWORLDHEIGHT is a const global.  Again, yeah, I know, need to use vectors instead of arrays for this part.

Code Sample:
  1.     void maze_recursive_division(int (*world)[REALWORLDHEIGHT], int xS, int yS, int xE, int yE){
  2.         if(xE-xS < 10 || yE-yS < 10){ return; } //too small to divide chamber (adjust to make larger/smaller chambers
  3.         //1) divide original chamber into two walls, at least 1 space wide (using 2 for this)
  4.         int xDivide = (rand() % (xE-xS-2)) + xS+2;
  5.         int yDivide = (rand() % (yE-yS-2)) + yS+2;
  6.         for(int x = xS; x < xE; x++){
  7.             if(world[x][yDivide] == 60){ //60 is "walkable" tile, 10 is "wall"
  8.                 world[x][yDivide] = 10;
  9.             }
  10.         }
  11.         for(int y = yS; y < yE; y++){
  12.             if(world[xDivide][y] == 60){
  13.                 world[xDivide][y] = 10;
  14.             }
  15.         }
  16.         //2) put "holes" in 3/4 of the new walls
  17.         //xs->xd
  18.         //xd->xe
  19.         //ys->yd
  20.         //yd->ye
  21.         int solidWall = rand() % 4; //0 1 2 3 - pick the wall to leave solid
  22.         /* gap
  23.         length:  pick between start and end:  xS -> xE   rand xDivide-xS
  24.         Start point:  Pick between start and End-Length:  xE-Len-xS + xS
  25.         */
  26.         if(solidWall != 0){ //xs -> xdivide
  27.             int gapLength = (rand() % (xDivide-xS));
  28.             int startPoint = rand() % (xDivide-gapLength-xS) + xS;
  29.             for(int x = startPoint; x < startPoint + gapLength; x++){
  30.                 world[x][yDivide] = 60;
  31.             }
  32.         }
  33.         if(solidWall != 1){ //xdivide -> xE
  34.             int gapLength = (rand() % (xE-xDivide));
  35.             int startPoint = rand() % (xE-xDivide-gapLength) + xDivide;
  36.             for(int x = startPoint; x < startPoint + gapLength; x++){
  37.                 world[x][yDivide] = 60;
  38.             }
  39.         }
  40.         if(solidWall != 0){ //ys -> ydivide
  41.             int gapLength = (rand() % (yDivide-yS));
  42.             int startPoint = rand() % (yDivide-gapLength-yS) + yS;
  43.             for(int y = startPoint; y < startPoint + gapLength; y++){
  44.                 world[xDivide][y] = 60;
  45.             }
  46.         }
  47.         if(solidWall != 1){ //ydivide -> yE
  48.             int gapLength = (rand() % (yE-yDivide));
  49.             int startPoint = rand() % (yE-yDivide-gapLength) + yDivide;
  50.             for(int y = startPoint; y < startPoint + gapLength; y++){
  51.                 world[xDivide][y] = 60;
  52.             }
  53.         }
  54.         //3) call subdivide on smaller chambers
  55.         maze_recursive_division(world, xS, yS, xDivide, yDivide);
  56.         maze_recursive_division(world, xS, yDivide, xDivide, yE);
  57.         maze_recursive_division(world, xDivide, yS, xE, yDivide);
  58.         maze_recursive_division(world, xDivide, yDivide, xE, yE);
  59.     }

maze generation, c++,


0 comments.
Sign in to post a comment!



No comments posted yet!