Maze Rats Part Three: PHP Maze Solving Algorithms

Maze Rats Part Three concludes Oscar Merida’s maze-solving trilogy with the complete dead-end filling algorithm. This installment focuses on optimization, edge cases, and integration with maze generation.

The dead-end filling approach is elegant in its simplicity. A dead end is a cell with exactly three walls and one passage. Because it leads nowhere, you fill it in and move to the adjacent cell. Repeat until every dead end is filled. The remaining cells form the solution path.

What You’ll Learn

Full implementation of dead-end filling solver
Optimizing the solver for large mazes
Handling edge cases and special maze configurations
Integrating solving with generation and rendering
Visualizing the solution path on the maze image
Performance analysis of solving algorithms
Extending the solver for different maze types

The Complete Solver

The full solver combines cell representation, dead-end detection, and recursive filling.

<?php
 
declare(strict_types=1);
 
namespace OMerida\Maze;
 
class Solver
{
    private const int WEST = 0x1;
    private const int EAST = 0x2;
    private const int SOUTH = 0x4;
    private const int NORTH = 0x8;
    private const int CLOSED = 15;
 
    private const array FILL = [
        self::WEST => [
            'opposite' => self::EAST,
            'xOffset' => -1,
            'yOffset' => 0,
        ],
        self::EAST => [
            'opposite' => self::WEST,
            'xOffset' => 1,
            'yOffset' => 0,
        ],
        self::NORTH => [
            'opposite' => self::SOUTH,
            'xOffset' => 0,
            'yOffset' => -1,
        ],
        self::SOUTH => [
            'opposite' => self::NORTH,
            'xOffset' => 0,
            'yOffset' => 1,
        ],
    ];
 
    public function __construct(
        private array $cells,
    ) {}
 
    public function getCells(): array
    {
        return $this->cells;
    }
 
    private function isDeadEnd(int $cell): bool
    {
        return in_array($cell, [0x7, 0xB, 0xD, 0xE], true);
    }
 
    public function findDeadEnd(): array|false
    {
        foreach ($this->cells as $y => $row) {
            foreach ($row as $x => $cell) {
                if ($this->isDeadEnd($cell)) {
                    return [$x, $y];
                }
            }
        }
        return false;
    }
 
    public function fillDeadEnd(int $x, int $y): void
    {
        $current = $this->cells[$y][$x];
        $this->cells[$y][$x] = self::CLOSED;
 
        if (0 === ($current & self::SOUTH)) {
            $fill = self::FILL[self::SOUTH];
        } elseif (0 === ($current & self::NORTH)) {
            $fill = self::FILL[self::NORTH];
        } elseif (0 === ($current & self::EAST)) {
            $fill = self::FILL[self::EAST];
        } else {
            $fill = self::FILL[self::WEST];
        }
 
        $newX = $x + $fill['xOffset'];
        $newY = $y + $fill['yOffset'];
 
        if ($this->inBounds($newX, $newY)) {
            $this->cells[$newY][$newX] += $fill['opposite'];
 
            if ($this->isDeadEnd($this->cells[$newY][$newX])) {
                $this->fillDeadEnd($newX, $newY);
            }
        }
    }
 
    private function inBounds(int $x, int $y): bool
    {
        return $x >= 0 && $y >= 0
            && $y < count($this->cells)
            && $x < count($this->cells[0]);
    }
 
    public function solve(): void
    {
        while (($deadEnd = $this->findDeadEnd()) !== false) {
            [$x, $y] = $deadEnd;
            $this->fillDeadEnd($x, $y);
        }
    }
}

Integration with Maze Generation

The solver works with any maze as long as cells use the same bitwise encoding. Here is a Recursive Backtracking generator that produces solvable mazes.

<?php
 
declare(strict_types=1);
 
class MazeGenerator
{
    private const int WEST = 0x1;
    private const int EAST = 0x2;
    private const int SOUTH = 0x4;
    private const int NORTH = 0x8;
    private const int CLOSED = 15;
 
    public function generate(int $rows, int $cols): array
    {
        $cells = array_fill(
            0,
            $rows,
            array_fill(0, $cols, self::CLOSED)
        );
 
        $this->carve($cells, 0, 0, $rows, $cols);
 
        return $cells;
    }
 
