对于不同的 Grid PathFinding(2D 网格寻路) 算法的性能比较与基准测试

Showcase
#1

对比库 / 算法：

  • PathFinding.js

    这是一个功能全面的 JavaScript 路径查找库，提供了 10 种 PathFinding 算法。

  • RCA 寻路

    作者：tangxuanli2014，其介绍是一个比“A星寻路”和“跳点寻路”更快的寻路算法。

  • AStarRoadSeeker

    作者：tangxuanli2014，其介绍是一个经过极限优化过的 AStar 算法。

  • l1-path-finder

    其介绍基于 Landmarks 和 Visibility Graphs 的预计算。在许多基准测试中，它的查询速度比标准的 JPS 快得多（接近 O(1)）。

  • JPS Plus with Goalbounding

    这是目前已知最快的网格寻路方案之一。 相比传统 A*，JPS+ 通常能快 100 倍到 1000 倍。查询时间几乎可以忽略不计。

  • AStar 优化版算法

    作者：真的很威，其介绍 100W 格的寻路在 5 毫秒以下。

  • QuadtreePathfinding

    一个基于四叉树进行路径查找的寻路库，使用了 A* 算法和 FlowField 流场。

25w 格子性能对比表格（按照寻路耗时从小到大）：

算法 / 库 语言 构建时间 (ms) 寻路时间 (μs) 动态障碍支持 备注
JPS+ w/ GoalBounding C++ 约 25 分钟 0.07 μs No 查表级速度，仅适用于完全静态的大型地图。
l1-path-finder JS 19.61 ms 25.31 μs Maybe 预计算可见性图。
RCA JS 7,713.68 ms 235.31 μs No 预处理时间长，当前不适合动态环境。
QuadtreePathfinding C++ 273 ms 972 μs Yes 四叉树 A* + FlowField。
IDA (PathFinding.js) JS 2.46 ms 2,451.15 μs Yes 内存优化算法。
BestFirst (PathFinding.js) JS 2.13 ms 2,572.31 μs Yes 贪婪算法，速度快但 不保证 路径最短。
BiBestFirst (PathFinding.js) JS 1.83 ms 2,599.59 μs Yes 双向贪婪算法。
AStar Opt Go 8.00 ms 3,199.00 μs Yes 比本表中 JS 标准 A* 实现快约 3.3 倍。
JumpPoint (PathFinding.js) JS 2.54 ms 5,974.99 μs Yes JPS 算法，大地图/空旷地形下的最佳动态选择。
AStar (8-dir, AStarRoadSeeker) JS - 7,637.45 μs Yes 8方向 A*。
AStar (PathFinding.js) JS 5.40 ms 10,852.43 μs Yes 标准 A* 实现。
BiAStar (PathFinding.js) JS 1.77 ms 12,534.19 μs Yes 双向 A*。
BreadthFirst (PathFinding.js) JS 1.76 ms 15,530.24 μs Yes 广度优先，无启发式，效率较低。
Orthogonal JPS JS 1.78 ms 17,911.84 μs Yes 正交 JPS (不允许对角线移动)，效率通常低于普通 JPS。
Dijkstra (PathFinding.js) JS 1.82 ms 27,520.34 μs Yes 需遍历所有节点，效率低。
BiDijkstra (PathFinding.js) JS 1.93 ms 31,069.99 μs Yes 双向 Dijkstra。
AStar (4-dir, AStarRoadSeeker) JS - 1,280,131.81 μs Yes :warning: 疑似异常数据。

原始日志：

bun index.ts

=== load map_500.json & build road nodes ===
build map time (ms): 55.751
baking time (us): 7657918.916
baking time (ms): 7657.932
check FinalPathList:
0  ->   x: 0  y: 0  nodeType:  0
1  ->   x: 27  y: 138  nodeType:  0
2  ->   x: 483  y: 366  nodeType:  0
3  ->   x: 485  y: 369  nodeType:  0
4  ->   x: 486  y: 372  nodeType:  0
5  ->   x: 499  y: 499  nodeType:  0
check SmoothFinalIndex:
 index  0
 index  1
 index  2
 index  3
 index  4
 index  5
