快速任意角度寻路

我正在为移动设备开发一款游戏，并且在决定使用哪种寻路算法时遇到麻烦。我的游戏在尺寸高达200x200的静态网格地图上播放。玩家可以向任何方向移动。由于该游戏是针对移动设备的，因此该算法需要非常快并且可以牺牲最优性。快速任意角度寻路

我在几种算法看起来到目前为止：

A *与JPS优化 - 这就是所谓快，但发现离散网格路径
HPA * - 从我所期望的，它可以更快该A * + JPS，但不是最佳的，并认为离散路径以及
西塔* - 这一发现好的连续的路径，但对于远点
安亚（http://www.grastien.net/ban/articles/hg-icaps13.pdf）太慢 - 最佳和任何角度，但相对未知，我怀疑它会太慢（我没有找到任何基准）

什么技术最适合我的需求？也许有一些好的和有效的平滑技术可以用来发布由JPS/HPA *发现的进程路径？还是有一些快速分层算法在连续路径上运行？

来源

2014-07-14 Matis

“静态”是指您可以预先计算路径数据还是您的地图不是静态的？ – biziclop

地图永不改变，所以预先计算绝对是一种选择。 – Matis

我真的没有任何进一步的建议。 :)好吧，那是谎言，如何将你的地图划分为“视线可到达”区域的图形？在这些区域内，您可以采取直接路线，并且可以使用更小的连接图进行区域之间的移动。 – biziclop

正如评论中指出的那样，在开始更复杂的任何事情之前，应该首先尝试使用标准的启发式搜索算法来适当地进行预计算，导航网格（或概率路线图）和其他状态空间的减少。

但是，即使您的网格每帧都在变化，200乘200网格并不是那么大，以至于每秒24帧的搜索都是不可想象的。假设你在游戏中进行的所有操作都是寻路，那么每帧大约需要40ms。如果你的计划者的运行次数少于（而且理想情况下少得多），那么你就有了使用暴力的合理机会。

衡量任何搜索算法执行效果或好坏的一个好方法就是需要扩展以查找解决方案的状态数量。具有良好启发式的（良好编写的）A *算法应该探索最小数量的状态，并且应该胜过任何需要访问每个状态的搜索。考虑到这一点，Dijkstra搜索应该比A *慢（因为它扩展了所有状态）。这意味着Dikstra搜索是计划A *所需时间的近似上限，即使在最糟糕的情况下，也很难构建）。

为了证明这不是不合理的，这里有一小段Python代码来填充八连接网格（合理的任意角度规划的一阶近似）和一些相关的性能结果。

import networkx as nx 
import itertools 
import numpy 
import matplotlib.pyplot as plt 

def grid_2d_8_connected(n, m): 
    G = nx.Graph() 
    xs = range(n) 
    ys = range(m) 
    dxs = [-1, 0, 1] 
    dys = [-1, 0, 1] 
    ds = [(dx, dy) for dx, dy in itertools.product(dxs, dys)] 
    ds = [ d for d in ds if d != (0,0) ] 
    for x, y in itertools.product(xs, ys): 
     G.add_node((x, y)) 
    nodes = set(G.nodes()) 
    for x, y in itertools.product(xs, ys): 
     for dx, dy in ds: 
      sprime = (x+dx, y+dy) 
      if sprime in nodes: 
       G.add_edge((x, y), sprime) 
    return G

运行快速性能测试：

G = grid_2d_8_connected(200, 200) 
%timeit nx.single_source_dijkstra_path_length(G, (0, 0)) 
1 loops, best of 3: 270 ms per loop

而且在略小格：

G = grid_2d_8_connected(75, 75) 
%timeit nx.single_source_dijkstra_path_length(G, (0, 0)) 
10 loops, best of 3: 35.6 ms per loop

这表明，即使200通过200网格，与通用图形数据结构，Dijkstra搜索（而不是A *）和使用解释型语言，计划在这个大小的网格上只是一个太慢的因素（在我的笔记本电脑上）。

将解释型语言（如Python）转换为编译代码的经验法则是，您通常可以将性能（对于足够大的问题）提高约10倍。使用解释代码应该足够快。

我的实验表明，将状态空间的每个维度的采样减少（略多于）两倍，几乎足以实现所需的性能。这将给你一个你想要的状态数量的代表（上限）在任何简化图中。

来源

2014-07-16 13:24:05

快速任意角度寻路

回答

相关问题