Detailed explanation of PHP maze generation and automatic pathfinding algorithm-PHP Tutorial-php.cn

Detailed explanation of PHP maze generation and automatic pathfinding algorithm

*文

Release： 2023-03-18 12:44:01

Original

2660 people have browsed it

How to use PHP to generate a maze and find a path to solve it? This article mainly introduces PHP's maze generation and automatic pathfinding algorithms, and provides a detailed explanation of PHP's maze generation and automatic pathfinding algorithms. I hope to be helpful.

The example in this article describes the deep calendar generation maze of PHP tree and the A* automatic pathfinding algorithm. Share it with everyone for your reference. The specific analysis is as follows:

A colleague recommended Sansi’s maze algorithm. After reading it, I thought it was pretty good, so I converted it to php
Sansi’s maze algorithm uses the principle of tree depth traversal, so the maze generated in this way is quite good. Thin, and there are relatively few dead ends!
There is only one path between any two points.

As for the A* pathfinding algorithm, it is the most popular fully automatic pathfinding algorithm

Without further ado, here’s the code

Maze generation class:

class Maze{
    // Maze Create
    private $_w;
    private $_h;
    private $_grids;
    private $_walkHistory;
    private $_walkHistory2;
    private $_targetSteps;
    // Construct
    public function Maze() {
        $this->_w = 6;
        $this->_h = 6;
        $this->_grids = array();
    }
    // 设置迷宫大小
    public function set($width = 6, $height = 6) {
        if ( $width > 0 ) $this->_w = $width;
        if ( $height > 0 ) $this->_h = $height;
        return $this;
    }
    // 取到迷宫
    public function get() {
        return $this->_grids;
    }
    // 生成迷宫
    public function create() {
        $this->_init();
        return $this->_walk(rand(0, count($this->_grids) -1 ));
    }
    // 获取死胡同点
    public function block($n = 0, $rand = false) {
        $l = count($this->_grids);
        for( $i = 1; $i < $l; $i++ ) {
            $v = $this->_grids[$i];
            if ( $v == 1 || $v == 2 || $v == 4 || $v == 8 ) {
                $return[] = $i;
            }
        }
        // 随机取点
        if ( $rand ) shuffle($return);
 
        if ( $n == 0 ) return $return;
 
        if ( $n == 1 ) {
            return array_pop($return);
        } else {
            return array_slice($return, 0, $n);
        }
    }
    /**
    |---------------------------------------------------------------
    | 生成迷宫的系列函数
    |---------------------------------------------------------------
    */
    private function _walk($startPos) {
        $this->_walkHistory = array();
        $this->_walkHistory2 = array();
        $curPos = $startPos;
        while ($this->_getNext0() != -1) {
            $curPos = $this->_step($curPos);
            if ( $curPos === false ) break;
        }
        return $this;
    }
    private function _getTargetSteps($curPos) {
        $p = 0;
        $a = array();
        $p = $curPos - $this->_w;
        if ($p > 0 && $this->_grids[$p] === 0 && ! $this->_isRepeating($p)) {
            array_push($a, $p);
        } else {
            array_push($a, -1);
        }
        $p = $curPos + 1;
        if ($p % $this->_w != 0 && $this->_grids[$p] === 0 && ! $this->_isRepeating($p)) {
            array_push($a, $p);
        } else {
            array_push($a, -1);
        }
        $p = $curPos + $this->_w;
        if ($p < count($this->_grids) && $this->_grids[$p] === 0 && ! $this->_isRepeating($p)) {
            array_push($a, $p);
        } else {
            array_push($a, -1);
        }
        $p = $curPos - 1;
        if (($curPos % $this->_w) != 0 && $this->_grids[$p] === 0 && ! $this->_isRepeating($p)) {
            array_push($a, $p);
        } else {
            array_push($a, -1);
        }
        return $a;
    }
    private function _noStep() {
        $l = count($this->_targetSteps);
        for ($i = 0; $i < $l; $i ++) {
            if ($this->_targetSteps[$i] != -1) return false;
        }
        return true;
    }
    private function _step($curPos) {
        $this->_targetSteps = $this->_getTargetSteps($curPos);
        if ( $this->_noStep() ) {
            if ( count($this->_walkHistory) > 0 ) {
                $tmp = array_pop($this->_walkHistory);
            } else {
                return false;
            }
            array_push($this->_walkHistory2, $tmp);
            return $this->_step($tmp);
        }
        $r = rand(0, 3);
        while ( $this->_targetSteps[$r] == -1) {
            $r = rand(0, 3);
        }
        $nextPos = $this->_targetSteps[$r];
        $isCross = false;
        if ( $this->_grids[$nextPos] != 0)
            $isCross = true;
        if ($r == 0) {
            $this->_grids[$curPos] ^= 1;
            $this->_grids[$nextPos] ^= 4;
        } elseif ($r == 1) {
            $this->_grids[$curPos] ^= 2;
            $this->_grids[$nextPos] ^= 8;
        } elseif ($r == 2) {
            $this->_grids[$curPos] ^= 4;
            $this->_grids[$nextPos] ^= 1;
        } elseif ($r == 3) {
            $this->_grids[$curPos] ^= 8;
            $this->_grids[$nextPos] ^= 2;
        }
        array_push($this->_walkHistory, $curPos);
        return $isCross ? false : $nextPos;
    }
    private function _isRepeating($p) {
        $l = count($this->_walkHistory);
        for ($i = 0; $i < $l; $i ++) {
            if ($this->_walkHistory[$i] == $p) return true;
        }
        $l = count($this->_walkHistory2);
        for ($i = 0; $i < $l; $i ++) {
            if ($this->_walkHistory2[$i] == $p) return true;
        }
        return false;
    }
    private function _getNext0() {
        $l = count($this->_grids);
 
        for ($i = 0; $i <= $l; $i++ ) {
            if ( $this->_grids[$i] == 0) return $i;
        }
        return -1;
    }
    private function _init() {
        $this->_grids = array();
        for ($y = 0; $y < $this->_h; $y ++) {
            for ($x = 0; $x < $this->_w; $x ++) {
                array_push($this->_grids, 0);
            }
        }
        return $this;
    }
}

