performance - 快速任意角度寻路

Question

我正在为移动设备开发一款游戏，但在决定人工智能使用哪种寻路算法时遇到了一些困难。我的游戏是在尺寸最大为 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倍。使用解释性代码应该可以足够快。

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