快速任意角度寻路-Java 学习之路

我正在为移动设备开发游戏，并且在决定用于我的AI的寻路算法时遇到一些麻烦 . 我的游戏是在大小高达200x200的静态网格 Map 上播放的 . 玩家可以向任何方向移动 . 由于游戏是针对移动设备的，因此算法需要非常快并且可能牺牲最优性 .

到目前为止我已经看了几个算法：

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

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

1 回答

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

但是，即使您的网格每帧都在变化，200 x 200网格也不会太大，以至于每秒24帧的搜索速度是不可想象的 . 假设你在游戏中所做的一切都是寻路，那么你就有合理的机会只使用蛮力 .

衡量任何搜索算法执行情况的好方法是为了找到解决方案而需要扩展的状态数 . 具有良好启发式的（编写良好的）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 *）并使用解释语言，在这个尺寸网格上的规划只是大约10太慢的因素（在我的笔记本电脑上）） .

移植到像Python这样的解释语言到编译代码的经验法则是，你通常会将性能提升（对于足够大的问题）大约10倍 . 使用解释代码应该足够快 .

我的实验表明，将状态空间的每个维度的采样减少（略大于）两倍，几乎足以实现所需的性能 . 这将为您提供任何简化图中所需状态数的代表（上限） .
回复于 2024-04-23T21:05:13+08:00

快速任意角度寻路

1 回答

相关问题