我有一个以多维数组形式存储的地图 ($map[row][col])，我希望创建从点 A 到点 B 的路径。

因为我可能会遇到一些带有转弯、角落等的障碍物，所以我希望使用 A* 搜索来计算最快的路径。
所以通用函数是
f(x) = g(x) + h(x)

我有所有这些值。 g(x) 是移动的成本（并且它保存在地图上）； h(x) 是 A 和 B 之间的线性距离。

所以我拥有我需要的一切，但我有一个问题：我该如何组织这一切？
我不需要测试替代路径，因为地图上的一个正方形要么可通行，要么不可通行，所以当我到达目标时，它应该是最短的路径。

我该如何组织这一切？
我尝试了多维数组，但我迷失了……:(

编辑
我编写了一些代码，这简直是一堆文字：)

//$start = array(28, 19), $end = array(14, 19)//$this->map->map 是一个多维数组，除了成本为 99 的 //阻塞方块外，其他所有方块的成本均为 1//$this->map->map == $this->radar//23-17、22-18、22-19、22-20、23-21、19-17、20-18、20-19、20-20、19-21 处的阻塞方块//它们就像 2 个镜像的胡须：Pfunction createPath($start, $end){    $found = false;    $temp  = $this->cost($start, $end);    foreach($temp as $t){        if($t['cost'] == $this->map->map[$end[0]][$end[1]]) $found = true;        $this->costStack[$t['cost']][] = array('grid' => $t['grid'], 'dir' => $t['dir']);    }    ksort($this->costStack);    if(!$found) {        foreach($this->costStack as $k => $stack){            foreach($stack as $kn => $node){                $curNode = $node['grid'];                unset($this->costStack[$k][$kn]);                break;            }            if(!count($this->costStack[$k])) unset($this->costStack[$k]);            break;        }        $this->createPath($curNode, $end);    }}function cost($current, $target){    $return = array();    //$AIM  = array('n' => array(-1,  0),'e' => array( 0,  1),'s' => array( 1,  0),'w' => array( 0, -1));    foreach($this->AIM as $direction => $offset){        $position[0] = $current[0] + $offset[0];        $position[1] = $current[1] + $offset[1];        //radar 是地图的副本        if ( $this->radar[$position[0]][$position[1]] == 'V') continue;        else $this->radar[$position[0]][$position[1]] =  'V';        $h = (int) $this->distance($position, $target);        $g = $this->map->map[$position[0]][$position[1]];        $return[] = array('grid' => $position,                          'dir'  => $direction,                          'cost' => $h + $g);    }    return $return;}

我希望你能理解一切，我尽量表达清楚了。
最终，我可以到达目的地，仅扩展成本较低的节点，但现在我遇到了一个问题。
如何将其转换为方向？我必须存储一个命令堆栈（例如 n、n、e 等），如何识别这些值中的路径？

回答：

我的结构如下：

• 创建一个 Grid 类来保存所有可能的节点（可能你的数组会放在这里）
• 创建一个 Node 类来表示节点。节点还将计算成本并存储由 AStar 设置的前驱/g 值
• 创建一个 AStar 类，它只获取两个节点（例如 startNode，endNode）
• 使用 PriorityQueue 作为你的开放列表
• 当 Node 被（AStar）询问它的邻居时，将该调用委托给 Grid

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

更新

（找到了我的旧项目 😉）

它可能不完全是你正在寻找的东西，但也许它是一个好的开始。

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

00000000000000000000000000000000000000000000000000000000W0000000000000000000000W0000000000000000000000W0000000000000000000000W00000WWWWWWW0000000000W000000000000S000000000W0000000000E

（test/maze.txt）

你会得到类似这样的东西：

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;  }}