使用 PHP 创建 A* 搜索

我的结构是：

• 有一个网格类来容纳所有可能的节点（你的数组可以在这里）
• 具有表示节点的 Node 类。节点还将计算成本并存储由AStar设置的前身/g值
• 有一个AStar类，它只会得到两个节点（例如startNode，endNode）
• 将优先级队列作为您的开放列表
• 当节点被AStar询问其邻居时，将该调用委托给Grid

我将尝试从以前的项目中收集一些代码示例，但可能需要一段时间。

更新

(找到我的旧项目;))

这可能不完全是你想要的，但也许这是一个开始。

因此，使用下面的文件，以及迷宫定义如下：

00000000000000000000000
00000000000000000000000
0000000000W000000000000
0000000000W000000000000
0000000000W000000000000
0000000000W00000WWWWWWW
0000000000W000000000000
S000000000W00000000000E

(测试/迷宫.txt)

你会得到这样的东西：

00000000000000000000000
0000000000X000000000000
000000000XWXX0000000000
00000000X0W00X000000000
000000XX00W000X00000000
00000X0000W0000XWWWWWWW
0000X00000W00000XXX0000
SXXX000000W00000000XXXE

索引.php

error_reporting(E_ALL ^ E_STRICT);
ini_set('display_errors', 'on');

header('Content-Type: text/plain; charset="utf-8"');

// simple autoloader
function __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;
  }
}