blogblog SyKoHPaTh

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