Polyanya - 无妥协的导航网格寻路

Polyanya 的 Rust 实现！Polyanya 是一种 任意角度路径规划 算法。

使用 Bevy 制作的 WASM 演示可在 此处 获取。

特性

• 使用 Polyanya 进行寻路：用于导航网格的高效任意角度路径规划算法。
• 多层导航网格支持：
  • 用于 3D 导航的重叠导航网格（楼层、桥梁等）。
  • 用于定向移动的单层。
  • 支持启用或禁用图层的条件图层遍历。
  • 具有不同遍历成本的图层，以实现更真实的寻路。

用法

可以通过指定外部边缘和内部障碍物来构建导航网格：

use glam::vec2;
use polyanya::*;

// Build a mesh from its outer edge
let triangulation = Triangulation::from_outer_edges(&[
    vec2(0., 6.), vec2(2., 5.),
    vec2(2., 4.), vec2(1., 4.),
    vec2(1., 3.), vec2(2., 1.),
    vec2(4., 1.), vec2(4., 2.),
    vec2(7., 4.), vec2(7., 0.),
    vec2(12., 0.), vec2(12., 3.),
    vec2(11., 3.), vec2(11., 5.),
    vec2(13., 5.), vec2(13., 7.),
    vec2(10., 7.), vec2(11., 8.),
    vec2(7., 8.), vec2(7., 7.),
    vec2(5., 7.), vec2(5., 8.),
    vec2(0., 8.),
]);
let mesh = triangulation.as_navmesh();

// Get the path between two points
let from = vec2(12.0, 0.0);
let to = vec2(3.0, 1.0);
let path = mesh.path(from, to);

assert_eq!(
    path.unwrap().path,
    vec![
        vec2(7.0, 4.0),
        vec2(4.0, 2.0),
        vec2(3.0, 1.0)
    ]
);

它们也可以通过手动指定顶点和多边形来构建，以实现完全控制。以下代码生成相同的网格

use glam::vec2;
use polyanya::*;

// Build a mesh from a list of vertices and polygons
let mesh = Mesh::new(
    vec![
        Vertex::new(vec2(0., 6.), vec![0, u32::MAX]),           // 0
        Vertex::new(vec2(2., 5.), vec![0, u32::MAX, 2]),        // 1
        Vertex::new(vec2(5., 7.), vec![0, 2, u32::MAX]),        // 2
        Vertex::new(vec2(5., 8.), vec![0, u32::MAX]),           // 3
        Vertex::new(vec2(0., 8.), vec![0, u32::MAX]),           // 4
        Vertex::new(vec2(1., 4.), vec![1, u32::MAX]),           // 5
        Vertex::new(vec2(2., 1.), vec![1, u32::MAX]),           // 6
        Vertex::new(vec2(4., 1.), vec![1, u32::MAX]),           // 7
        Vertex::new(vec2(4., 2.), vec![1, u32::MAX, 2]),        // 8
        Vertex::new(vec2(2., 4.), vec![1, 2, u32::MAX]),        // 9
        Vertex::new(vec2(7., 4.), vec![2, u32::MAX, 4]),        // 10
        Vertex::new(vec2(10., 7.), vec![2, 4, 6, u32::MAX, 3]), // 11
        Vertex::new(vec2(7., 7.), vec![2, 3, u32::MAX]),        // 12
        Vertex::new(vec2(11., 8.), vec![3, u32::MAX]),          // 13
        Vertex::new(vec2(7., 8.), vec![3, u32::MAX]),           // 14
        Vertex::new(vec2(7., 0.), vec![5, 4, u32::MAX]),        // 15
        Vertex::new(vec2(11., 3.), vec![4, 5, u32::MAX]),       // 16
        Vertex::new(vec2(11., 5.), vec![4, u32::MAX, 6]),       // 17
        Vertex::new(vec2(12., 0.), vec![5, u32::MAX]),          // 18
        Vertex::new(vec2(12., 3.), vec![5, u32::MAX]),          // 19
        Vertex::new(vec2(13., 5.), vec![6, u32::MAX]),          // 20
        Vertex::new(vec2(13., 7.), vec![6, u32::MAX]),          // 21
        Vertex::new(vec2(1., 3.), vec![1, u32::MAX]),           // 22
    ],
    vec![
        Polygon::new(vec![0, 1, 2, 3, 4], true),           // 0
        Polygon::new(vec![5, 22, 6, 7, 8, 9], true),       // 1
        Polygon::new(vec![1, 9, 8, 10, 11, 12, 2], false), // 2
        Polygon::new(vec![12, 11, 13, 14], true),          // 3
        Polygon::new(vec![10, 15, 16, 17, 11], false),     // 4
        Polygon::new(vec![15, 18, 19, 16], true),          // 5
        Polygon::new(vec![11, 17, 20, 21], true),          // 6
    ],
).unwrap();

