maze-generation-patterns

name	maze-generation-patterns
description	Document maze generation algorithms (recursive backtracking, etc.), provide error handling patterns, include retry logic with limited attempts, document pathfinding validation patterns, and provide test patterns for maze generation. Use when implementing maze generation features.

Maze Generation Patterns

Overview

Patterns for implementing maze generation algorithms, including error handling, retry logic, pathfinding validation, and testing approaches.

Maze Generation Algorithms

Algorithm 1: Recursive Backtracking

Most common algorithm for maze generation:

interface Cell {
  x: number;
  y: number;
  walls: {
    north: boolean;
    south: boolean;
    east: boolean;
    west: boolean;
  };
  visited: boolean;
}

function generateMazeRecursiveBacktracking(
  width: number,
  height: number,
  seed?: number
): Cell[][] {
  // Initialize grid
  const grid: Cell[][] = [];
  for (let y = 0; y < height; y++) {
    grid[y] = [];
    for (let x = 0; x < width; x++) {
      grid[y][x] = {
        x,
        y,
        walls: { north: true, south: true, east: true, west: true },
        visited: false,
      };
    }
  }

  // Seed RNG if provided
  if (seed !== undefined) {
    seedRNG(seed);
  }

  // Stack for backtracking
  const stack: Cell[] = [];
  let current = grid[0][0];
  current.visited = true;
  stack.push(current);

  // Generate maze
  while (stack.length > 0) {
    const neighbors = getUnvisitedNeighbors(current, grid);
    
    if (neighbors.length > 0) {
      // Choose random neighbor
      const next = neighbors[Math.floor(seededRandom() * neighbors.length)];
      
      // Remove wall between current and next
      removeWall(current, next);
      
      // Mark next as visited
      next.visited = true;
      stack.push(next);
      current = next;
    } else {
      // Backtrack
      current = stack.pop()!;
    }
  }

  return grid;
}

function getUnvisitedNeighbors(cell: Cell, grid: Cell[][]): Cell[] {
  const neighbors: Cell[] = [];
  const { x, y } = cell;

  // Check all four directions
  const directions = [
    { x: 0, y: -1, name: 'north' },
    { x: 0, y: 1, name: 'south' },
    { x: 1, y: 0, name: 'east' },
    { x: -1, y: 0, name: 'west' },
  ];

  for (const dir of directions) {
    const nx = x + dir.x;
    const ny = y + dir.y;

    if (
      nx >= 0 &&
      nx < grid[0].length &&
      ny >= 0 &&
      ny < grid.length &&
      !grid[ny][nx].visited
    ) {
      neighbors.push(grid[ny][nx]);
    }
  }

  return neighbors;
}

function removeWall(current: Cell, next: Cell): void {
  const dx = next.x - current.x;
  const dy = next.y - current.y;

  if (dx === 1) {
    // Moving east
    current.walls.east = false;
    next.walls.west = false;
  } else if (dx === -1) {
    // Moving west
    current.walls.west = false;
    next.walls.east = false;
  } else if (dy === 1) {
    // Moving south
    current.walls.south = false;
    next.walls.north = false;
  } else if (dy === -1) {
    // Moving north
    current.walls.north = false;
    next.walls.south = false;
  }
}

Algorithm 2: Kruskal's Algorithm

Alternative algorithm using union-find:

function generateMazeKruskal(
  width: number,
  height: number,
  seed?: number
): Cell[][] {
  // Initialize grid with all walls
  const grid: Cell[][] = initializeGrid(width, height);
  
  // Create list of all walls
  const walls: Array<{ cell1: Cell; cell2: Cell }> = [];
  // ... populate walls list ...
  
  // Shuffle walls
  if (seed !== undefined) {
    seedRNG(seed);
  }
  shuffle(walls);
  
  // Union-find data structure
  const parent = new Map<Cell, Cell>();
  
  // Process walls
  for (const wall of walls) {
    if (find(wall.cell1) !== find(wall.cell2)) {
      removeWall(wall.cell1, wall.cell2);
      union(wall.cell1, wall.cell2);
    }
  }
  
  return grid;
}

Error Handling Patterns

Pattern 1: Try-Catch with Fallback

Handle generation errors with fallback maze:

function generateMaze(seed: number): MazeData {
  try {
    // Check for test mode failure injection
    if ((window as any).__TEST_MAZE_FAILURE__) {
      throw new Error('Test mode: Forced maze generation failure');
    }
    
    return generateMazeRecursiveBacktracking(10, 10, seed);
  } catch (error) {
    console.error('Maze generation failed:', error);
    // Create simple fallback maze
    return createFallbackMaze();
  }
}

function createFallbackMaze(): MazeData {
  // Simple straight path from start to exit
  const grid: Cell[][] = [];
  for (let y = 0; y < 10; y++) {
    grid[y] = [];
    for (let x = 0; x < 10; x++) {
      grid[y][x] = {
        x,
        y,
        walls: {
          north: y !== 0,
          south: y !== 9,
          east: x !== 9,
          west: x !== 0,
        },
        visited: false,
      };
    }
  }
  
  // Create straight path
  for (let x = 0; x < 10; x++) {
    grid[0][x].walls.south = false;
    grid[1][x].walls.north = false;
  }
  
  return { grid, start: { x: 0, y: 0 }, exit: { x: 9, y: 1 } };
}

