#include #include #include int Max_col, Max_row; char *field; /* ** compass direction encoded in four bits ** 0000 - ---- - no direction (starting point) ** 0001 - ---W - West ** 0010 - --E- - East ** 0100 - -N-- - North ** 1000 - S--- - South */ #define START 0 /* no bits on */ #define WEST (1 << 0) /* 1's bit on */ #define EAST (1 << 1) /* 2's bit on */ #define NORTH (1 << 2) /* 4's bit on */ #define SOUTH (1 << 3) /* 8's bit on */ /* ** single cell indicators encoded in three bits ** xx1 - South Wall ** x1x - East Wall ** 1xx - Cell has been occupied */ #define WALL_SOUTH (1 << 0) #define WALL_EAST (1 << 1) #define OCCUPIED (1 << 2) #define WAS_OCCUPIED 1 #define WAS_FREE 0 /* convenience macro for single cell addressing */ #define Cell(x,y) (field + (y * Max_col) + x) /* convenience macro for generating an exploration heading */ #define getHeading() (1 << (rand() % 4)) /* ** Initialize the entire "field" so that each cell ** has a South wall, an East wall, and is not occupied */ void setupCells(int col, int row, char *thefield) { Max_row = row; Max_col = col; field = thefield; for (row = 0; row < Max_row; ++row) for (col = 0; col < Max_col; ++col) *Cell(col,row) = (WALL_SOUTH | WALL_EAST) & ~OCCUPIED; } /* ** Occupy and explore outwards from the indicated cell, ** Return whether the cell was already occupied or not */ int exploreCells(int col, int row, int camefrom) { int exploring, heading; /* are we allowed to explore this cell? */ if ((col < 0) /* cell is off the WEST edge of the map */ || (col >= Max_col) /* cell is off the EAST edge of the map */ || (row < 0) /* cell is off the NORTH edge of the map */ || (row >= Max_row) /* cell is off the SOUTH edge of the map */ || ( *Cell(col,row) & OCCUPIED)) /* been here before */ return WAS_OCCUPIED; /* this cell is TABU */ /* * mark territory as occupied, break down intervening wall * * If we camefrom the SOUTH, we remove the SOUTH wall of the current cell * the EAST, we remove the EAST wall of the current cell * the NORTH, we don't remove any walls * the WEST, we don't remove any walls * the START, we don't remove any walls */ *Cell(col,row) |= OCCUPIED; switch (camefrom) { case SOUTH: *Cell(col,row) &= ~WALL_SOUTH; break; case EAST: *Cell(col,row) &= ~WALL_EAST; break; } /* * explore new territory from here - stop when we've exhausted all directions * * We don't have to explore in the direction we camefrom, so we remove it * from the list of directions we are to explore. * * We will continue to explore until we have explored in all directions */ for (exploring = (WEST | EAST | NORTH | SOUTH) & ~camefrom ; /* directions we can go */ exploring; /* directions unexplored */ exploring &= ~heading) /* remove last heading */ { /* chose a new direction to explore in, see if we've gone that way before */ switch (exploring & (heading = getHeading())) { case WEST: /* haven't tried West yet */ /* we go WEST, and remove the EAST wall of the cell above*/ exploreCells(col-1, row, EAST); break; case EAST: /* haven't tried East yet */ /* if we can go EAST, we remove the EAST wall of this cell*/ if (exploreCells(col+1,row,WEST) == WAS_FREE) *Cell(col,row) &= ~WALL_EAST; break; case NORTH: /* haven't tried North yet */ /* we go NORTH and remove the SOUTH wall of the cell above */ exploreCells(col, row-1,SOUTH); break; case SOUTH: /* haven't tried South yet */ /* if we can go SOUTH, we remove the SOUTH wall of this cell*/ if (exploreCells(col,row+1,NORTH) == WAS_FREE) *Cell(col,row) &= ~WALL_SOUTH; break; default: break; } } return WAS_FREE; } /* ** Print the map of the maze, cell at a time ** West wall of NorthWest cell removed for entrance ** West wall of SouthWest cell removed for exit */ void displayCells(void) { int row, col, line; /* show a continious wall on the northernmost edge */ putchar('\t'); putchar('+'); for (col = 0; col < Max_col; ++col) printf("---+"); puts(""); /* Draw each row of cells */ for (row = 0; row < Max_row; ++row) { /* ** first two lines contain the floor and East wall ** of each cell. Also, we draw the Western wall of ** the westernmost cell. ** ** NB: For the cell in the NW corner, and the cell ** in the SW corner, we don't draw in their western ** wall, but instead draw in the entrance and exits. */ for (line = 0; line < 2; ++line) { putchar('\t'); /* Entrance, Exit, or Westmost wall */ if ((row == 0) || (row == Max_row - 1)) putchar(' '); /* entrance or exit */ else putchar('|'); /* westernmost wall */ /* floor and east wall of each cell */ for (col = 0; col < Max_col; ++col) { if (*Cell(col,row) & OCCUPIED) printf(" "); /* we've seen this cell */ else printf(" # "); /* should never happen */ if (*Cell(col,row) & WALL_EAST) putchar('|'); else putchar(' '); } puts(""); } /* third line contains South walls */ putchar('\t'); putchar('+'); for (col = 0; col < Max_col; ++col) { if (*Cell(col,row) & WALL_SOUTH) printf("---+"); else printf(" +"); } puts(""); } } /* ** Build a maze */ int buildMaze(unsigned col, unsigned row) { srand((unsigned int)time(NULL)); if ((field = malloc(row * col)) == NULL) return 1; Max_row = row; Max_col = col; for (row = 0; row < Max_row; ++row) for (col = 0; col < Max_col; ++col) *Cell(col,row) = (WALL_SOUTH | WALL_EAST) & ~OCCUPIED; exploreCells((col+1)/2,(row+1)/2,START); displayCells(); return 0; } int usage(char *name, char *message) { if (message && strlen(message)) fprintf(stderr,"Error: %s\n",message); fprintf(stderr,"Usage: %s width height\n",name); return EXIT_FAILURE; } int main(int argc, char *argv[]) { unsigned width, height; if (argc != 3) return usage(argv[0],NULL); if ((width = atoi(argv[1])) <= 1) return usage(argv[0],"width must be greater than 1"); if ((height = atoi(argv[2])) <= 1) return usage(argv[0],"height must be greater than 1"); if (buildMaze(width, height) != 0) return usage(argv[0],"your dimensions are too big"); return EXIT_SUCCESS; } /* This program copyright (c) Lew Pitcher, 2008, 2009 */