Maze problem | Maze algorithm | Backtracking | Recursive | مسئله ماز | مسئله هزارتو | بازگشتی | مسئله مارپیچ |بک ترک

maze_recursive.php

<?php
/**
  * @author Arman Hosseini <namra.1377@gmail.com>
  */
?>
<style type="text/css">
    * {
        margin: 0;
        padding: 0;
    }
    body {
        background: white;
        text-align: center;
        margin: 10px;
    }
    li {
        display: inline-block;
        margin-right: 10px;
        width: 30px;
        height: 30px;
    }
    ul {
        margin-bottom: 5px;
    }
    .yellowPoint {
        background-color: #ffe120;
    }
    .bluePoint {
        background-color: #2879ff;
    }
    .greenPoint {
        background-color: #44ff9e;
    }
</style>
<?php

class Maze
{
    const OPEN = 0;
    const WALL = 1;
    const WALK = 2;
    const BACKTRACK = 3;

    private $map = [];
    private $end = false;

    public function __construct($map)
    {
        $this->map = $map;
    }

    public function draw()
    {
        foreach ($this->map as $rowNumber => &$row) {
            echo "<ul>";
            foreach ($row as $colNumber => &$colValue) {
                printf("<li class='%s'></li>", ($class = $this->getStepCSSClass($colValue)));
            }
            echo "</ul>";
        }

        return $this;
    }

    public function getStepCSSClass($point)
    {
        switch ($point) {
            case self::OPEN: case self::BACKTRACK:
                return 'bluePoint';
                break;
            case self::WALL:
                return 'yellowPoint';
                break;
            case self::WALK:
                return 'greenPoint';
                break;
        }

        return;
    }

    public function getEndRow()
    {
        return count($this->map) - 1;
    }

    public function getEndCol()
    {
        return count($this->map[$this->getEndRow()]) - 1;
    }

    public function solve($row = 0, $col = 0)
    {
        $this->walk($row, $col);

        if (($row === $this->getEndRow() && $col === $this->getEndCol()))
            $this->end = true;
        else {
            if ($this->canMoveTo($row + 1, $col)) {
                $this->solve($row + 1, $col);
            }
            if ($this->canMoveTo($row, $col + 1)) {
                $this->solve($row, $col + 1);
            }
            if ($this->canMoveTo($row - 1, $col)) {
                $this->solve($row - 1, $col);
            }
            if ($this->canMoveTo($row, $col - 1)) {
                $this->solve($row, $col - 1);
            }

            $this->backtrack($row, $col);
        }

        return;
    }

    public function walk($row, $col)
    {
        if ( !$this->end )
            $this->map[$row][$col] = self::WALK;
    }

    public function canMoveTo($row, $col)
    {
        if ( $this->end ) {
            return false;
        }

        $nextPosition = @$this->map[$row][$col];

        if ( null === $nextPosition || in_array($nextPosition, [self::WALL, self::WALK, self::BACKTRACK]) )
            return false;

        return true;
    }

    public function backtrack($row, $col)
    {
        if ( $this->end ) {
            return;
        }

        $this->map[$row][$col] = self::BACKTRACK;
    }
}


$map = [
    [0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],
    [0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0],
    [0,1,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,1,0],
    [0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0],
    [0,0,0,1,0,0,1,0,1,1,0,1,0,0,0,0,0,1,0,1],
    [1,1,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0],
    [0,0,1,0,0,1,0,1,1,1,1,0,0,0,0,0,1,0,0,0],
    [0,0,0,0,0,0,0,0,0,1,0,1,0,1,1,0,0,0,0,1],
    [0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0],
    [1,1,1,0,1,1,0,0,1,0,0,1,0,0,0,0,0,0,1,1],
    [1,0,0,1,0,0,1,1,0,1,1,0,1,0,0,1,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0],
    [0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,1,1,0,0,0],
    [0,1,1,1,0,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0],
    [1,1,1,1,1,1,0,1,1,0,1,0,1,1,0,1,0,0,0,0],
];
$maze = new Maze($map);
$maze->solve();
$maze->draw();