PHP树的深度编历生成迷宫及A*自动寻路算法实例分析_PHP

本文实例讲述了PHP树的深度编历生成迷宫及A*自动寻路算法。分享给大家供大家参考。具体分析如下：

有一同事推荐了三思的迷宫算法，看了感觉还不错，就转成php
三思的迷宫算法是采用树的深度遍历原理，这样生成的迷宫相当的细，而且死胡同数量相对较少！
任意两点之间都存在唯一的一条通路。

至于A*寻路算法是最大众化的一全自动寻路算法

废话不多说，贴上带代码

迷宫生成类：

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

喜欢 (0)赏

[搞代码]

分享 (0)