*寻路需要很长的时间,需要快捷键

所以我有一个游戏,玩家可以移动一个网格108 X 192大。 它使用简单的A *path查找algorithm来移动。 不幸的是,在0.03秒之后,它只能看到大约300个节点,这意味着如果终止节点被阻止通过,它将花费大约2秒的时间来实现这一点(A *没有优化返回失败,当打开的列表是空荡荡的,什么时候检查了每一条路,意识到没有办法解决)。 我想要至less20帧!

我没有使用任何优化,网格中的每个点都是布尔型的阻塞或未阻塞。 任何方法来加速?

例如,在Dota 2(一个受欢迎的MOBA)中,地图上充满了树木和悬崖,15,000个游戏单位大小为15,000个游戏单位,但是只要你点击你想要的位置,角色就会开始移动。 他们如何做到这一点,这是我失踪的一件简单的事情?

Solutions Collecting From Web of "*寻路需要很长的时间,需要快捷键"

正如你自己所说的,你还没有诉诸优化。 所以是的,有很多方法来加速。

但是,既然你是一般性的谈话,我会坚持我认为是改善寻路performance的最佳指导:减小问题的规模。 换句话说,lesssearch,search更小。

1a)一方面,lesssearch意味着确保只有一些代理一次searchpath。 但是,我想你的回答是,你并没有与许多代理人path寻找斗争,所以…

1b)…一方面在较小的区域search意味着减less在path寻找步骤中必须评估的可能path。 为此,经常使用空间分区。 场景被划分为多个区域,以便一次可以在较小的search空间中执行pathsearch。 此外,通过划分场景,存在本质上实现分级path寻找的searchalgorithm,例如HPA *和HAA *。

划分空间的想法如下。 你将把地图集中成区域。 当代理人必须find一条path时,首先会在更高层次上进行path寻找,也就是从哪个区域去找哪个区域。 他们将在当前区域内find它的path。当它改变区域时,将执行另一个区域内path查找。

有关这方面的更多信息和更好的可视化,请参阅以下问题的答案之一: 对于一个非常大的过程生成的环境,最适合的path查找解决scheme是什么?

0.03秒内的300个节点意味着每秒只有10,000个节点,这似乎相当缓慢。 在实现分层分区等更复杂的方法之前,我要做的第一件事是优化代码。

  1. 运行分析器 ,找出哪些function使用最多的时间。 时间的stream逝往往让人感到惊讶,当你认为速度慢的时候,最好不要慢下来,这是浪费你的时间。
  2. 检查正在使用的数据结构你应该没有通过打开/closures套循环! 开放集是一个优先级队列,应该使用优先级队列数据结构,它可以在不search整个数据结构的情况下find最佳节点。 我通常使用二进制堆。 封闭集既可以作为内部结构实现,也可以作为每个节点上的布尔标志来实现,也可以作为一个集合(哈希表或数组)来作为外部结构实现。 如果你想看看,我有C + +和Python(和不完整的C#代码) 示例代码 。
  3. 如果terminal节点被阻塞是一个常见的问题, 连接组件 (“岛ID”)是非常简单和快速实施。 你预处理地图一次。 循环遍历每个节点。 如果它已经有一个岛ID,然后跳过它。 如果没有,则先从该节点运行宽度或深度优先search,并用新的岛ID标记所有访问的节点。 当你运行A *时,你将首先比较岛ID。 如果他们不同,你会立即知道没有path。 (注意:如果所有的边都是双向的,这只是有用的,单向边会使这变得复杂。
  4. 只有当你已经使用好的数据结构,而系统仍然太慢,我会建议调查层次结构或航点或收缩层次或更先进的技术。 15000×15000地图可能需要这样的东西,但你的108×192网格不应该。

大大加快A *速度的最快方法是:

该algorithm经常testing节点是否处于OPENCLOSED集。 这个testing是O(1)是至关重要的。 你不想遍历整个集合,看看它是否在那里。

每个节点的两个布尔值要快得多,它会告诉你一个节点是否处于OPENCLOSED集。

单凭这种改变会让你的执行速度快许多倍。

但是,是的,你确实提出了一个很好的观点:如果目标不可达,那么每个可到达的节点都会被不幸地遍历。 所以无法访问的节点对于path查找来说是最昂贵的。