PHPツリーディープカレンダー生成迷路とA*自動経路探索アルゴリズム解析例、迷路例解析_PHPチュートリアル

PHP ツリーの深いカレンダー生成迷路と A* 自動経路探索アルゴリズムの分析例、迷路例分析

この記事では、PHP ツリーの深いカレンダー生成迷路と A* 自動経路探索アルゴリズムについて説明します。参考のためにみんなで共有してください。具体的な分析は次のとおりです:

同僚が Sansi の迷路アルゴリズムを勧めてくれたので、読んでとても良いと思ったので、PHP に変換しました。 Sansi の迷路アルゴリズムはツリー深度トラバースの原理を使用しており、この方法で生成される迷路は非常に薄く、行き止まりの数は比較的少ないです。
任意の 2 点間にはパスが 1 つだけあります。

A* 経路探索アルゴリズムに関しては、最も人気のある完全自動経路探索アルゴリズムです

これ以上ナンセンスは不要です。コードを投稿するだけです

迷路生成クラス:
コードをコピーします コードは次のとおりです: class Maze{
//迷路作成
プライベート $_w;
プライベート $_h;
プライベート $_grid;
プライベート $_walkHistory;
プライベート $_walkHistory2;
プライベート $_targetSteps;
// 構築
パブリック関数 Maze() {
$this->_w = 6;
$this->_h = 6;
$this->_grids = array();
}
//迷路のサイズを設定します
パブリック関数セット($width = 6, $height = 6) {
If ( $width > 0 ) $this->_w = $width;
If ( $height > 0 ) $this->_h = $height;
$this を返します;
}
// 迷路を手に入れましょう
パブリック関数 get() {
return $this->_grids;
}
// 迷路を生成します
パブリック関数 create() {
$this->_init();
return $this->_walk(rand(0, count($this->_grids) -1 ));
}
// 行き止まり点を取得します
パブリック関数ブロック($n = 0, $rand = false) {
$l = count($this->_grids);
for( $i = 1; $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);
}
}
/**
|------------------------------------------------- ---------------
| 迷路を生成する一連の関数
|------------------------------------------------- ---------------
​*/
プライベート関数 _walk($startPos) {
$this->_walkHistory = array();
$this->_walkHistory2 = array();
$curPos = $startPos;
while ($this->_getNext0() != -1) {
$curPos = $this->_step($curPos);
If ( $curPos === false ) Break;
}
$this を返します;
}
プライベート関数 _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);
        } その他 {
            array_push($a, -1);
        }
        $p = $curPos + $this->_w;
        if ($p _grids) && $this->_grids[$p] === 0 && ! $this->_isRepeating($p)) {
            array_push($a, $p);
        } その他 {
            array_push($a, -1);
        }
        $p = $curPos - 1;
        if (($curPos % $this->_w) != 0 && $this->_grids[$p] === 0 && ! $this->_isRepeating($p)) {
            array_push($a, $p);
        } その他 {
            array_push($a, -1);
        }
        $a を返します;
    }
    プライベート関数 _noStep() {
        $l = count($this->_targetSteps);
        for ($i = 0; $i             if ($this->_targetSteps[$i] != -1) return false;
        }
        true を返します;
    }
    プライベート関数 _step($curPos) {
        $this->_targetSteps = $this->_getTargetSteps($curPos);
        if ( $this->_noStep() ) {
            if ( count($this->_walkHistory) > 0 ) {
                $tmp = array_pop($this->_walkHistory);
            } その他 {
                false を返します;
            }
            array_push($this->_walkHistory2, $tmp);
            return $this->_step($tmp);
        }
        $r = ランド(0, 3);
        while ( $this->_targetSteps[$r] == -1) {
            $r = ランド(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);
        $isCross を返しますか? false : $nextPos;
    }
    プライベート関数 _isRepeating($p) {
        $l = count($this->_walkHistory);
        for ($i = 0; $i             if ($this->_walkHistory[$i] == $p) return true;
        }
        $l = count($this->_walkHistory2);
        for ($i = 0; $i             if ($this->_walkHistory2[$i] == $p) return true;
        }
        false を返します;
    }
    プライベート関数 _getNext0() {
        $l = count($this->_grids);
 
        for ($i = 0; $i             if ( $this->_grids[$i] == 0) return $i;
        }
        -1 を返します;
    }
    プライベート関数 _init() {
        $this->_grids = array();
        for ($y = 0; $y _h; $y ++) {
            for ($x = 0; $x _w; $x ++) {
                array_push($this->_grids, 0);
            }
        }
        $this を返します;
    }
}

A*寻路算法
复制代码代码如下:class AStar{
    // Aスター
    プライベート $_open;
    プライベート $_closed;
    プライベート $_start;
    プライベート $_end;
    プライベート $_grid;
    プライベート$_w;
    プライベート $_h;
    // 構築
    パブリック関数 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;
        $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 _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 = 配列();
                while( $nowNode['p'] !== null ) {
                    array_unshift($tp, $nowNode['p']);
                    $nowNode = $this->_closed[$nowNode['p']];
                }
                array_push($tp, $this->_end);
                休憩;
            }
            $this->_setPoint($nowNode['i']);
        }
        $this->_closed = array();
        $this->_open = array();
        $tp を返します;
    }
    プライベート関数 _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);
        }
    }
    プライベート関数 _checkPoint($pNode, $next) {
        if ( $this->_closed[$next] ) {
            $_g = $this->_closed[$pNode]['g'] + $this->_getG($next);
            if ( $_g                 $this->_closed[$next]['g'] = $_g;
                $this->_closed[$next]['f'] = $this->_closed[$next]['g'] + $this->_closed[$next]['h'];
                $this->_closed[$next]['p'] = $pNode;
            }
        } その他 {
            $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;
        }
    }
    プライベート関数 _getG($point) {
        return abs($this->_start - $point);
    }
    プライベート関数 _getH($point) {
        return abs($this->_end - $point);
    }
}

完全なサンプル コード ポイントはここからダウンロードできます。
必要があります大家は直接デモを行うことができます、看看効果!

ここで説明されている大家向けの php プログラムの設計が役立つことを希望します。

http://www.bkjia.com/PHPjc/965566.html

www.bkjia.comtru​​ehttp://www.bkjia.com/PHPjc/965566.html技術記事 PHP の深さブロック生成迷路および A* 自動回路法の例の分析、迷路例分析 ここでは、PHP の深さブロック生成迷路および A* 自動回路法の例を説明します。