x:
x: 0    y: 0
x: 27   y: 138
x: 483  y: 366
x: 485  y: 369
x: 486  y: 372
x: 499  y: 499
--- pair #0 stats ---
seekPath min (us): 192.250
seekPath max (us): 354.500
seekPath avg (us): 235.305
seekPath min (ms): 0.192
seekPath max (ms): 0.351
seekPath avg (ms): 0.235

=== Benchmarking AStarRoadSeeker ===

>>> Config: AStar (None, 4-dir)
--- pair #0 stats ---
seekPath min (us): 1220082.333
seekPath max (us): 1332154.458
seekPath avg (us): 1280131.805
seekPath min (ms): 1220.084
seekPath max (ms): 1332.156
seekPath avg (ms): 1280.133

>>> Config: AStar (None, 8-dir)
--- pair #0 stats ---
seekPath min (us): 6736.542
seekPath max (us): 8661.166
seekPath avg (us): 7637.452
seekPath min (ms): 6.737
seekPath max (ms): 8.662
seekPath avg (ms): 7.638

>>> Config: AStar (Better, 4-dir)
--- pair #0 stats ---
seekPath min (us): 1287185.542
seekPath max (us): 1372853.375
seekPath avg (us): 1302490.929
seekPath min (ms): 1287.186
seekPath max (ms): 1372.854
seekPath avg (ms): 1302.492

>>> Config: AStar (Better, 8-dir)
--- pair #0 stats ---
seekPath min (us): 6987.041
seekPath max (us): 8371.542
seekPath avg (us): 7687.005
seekPath min (ms): 6.987
seekPath max (ms): 8.372
seekPath avg (ms): 7.687

>>> Config: AStar (Best, 4-dir)
--- pair #0 stats ---
seekPath min (us): 1290949.667
seekPath max (us): 1322912.250
seekPath avg (us): 1301948.857
seekPath min (ms): 1290.951
seekPath max (ms): 1322.914
seekPath avg (ms): 1301.950

>>> Config: AStar (Best, 8-dir)
--- pair #0 stats ---
seekPath min (us): 7850.584
seekPath max (us): 9768.334
seekPath avg (us): 8683.347
seekPath min (ms): 7.851
seekPath max (ms): 9.769
seekPath avg (ms): 8.684

=== PathFinding.js AStar ===
construction time (ms): 5.395
baking time (ms): 0.000
--- pair #0 stats ---
seekPath min (us): 9047.000
seekPath max (us): 15341.750
seekPath avg (us): 10852.431
seekPath min (ms): 9.048
seekPath max (ms): 15.347
seekPath avg (ms): 10.854

=== PathFinding.js BestFirst ===
construction time (ms): 2.134
baking time (ms): 0.000
--- pair #0 stats ---
seekPath min (us): 1826.625
seekPath max (us): 6846.250
seekPath avg (us): 2572.305
seekPath min (ms): 1.827
seekPath max (ms): 6.849
seekPath avg (ms): 2.573

=== PathFinding.js BreadthFirst ===
construction time (ms): 1.755
baking time (ms): 0.000
--- pair #0 stats ---
seekPath min (us): 14261.209
seekPath max (us): 18897.208
seekPath avg (us): 15530.243
seekPath min (ms): 14.262
seekPath max (ms): 18.901
seekPath avg (ms): 15.532

=== PathFinding.js Dijkstra ===
construction time (ms): 1.819
baking time (ms): 0.000
--- pair #0 stats ---
seekPath min (us): 25896.417
seekPath max (us): 32080.208
seekPath avg (us): 27520.343
seekPath min (ms): 25.896
seekPath max (ms): 32.083
seekPath avg (ms): 27.522

