Create an A* search with PHP
My structure was:
- Have a Grid-class for holding all possible nodes (propably your arraygoes here)
- Have a Node-class representing the nodes. Nodes will also calculated costs and store predecessor/g-values set by AStar
- Have a AStar class, which will only get two nodes (e.g. startNode, endNode)
- Have a PriorityQueue as your open-list
- when a Node is asked (by AStar) about it's neighbors, delegated that call to Grid
I'll try to collect some code samples from a prior project, could take a while though.
Update
(found my old project ;))
It's probably not exactly what you're looking for, but maybe it's a start.
So using the files below, and mazes defined like:
00000000000000000000000000000000000000000000000000000000W0000000000000000000000W0000000000000000000000W0000000000000000000000W00000WWWWWWW0000000000W000000000000S000000000W00000000000E
(test/maze.txt)
You'll get something like this:
000000000000000000000000000000000X000000000000000000000XWXX000000000000000000X0W00X000000000000000XX00W000X0000000000000X0000W0000XWWWWWWW0000X00000W00000XXX0000SXXX000000W00000000XXXE
index.php
error_reporting(E_ALL ^ E_STRICT);ini_set('display_errors', 'on');header('Content-Type: text/plain; charset="utf-8"');// simple autoloaderfunction __autoload($className) { $path = '/lib/' . str_replace('_', '/', $className) . '.php'; foreach (explode(PATH_SEPARATOR, get_include_path()) as $prefix) { if (file_exists($prefix . $path)) { require_once $prefix . $path; } }}// init maze$maze = new Maze_Reader('test/maze.txt');$startNode = $maze->getByValue('S', true);$endNode = $maze->getByValue('E', true);$astar = new AStar;if ($astar->getPath($startNode, $endNode)) { do { if (!in_array($endNode->value(), array('S', 'E'))) { $endNode->value('X'); } } while ($endNode = $endNode->predecessor());}echo $maze;
/lib/AStar.php
/** * A simple AStar implementation */class AStar{ protected $openList; protected $closedList; /** * Constructs the astar object */ public function __construct() { $this->openList = new PriorityQueue; $this->closedList = new SplObjectStorage; } public function getPath($startNode, $endNode) { $this->openList->insert(0, $startNode); while (!$this->openList->isEmpty()) { $currentNode = $this->openList->extract(); if ($currentNode->equals($endNode)) { return $currentNode; } $this->expandNode($currentNode, $endNode); $this->closedList[$currentNode] = true; } return false; } protected function expandNode($currentNode, $endNode) { foreach ($currentNode->successors() as $successor) { if (isset($this->closedList[$successor])) { continue; } $tentative_g = $currentNode->g() + $currentNode->distance($successor); if ($this->openList->indexOf($successor) > -1 && $tentative_g >= $successor->g()) { continue; } $successor->predecessor($currentNode); $successor->g($tentative_g); $f = $tentative_g + $successor->distance($endNode); if ($this->openList->indexOf($successor) > -1) { $this->openList->changeKey($successor, $f); continue; } $this->openList->insert($f, $successor); } }}
/lib/PriorityQueue.php
class PriorityQueue{ protected $keys = array(); protected $values = array(); /** * Helper function to swap two <key>/<value> pairs * * @param Integer a * @param Integer b * @return Integer b */ protected function swap($a, $b) { // swap keys $c = $this->keys[$a]; $this->keys[$a] = $this->keys[$b]; $this->keys[$b] = $c; // swap values $c = $this->values[$a]; $this->values[$a] = $this->values[$b]; $this->values[$b] = $c; return $b; } /** * Heapify up * * @param Integer pos * @return void */ protected function upHeap($pos) { while ($pos > 0) { $parent = ($pos - 1) >> 2; if ($this->compare($this->keys[$pos], $this->keys[$parent]) >= 0) { break; } $pos = $this->swap($pos, $parent); } } /** * Heapify down * * @param Integer pos * @return void */ protected function downHeap($pos) { $len = sizeof($this->keys); $max = ($len - 1) / 2; while ($pos < $max) { $child = 2 * $pos + 1; if ($child < $len - 1 && $this->compare($this->keys[$child], $this->keys[$child + 1]) > 0) { $child += 1; } if ($this->compare($this->keys[$pos], $this->keys[$child]) <= 0) { break; } $pos = $this->swap($pos, $child); } } /** * Insert an <key>/<value> pair into the queue * * @param Object key * @param Object value * @return this */ public function insert($key, $value) { $this->keys[] = $key; $this->values[] = $value; $this->upHeap(sizeof($this->keys) - 1); return $this; } /** * Extract the top <value> * * @return Object */ public function extract() { $resultValue = $this->values[0]; $lastValue = array_pop($this->values); $lastKey = array_pop($this->keys); if (sizeof($this->keys) > 0) { $this->values[0] = $lastValue; $this->keys[0] = $lastKey; $this->downHeap(0); } return $resultValue; } /** * Changes the <key> of a <value> * * @param Object key * @param Object value * @return this */ public function changeKey($key, $value) { $pos = $this->indexOf($value); if ($pos !== false) { $this->keys[$pos] = $key; $this->upHeap($pos); } return $this; } /** * Returns the index of <value> or false if <value> is not in the queue * * @return false|Int */ public function indexOf($value) { return array_search($value, $this->values, true); } /** * Used to campare two <key>s. * * @param Object a * @param Object b * @return Number */ protected function compare($a, $b) { return $a - $b; } /** * Returns true if the queue is empty * * @return Boolean */ public function isEmpty() { return sizeof($this->keys) === 0; }}
/lib/Maze/Reader.php
class Maze_Reader implements IteratorAggregate{ /** * The initial maze * @var string */ protected $rawMaze; /** * A tow dimensional array holding the parsed maze * @var array */ protected $map = array(); /** * A flat array holding all maze nodes * @var array */ protected $nodes = array(); /** * A value map for easier access * @var array */ protected $valueMap = array(); /** * Constructs a maze reader * * @param string $file A path to a maze file */ public function __construct($file) { $this->rawMaze = file_get_contents($file); $this->parseMaze($this->rawMaze); } /** * Parses the raw maze into usable Maze_Nodes * * @param string $maze */ protected function parseMaze($maze) { foreach (explode("\n", $maze) as $y => $row) { foreach (str_split(trim($row)) as $x => $cellValue) { if (!isset($this->map[$x])) { $this->map[$x] = array(); } if (!isset($this->valueMap[$cellValue])) { $this->valueMap[$cellValue] = array(); } $this->nodes[] = new Maze_Node($x, $y, $cellValue, $this);; $this->map[$x][$y] =& $this->nodes[sizeof($this->nodes) - 1]; $this->valueMap[$cellValue][] =& $this->nodes[sizeof($this->nodes) - 1]; } } } /** * Returns the neighobrs of $node * * @return array */ public function getNeighbors(Maze_Node $node) { $result = array(); $top = $node->y() - 1; $right = $node->x() + 1; $bottom = $node->y() + 1; $left = $node->x() - 1; // top left if (isset($this->map[$left], $this->map[$left][$top])) { $result[] = $this->map[$left][$top]; } // top center if (isset($this->map[$node->x()], $this->map[$node->x()][$top])) { $result[] = $this->map[$node->x()][$top]; } // top right if (isset($this->map[$right], $this->map[$right][$top])) { $result[] = $this->map[$right][$top]; } // right if (isset($this->map[$right], $this->map[$right][$node->y()])) { $result[] = $this->map[$right][$node->y()]; } // bottom right if (isset($this->map[$right], $this->map[$right][$bottom])) { $result[] = $this->map[$right][$bottom]; } // bottom center if (isset($this->map[$node->x()], $this->map[$node->x()][$bottom])) { $result[] = $this->map[$node->x()][$bottom]; } // bottom left if (isset($this->map[$left], $this->map[$left][$bottom])) { $result[] = $this->map[$left][$bottom]; } // left if (isset($this->map[$left], $this->map[$left][$node->y()])) { $result[] = $this->map[$left][$node->y()]; } return $result; } /** * @IteratorAggregate */ public function getIterator() { return new ArrayIterator($this->nodes); } /** * Returns a node by value * * @param mixed $value * @param boolean $returnOne * @param mixed $fallback * @return mixed */ public function getByValue($value, $returnOne = false, $fallback = array()) { $result = isset($this->valueMap[$value]) ? $this->valueMap[$value] : $fallback; if ($returnOne && is_array($result)) { $result = array_shift($result); } return $result; } /** * Simple output */ public function __toString() { $result = array(); foreach ($this->map as $x => $col) { foreach ($col as $y => $node) { $result[$y][$x] = (string)$node; } } return implode("\n", array_map('implode', $result)); }}
/lib/Maze/Node.php
class Maze_Node{ protected $x; protected $y; protected $value; protected $maze; protected $g; protected $predecessor; /** * @param Integer $x * @param Integer $y * @param mixed $value * @param Maze_Reader $maze */ public function __construct($x, $y, $value, $maze) { $this->x = $x; $this->y = $y; $this->value = $value; $this->maze = $maze; } /** * Getter for x * * @return Integer */ public function x() { return $this->x; } /** * Getter for y * * @return Integer */ public function y() { return $this->y; } /** * Setter/Getter for g * * @param mixed $g * @return mixed */ public function g($g = null) { if ($g !== null) { $this->g = $g; } return $this->g; } /** * Setter/Getter for value * * @param mixed $value * @return mixed */ public function value($value = null) { if ($value !== null) { $this->value = $value; } return $this->value; } /** * Setter/Getter for predecessor * * @param Maze_Node $predecessor * @return Maze_Node|null */ public function predecessor(Maze_Node $predecessor = null) { if ($predecessor !== null) { $this->predecessor = $predecessor; } return $this->predecessor; } /** * simple distance getter * * @param Maze_Node $that * @return Float */ public function distance(Maze_Node $that) { if ($that->value() === 'W') { return PHP_INT_MAX; } return sqrt(pow($that->x() - $this->x, 2) + pow($that->y() - $this->y, 2)); } /** * Test for equality * * @param Maze_Node $that * @return boolean */ public function equals(Maze_Node $that) { return $this == $that; } /** * Returns the successors of this node * * @return array */ public function successors() { return $this->maze->getNeighbors($this); } /** * For debugging * * @return string */ public function __toString() { return (string)$this->value; }}