Shulou(Shulou.com)06/03 Report--

This article mainly shows you the "PHP how to achieve the depth of tree calendar generation maze and A* automatic pathfinding algorithm", the content is easy to understand, clear, hope to help you solve your doubts, the following let the editor lead you to study and learn "PHP how to achieve tree depth calendar generation maze and A* automatic pathfinding algorithm" this article.

The specific analysis is as follows:

A colleague recommended the maze algorithm of thinking twice. After reading it, it felt good, so I switched it to php.

The maze algorithm of thinking twice uses the depth traversal principle of the tree, so the resulting maze is quite fine, and the number of dead ends is relatively small!

There is a unique path between any two points.

As for the A* pathfinding algorithm, it is the most popular automatic pathfinding algorithm.

Maze generation class:

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 () } / / set the maze size public function set ($width = 6, $height = 6) {if ($width > 0) $this- > _ w = $width; if ($height > 0) $this- > _ h = $height; return $this;} / / get the maze public function get () {return $this- > _ grids } / / generate a maze public function create () {$this- > _ init (); return $this- > _ walk (rand (0, count ($this- > _ grids)-1));} / / get the dead end point 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;}} / / Random point if ($rand) shuffle ($return); if ($n = = 0) return $return; if ($n = = 1) {return array_pop ($return) } else {return array_slice ($return, 0, $n) }} / * * |-- | A series of functions that generate a maze |-- -* / 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 _ 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* the code for the pathfinding algorithm is as follows: 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 } / / finding public function search in the maze ($start = false, $end = false) {return $this- > _ search ($start, $end) } / * * |-- | automatic path finding-A-star algorithm |- -- * / 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]; / all optional directions queued 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);}} above are all the contents of the article "how to realize the maze of tree depth calendar generation and A* automatic pathfinding algorithm". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.