搜尋
首頁php教程php手册PHP树的深度编历生成迷宫及A*自动寻路算法实例分析

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

 这篇文章主要介绍了PHP树的深度编历生成迷宫及A*自动寻路算法,实例分析了php实现A*寻路算法的技巧,具有一定参考借鉴价值,需要的朋友可以参考下

 

 

本文实例讲述了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 $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 _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 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 if ($this->_walkHistory[$i] == $p) return true;
}
$l = count($this->_walkHistory2);
for ($i = 0; $i if ($this->_walkHistory2[$i] == $p) return true;
}
return false;
}
private function _getNext0() {
$l = count($this->_grids);

for ($i = 0; $i if ( $this->_grids[$i] == 0) return $i;
}
return -1;
}
private function _init() {
$this->_grids = array();
for ($y = 0; $y _h; $y ++) {
for ($x = 0; $x _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 _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 $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程序设计有所帮助。

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

MantisBT

MantisBT

Mantis是一個易於部署的基於Web的缺陷追蹤工具,用於幫助產品缺陷追蹤。它需要PHP、MySQL和一個Web伺服器。請查看我們的演示和託管服務。

EditPlus 中文破解版

EditPlus 中文破解版

體積小,語法高亮,不支援程式碼提示功能

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強大的PHP整合開發環境

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser是一個安全的瀏覽器環境,安全地進行線上考試。該軟體將任何電腦變成一個安全的工作站。它控制對任何實用工具的訪問,並防止學生使用未經授權的資源。

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)