PHP树的深度编历生成迷宫及A*自动寻路算法实例分析_php技巧
本文实例讲述了PHP树的深度编历生成迷宫及A*自动寻路算法。分享给大家供大家参考。具体分析如下:
有一同事推荐了三思的迷宫算法,看了感觉还不错,就转成php
三思的迷宫算法是采用树的深度遍历原理,这样生成的迷宫相当的细,而且死胡同数量相对较少!
任意两点之间都存在唯一的一条通路。
至于A*寻路算法是最大众化的一全自动寻路算法
废话不多说,贴上带代码
迷宫生成类:
// 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*寻路算法
// 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程序设计有所帮助。

Heiße KI -Werkzeuge

Undresser.AI Undress
KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover
Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool
Ausziehbilder kostenlos

Clothoff.io
KI-Kleiderentferner

Video Face Swap
Tauschen Sie Gesichter in jedem Video mühelos mit unserem völlig kostenlosen KI-Gesichtstausch-Tool aus!

Heißer Artikel

Heiße Werkzeuge

Notepad++7.3.1
Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version
Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1
Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6
Visuelle Webentwicklungstools

SublimeText3 Mac-Version
Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Heiße Themen



PHP 8.4 bringt mehrere neue Funktionen, Sicherheitsverbesserungen und Leistungsverbesserungen mit einer beträchtlichen Menge an veralteten und entfernten Funktionen. In dieser Anleitung wird erklärt, wie Sie PHP 8.4 installieren oder auf PHP 8.4 auf Ubuntu, Debian oder deren Derivaten aktualisieren. Obwohl es möglich ist, PHP aus dem Quellcode zu kompilieren, ist die Installation aus einem APT-Repository wie unten erläutert oft schneller und sicherer, da diese Repositorys in Zukunft die neuesten Fehlerbehebungen und Sicherheitsupdates bereitstellen.

Wenn Sie ein erfahrener PHP-Entwickler sind, haben Sie möglicherweise das Gefühl, dass Sie dort waren und dies bereits getan haben. Sie haben eine beträchtliche Anzahl von Anwendungen entwickelt, Millionen von Codezeilen debuggt und eine Reihe von Skripten optimiert, um op zu erreichen

Visual Studio Code, auch bekannt als VS Code, ist ein kostenloser Quellcode-Editor – oder eine integrierte Entwicklungsumgebung (IDE) –, die für alle gängigen Betriebssysteme verfügbar ist. Mit einer großen Sammlung von Erweiterungen für viele Programmiersprachen kann VS Code c

JWT ist ein offener Standard, der auf JSON basiert und zur sicheren Übertragung von Informationen zwischen Parteien verwendet wird, hauptsächlich für die Identitätsauthentifizierung und den Informationsaustausch. 1. JWT besteht aus drei Teilen: Header, Nutzlast und Signatur. 2. Das Arbeitsprinzip von JWT enthält drei Schritte: Generierung von JWT, Überprüfung von JWT und Parsingnayload. 3. Bei Verwendung von JWT zur Authentifizierung in PHP kann JWT generiert und überprüft werden, und die Funktionen und Berechtigungsinformationen der Benutzer können in die erweiterte Verwendung aufgenommen werden. 4. Häufige Fehler sind Signaturüberprüfungsfehler, Token -Ablauf und übergroße Nutzlast. Zu Debugging -Fähigkeiten gehört die Verwendung von Debugging -Tools und Protokollierung. 5. Leistungsoptimierung und Best Practices umfassen die Verwendung geeigneter Signaturalgorithmen, das Einstellen von Gültigkeitsperioden angemessen.

Dieses Tutorial zeigt, wie XML -Dokumente mit PHP effizient verarbeitet werden. XML (Extensible Markup-Sprache) ist eine vielseitige textbasierte Markup-Sprache, die sowohl für die Lesbarkeit des Menschen als auch für die Analyse von Maschinen entwickelt wurde. Es wird üblicherweise für die Datenspeicherung ein verwendet und wird häufig verwendet

Eine Zeichenfolge ist eine Folge von Zeichen, einschließlich Buchstaben, Zahlen und Symbolen. In diesem Tutorial wird lernen, wie Sie die Anzahl der Vokale in einer bestimmten Zeichenfolge in PHP unter Verwendung verschiedener Methoden berechnen. Die Vokale auf Englisch sind a, e, i, o, u und sie können Großbuchstaben oder Kleinbuchstaben sein. Was ist ein Vokal? Vokale sind alphabetische Zeichen, die eine spezifische Aussprache darstellen. Es gibt fünf Vokale in Englisch, einschließlich Großbuchstaben und Kleinbuchstaben: a, e, ich, o, u Beispiel 1 Eingabe: String = "TutorialPoint" Ausgabe: 6 erklären Die Vokale in der String "TutorialPoint" sind u, o, i, a, o, ich. Insgesamt gibt es 6 Yuan

Statische Bindung (statisch: :) implementiert die späte statische Bindung (LSB) in PHP, sodass das Aufrufen von Klassen in statischen Kontexten anstatt Klassen zu definieren. 1) Der Analyseprozess wird zur Laufzeit durchgeführt.

Was sind die magischen Methoden von PHP? Zu den magischen Methoden von PHP gehören: 1. \ _ \ _ Konstrukt, verwendet, um Objekte zu initialisieren; 2. \ _ \ _ Destruct, verwendet zur Reinigung von Ressourcen; 3. \ _ \ _ Call, behandeln Sie nicht existierende Methodenaufrufe; 4. \ _ \ _ GET, Implementieren Sie den dynamischen Attributzugriff; 5. \ _ \ _ Setzen Sie dynamische Attributeinstellungen. Diese Methoden werden in bestimmten Situationen automatisch aufgerufen, wodurch die Code -Flexibilität und -Effizienz verbessert werden.