=== PathFinding.js IDAStar ===
construction time (ms): 2.464
baking time (ms): 0.000
--- pair #0 stats ---
seekPath min (us): 1723.375
seekPath max (us): 5352.959
seekPath avg (us): 2451.146
seekPath min (ms): 1.724
seekPath max (ms): 5.357
seekPath avg (ms): 2.452

=== PathFinding.js JumpPoint ===
construction time (ms): 2.536
baking time (ms): 0.000
--- pair #0 stats ---
seekPath min (us): 5541.417
seekPath max (us): 7484.541
seekPath avg (us): 5974.988
seekPath min (ms): 5.542
seekPath max (ms): 7.486
seekPath avg (ms): 5.975

=== PathFinding.js OrthogonalJumpPoint ===
construction time (ms): 1.777
baking time (ms): 0.000
--- pair #0 stats ---
seekPath min (us): 16837.584
seekPath max (us): 21604.459
seekPath avg (us): 17911.843
seekPath min (ms): 16.839
seekPath max (ms): 21.608
seekPath avg (ms): 17.913

=== PathFinding.js BiAStar ===
construction time (ms): 1.773
baking time (ms): 0.000
--- pair #0 stats ---
seekPath min (us): 11305.042
seekPath max (us): 16305.125
seekPath avg (us): 12534.191
seekPath min (ms): 11.305
seekPath max (ms): 16.308
seekPath avg (ms): 12.535

=== PathFinding.js BiBestFirst ===
construction time (ms): 1.833
baking time (ms): 0.000
--- pair #0 stats ---
seekPath min (us): 1999.459
seekPath max (us): 5554.125
seekPath avg (us): 2599.586
seekPath min (ms): 2.000
seekPath max (ms): 5.556
seekPath avg (ms): 2.600

=== PathFinding.js BiBreadthFirst ===
construction time (ms): 1.782
baking time (ms): 0.000
--- pair #0 stats ---
seekPath min (us): 15564.958
seekPath max (us): 20002.208
seekPath avg (us): 16825.184
seekPath min (ms): 15.566
seekPath max (ms): 20.005
seekPath avg (ms): 16.827

=== PathFinding.js BiDijkstra ===
construction time (ms): 1.931
baking time (ms): 0.000
--- pair #0 stats ---
seekPath min (us): 29218.625
seekPath max (us): 35471.792
seekPath avg (us): 31069.992
seekPath min (ms): 29.220
seekPath max (ms): 35.475
seekPath avg (ms): 31.072

=== l1-path-finder ===
construction time (ms): 19.608
baking time (ms): 0.000
--- pair #0 stats ---
seekPath min (us): 13.625
seekPath max (us): 57.750
seekPath avg (us): 25.309
seekPath min (ms): 0.014
seekPath max (ms): 0.057
seekPath avg (ms): 0.025

go build -trimpath -ldflags='-s -w' -o main_fast ./Main && ./main_fast

NewMapManager Start Time: 1763514668050
NewMapManager End Time: 1763514668058
NewMapManager Time Taken: 8 milliseconds
=== Go PathFind benchmark on mapObstacle_500.json ===
check FinalPathList:
0  ->   x: 0  y: 0  nodeType:  0
1  ->   x: 28  y: 65  nodeType:  0
2  ->   x: 424  y: 455  nodeType:  0
3  ->   x: 428  y: 465  nodeType:  0
4  ->   x: 434  y: 471  nodeType:  0
5  ->   x: 499  y: 499  nodeType:  0
check SmoothFinalIndex:
 index  0
 index  1
 index  2
 index  3
 index  4
 index  5
x:
x: 0    y: 0
x: 28   y: 65
x: 424  y: 455
x: 428  y: 465
x: 434  y: 471
x: 499  y: 499
--- Go PathFind stats ---
min (us): 2743.000
max (us): 4289.000
avg (us): 3199.000
min (ms): 2.000
max (ms): 4.000
avg (ms): 3.000

