README

PHP的运动规划解决方案。

安装

使用 composer require stratadox/pathfinder 安装

示例

图中的最短路径(s)

<?php
use Stratadox\Pathfinder\DynamicPathfinder;
use Stratadox\Pathfinder\Graph\At;
use Stratadox\Pathfinder\Graph\Builder\GraphEnvironment;
use Stratadox\Pathfinder\Graph\Builder\WithEdge;

$environment = GraphEnvironment::create()
    ->withLocation('A', At::position(0, 0), WithEdge::to('B', 5)->andTo('C', 8))
    ->withLocation('B', At::position(0, 1), WithEdge::to('D', 9)->andTo('A', 1))
    ->withLocation('C', At::position(1, 0), WithEdge::to('D', 4)->andTo('A', 1))
    ->withLocation('D', At::position(1, 1), WithEdge::to('B', 3)->andTo('C', 9))
    ->make();

$shortestPath = DynamicPathfinder::operatingIn($environment);

assert(['A', 'C', 'D'] === $shortestPath->between('A', 'D'));
assert(['D', 'B', 'A'] === $shortestPath->between('D', 'A'));

assert([
    'B' => ['A', 'B'],
    'C' => ['A', 'C'],
    'D' => ['A', 'C', 'D'],
] === $shortestPath->from('A'));

网格中的最短路径

<?php
use Stratadox\Pathfinder\DynamicPathfinder;
use Stratadox\Pathfinder\Graph\Builder\GridEnvironment;
use Stratadox\Pathfinder\Graph\Builder\Obstacle;
use Stratadox\Pathfinder\Graph\Builder\Square;

$environment = GridEnvironment::create()
    ->withRow(
       Square::labeled('A1'),
       Square::labeled('B1'),
       Square::labeled('C1'),
       Square::labeled('D1')
    )
    ->withRow(
       Square::labeled('A2'),
       Obstacle::here(),
       Obstacle::here(),
       Square::labeled('D2')
    )
    ->withRow(
       Square::labeled('A3'),
       Square::labeled('B3'),
       Square::labeled('C3'),
       Square::labeled('D3')
    )
    ->make();

$shortestPath = DynamicPathfinder::operatingIn($environment);

assert(
    ['B1', 'A1', 'A2', 'A3', 'B3'] === $shortestPath->between('B1', 'B3')
);

所有最短路径的完整集合

<?php
use Stratadox\Pathfinder\Graph\Builder\GridEnvironment;
use Stratadox\Pathfinder\FloydWarshallIndexer;
use Stratadox\Pathfinder\StaticPathfinder;

$environment = GridEnvironment::fromArray([
    [1.0, 1.0, 1.0, 1.0],
    [1.0, INF, INF, 1.0],
    [1.0, 1.0, 1.0, 1.0],
])->make();

// slow operation: perform at deploy-time
$index = FloydWarshallIndexer::operatingIn($environment)->allShortestPaths();

// very fast operations: for use at runtime
$shortestPath = StaticPathfinder::using($index, $environment);

assert(
    ['B1', 'A1', 'A2', 'A3', 'B3'] === $shortestPath->between('B1', 'B3')
);

特性

Pathfinder模块提供两种功能：构建环境，以及在该环境中搜索最短路径。

搜索算法

存在许多执行图遍历的算法。Pathfinder模块实现了其中的一些。

Dijkstra算法

原始的路径查找解决方案：Dijkstra算法是一种不假设未知路线的广度优先搜索算法。（即，它没有启发式）

此算法可用于单路径和多路径搜索：除了找到从A点到B点的最短路径外，它还可以一次性找到从A点到所有其他可达点的最短路径。

对于寻找单路径，它通常比A*慢，除非没有启发式方法可用。然而，当寻找从单一源点出发的所有路径时，Dijkstra算法通常是首选的路径查找选择。

A*算法

寻找运行时路径的快速算法是A*搜索。

A*是一种最佳优先搜索算法，它通过维护一个包含考虑节点的优先队列来找到最短（最便宜的）路径，使用到目前为止路径的成本加上剩余路径的估计成本作为（逆）优先级指标。

在适用一致性启发式的情况下，使用A*算法可以比Dijkstra算法带来更好的性能。

默认情况下，使用欧几里得距离作为启发式（估计剩余路径的成本）。另外，还可以使用曼哈顿距离、切比雪夫距离或Floyd-Warshall算法的结果。

Bellman-Ford算法

