21 个版本 (7 个破坏性更新)
0.8.1 | 2024年8月6日 |
---|---|
0.7.1 | 2024年7月3日 |
0.5.2 | 2024年3月9日 |
0.4.0 | 2023年6月20日 |
0.2.0 | 2022年11月13日 |
#539 in 游戏开发
每月 1,219 次下载
用于 3 个库 (2 个直接)
4MB
128K SLoC
Polyanya - 导航网格上的无妥协路径查找
Rust 中 Polyanya 的实现!Polyanya 是一种 任意角度路径规划 算法。
使用方法
use glam::Vec2;
use polyanya::*;
// Build a mesh from a list of vertices and polygons
let mesh = Mesh::new(
vec![
Vertex::new(Vec2::new(0., 6.), vec![0, u32::MAX]), // 0
Vertex::new(Vec2::new(2., 5.), vec![0, u32::MAX, 2]), // 1
Vertex::new(Vec2::new(5., 7.), vec![0, 2, u32::MAX]), // 2
Vertex::new(Vec2::new(5., 8.), vec![0, u32::MAX]), // 3
Vertex::new(Vec2::new(0., 8.), vec![0, u32::MAX]), // 4
Vertex::new(Vec2::new(1., 4.), vec![1, u32::MAX]), // 5
Vertex::new(Vec2::new(2., 1.), vec![1, u32::MAX]), // 6
Vertex::new(Vec2::new(4., 1.), vec![1, u32::MAX]), // 7
Vertex::new(Vec2::new(4., 2.), vec![1, u32::MAX, 2]), // 8
Vertex::new(Vec2::new(2., 4.), vec![1, 2, u32::MAX]), // 9
Vertex::new(Vec2::new(7., 4.), vec![2, u32::MAX, 4]), // 10
Vertex::new(Vec2::new(10., 7.), vec![2, 4, 6, u32::MAX, 3]), // 11
Vertex::new(Vec2::new(7., 7.), vec![2, 3, u32::MAX]), // 12
Vertex::new(Vec2::new(11., 8.), vec![3, u32::MAX]), // 13
Vertex::new(Vec2::new(7., 8.), vec![3, u32::MAX]), // 14
Vertex::new(Vec2::new(7., 0.), vec![5, 4, u32::MAX]), // 15
Vertex::new(Vec2::new(11., 3.), vec![4, 5, u32::MAX]), // 16
Vertex::new(Vec2::new(11., 5.), vec![4, u32::MAX, 6]), // 17
Vertex::new(Vec2::new(12., 0.), vec![5, u32::MAX]), // 18
Vertex::new(Vec2::new(12., 3.), vec![5, u32::MAX]), // 19
Vertex::new(Vec2::new(13., 5.), vec![6, u32::MAX]), // 20
Vertex::new(Vec2::new(13., 7.), vec![6, u32::MAX]), // 21
Vertex::new(Vec2::new(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();
// Get the path between two points
let from = Vec2::new(12.0, 0.0);
let to = Vec2::new(3.0, 1.0);
let path = mesh.path(from, to);
assert_eq!(
path.unwrap().path,
vec![
Vec2::new(7.0, 4.0),
Vec2::new(4.0, 2.0),
Vec2::new(3.0, 1.0)
]
);
上面的代码将构建以下网格,绿色标记多边形,红色标记顶点
原始作品
查看 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
这个包似乎生成更多节点,但比 cpp 实现更快。还有一些已知情况需要改进
- 共线优化,当搜索节点根和间隔都在同一直线上时
- 三角形优化,当在三角形多边形中搜索时
- 当交点非常接近顶点时,有时会生成额外的瘦搜索节点
- 搜索起始和结束节点成本更高
使用功能 stats
编译此包将输出几乎与默认 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 许可证下获得。
依赖关系
~11MB
~216K SLoC