18 个版本 (5 个破坏性更新)

0.8.0	2023 年 4 月 21 日
0.7.6	2023 年 4 月 16 日
0.6.2	2023 年 4 月 9 日
0.5.1	2023 年 3 月 31 日
0.3.5	2023 年 3 月 29 日

#878 in 算法

58 每月下载量

MIT 许可证

77KB
1.5K SLoC

路径查找库

本库将包含标准路径查找算法，并返回结果图对象。您可以在基于图或网格的结构中搜索路径。

如何使用

使用 markdown-toc 生成目录表

目前支持:

构建图
图操作
创建网格
网格操作
从图中创建最小生成树 (MST)
使用深度优先搜索 (DFS) 查找路径
使用广度优先搜索 (BFS)
使用双向广度优先搜索 (BBFS)
使用 Dijkstra 算法
使用 A* 算法，带有启发式方法
- 欧几里得距离
- 曼哈顿距离
待定：带有启发式方法的分层路径查找 A* (HPA*)
- 欧几里得距离
- 曼哈顿距离

下载包：https://crates.io/crates/path-finding

如何使用

目前，我们有以下主要概念

边
节点
图
Vec3
网格

您只需将边传递给图。节点将自动生成。每种路径查找方法都将接受一个图，并返回只包含结果边和节点的图。

或者，如果您提供邻接矩阵，也可以创建图。边和节点将自动生成。

如果您想使用 A* 路径查找算法，请确保为每个节点提供位置信息。

此外，我们还在基于 2D 网格结构的每个算法上进行了支持。

创建图

创建边

pub fn your_function() {
    graph::Edge::from(
        0 /* edge index */,
        0 /* source node */,
        1 /* destination node */,
        0.1, /* weight */
    );
}

从边创建图

pub fn your_function() {
    graph::Graph::from(Vec::from([edge1, edge2]));
}

从邻接矩阵创建图

pub fn your_function() {
    let mut matrix: &[&[f32]] = &[
        &[0.0, 4.0, 0.0, 0.0, 0.0, 0.0, 0.0, 8.0, 0.0],
        &[4.0, 0.0, 8.0, 0.0, 0.0, 0.0, 0.0, 11.0, 0.0],
        &[0.0, 8.0, 0.0, 7.0, 0.0, 4.0, 0.0, 0.0, 2.0],
        &[0.0, 0.0, 7.0, 0.0, 9.0, 14.0, 0.0, 0.0, 0.0],
        &[0.0, 0.0, 0.0, 9.0, 0.0, 10.0, 0.0, 0.0, 0.0],
        &[0.0, 0.0, 4.0, 14.0, 10.0, 0.0, 2.0, 0.0, 0.0],
        &[0.0, 0.0, 0.0, 0.0, 0.0, 2.0, 0.0, 1.0, 6.0],
        &[8.0, 11.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 7.0],
        &[0.0, 0.0, 2.0, 0.0, 0.0, 0.0, 6.0, 7.0, 0.0]
    ];

    graph::Graph::from_adjacency_matrix(matrix);
}

图操作

您可能想获取一些信息或以某种方式修改图。因此，为了方便操作或为启发式函数提供数据，当前图支持三个功能。

按权重升序排序

pub fn your_function() {
    let edges: Vec<Edge> = graph.sorted_by_weight_asc(); // will return a vector with edges ascending by weight 
}

提供位置

pub fn your_function() {
    // provide a hashmap, mapping the node id to a position - used for a* pathfinding heuristics
    graph.offer_positions(HashMap::from([(1, Vec3::from(0.1, 0.2, 0.3))]));
}

创建网格

从成本矩阵创建网格

在某些情况下，例如2D游戏，基于网格的结构是有利的。可以通过传递成本矩阵给构造函数 ::from 来创建网格。在您提供的矩阵的每个条目中，您可以使用一个无符号整数表示从任何相邻位置移动到该位置所需的努力。例如，在下面的示例中，从位置 (0, 0) 移动到位置 (0, 1) 将需要2的努力，或成本。等效地，从 (2, 2) 移动到 (1, 1) 将产生1的成本。基于这些信息，我们希望在每种路径查找算法中提供对基于网格结构的支持。

