欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2023-11-11 18:33:04
本文实例讲述了php树的深度编历生成迷宫及a*自动寻路算法。分享给大家供大家参考。具体分析如下: 有一同事推荐了三思的迷宫算法,看了感觉还不错,就转成php 三思的迷宫...

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

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

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

废话不多说,贴上带代码

迷宫生成类:

复制代码 代码如下:
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;
    }
}

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);
    }
    /**
    |---------------------------------------------------------------
    | 自动寻路 - 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['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);
    }
}

完整实例代码点击此处。

有需要大家可以直接下demo,看看效果!

希望本文所述对大家的php程序设计有所帮助。