Copy after login

A*Pathfinding algorithm

class AStar{
    // A-star
    private $_open;
    private $_closed;
    private $_start;
    private $_end;
    private $_grids;
    private $_w;
    private $_h;
    // Construct
    public function AStar(){
        $this->_w = null;
        $this->_h = null;
        $this->_grids = null;
    }
    public function set($width, $height, $grids) {
        $this->_w = $width;
        $this->_h = $height;
        $this->_grids = $grids;
        return $this;
    }
    // 迷宫中寻路
    public function search($start = false, $end = false) {
        return $this->_search($start, $end);
    }
    /**
    |---------------------------------------------------------------
    | 自动寻路 - A-star 算法
    |---------------------------------------------------------------
    */
    public function _search($start = false, $end = false) {
        if ( $start !== false ) $this->_start = $start;
        if ( $end !== false ) $this->_end = $end;
        $_sh = $this->_getH($start);
        $point[&#39;i&#39;] = $start;
        $point[&#39;f&#39;] = $_sh;
        $point[&#39;g&#39;] = 0;
        $point[&#39;h&#39;] = $_sh;
        $point[&#39;p&#39;] = null;
        $this->_open[] = $point;
        $this->_closed[$start] = $point;
        while ( 0 < count($this->_open) ) {
            $minf = false;
            foreach( $this->_open as $key => $maxNode ) {
                if ( $minf === false || $minf > $maxNode[&#39;f&#39;] ) {
                    $minIndex = $key;
                }
            }
            $nowNode = $this->_open[$minIndex];
            unset($this->_open[$minIndex]);
            if ( $nowNode[&#39;i&#39;] == $this->_end ) {
                $tp = array();
                while( $nowNode[&#39;p&#39;] !== null ) {
                    array_unshift($tp, $nowNode[&#39;p&#39;]);
                    $nowNode = $this->_closed[$nowNode[&#39;p&#39;]];
                }
                array_push($tp, $this->_end);
                break;
            }
            $this->_setPoint($nowNode[&#39;i&#39;]);
        }
        $this->_closed = array();
        $this->_open = array();
        return $tp;
    }
    private function _setPoint($me) {
        $point = $this->_grids[$me];
        // 所有可选方向入队列
        if ( $point & 1 ) {
            $next = $me - $this->_w;
            $this->_checkPoint($me, $next);
        }
        if ( $point & 2 ) {
            $next = $me + 1;
            $this->_checkPoint($me, $next);
        }
        if ( $point & 4 ) {
            $next = $me + $this->_w;
            $this->_checkPoint($me, $next);
        }
        if ( $point & 8 ) {
            $next = $me - 1;
            $this->_checkPoint($me, $next);
        }
    }
    private function _checkPoint($pNode, $next) {
        if ( $this->_closed[$next] ) {
            $_g = $this->_closed[$pNode][&#39;g&#39;] + $this->_getG($next);
            if ( $_g < $check[&#39;g&#39;] ) {
                $this->_closed[$next][&#39;g&#39;] = $_g;
                $this->_closed[$next][&#39;f&#39;] = $this->_closed[$next][&#39;g&#39;] + $this->_closed[$next][&#39;h&#39;];
                $this->_closed[$next][&#39;p&#39;] = $pNode;
            }
        } else {
            $point[&#39;p&#39;] = $pNode;
            $point[&#39;h&#39;] = $this->_getH($next);
            $point[&#39;g&#39;] = $this->_getG($next);
            $point[&#39;f&#39;] = $point[&#39;h&#39;] + $point[&#39;g&#39;];
            $point[&#39;i&#39;] = $next;
            $this->_open[] = $point;
            $this->_closed[$next] = $point;
        }
    }
    private function _getG($point) {
        return abs($this->_start - $point);
    }
    private function _getH($point) {
        return abs($this->_end - $point);
    }
}

Copy after login

Related recommendations:

PHP common sorting algorithm learning

Summary of PHP traversal algorithm

How PHP implements the binary search algorithm

The above is the detailed content of Detailed explanation of PHP maze generation and automatic pathfinding algorithm. For more information, please follow other related articles on the PHP Chinese website!