g+
+ -std=c++11 -O3 main_linux.cpp PrecomputeMap.cp
p JPSPlus.cpp FPUtil.cpp GenericHeap.cpp BucketP
riorityQueue.cpp SimpleUnsortedPriorityQueue.cpp
 UnsortedPriorityQueue.cpp FastStack.cpp Dijkstr
aFloodfill.cpp -o jps_test && ./jps_test

Baking Time (Precompute): 1505583 ms
Pathfinding Time (Average of 100 tests): 0.07 us
Total Pathfinding Time: 0.007 ms
Valid Paths Found: 99/100

CXX = clang++
CXXFLAGS = -std=c++20 -O3 -march=native -DNDEBUG -Wall
INCLUDES = -ISource -I_deps

make benchmark && ./benchmark
编译 benchmark.cpp
链接 benchmark
编译完成！
加载地图数据: map_500.json
地图加载时间: 4 ms
障碍物数量: 9992

构建四叉树地图...
四叉树构建时间: 273 ms

开始寻路测试...
起点: (0, 0)
终点: (499, 499)
寻路时间: 972 μs (0.972 ms)
路径点数: 157
路径代价: 706

========== 性能总结 ==========
地图大小: 500x500
障碍物数量: 9992
构建时间: 273 ms
寻路时间: 0.972 ms
=============================

注：

  • 由于 JPS Plus with Goalbounding 的预处理时间太长（25 分钟以上，有 Issue 表示 1000x1000 的数据甚至需要一周时间），所以放弃了编译成 wasm 进行测试更加公平的想法。
  • 对于为什么没有将 AStar 优化版算法 编译成 wasm 再进行测试，原生测试性能数据结果已经显示出没有必要遂放弃。
  • 所以对参与的语言（Go、C++、JS）都做了相应的最佳场景：由于 JS 有 JIT 机制，所以都编写了预热代码；由于 Go 和 C++ 是编译型语言，所以启用所有优化 flag 对其进行了编译再运行；尽可能关闭日志打印；并展示最大、最小、平均耗时。
  • 地图数据与目标点来自 AStar 优化版算法 项目中的 mapObstacle_500.json。
  • 测试源码
  • 本次基准测试结果仅供参考，非绝对严谨的对比研究，请尽情下载源码并在下方勘误。

总结：

单看性能数据，l1-path-finder 构建时间 19.61 ms，单次寻路平均 25.31 μs 的成绩惊人，并且其仓库有详细的原理解释与论文引用，我认为是首选。

而 tangxuanli2014 的自研 RCA 算法的寻路耗时 236.31 μs 相比标准 AStar 确实快了近 50 倍，虽然其构建时间较长。

真的很威 的 Go 语言实现的 AStar 优化版算法耗时 3199 μs 相比 JS 实现的标准版本 AStar 也快了 3 倍左右。

之所以构建这次基准测试，源自该贴的技术讨论。

只要是技术讨论就是好事，对于性能的讨论，我觉得开源的、客观的、全面的基准数据胜过千言万语。

对于 PathFinding 来说，本帖的基准测试也不够全面、严谨和准确：

  • 虽然我们考虑了构建、寻路时间，考虑了是否支持动态障碍，但其实内存占用，路径质量也是重要的技术选型要点，并没有考虑在内。
  • 各个算法的编程语言不同，且对于像 JS 这种有 JIT 机制的语言来说，不同的写法性能差距非常大。比如由于 RCA 算法的源码是针对其编辑器编写的，需要构造大量的对象，如果转为通用库，可提升的空间还非常大。

很多时候性能优化是取舍问题，任何单一数据的性能提升，往往伴随另一方面性能的下降。

不管是了解算法原理、还是进行全面的测试都很重要，不然只能说，很好，那么代价是什么？

33赞
比“A星寻路”和“跳点寻路”快很多倍的《RCA寻路》介绍，能解决大地图寻路性能不足的问题
比“A星寻路”和“跳点寻路”更快的寻路算法《RCA寻路》介绍，对付大地图寻路的利器。
#2

