performance - 快速任意角度寻路

Question

我正在为移动设备开发一款游戏，在决定为我的 AI 使用哪种寻路算法时遇到了一些困难。我的游戏在最大 200x200 的静态网格 map 上进行。玩家可以向任何方向移动。由于游戏是针对移动设备的，因此算法需要非常快并且可以牺牲最优性。

到目前为止，我已经研究了几种算法:

• 具有 JPS 优化的 A* - 它应该很快，但会找到离散的网格路径
• HPA* - 根据我的预期，它可以比 A* + JPS 更快，但不是最优的并且也能找到离散路径
• Theta* - 这个找到很好的连续路径，但对于远处的点来说太慢了
• Anya ( http://www.grastien.net/ban/articles/hg-icaps13.pdf ) - 最佳和任意角度，但相对未知，我怀疑它会太慢(我没有找到任何基准)

哪种技术最适合我的需求？也许有一些好的和有效的平滑技术可用于发布 JPS/HPA* 找到的进程路径？或者是否有一些在连续路径上运行的快速分层算法？

Answer 1

如评论中所述，在开始任何更复杂的事情之前，应该首先尝试使用标准启发式搜索算法进行适当的预计算、导航网格(或概率路线图)和其他状态空间缩减。

但是，即使您的网格每一帧都在变化，200 x 200 的网格也不会大到无法以每秒 24 帧的速度运行搜索。假设您在游戏 中所做的一切都是寻路，那么您将有大约 40 毫秒一帧。如果您的规划器运行的次数少于(理想情况下少得多)，您就有合理的机会使用蛮力。

衡量任何搜索算法性能好坏的一个很好的衡量标准是它需要扩展以找到解决方案的状态数量。一个(写得很好的)具有良好启发式的 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 x 200 的网格，具有通用图形数据结构、Dijkstra 搜索(而不是 A*)并使用解释性语言，在这个大小的网格上进行规划也只是慢了大约 10 倍(在我的笔记本电脑上)。

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

我的实验表明，将状态空间每个维度的采样减少(多于)两倍，几乎足以自行实现所需的性能。这将为您提供任何简化图中所需状态数量的代表(上限)。