PHP tree deep calendar generation maze and A* automatic pathfinding algorithm example analysis, maze example analysis

Example analysis of deep chronological maze generation of PHP trees and A* automatic pathfinding algorithm, maze example analysis

This article describes the deep chronological generation of mazes and A* of PHP trees through examples *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. The maze generated in this way is quite thin, and the number of dead ends is relatively small!
There is only one path between any two points.

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

No further nonsense, just paste the code

Maze generation class:
Copy code The code is as follows: 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();
}
//Set the maze size
Public function set($width = 6, $height = 6) {
If ( $width > 0 ) $this->_w = $width;
If ( $height > 0 ) $this->_h = $height;
         return $this;
}
// Get the maze
Public function get() {
          return $this->_grids;
}
// Generate maze
Public function create() {
           $this->_init();
            return $this->_walk(rand(0, count($this->_grids) -1 ));
}
// Get the dead end point
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;
            }
}
            // Randomly pick points
            if ( $rand ) shuffle($return);

            if ( $n == 0 ) return $return;

           if ( $n == 1 ) {
              return array_pop($return);
         } else {
                return array_slice($return, 0, $n);
}
}
/**
|------------------------------------------------- ---------------
| | Series of functions to generate maze
|------------------------------------------------- ---------------
*/
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;
    }
}

A*寻路算法
复制代码代码如下: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);
    }
    /**
|------------------------------------------------- ---------------
| Automatic path finding - A-star algorithm
|------------------------------------------------- ---------------
*/
    public function _search($start = false, $end = false) {
        if ( $start !== false ) $this->_start = $start;
        if ( $end !== false ) $this->_end = $end;
        $_sh = $this->_getH($start);
        $point['i'] = $start;
        $point['f'] = $_sh;
        $point['g'] = 0;
        $point['h'] = $_sh;
        $point['p'] = 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['f'] ) {
                    $minIndex = $key;
                }
            }
            $nowNode = $this->_open[$minIndex];
            unset($this->_open[$minIndex]);
            if ( $nowNode['i'] == $this->_end ) {
                $tp = array();
                while( $nowNode['p'] !== null ) {
                    array_unshift($tp, $nowNode['p']);
                    $nowNode = $this->_closed[$nowNode['p']];
                }
                array_push($tp, $this->_end);
                break;
            }
            $this->_setPoint($nowNode['i']);
        }
        $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]['g'] + $this->_getG($next);
            if ( $_g < $check['g'] ) {
                $this->_closed[$next]['g'] = $_g;
                $this->_closed[$next]['f'] = $this->_closed[$next]['g'] + $this->_closed[$next]['h'];
                $this->_closed[$next]['p'] = $pNode;
            }
        } else {
            $point['p'] = $pNode;
            $point['h'] = $this->_getH($next);
            $point['g'] = $this->_getG($next);
            $point['f'] = $point['h'] + $point['g'];
            $point['i'] = $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);
    }
}