通常被称为Bellman-Ford算法，但实际上是由Alfonso Shimbel发明的，这个算法在寻找从给定源点出发的所有最短路径方面比Dijkstra算法慢但更灵活。

当图可能包含负成本环时，做出的速度牺牲是，在这种情况下，这个算法在击败Dijkstra时无与伦比，因为Dijkstra会永远继续搜索。

Bellman-Ford算法具有停止和检测负环的能力，而不是消耗无限资源，会抛出异常。

Floyd-Warshall

Floyd-Warshall算法（由Bernard Roy发明）用于寻找每个可能起始顶点和每个可能终止顶点之间的所有路径。

具有O(v^3)的运行时间，其中v是顶点的数量，Floyd-Warshall算法可能运行得太慢，无法在运行时使用。然而，由于该算法能够找到通过环境的所有可能最短路径，因此它非常适合在部署时构建最短路径索引。

对于静态环境，这意味着在运行时路径查找成本的显著降低：由于所有最短路径都已经知道，因此无需在运行时搜索路径。

在可能只发生微小变化的环境中，Floyd-Warshall算法的结果可以用作A*搜索的启发式方法。

变种

动态路径查找器

动态路径查找器是一个自动组合的路径查找器，根据请求和环境类型在A*、Bellman-Ford和Dijkstra算法之间交替使用。

在查找多个路径时，它使用Dijkstra算法——除非图包含负边权，在这种情况下，应用Bellman-Ford。

在搜索单个路径时，也可以应用Dijkstra算法。当以下条件成立时，使用A*：

• 路径穿越地理环境，利用启发式方法的引导
• 图中包含具有负成本的边，以防止A*的开放/关闭集无限循环

默认情况下使用欧几里得距离，可以使用例如指定不同的距离

<?php
use Stratadox\Pathfinder\DynamicPathfinder;
use Stratadox\Pathfinder\Estimate\Estimate;
use Stratadox\Pathfinder\Distance\Chebyshev;

/** @var \Stratadox\Pathfinder\Environment $environment */
DynamicPathfinder::withHeuristic(Estimate::costAs(
    Chebyshev::inDimensions(2), 
    $environment
));

当可用时，可以使用以下方式提供环境图（Floyd-Warshall结果）

<?php
use Stratadox\Pathfinder\DynamicPathfinder;
use Stratadox\Pathfinder\Estimate\FromPreviousEnvironment;

/** @var \Stratadox\Pathfinder\Indexer $indexer */
/** @var \Stratadox\Pathfinder\Environment $environment */
DynamicPathfinder::withHeuristic(FromPreviousEnvironment::state(
    $indexer->heuristic(), 
    $environment
));

由于假设环境是动态的，因此该图仅用作A*启发式方法。

静态路径查找器

静态路径查找器假设环境不会改变，并具有通过该环境的最短路径图。

虽然仅限于不变的环境，但静态路径查找器是最快的解决方案。在内部，它所做的只是大量查找，其数量正好等于路径的长度。

图

主要文章：图。

路径查找器在包含权重的有向和标记图中工作。图中的每个顶点至少有一个标记，用作标识。

通过图中的路径的成本由其边的权重之和确定。

环境

当通过具有空间属性的图查找路径时，可以使用启发式方法优化单目标搜索。

本文档“示例”部分中创建的图是此类环境的示例。

可以使用任意数量的欧几里得空间维度，仅受启发式方法配置的限制。

网络

并非所有图都有相关的地理信息。那些没有相关地理信息的称为网络。

虽然路径查找器不能利用启发式方法来加速搜索，但它仍然可以足够好地找到最便宜的路径。

<?php
use Stratadox\Pathfinder\Graph\Builder\GraphNetwork;
use Stratadox\Pathfinder\Graph\Builder\WithEdge;

GraphNetwork::create()
    ->withVertex('A', WithEdge::to('B', 5)->andTo('C', 8))
    ->withVertex('B', WithEdge::to('D', 9)->andTo('A', 1))
    ->withVertex('C', WithEdge::to('D', 4)->andTo('A', 1))
    ->withVertex('D', WithEdge::to('B', 3)->andTo('C', 9))
    ->make();

使用您自己的网络

如果您已经有了图机制呢？也许您的图已经建模，也许它遵循某个特定的A/R ORM的结构。

在这种情况下，只需实现网络或环境接口（直接或通过适配器），就可以继续了！

关于此类适配器外观的示例，请参阅graphp 查找器包。