

 This page uses content from Wikipedia. The original article was at Maze generation algorithm. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)




Task

Generate and show a maze, using the simple Depth-first search algorithm.

Start at a random cell.
Mark the current cell as visited, and get a list of its neighbors. For each neighbor, starting with a randomly selected neighbor:
If that neighbor hasn't been visited, remove the wall between this cell and that neighbor, and then recurse with that neighbor as the current cell.


 Related tasks
 Maze solving.


<?php
class Maze 
{
    protected $width;
    protected $height;
    protected $grid;
    protected $path;
    protected $horWalls;
    protected $vertWalls;
    protected $dirs;
    protected $isDebug;
 
    public function __construct($x, $y, $debug = false)
    {
        $this->width = $x;
        $this->height = $y;
        $this->path = [];        
        $this->dirs = [ [0, -1], [0, 1], [-1, 0], [1, 0]]; // array of coordinates of N,S,W,E
        $this->horWalls = []; // list of removed horizontal walls (---+)        
        $this->vertWalls = [];// list of removed vertical walls (|)        
        $this->isDebug = $debug; // debug flag
 
        // generate the maze:
        $this->generate();
    }
 
    protected function generate()
    {        
        $this->initMaze(); // init the stack and an unvisited grid
        // start from a random cell and then proceed recursively
        $this->walk(mt_rand(0, $this->width-1), mt_rand(0, $this->height-1));
    }
 
    /**
    * Actually prints the Maze, on stdOut. Put in a separate method to allow extensibility
    * For simplicity sake doors are positioned on the north wall and east wall
    */
    public function printOut()
    {
        $this->log("Horizontal walls: %s", json_encode($this->horWalls));
        $this->log("Vertical walls: %s", json_encode($this->vertWalls));        
 
        $northDoor = mt_rand(0,$this->width-1);
        $eastDoor = mt_rand(0, $this->height-1);
 
        $str = '+';
        for ($i=0;$i<$this->width;$i++) {
            $str .= ($northDoor == $i) ? '   +' : '---+';
        }
        $str .= PHP_EOL;
        for ($i=0; $i<$this->height; $i++) {
 
            for ($j=0; $j<$this->width; $j++) {
                $str .= (!empty($this->vertWalls[$j][$i]) ? $this->vertWalls[$j][$i] : '|   ');
            }
            $str .= ($i == $eastDoor ? '  ' : '|').PHP_EOL.'+';
            for ($j=0; $j<$this->width; $j++) {
                $str .= (!empty($this->horWalls[$j][$i]) ? $this->horWalls[$j][$i] : '---+');
            }
            $str .= PHP_EOL;
        }
        echo $str;
    }
 
    /**
    * Logs to stdOut if debug flag is enabled
    */
    protected function log(...$params)
    {
        if ($this->isDebug) {
            echo vsprintf(array_shift($params), $params).PHP_EOL;
        }
    }
 
    private function walk($x, $y)
    {
        $this->log('Entering cell %d,%d', $x, $y);
        // mark current cell as visited     
        $this->grid[$x][$y] = true; 
        // add cell to path
        $this->path[] = [$x, $y];
        // get list of all neighbors
        $neighbors = $this->getNeighbors($x, $y);       
        $this->log("Valid neighbors: %s", json_encode($neighbors));
 
        if(empty($neighbors)) {
            // Dead end, we need now to backtrack, if there's still any cell left to be visited
            $this->log("Start backtracking along path: %s", json_encode($this->path));
            array_pop($this->path);
            if (!empty($this->path)) {
                $next = array_pop($this->path);
                return $this->walk($next[0], $next[1]);
            }
        } else {            
            // randomize neighbors, as per request
            shuffle($neighbors);
 
            foreach ($neighbors as $n) {
                $nextX = $n[0];
                $nextY = $n[1];
                if ($nextX == $x) {
                    $wallY = max($nextY, $y);
                    $this->log("New cell is on the same column (%d,%d), removing %d, (%d-1) horizontal wall", $nextX, $nextY, $x, $wallY);
                    $this->horWalls[$x][min($nextY, $y)] = "   +";
                }
                if ($nextY == $y) {
                    $wallX = max($nextX, $x);
                    $this->log("New cell is on the same row (%d,%d), removing %d,%d vertical wall", $nextX, $nextY, $wallX, $y);
                    $this->vertWalls[$wallX][$y] = "    ";              
                }
                return $this->walk($nextX, $nextY);
            }
        }
    }
 
    /**
    * Initialize an empty grid of $width * $height dimensions
    */
    private function initMaze()
    {
        for ($i=0;$i<$this->width;$i++) {
            for ($j = 0;$j<$this->height;$j++) {
                $this->grid[$i][$j] = false;
            }
        }
    }
 
    /**
    * @param int $x
    * @param int $y
    * @return array
    */
    private function getNeighbors($x, $y) 
    {       
        $neighbors = [];
        foreach ($this->dirs as $dir) {
            $nextX = $dir[0] + $x;
            $nextY = $dir[1] + $y;
            if (($nextX >= 0 && $nextX < $this->width && $nextY >= 0 && $nextY < $this->height) && !$this->grid[$nextX][$nextY]) {
                $neighbors[] = [$nextX, $nextY];
            }
        }
        return $neighbors;
    }
}
 
$maze = new Maze(10,10);
$maze->printOut();