gene-ressler/maze.c

## maze.c
/*
 * A parameterized rectangular grid maze generator.
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Maze data bits.
#define VISITED 1
#define RIGHT 2
#define BOTTOM 4
#define GOAL 8

// Weights for directions taken at each new cell. Tweak for cool effects.
#define FORWARD_WEIGHT 3
#define LEFT_WEIGHT 2
#define RIGHT_WEIGHT 1
#define TOTAL_WEIGHT (FORWARD_WEIGHT + LEFT_WEIGHT + RIGHT_WEIGHT)

// Compass directions on the i-j (row-column) plane.
#define S 0
#define E 1
#define N 2
#define W 3

// Directions leaving a positon after arriving via the one in first index.
// Second index is forward, left, right.
static int dirs[4][3] = {
  { S, E, W }, { E, N, S }, { N, W, E }, { W, S, N }
};

// i-j steps corresponding to directions.
static int steps[4][2] = {
  { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }
};

// i-j offsets and mask to erase a wall just crossed in index direction.
static int erasers[4][3] = {
  {-1, 0, ~BOTTOM }, { 0,-1, ~RIGHT }, { 0, 0, ~BOTTOM }, { 0, 0, ~RIGHT }
};

// Prepare the arena to build a maze.
void init(int m, int n, unsigned char maze[][n]) {
  srandom(time(0));
  for (int i = 0; i < m; ++i)
    for (int j = 0; j < n; ++j)
      maze[i][j] = (RIGHT | BOTTOM);
}

// Accumulator for cell at max distance from start.
typedef struct {
  int max_dist;
  int i, j;
} STATE;

// Search the maze grid randomly depth first, erasing walls as we go.
void search(int m, int n, unsigned char maze[][n], // maze
    int i, int j, // current cell in maze
    int dir,      // direction we went to get here
    int dist,     // distance from start
    STATE *state) {
  // Give up if we're outside the maze or have already visited the cell.
  if (i < 0 || i >= m || j < 0 || j >= n || (maze[i][j] & VISITED)) return;

  // Now we've visited.
  maze[i][j] |= VISITED;

  // Accumulate max distance from start.
  if (dist > state->max_dist) {
    state->max_dist = dist;
    state->i = i;
    state->j = j;
  }

  // Erase the wall we just traversed.
  maze[i + erasers[dir][0]][j + erasers[dir][1]] &= erasers[dir][2];

  // Use a weighted die to decide order of forward, left, and right search.
  int r = random() % TOTAL_WEIGHT;
  int s = r < FORWARD_WEIGHT ? 0 : r < FORWARD_WEIGHT + LEFT_WEIGHT ? 1 : 2;

  // Search recursively in that order.
  for (int q = 0; q < 3; ++q) {
    int new_dir = dirs[dir][(s + q) % 3];
    search(m, n, maze,
        i + steps[new_dir][0], j + steps[new_dir][1], new_dir,
        dist + 1, state);
  }
}

// Use the accumulator to mark a goal that's at max distance from start.
void mark_goal(int n, unsigned char maze[][n], STATE *state) {
  maze[state->i][state->j] |= GOAL;
}

// Render the maze as ascii art.
void print(int m, int n, unsigned char maze[][n]) {
  printf("+");
  for (int j = 0; j < n; ++j) printf("---+");
  printf("\n");
  for (int i = 0; i < m; ++i) {
    printf("|");
    for (int j = 0; j < n; ++j)
      printf(" %c %c",
          maze[i][j] & GOAL  ? '*' : ' ',
          maze[i][j] & RIGHT ? '|' : ' ');
    printf("\n+");
    for (int j = 0; j < n; ++j) printf(maze[i][j] & BOTTOM ? "---+" : "   +");
    printf("\n");
  }
}

// Create and print a maze.
int main(int argc, char *argv[]) {
  int m = 20, n = 30, t, i = 1;
  if (i < argc) {
    if (sscanf(argv[i], "%d", &t) == 1) m = t;
    ++i;
  }
  if (i < argc) {
    if (sscanf(argv[i], "%d", &t) == 1) n = t;
    ++i;
  }
  STATE state[1] = { 0, 0, 0 };
  unsigned char maze[m][n];

  init(m, n, maze);
  search(m, n, maze, 0, n - 1, W, 0, state);
  mark_goal(n, maze, state);
  print(m, n, maze);
  printf("Distance: %d\n", state->max_dist);

  return 0;
}
	/*
	* A parameterized rectangular grid maze generator.
	*/
	#include <stdio.h>
	#include <stdlib.h>
	#include <time.h>

	// Maze data bits.
	#define VISITED 1
	#define RIGHT 2
	#define BOTTOM 4
	#define GOAL 8

	// Weights for directions taken at each new cell. Tweak for cool effects.
	#define FORWARD_WEIGHT 3
	#define LEFT_WEIGHT 2
	#define RIGHT_WEIGHT 1
	#define TOTAL_WEIGHT (FORWARD_WEIGHT + LEFT_WEIGHT + RIGHT_WEIGHT)

	// Compass directions on the i-j (row-column) plane.
	#define S 0
	#define E 1
	#define N 2
	#define W 3

	// Directions leaving a positon after arriving via the one in first index.
	// Second index is forward, left, right.
	static int dirs[4][3] = {
	{ S, E, W }, { E, N, S }, { N, W, E }, { W, S, N }
	};

	// i-j steps corresponding to directions.
	static int steps[4][2] = {
	{ 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }
	};

	// i-j offsets and mask to erase a wall just crossed in index direction.
	static int erasers[4][3] = {
	{-1, 0, ~BOTTOM }, { 0,-1, ~RIGHT }, { 0, 0, ~BOTTOM }, { 0, 0, ~RIGHT }
	};

	// Prepare the arena to build a maze.
	void init(int m, int n, unsigned char maze[][n]) {
	srandom(time(0));
	for (int i = 0; i < m; ++i)
	for (int j = 0; j < n; ++j)
	maze[i][j] = (RIGHT \| BOTTOM);
	}

	// Accumulator for cell at max distance from start.
	typedef struct {
	int max_dist;
	int i, j;
	} STATE;

	// Search the maze grid randomly depth first, erasing walls as we go.
	void search(int m, int n, unsigned char maze[][n], // maze
	int i, int j, // current cell in maze
	int dir, // direction we went to get here
	int dist, // distance from start
	STATE *state) {
	// Give up if we're outside the maze or have already visited the cell.
	if (i < 0 \|\| i >= m \|\| j < 0 \|\| j >= n \|\| (maze[i][j] & VISITED)) return;

	// Now we've visited.
	maze[i][j] \|= VISITED;

	// Accumulate max distance from start.
	if (dist > state->max_dist) {
	state->max_dist = dist;
	state->i = i;
	state->j = j;
	}

	// Erase the wall we just traversed.
	maze[i + erasers[dir][0]][j + erasers[dir][1]] &= erasers[dir][2];

	// Use a weighted die to decide order of forward, left, and right search.
	int r = random() % TOTAL_WEIGHT;
	int s = r < FORWARD_WEIGHT ? 0 : r < FORWARD_WEIGHT + LEFT_WEIGHT ? 1 : 2;

	// Search recursively in that order.
	for (int q = 0; q < 3; ++q) {
	int new_dir = dirs[dir][(s + q) % 3];
	search(m, n, maze,
	i + steps[new_dir][0], j + steps[new_dir][1], new_dir,
	dist + 1, state);
	}
	}

	// Use the accumulator to mark a goal that's at max distance from start.
	void mark_goal(int n, unsigned char maze[][n], STATE *state) {
	maze[state->i][state->j] \|= GOAL;
	}

	// Render the maze as ascii art.
	void print(int m, int n, unsigned char maze[][n]) {
	printf("+");
	for (int j = 0; j < n; ++j) printf("---+");
	printf("\n");
	for (int i = 0; i < m; ++i) {
	printf("\|");
	for (int j = 0; j < n; ++j)
	printf(" %c %c",
	maze[i][j] & GOAL ? '*' : ' ',
	maze[i][j] & RIGHT ? '\|' : ' ');
	printf("\n+");
	for (int j = 0; j < n; ++j) printf(maze[i][j] & BOTTOM ? "---+" : " +");
	printf("\n");
	}
	}

	// Create and print a maze.
	int main(int argc, char *argv[]) {
	int m = 20, n = 30, t, i = 1;
	if (i < argc) {
	if (sscanf(argv[i], "%d", &t) == 1) m = t;
	++i;
	}
	if (i < argc) {
	if (sscanf(argv[i], "%d", &t) == 1) n = t;
	++i;
	}
	STATE state[1] = { 0, 0, 0 };
	unsigned char maze[m][n];

	init(m, n, maze);
	search(m, n, maze, 0, n - 1, W, 0, state);
	mark_goal(n, maze, state);
	print(m, n, maze);
	printf("Distance: %d\n", state->max_dist);

	return 0;
	}