Pattern 2: Retry Logic with Limited Attempts

Retry generation with limited attempts:

function generateMazeWithRetry(
  seed: number,
  maxAttempts: number = 3
): MazeData {
  for (let attempt = 1; attempt <= maxAttempts; attempt++) {
    try {
      return generateMazeRecursiveBacktracking(10, 10, seed + attempt);
    } catch (error) {
      console.warn(`Maze generation attempt ${attempt} failed:`, error);
      
      if (attempt === maxAttempts) {
        console.error('All maze generation attempts failed, using fallback');
        return createFallbackMaze();
      }
    }
  }
  
  // Should never reach here, but TypeScript needs it
  return createFallbackMaze();
}

Pattern 3: Validation Before Return

Validate maze before returning:

function generateMaze(seed: number): MazeData {
  const maze = generateMazeRecursiveBacktracking(10, 10, seed);
  
  // Validate maze
  if (!validateMaze(maze)) {
    console.error('Generated maze failed validation, using fallback');
    return createFallbackMaze();
  }
  
  return maze;
}

function validateMaze(maze: MazeData): boolean {
  // Check if start and exit exist
  if (!maze.start || !maze.exit) {
    return false;
  }
  
  // Check if path exists from start to exit
  if (!pathExists(maze.start, maze.exit, maze.grid)) {
    return false;
  }
  
  return true;
}

Pathfinding Validation Patterns

Pattern 1: BFS Pathfinding

Verify path exists using breadth-first search:

function pathExists(
  start: { x: number; y: number },
  exit: { x: number; y: number },
  grid: Cell[][]
): boolean {
  const queue: Array<{ x: number; y: number }> = [start];
  const visited = new Set<string>();
  visited.add(`${start.x},${start.y}`);

  while (queue.length > 0) {
    const current = queue.shift()!;

    // Check if reached exit
    if (current.x === exit.x && current.y === exit.y) {
      return true;
    }

    // Check all neighbors
    const neighbors = getNeighbors(current, grid);
    for (const neighbor of neighbors) {
      const key = `${neighbor.x},${neighbor.y}`;
      if (!visited.has(key)) {
        visited.add(key);
        queue.push(neighbor);
      }
    }
  }

  return false;
}

function getNeighbors(
  cell: { x: number; y: number },
  grid: Cell[][]
): Array<{ x: number; y: number }> {
  const neighbors: Array<{ x: number; y: number }> = [];
  const { x, y } = cell;
  const cellData = grid[y][x];

  // Check all four directions
  if (!cellData.walls.north && y > 0) {
    neighbors.push({ x, y: y - 1 });
  }
  if (!cellData.walls.south && y < grid.length - 1) {
    neighbors.push({ x, y: y + 1 });
  }
  if (!cellData.walls.east && x < grid[0].length - 1) {
    neighbors.push({ x: x + 1, y });
  }
  if (!cellData.walls.west && x > 0) {
    neighbors.push({ x: x - 1, y });
  }

  return neighbors;
}

Pattern 2: A* Pathfinding

More efficient pathfinding for larger mazes:

function findPathAStar(
  start: { x: number; y: number },
  exit: { x: number; y: number },
  grid: Cell[][]
): Array<{ x: number; y: number }> | null {
  // A* implementation
  // ... (standard A* algorithm) ...
  return path;
}

Test Patterns for Maze Generation

Test 1: Deterministic Generation

Verify same seed produces same maze:

describe('Maze Generation', () => {
  it('generates same maze with same seed', () => {
    const seed = 42;
    const maze1 = generateMaze(seed);
    const maze2 = generateMaze(seed);
    expect(maze1).toEqual(maze2);
  });
});

Test 2: Path Validation

Verify path exists from start to exit:

it('generates maze with valid path', () => {
  const maze = generateMaze(42);
  const pathExists = pathExists(maze.start, maze.exit, maze.grid);
  expect(pathExists).toBe(true);
});

Test 3: Error Handling

Verify error handling works:

it('handles generation errors with fallback', () => {
  (window as any).__TEST_MAZE_FAILURE__ = true;
  const maze = generateMaze(42);
  expect(maze).toBeDefined();
  expect(maze.grid).toBeDefined();
  (window as any).__TEST_MAZE_FAILURE__ = false;
});

Test 4: Retry Logic

Verify retry logic works:

it('retries generation on failure', () => {
  let attemptCount = 0;
  const originalGenerate = generateMazeRecursiveBacktracking;
  
  // Mock to fail first two attempts
  generateMazeRecursiveBacktracking = jest.fn(() => {
    attemptCount++;
    if (attemptCount < 3) {
      throw new Error('Generation failed');
    }
    return originalGenerate(10, 10, 42);
  });
  
  const maze = generateMazeWithRetry(42, 3);
  expect(maze).toBeDefined();
  expect(attemptCount).toBe(3);
});

Best Practices

1. Use seeded RNG: Deterministic generation for testing
2. Handle errors gracefully: Fallback maze if generation fails
3. Validate mazes: Verify path exists before using
4. Retry with limits: Don't retry forever
5. Test thoroughly: Test generation, validation, error handling

Resources

• rng-seeding-patterns skill - RNG seed management
• phaser-game-testing skill - Testing patterns