<?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]]; 
        $this->horWalls = []; 
        $this->vertWalls = [];
        $this->isDebug = $debug; 

        
        $this->generate();
    }

    protected function generate()
    {        
        $this->initMaze(); 
        
        $this->walk(mt_rand(0, $this->width-1), mt_rand(0, $this->height-1));
    }

    
    public function printOut()
    {
        $this->log(, json_encode($this->horWalls));
        $this->log(, 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;
    }

    
    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);
        
        $this->grid[$x][$y] = true; 
        
        $this->path[] = [$x, $y];
        
        $neighbors = $this->getNeighbors($x, $y);       
        $this->log(, json_encode($neighbors));

        if(empty($neighbors)) {
            
            $this->log(, 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 {            
            
            shuffle($neighbors);

            foreach ($neighbors as $n) {
                $nextX = $n[0];
                $nextY = $n[1];
                if ($nextX == $x) {
                    $wallY = max($nextY, $y);
                    $this->log(, $nextX, $nextY, $x, $wallY);
                    $this->horWalls[$x][min($nextY, $y)] = ;
                }
                if ($nextY == $y) {
                    $wallX = max($nextX, $x);
                    $this->log(, $nextX, $nextY, $wallX, $y);
                    $this->vertWalls[$wallX][$y] = ;              
                }
                return $this->walk($nextX, $nextY);
            }
        }
    }

    
    private function initMaze()
    {
        for ($i=0;$i<$this->width;$i++) {
            for ($j = 0;$j<$this->height;$j++) {
                $this->grid[$i][$j] = false;
            }
        }
    }

    
    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();