pub fn your_function() { let grid = grid::Grid::from(&[ &[4.0, 2.0, 1.0], &[2.0, 1.0, 0.0], &[3.0, 4.0, 7.0] ]); } 网格操作外部检查一个位置是否在网格外。传递一个坐标给下面的函数。 pub fn your_function() { grid.outside((0, 1)); } 内部检查一个位置是否在网格内。传递一个坐标给下面的函数。 pub fn your_function() { grid.within((0, 1)); } 节点 ID 将您的坐标转换为节点ID pub fn your_function() { grid.node_id((0, 1)); } 成本检索移动到提供的节点ID所需的成本 pub fn your_function() { grid.cost(3); } 最小生成树 pub fn your_function() { let mst_graph = graph::minimum_spanning(graph); } 深度优先搜索对于图 pub fn your_function() { let dfs = path::in_graph( 4 /* source */, 1 /* target */, &graph, Box::from(DepthFirstSearch {}) /* used algorithm */ ); } 对于网格 pub fn your_function() { let dfs = path::in_grid( 4 /* source */, 1 /* target */, &grid, Box::from(DepthFirstSearch {}) /* used algorithm */ ); } 广度优先搜索对于图 pub fn your_function() { let bfs = path::in_graph( 4 /* source */, 1 /* target */, &graph, Box::from(BreadthFirstSearch {}) /* used algorithm */ ); } 对于网格 pub fn your_function() { let dfs = path::in_grid( 4 /* source */, 1 /* target */, &grid, Box::from(BreadthFirstSearch {}) /* used algorithm */ ); } 双向广度优先搜索对于图 pub fn your_function() { let bi_bfs = path::in_graph( 4 /* source */, 1 /* target */, &graph, Box::from(BiBreadthFirstSearch {}) /* used algorithm */ ); } 对于网格 pub fn your_function() { let bi_bfs = path::in_grid( 4 /* source */, 1 /* target */, &grid, Box::from(BiBreadthFirstSearch {}), /* used algorithm */ ); } Dijkstra 路径搜索对于图 pub fn your_function() { let dijkstra = path::in_graph( 4 /* source */, 1 /* target */, &graph, Box::from(Dijkstra {}) /* used algorithm */ ); } 对于网格 pub fn your_function() { let bi_bfs = path::in_grid( 4 /* source */, 1 /* target */, &grid, Box::from(Dijkstra {}), /* used algorithm */ ); } A* 路径搜索您可以通过提供以下示例所示现有启发式函数或您自己的启发式函数来使用A*路径查找算法。如果您使用现有启发式函数，请确保提供节点的位置信息。对于图 pub fn your_function_with_euclidean_distance() { let a_star = path::in_graph( 4 /* source */, 1 /* target */, &graph, Box::from(AStar { heuristic: Box::from(euclidean_distance) }), /* used algorithm + euclidean distance heuristic function */ ); } pub fn your_function_with_manhattan_distance() { let a_star = path::in_graph( 4 /* source */, 1 /* target */, &graph, Box::from(AStar { heuristic: Box::from(manhattan_distance) }), /* used algorithm + manhattan distance heuristic function */ ); } 对于网格 pub fn your_function_with_euclidean_distance() { let a_star = path::in_grid( 4 /* source */, 1 /* target */, &grid, Box::from(AStar { heuristic: Box::from(euclidean_distance) }), /* used algorithm + euclidean distance heuristic function */ ); } pub fn your_function_with_manhattan_distance() { let a_star = path::in_grid( 4 /* source */, 1 /* target */, &grid, Box::from(AStar { heuristic: Box::from(manhattan_distance) }), /* used algorithm + manhattan distance heuristic function */ ); } 待定：分层 A* 路径搜索类似于A*路径查找算法，您可以提供上一节中所示现有启发式函数或您自己的启发式函数。如果您使用现有启发式函数，请确保提供节点的位置信息。除了A*的功能外，此算法还需要您将图传递给层次A*实例。原因是简单的，算法将在创建时将图分割成段并缓存后续路径查找过程中所需的信息。 pub fn your_function_with_euclidean_distance() { let a_star = path::in_graph( 4 /* source */, 1 /* target */, &graph, Box::from(HierarchicalAStar { heuristic, graph }), /* used algorithm and graph */ ); }

依赖项 ~3MB ~58K SLoC 导数 ordered-float 3.4 优先队列