| 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[][] {
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,
};
}
}
if (seed !== undefined) {
seedRNG(seed);
}
const stack: Cell[] = [];
let current = grid[0][0];
current.visited = true;
stack.push(current);
while (stack.length > 0) {
const neighbors = getUnvisitedNeighbors(current, grid);
if (neighbors.length > 0) {
const next = neighbors[Math.floor(seededRandom() * neighbors.length)];
removeWall(current, next);
next.visited = true;
stack.push(next);
current = next;
} else {
current = stack.pop()!;
}
}
return grid;
}
function getUnvisitedNeighbors(cell: Cell, grid: Cell[][]): Cell[] {
const neighbors: Cell[] = [];
const { x, y } = cell;
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) {
current.walls.east = false;
next.walls.west = false;
} else if (dx === -1) {
current.walls.west = false;
next.walls.east = false;
} else if (dy === 1) {
current.walls.south = false;
next.walls.north = false;
} else if (dy === -1) {
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[][] {
const grid: Cell[][] = initializeGrid(width, height);
const walls: Array<{ cell1: Cell; cell2: Cell }> = [];
if (seed !== undefined) {
seedRNG(seed);
}
shuffle(walls);
const parent = new Map<Cell, Cell>();
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 {
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);
return createFallbackMaze();
}
}
function createFallbackMaze(): MazeData {
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,
};
}
}
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();
}
}
}
return createFallbackMaze();
}
Pattern 3: Validation Before Return
Validate maze before returning:
function generateMaze(seed: number): MazeData {
const maze = generateMazeRecursiveBacktracking(10, 10, seed);
if (!validateMaze(maze)) {
console.error('Generated maze failed validation, using fallback');
return createFallbackMaze();
}
return maze;
}
function validateMaze(maze: MazeData): boolean {
if (!maze.start || !maze.exit) {
return false;
}
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()!;
if (current.x === exit.x && current.y === exit.y) {
return true;
}
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];
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 {
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;
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
- Use seeded RNG: Deterministic generation for testing
- Handle errors gracefully: Fallback maze if generation fails
- Validate mazes: Verify path exists before using
- Retry with limits: Don't retry forever
- Test thoroughly: Test generation, validation, error handling
Resources
rng-seeding-patterns skill - RNG seed management
phaser-game-testing skill - Testing patterns