README

A Star路径查找算法的PHP实现。

要求

您需要PHP >= 8.0来使用此库，但推荐使用最新稳定版本的PHP。

如果您需要在较旧的PHP版本（或HHVM）上运行此库，请安装1.x版本。

安装

安装 composer。
将A Star算法包添加到您的composer.json文件中并下载
```
composer require jmgq/a-star
```

用法

创建一个实现了DomainLogicInterface的类。此接口中三个方法的参数都是节点。节点可以是任何类型：它可以是字符串、整数、对象等。您根据业务逻辑决定节点的形状。您可以提供一种方式来识别您的节点（查看原因和方法）。

use JMGQ\AStar\DomainLogicInterface;

class DomainLogic implements DomainLogicInterface
{
    // ...

    public function getAdjacentNodes(mixed $node): iterable
    {
        // Return a collection of adjacent nodes
    }

    public function calculateRealCost(mixed $node, mixed $adjacent): float | int
    {
        // Return the actual cost between two adjacent nodes
    }

    public function calculateEstimatedCost(mixed $fromNode, mixed $toNode): float | int
    {
        // Return the heuristic estimated cost between the two given nodes
    }

    // ...
}

实例化AStar类，它需要新创建的域逻辑对象

use JMGQ\AStar\AStar;

$domainLogic = new DomainLogic();

$aStar = new AStar($domainLogic);

这就完成了！您现在可以使用AStar类中的run方法来生成两个节点之间的最佳路径。此方法将返回一个有序的节点列表，从起始节点到目标节点。如果没有解决方案，则返回一个空列表。
```
$solution = $aStar->run($start, $goal);
```

指定唯一的节点ID

为了正确工作，A*算法需要唯一地标识每个节点。此库将为每个节点自动生成一个默认ID，该ID将是使用PHP的serialize函数序列化节点的结果。这有两个主要缺点

它并不总是正确的：例如，假设一个节点由具有两个键：x和y的关联数组表示。以下两个节点是相同的，但它们的序列化值并不相同

$node1 = ['x' => 4, 'y' => 5];
$node2 = ['y' => 5, 'x' => 4];
serialize($node1); // a:2:{s:1:"x";i:4;s:1:"y";i:5;}
serialize($node2); // a:2:{s:1:"y";i:5;s:1:"x";i:4;}

性能问题：如果节点结构非常复杂，序列化它可能需要太长时间。

而不是依赖于这种默认机制，您可以通过确保您的节点实现了NodeIdentifierInterface（它仅声明一个方法）来自动提供节点ID，从而避免序列化过程

interface NodeIdentifierInterface
{
    public function getUniqueNodeId(): string;
}

例如，这是它在地形示例中的实现方式

use JMGQ\AStar\Node\NodeIdentifierInterface;

class Position implements NodeIdentifierInterface
{
    private int $row;
    private int $column;

    // ...

    public function getUniqueNodeId(): string
    {
        return $this->row . 'x' . $this->column;
    }

    // ...
}

示例

在示例文件夹中有两个工作实现。

地形示例

为了执行此示例，请运行以下命令

composer example:terrain

此示例计算矩形棋盘上两个方块之间的最佳路线。每个方块都有一个与之关联的成本，表示在TerrainCost对象中。TerrainCost数组中的每个值都表示进入该特定方块的成本。

例如，给定以下地形

  | 0 1 2 3
-----------
0 | 1 1 1 2
1 | 1 2 3 4
2 | 1 1 1 1

从任何相邻方块进入（1, 3）方块（第1行，第3列）的成本是4个单位。因此，（0, 2）和（1, 3）之间的实际距离是4个单位。

图示例

为了执行此示例，请运行以下命令

composer example:graph

重要提示

此示例计算有向图中两个给定节点之间的最短路径。
节点位置由其X和Y坐标确定。
Link 类指定两个节点之间的一条弧（单向连接）。例如，Link(A, B, D) 表示从节点 A 到节点 B 的一条弧，距离为 D 个单位。

基准测试

该项目包含一个基准测试工具，可以用来测试算法的效率。这特别有助于评估对算法所做的任何更改。基准测试针对地形示例进行。

要使用默认参数执行它，只需运行

composer benchmark

有关参数的完整列表，请运行

composer benchmark help benchmark

例如，以下命令针对10个不同大小为5x5的地形，另外10个不同大小为12x12的地形运行算法，并使用123456作为种子随机生成每个地形瓦片的成本

composer benchmark -- --iterations=10 --size=5 --size=12 --seed=123456

贡献

欢迎为该项目做出贡献。如果您想做出贡献，请fork该项目，创建一个功能分支，并发送拉取请求。

开发环境

为了设置您的开发环境，请按照以下步骤操作

安装 Docker。
构建镜像：docker build -t php-a-star .

运行镜像

docker run -it \
    --mount type=bind,source="$(pwd)",target=/opt/php-a-star \
    php-a-star \
    sh

编码标准

为了确保代码库的一致性，请确保您的代码遵循以下约定

代码应遵循 PSR-12 文档中定义的标准。
使用驼峰式命名变量，而不是下划线。
无论构造函数有多少参数，实例化类时都应使用括号。
编写自文档化的代码而不是实际的注释（除非绝对必要）。

换句话说，请模仿现有的代码。

请记住，您可以通过运行 composer coding-standards 来验证您的代码是否遵循编码标准。

测试

该项目遵循 TDD 原则进行开发，并力求最大测试覆盖率。因此，鼓励您为新的代码编写测试。如果您的代码是错误修复，请编写一个测试来证明您的代码确实修复了该错误。

如果您不知道如何编写测试，请不要气馁，发送带有测试的拉取请求，我会在以后尝试添加它们。

要运行测试套件和代码覆盖率报告，只需执行 composer test。

静态分析工具

为了确保代码库的质量达到高标准，以下静态分析工具作为CI管道的一部分运行

您可以使用 composer static-analysis 运行所有本地静态分析工具。

贡献者

请自由地把自己添加到贡献者列表中。

变更日志

阅读变更日志。

jmgq / a-star

维护者

详细信息