上述代码将构建以下网格，其中多边形以绿色标记，顶点以红色标记：

原始作品

查看 cpp 实现。

index;micro;successor_calls;generated;pushed;popped;pruned_post_pop;length;gridcost
0;4960.92;6974;4368;4313;3823;21;1123.222637572437;1199.73

此 crate 似乎会生成稍多的节点，但通常比 cpp 实现更快。仍有几个已知案例需要改进：

• 共线优化，当搜索节点根节点和区间都位于同一条直线上时
• 三角形优化，当在三角形多边形中进行搜索时
• 当交点非常接近顶点时，有时会生成一个额外的细长搜索节点
• 搜索起始节点和结束节点的成本更高

使用 feature stats 编译此 crate 将输出与默认 cpp 实现输出几乎相同级别的信息。

index;micros;successor_calls;generated;pushed;popped;pruned_post_pop;length
0;2990.083;6983;7748;4314;3828;21;1123.2228

verbose 功能将产生与将 verbose 设置为 1]相同的输出。

        pushing: root=(993, 290); left=(989, 303); right=(1001, 288); f=1020.21, g=0.00
        pushing: root=(993, 290); left=(984, 301); right=(988, 303); f=1016.98, g=0.00
        pushing: root=(993, 290); left=(982, 300); right=(984, 301); f=1016.06, g=0.00
        pushing: root=(993, 290); left=(994, 285); right=(981, 299); f=1014.84, g=0.00
popped off: root=(993, 290); left=(994, 285); right=(981, 299); f=1014.84, g=0.00
        intermediate: root=(993, 290); left=(988, 282); right=(981, 299); f=1014.84, g=0.00
        pushing: root=(993, 290); left=(977, 299); right=(980, 299); f=1015.14, g=0.00
        pushing: root=(993, 290); left=(984, 280); right=(976, 297); f=1014.84, g=0.00
popped off: root=(993, 290); left=(984, 280); right=(976, 297); f=1014.84, g=0.00
        pushing: root=(993, 290); left=(973, 296); right=(976, 297); f=1014.84, g=0.00
        pushing: root=(993, 290); left=(970, 295); right=(973, 296); f=1014.86, g=0.00
        pushing: root=(993, 290); left=(967, 294); right=(970, 295); f=1015.01, g=0.00
        pushing: root=(993, 290); left=(965, 293); right=(967, 294); f=1015.28, g=0.00
        pushing: root=(993, 290); left=(977, 276); right=(965, 293); f=1015.58, g=0.00
        pushing: root=(993, 290); left=(983, 279); right=(979, 277); f=1023.95, g=0.00
popped off: root=(993, 290); left=(973, 296); right=(976, 297); f=1014.84, g=0.00
popped off: root=(993, 290); left=(970, 295); right=(973, 296); f=1014.86, g=0.00
popped off: root=(993, 290); left=(967, 294); right=(970, 295); f=1015.01, g=0.00
popped off: root=(993, 290); left=(977, 299); right=(980, 299); f=1015.14, g=0.00
popped off: root=(993, 290); left=(965, 293); right=(967, 294); f=1015.28, g=0.00
popped off: root=(993, 290); left=(977, 276); right=(965, 293); f=1015.58, g=0.00
        pushing: root=(993, 290); left=(963, 292); right=(965, 293); f=1015.58, g=0.00
        pushing: root=(993, 290); left=(961, 291); right=(963, 292); f=1015.94, g=0.00
        pushing: root=(993, 290); left=(971, 273); right=(959, 289); f=1017.13, g=0.00
...

测试中使用的网格文件来自 cpp 实现，并采用 MIT 许可证。