    private function carve(
        array &$cells,
        int $row,
        int $col,
        int $maxRows,
        int $maxCols,
    ): void {
        $directions = [
            [self::NORTH, self::SOUTH, -1, 0],
            [self::SOUTH, self::NORTH, 1, 0],
            [self::WEST, self::EAST, 0, -1],
            [self::EAST, self::WEST, 0, 1],
        ];
 
        shuffle($directions);
 
        foreach ($directions as [$wall, $opening, $dr, $dc]) {
            $newRow = $row + $dr;
            $newCol = $col + $dc;
 
            if ($newRow < 0 || $newRow >= $maxRows
                || $newCol < 0 || $newCol >= $maxCols
            ) {
                continue;
            }
 
            if ($cells[$newRow][$newCol] !== self::CLOSED) {
                continue;
            }
 
            $cells[$row][$col] &= ~$wall;
            $cells[$newRow][$newCol] &= ~$opening;
 
            $this->carve(
                $cells,
                $newRow,
                $newCol,
                $maxRows,
                $maxCols,
            );
        }
    }
}

Visualizing the Solved Maze

Highlight the solution path in a different color. After solving, trace the path from the entrance to the exit.

<?php
 
declare(strict_types=1);
 
class SolvedMazeRenderer extends MazeRenderer
{
    private int $solutionColor;
 
    public function renderWithSolution(
        array $cells,
        array $solutionPath,
        string $outputPath,
    ): void {
        parent::render($cells, $outputPath);
 
        // Overlay solution path
        $this->solutionColor = imagecolorallocate(
            $this->image,
            0xFF,
            0x00,
            0x00, // Red solution path
        );
 
        $padding = (int) ceil($this->cellSize * 0.6);
        $half = (int) ($this->cellSize / 2);
 
        for ($i = 0; $i < count($solutionPath) - 1; $i++) {
            [$x1, $y1] = $solutionPath[$i];
            [$x2, $y2] = $solutionPath[$i + 1];
 
            imagesetthickness($this->image, 4);
            imageline(
                $this->image,
                $x1 * $this->cellSize + $padding + $half,
                $y1 * $this->cellSize + $padding + $half,
                $x2 * $this->cellSize + $padding + $half,
                $y2 * $this->cellSize + $padding + $half,
                $this->solutionColor,
            );
        }
 
        imagepng($this->image, $outputPath);
    }
}

Handling Edge Cases in the Solver

Before solving, validate that the maze array is well-formed. Check that all rows have the same length and that each cell value is within the valid range of 0 to 15.

<?php
 
declare(strict_types=1);
 
class Solver
{
    public function validateMaze(): void
    {
        if (empty($this->cells)) {
            throw new \InvalidArgumentException('Maze cannot be empty');
        }
 
        $rowCount = count($this->cells[0]);
 
        foreach ($this->cells as $y => $row) {
            if (count($row) !== $rowCount) {
                throw new \InvalidArgumentException(
                    "Row {$y} has inconsistent column count"
                );
            }
 
            foreach ($row as $x => $cell) {
                if ($cell < 0 || $cell > 15) {
                    throw new \InvalidArgumentException(
                        "Invalid cell value at ({$x}, {$y}): {$cell}"
                    );
                }
            }
        }
    }
}

Call validateMaze() at the start of solve() to fail fast with a clear error message.

Path Tracing After Solving

After dead-end filling, trace the remaining path from start to exit.

<?php
 
declare(strict_types=1);
 
class PathTracer
{
    public function __construct(
        private array $cells,
    ) {}
 
    public function trace(int $startX, int $startY, int $endX, int $endY): array
    {
        $path = [];
        $visited = [];
        $current = [$startX, $startY];
 
        while ($current !== [$endX, $endY]) {
            $path[] = $current;
            $visited[$current[1]][$current[0]] = true;
 
            [$x, $y] = $current;
            $cell = $this->cells[$y][$x];
            $next = null;
 
            // Check each direction for an open passage
            if (!($cell & Solver::NORTH) && !($visited[$y - 1][$x] ?? false)) {
                $next = [$x, $y - 1];
            } elseif (!($cell & Solver::SOUTH) && !($visited[$y + 1][$x] ?? false)) {
                $next = [$x, $y + 1];
            } elseif (!($cell & Solver::WEST) && !($visited[$y][$x - 1] ?? false)) {
                $next = [$x - 1, $y];
            } elseif (!($cell & Solver::EAST) && !($visited[$y][$x + 1] ?? false)) {
                $next = [$x + 1, $y];
            }
 
            if ($next === null) {
                // Backtrack - should not happen in a solved maze
                break;
            }
 
            $current = $next;
        }
 
        $path[] = [$endX, $endY];
        return $path;
    }
}

