README

A-star 是一种路径查找算法，用 PHP 编写。它可以通过使用不同的启发式方法在二维数组中找到两点之间的最短路径。

安装

composer require blackscorp/astar

用法

首先为您的地图创建一个二维数组

  $map = [
            [0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0],
            [0, 0, 0, 1, 1],
            [0, 0, 0, 1, 0],
        ];

每个键代表地图的 x 和 y 位置。数组中的每个值代表成本，A-star 尝试找到成本最低的路径。如果需要，您可以使用负键。

接下来将数组转换为网格，网格是一组节点的集合。

$grid = new BlackScorp\Astar\Grid($map);

现在您可以这样从网格中获取节点

$startPosition = $grid->getPoint(3,1);
$endPosition = $grid->getPoint(0,0);

最后，将网格传递给 Astar 并搜索最短路径

$astar = new BlackScorp\Astar\Astar($grid);
$nodes = $astar->search($startPosition,$endPosition);
if(count($nodes) === 0){
   echo "Path not found";
}else{
  foreach($nodes as $node){
     echo $node->getY().'/'.$node->getX().'<br/>';
  }
}

设置

默认情况下禁用了对角方向，可以通过以下方式启用

$astar->enableDiagonal();

一旦启用对角选项，算法将使用 曼哈顿 启发式找到最短路径。

曼哈顿不是精确的，但计算成本较低，然而您可以使用其他启发式方法，如对角或欧几里得，以下代码所示。

$astar->setHeuristic(new BlackScorp\Astar\Heuristic\Euclidean());

您还可以创建自定义启发式方法。

阻塞位置

有些情况下，您希望完全阻塞特定路径，独立于成本，您可以使用以下代码做到这一点

astar->blocked([3,2]);

这基本上意味着在初始地图中

  $map = [
            [0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0],
            [0, 2, 2, 0, 0],
            [0, 3, 0, 1, 1],
            [0, 0, 0, 1, 0],
        ];

值 3 和 2 无法通过。

贡献

请随意提交拉取请求，仍有改进的空间，Grid 包含一个二维数组，可能会被 SplFixedArray 或类似的东西替换。

运行测试以确保没有出错。

许可

A-Star 是在 MIT 许可证条款下分发的免费软件。