PHP 트리 딥 캘린더 생성 미로 및 A* 자동 경로 찾기 알고리즘 예제 분석_php 기술

이 기사의 예에서는 PHP 트리의 심층 달력 생성 미로와 A* 자동 경로 찾기 알고리즘을 설명합니다. 참고할 수 있도록 모든 사람과 공유하세요. 구체적인 분석은 다음과 같습니다.

동료가 Sansi의 미로 알고리즘을 추천해 봤는데 꽤 좋다고 생각해서 PHP로 변환했습니다.
Sansi의 미로 알고리즘은 트리 깊이 탐색 원리를 사용합니다. 이렇게 생성된 미로는 상당히 얇으며 막다른 골목의 수도 상대적으로 적습니다.
두 지점 사이에는 경로가 하나만 있습니다.

A* 길찾기 알고리즘은 가장 널리 사용되는 완전 자동 길찾기 알고리즘입니다

더 이상 쓸데없는 말은 하지 말고 코드만 붙여넣으세요

미로 생성 수업:

코드 복사 코드는 다음과 같습니다.

클래스 미로{
    // 미로 만들기
    비공개 $_w;
    비공개 $_h;
    비공개 $_grids;
    비공개 $_walkHistory;
    비공개 $_walkHistory2;
    비공개 $_targetSteps;
    // 구성
    공개 함수 Maze() {
        $this->_w = 6;
        $this->_h = 6;
        $this->_grids = 배열();
    }
    // 设置迷宫大小
    공개 함수 세트($width = 6, $height = 6) {
        if ( $width > 0 ) $this->_w = $width;
        if ( $height > 0 ) $this->_h = $height;
        $this를 반환하세요.
    }
    // 取到迷宫
    공개 함수 get() {
        $this->_grids;
반환     }
    // 生成迷宫
    공개 함수 생성() {
        $this->_init();
        return $this->_walk(rand(0, count($this->_grids) -1 ));
    }
    // 获取死胡同点
    공용 함수 블록($n = 0, $rand = false) {
        $l = 개수($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);
        } 그 밖의 {
            return array_slice($return, 0, $n);
        }
    }
    /**
|------------------------------------------------- ---------------
| 미로를 생성하는 일련의 함수
|------------------------------------------------- ---------------
​*/
    개인 함수 _walk($startPos) {
        $this->_walkHistory = 배열();
        $this->_walkHistory2 = 배열();
        $curPos = $startPos;
        while ($this->_getNext0() != -1) {
            $curPos = $this->_step($curPos);
            if ( $curPos === false ) break;
        }
        $this를 반환하세요.
    }
    비공개 함수 _getTargetSteps($curPos) {
        $p = 0;
        $a = 배열();
        $p = $curPos - $this->_w;
        if ($p > 0 && $this->_grids[$p] === 0 && ! $this->_isRepeating($p)) {
            array_push($a, $p);
        } 그 밖의 {
            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 < count($this->_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 = 개수($this->_targetSteps);
        for ($i = 0; $i < $l; $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 = 거짓;
        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를 반환하시겠습니까? 거짓 : $nextPos;
    }
    비공개 함수 _isRepeating($p) {
        $l = 개수($this->_walkHistory);
        for ($i = 0; $i < $l; $i ) {
            if ($this->_walkHistory[$i] == $p) return true;
        }
        $l = 개수($this->_walkHistory2);
        for ($i = 0; $i < $l; $i ) {
            if ($this->_walkHistory2[$i] == $p) return true;
        }
        false를 반환합니다.
    }
    비공개 함수 _getNext0() {
        $l = 개수($this->_grids);
 
        for ($i = 0; $i <= $l; $i ) {
            if ( $this->_grids[$i] == 0) $i를 반환합니다.
        }
        반환 -1;
    }
    개인 함수 _init() {
        $this->_grids = 배열();
        for ($y = 0; $y             for ($x = 0; $x < $this->_w; $x ) {
                array_push($this->_grids, 0);
            }
        }
        $this를 반환하세요.
    }
}

A*寻路算法

复代码 代码如下:

클래스 AStar{
    // 에이스타
    비공개 $_open;
    비공개 $_closed;
    비공개 $_start;
    비공개 $_end;
    비공개 $_grids;
    비공개 $_w;
    비공개 $_h;
    // 구성
    공개 함수 AStar(){
        $this->_w = null;
        $this->_h = null;
        $this->_grids = null;
    }
    공개 함수 세트($width, $height, $grids) {
        $this->_w = $width;
        $this->_h = $높이;
        $this->_grids = $grids;
        $this를 반환하세요.
    }
    // 迷宫中寻路
    공개 함수 검색($start = false, $end = false) {
        return $this->_search($start, $end);
    }
    /**
|------------------------------------------------- ---------------
| 자동 경로 찾기 - A-star 알고리즘
|------------------------------------------------- ---------------
​*/
    공개 함수 _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] = $포인트;
        while ( 0 < count($this->_open) ) {
            $minf = 거짓;
            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 = 배열();
        $this->_open = 배열();
        $tp를 반환하세요;
    }
    개인 함수 _setPoint($me) {
        $point = $this->_grids[$me];
        // 所有可选方向入队列
        if ( $point & 1 ) {
            $next = $me - $this->_w;
            $this->_checkPoint($me, $next);
        }
        if ( $point & 2 ) {
            $next = $나 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 < $check['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] = $포인트;
        }
    }
    비공개 함수 _getG($point) {
        return abs($this->_start - $point);
    }
    비공개 함수 _getH($point) {
        return abs($this->_end - $point);
    }
}

完整实例代码点击此处本站下载。

有需要大家可以直接下데모，看看效果！

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