Detaillierte Erläuterung der PHP-Labyrinthgenerierung und des automatischen Pfadfindungsalgorithmus

Wie erstelle ich mit PHP ein Labyrinth und finde einen Weg, es zu lösen? In diesem Artikel werden hauptsächlich die Labyrinth-Generierung und die automatischen Pfadfindungsalgorithmen von PHP vorgestellt und die Labyrinth-Generierung und die automatischen Pfadfindungsalgorithmen von PHP ausführlich erläutert. Ich hoffe, es hilft allen.

Das Beispiel in diesem Artikel beschreibt das tiefe Kalendergenerierungslabyrinth des PHP-Baums und den automatischen Pfadfindungsalgorithmus A*. Teilen Sie es als Referenz mit allen. Die spezifische Analyse lautet wie folgt:

Ein Kollege empfahl den Labyrinth-Algorithmus von Sansi. Nachdem ich ihn gelesen hatte, fand ich ihn ziemlich gut, also habe ich ihn in PHP konvertiert.
Der Labyrinth-Algorithmus von Sansi verwendet das Prinzip der Baumtiefe Durchquerung, daher ist das auf diese Weise erzeugte Labyrinth ziemlich dünn und die Anzahl der Sackgassen ist relativ gering!
Es gibt nur einen Pfad zwischen zwei beliebigen Punkten.

Der A*-Pfadfindungsalgorithmus ist der beliebteste vollautomatische Pfadfindungsalgorithmus

Ohne weitere Umschweife ist hier der Code

Labyrinth-Generierungsklasse:

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;
    }
}

Ein*-Pfadfindungsalgorithmus

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['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[&#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);
    }
}

Verwandte Empfehlungen:

Lernen gängiger PHP-Sortieralgorithmen

Zusammenfassung des PHP-Traversal-Algorithmus

Wie PHP den binären Suchalgorithmus implementiert

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der PHP-Labyrinthgenerierung und des automatischen Pfadfindungsalgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!