路径查找库

Rust 初学者 - 欢迎反馈！

本库将包含标准路径查找算法，并返回结果路径或图对象

• 如何使用
  • 创建图
  • 图操作
    • 按权重升序排序
    • 提供位置
  • 最小生成树
  • 深度优先搜索
  • 广度优先搜索
  • 双向广度优先搜索
  • Dijkstra 路径搜索
  • A* 路径搜索

使用 markdown-toc 生成的目录表

目前支持:

• 构建图
• 从图中创建最小生成树
• 使用深度优先搜索查找路径
• 使用广度优先搜索查找路径
• 使用双向广度优先搜索查找路径
• 使用 Dijkstra 算法查找路径
• 使用 A* 算法查找路径，带启发式函数
  • 欧几里得距离
  • 曼哈顿距离

下载库: https://crates.io/search?q=path-finding-lib

如何使用

目前，我们有三个主要概念

• 边
• 节点
• 图
• 位置

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

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

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

创建图

• 创建边

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, Position::from(0.1, 0.2, 0.3))]));
}

最小生成树

pub fn your_function() {
    let mst_graph = graph::minimum_spanning(graph);
}

深度优先搜索

pub fn your_function() {
    let dfs = path::find(
        4 /* source */,
        1 /* target */,
        &graph,
        Box::from(DepthFirstSearch {}) /* used algorithm */
    );
}

广度优先搜索

pub fn your_function() {
    let bfs = path::find(
        4 /* source */,
        1 /* target */,
        &graph,
        Box::from(BreadthFirstSearch {}) /* used algorithm */
    );
}

双向广度优先搜索

pub fn your_function() {
    let bi_bfs = path::find(
        4 /* source */,
        1 /* target */,
        &graph,
        Box::from(BiBreadthFirstSearch {}) /* used algorithm */
    );
}

Dijkstra 路径搜索

pub fn your_function() {
    let dijkstra = path::find(
        4 /* source */,
        1 /* target */,
        &graph,
        Box::from(Dijkstra {}) /* used algorithm */
    );
}

A* 路径搜索

您可以通过提供以下所示现有的启发式函数或您自己的启发式函数来使用A*路径查找算法。如果您使用现有的启发式函数，请确保提供节点的位置信息。

pub fn your_function_with_euclidean_distance() {
    let a_star = path::find(
        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::find(
        4 /* source */,
        1 /* target */,
        &graph,
        Box::from( AStar { heuristic: Box::from(manhattan_distance) }), /* used algorithm + manhattan distance heuristic function */
    );
}