Performance Analysis

Dead-end filling is efficient for most mazes. The algorithm visits each cell at most once, giving O(n) time complexity where n is the number of cells.

For a 40x60 maze (2,400 cells), the solver typically completes in under 10 milliseconds in PHP 8.2. The recursive filling may hit PHP’s recursion limit for pathological cases, but most reasonably generated mazes stay within limits.

<?php
 
$rows = 40;
$cols = 60;
 
$generator = new MazeGenerator();
$cells = $generator->generate($rows, $cols);
 
$solver = new Solver($cells);
 
$start = microtime(true);
$solver->solve();
$elapsed = (microtime(true) - $start) * 1000;
 
echo "Solved {$rows}x{$cols} maze in {$elapsed} ms" . PHP_EOL;
 
$tracer = new PathTracer($solver->getCells());
$path = $tracer->trace(0, 0, $rows - 1, $cols - 1);
echo "Solution path length: " . count($path) . " steps" . PHP_EOL;

Real-World Use Cases

Procedural Content Generation

Generate dungeons, levels, and maps for games. The solver validates that generated content has a valid solution.

Path Planning Algorithms

Adapt dead-end filling for robotic path planning in grid-based environments where the robot must map and navigate unknown spaces.

Network Deadlock Detection

The same principle applies to detecting deadlocks in network routing or resource allocation. Dead ends represent unrecoverable states.

Puzzle Validation

Ensure puzzles have exactly one solution by running the solver and verifying the result.

Best Practices

Separate generation from solving - Keep MazeGenerator and Solver as independent classes. They communicate through the cell array.
Use strict type checking - in_array(..., true) prevents type coercion issues with integer comparisons.
Document bit mask values - Constants like 0x7 and 0xB are magic numbers. Document which wall is missing for each.
Test with known mazes - Create tiny mazes (3x3) with known solutions to validate your solver.
Consider iterative approaches - For very large mazes, convert the recursive fill to an explicit stack to avoid recursion limits.

Common Mistakes to Avoid

Incorrect bounds checking - Off-by-one errors in bounds checks crash on edge cells.
Modifying cells during iteration - Filling a dead end changes neighbor cells. Ensure the next iteration uses updated values.
Forgetting visited tracking - Path tracing without visited tracking enters infinite loops.
Assuming single solution - Some maze generation algorithms create loops. Dead-end filling removes only trivial dead ends.
Mixing row/col order - Be consistent. PHP arrays are $array[row][col], which maps to $array[$y][$x].

Frequently Asked Questions

Does dead-end filling work on mazes with loops?

It removes dead ends but leaves loops intact. For mazes with multiple paths, the remaining cells after filling include all possible paths.

How does this compare to A* or Dijkstra?

A* finds the shortest path. Dead-end filling finds the only path (in a simply connected maze). Both are valid for different use cases.

Can I use this solver for 3D mazes?

The bitwise encoding extends to 3D by adding UP and DOWN bits. The same filling algorithm works with additional directional checks.

Why use bitwise encoding instead of arrays of booleans?

Bitwise operations are faster and use less memory. A single integer stores four wall states. Boolean arrays require four times the memory.

How do I handle the maze entrance and exit?

Mark the entrance by opening the north wall of the first cell and the exit by opening the south wall of the last cell.

Can I solve mazes from images?

Yes. Load the maze image, detect wall pixels to build the cell array, solve, and overlay the solution on the image.

What maze sizes are practical in PHP?

Up to 500x500 (250,000 cells) works in PHP with reasonable memory and time. Larger mazes benefit from the iterative algorithm.

Conclusion

Maze Rats Part Three completes the trilogy with a production-ready dead-end filling solver. The algorithm is simple, fast, and broadly applicable beyond puzzle solving.

The techniques you have learned throughout this series bitwise encoding, recursive traversal, grid rendering, and algorithmic problem solving transfer directly to game development, pathfinding, and spatial reasoning applications in PHP.

Experiment with different maze generation algorithms. Try Prim’s or Wilson’s algorithm. Compare solution paths. Each variation deepens your understanding of algorithmic thinking and PHP’s capabilities for computational problem solving.