同种语言下，算法原理决定上限，实现细节技巧影响下限

对比太棒，github收集一波

2赞
#3

只能说，有理有据，很强！ :+1:

#4

我今年自研的RCA寻路看来还是排得上号的，不过我在烘焙阶段没有提前把相关墙角间距离数据提前保存好，每次寻路都重新计算一次两点间的距离，g值的距离计算为了更精确，还用到勾股定理开平方求距离长度这种比较废性能的算法，如果我把这些距离提前算好储存，性能应该还能提升一倍。

还有里面提到不合适动态地形也不是很准确，代码是可以实现区域烘焙的，地形有个障碍损坏了成了平地，可以将损坏前可能存在的墙角的数据清除，再把新墙角和周围墙角链接，区域二次烘焙数据量少不会有太大消耗，这样能支持动态地形。

#5

看来最快的仍然是JPS+算法，不过预处理地图的速度太慢了，看issue 说可以将预处理速度提升25%

#6

在原帖看到了你说可以支持动态地形，所以备注的是当前，RCA 算法的寻路耗时还是很低的，赞。

希望能够继续优化做成通用库，拆除/区域烘焙的功能可以开箱即用，到时候可以对不同算法的动态障碍的清除、添加也做一个基准测试。

#7

l1-path-finder 这个寻路算法，倒是第一次看到，看效果是所有寻路算法中最平衡的寻路了，预处理时间和寻路时间 都很不错

#8

给楼主点赞，收藏一波

#9

我写的优化版A星寻路AStarRoadSeeker在A星寻路性能也是比较同类型A星寻路中性能也比较靠前。

就是设置的4方向寻路类型性能落后，这个是肯定的，四方向寻路每次只检测上下左右4格子，比八方向的检测次数多一倍，对openlist处理的次数也多一倍。

#10

前三的算法里，只有我这个是用JavaScript写的吧，其它都是c++，能排这样高也不错了，如果按我说的把墙角的距离数据提前存储好，再用c++实现一版用来测试效率效率能进一步提升很多。

这个后面有开发者有相关需求时我会加一下接口，实现动态地图。如果Cocos引擎方想内置这个寻路算法我也可以提供技术支持。

#11

https://hit9.dev/post/pathfinding-quadtree-astar

不知道这个能排几号

#12

对了，看看能不能设计一个大死胡同，类似一个方形的大房间，出口只有一个，房间内部有10万个格子，起始点在房间内，向房间外的四周各寻一个目标，看看我写的RCA寻路算法能不能排进第一。

地图数据可以用我写的在线地图编辑器创建，创建一个1000010000尺寸的地图数据，格子大小为2020，这样就有500行*500列=25万格子了。

当初我设计个RCA算法就是为了对付死胡同的，之前写的A星算法就是因为钻入死胡同内，要把死胡同内的的所有格子检测完才能找到出口，导致消耗了很大的寻路深度才能找的目标，所以决心设计一个新算法。

#13

要测试 可以搞迷宫套迷宫套迷宫套迷宫套迷宫套迷宫…

#14

这个可以，复杂的地形才能验证寻路算法是不是最佳。

#15

别只看性能了，你的RCA算法的路径质量感觉问题不小。简单的测试场景都会找到非欧几里得最短路径，找到路径和用曼哈顿距离做启发函数的A*路径一样。

#16

因为我写格子h值确实是用曼哈顿距离估算的，和A星寻路一样。如果你要精准就改成用欧几距离。源码里我封装好这个值的计算，并备注好了，可以手动修改。用曼哈顿距离，跟最短距离的误差也差不了多少，5个格子以内的距离差距。

#17

精华帖！！

#18

l1-path-finder 是 JS 实现的算法，对于 JS 语言本身的运用来说，优化程度也较高。

#19

我模糊记得在那里看到过 ,开方的快捷计算, 好像是用在shader中是还是那里的?

#20

晚上有空我可以补充测试一下。