Forever Loop.

Trouble Busters

Thoughts on Pathfinding – 实现(下)

Thoughts on Pathfinding – 实现(上)的部分中,我们说到了一些不同数据结构对于整个算法复杂度的影响,今天我们将继续列举一些数据结构带来的影响,以及在实际情况中的应用。

哈希表

索引数组使用了大量的内存来保存那些不在 OPEN 集中的节点。一个改变的方法就是使用哈希表,使用哈希函数 h(n) 把图上的每一个节点 n 映射到一个哈希码。让哈希表的大小是 N 的两倍来让发生冲突的可能性降到最小。假设 h(n) 的复杂度是 O(1),因为我们需要搜索整个结构,那么关系检查操作复杂度为 O(1),插入操作复杂度是 O(1),移除操作复杂度是 O(numnodes)。提升优先级操作的复杂度是 O(1)。

伸展树

堆是一种基于树的结构,它的期望时间复杂度是 O(log F)。在 A* 中,当你移出一个节点时由于其他节点需要移动的特性,最佳复杂度以及最差复杂度的变化会比较大。如果我们能够设计一种数据结构使得复杂的的变化趋于可控,哪怕最佳情况下的花费可能会变高。

伸展树就是一种可以自我调整的树形结构。任何对节点的访问都尝试把该节点推到树的顶部。这就产生了一种类似“缓存”的效果:很少被使用的节点将在不影响速度的情况下被慢慢地被移动到树的底部。你的伸展树有多大并不重要,因为操作的所需要的时间与你的“缓存空间”有关。在 A* 中,低花费的节点会被经常使用,高花费的节点不会被长时间使用,所以那些高花费的节点可以移动到树的底部。

在使用了伸展树以后,集合关系检查,插入,移除最佳以及优先级操作的最佳复杂度都是 O(log F),最差复杂度是 O(F)。有代表性的是,伸展树带来的缓存效果能避免最坏情况的发生。迪杰斯特拉算法以及带有低估的启发式函数的 A* 算法却有一些特性让伸展树达不了最优。特别是对于某个节点 n 以及邻居节点 n’ ,理论上当 f(n’) >= f(n) 发生时,插入操作有可能只在树的一侧插入以至整个树失去平衡。尽管我没有可靠的用例。

(更多…)

Thoughts on Pathfinding – 实现(上)

如果不考虑具体的实现代码,A* 算法其实是相当简单的。想象它有一个 OPEN 集和一个 CLOSED 集。其中 OPEN 集保存着等待那些筛选的节点。在最初,OPEN 集只包含一个元素,那就是最开始的起始节点。CLOSED 集包含那些已经被访问过的节点。在最初,CLOSED 集是没有任何内容的。如果用图的方式来理解,那么 OPEN 集就是边境而 CLOSED 集就是那些可访问区域的内部。由于每一个节点同时保存着指向其父节点的指针,所以我们可以知道它是如何被访问到的。

在实际流程中,有一个主要的循环不停地从 OPEN 集中取出最佳的节点 n(拥有最小 f 值的节点)并检查这个节点。如果 n 是最终的目标节点,那么我们的任务就完成了。否则,节点 n 将从 OPEN 集中移除并加入 CLOSED 集。接着检查节点 n 的邻居,节点 n’。如果 n’ 也被访问过,那么我们就不再考虑这个节点(注)。如果 n’ 在 OPEN 集中,那么它以后肯定是会被检查到的,所以我们现在也不需要考虑这个节点(注)。否则,我们把 n’ 加入 OPEN 集中,并把它的父节点设置成 n。通往节点 n’ 的花费 g(n’) 将被设置成 g(n) + movementcost(n, n’)。

你可以在这里查看一些交互式图例的演示。

注:我在这里忽视了一个小小的细节。操作时你其实需要检查节点的 g 值是否变小了,如果变小了,你应该重新 OPEN 它。

注:如果你使用的是始终最小的启发式,这种情况不会发生。在实际设计中,通常使用的是不最小的启发式

你可以在这里看到 Python 的 C++ 的实现方法。

(更多…)

Thoughts on Pathfinding – 启发式

启发式函数h(n)用于告知A*从图中任意一个顶点n到终点的最小预计花费。因此选择(构造)一个好的启发式函数是非常重要的。

启发式在A*中的体现:

启发式可以用来控制A*的表现。

  • 在极端情况下,如果h(n)为0,那么这时只有g(n)在负责A*,于是A*算法就变成了能够保证找到最短路径的Dijkstra算法。
  • 如果h(n)总是低于(或者等于)从n移动到终点的花费,A*依旧能够保证找到最短路径。h(n) 越小,A*拓展的节点越多,使得运行速度变慢。
  • 如果h(n)正好等于从n移动到终点的花费,那么A*将只快速得追踪生成的最短路径并且不再拓展节点。尽管这种情况并不可能常常发生,但是你可以在某些特别的环境下使用这种特性。只要你给了A*所需要的最佳的信息,A*的表现将非常优秀。
  • 在另一个极端情况下,如果h(n)相对于g(n)实在是太高了,那么这时只有h(n)在负责A*,于是A*算法就变成了贪婪最优优先搜索。

于是,我们对于h(n)如何控制A*的表现有了一个有趣的认识:在非常恰好的情况下,我们会非常快速得获得最短路径。但如果h(n)太低了,尽管我们依然能够获得最短路径,可是运行速度却变慢了。反之如果h(n)太高了,我们不一定能够获得最短路径,但是运行速度会变快。

A*的这个属性是非常有用的。举个例子,在某些情况下,你可能宁可需要一个只要“足够了”的路径而不是“完美”的路径。于是此时只要改变g(n)和h(n)之间的平衡,你就可以获得自己想要的结果。

注意:从技术上来讲,如果启发式功能没被使用,那么A*算法应该只被称为A。但是,我将仍然称之为A*因为它们的实现仍然是相同的,而且社区上几乎从来不会特意区分A还是A*。

(更多…)

Thoughts on Pathfinding – A*简介

原文出自:http://theory.stanford.edu/~amitp/GameProgramming/index.html

这是一篇非常适合初学者的算法文章,尽管网络上已经存在一些翻译版本,但是最近作者又对其进行了一些额外的补充,本着分享知识,顺便锻炼一下自己的翻译水平和算法水平的想法,我将结合已有的译文版本以及自己的理解同时配上中文版的插图,竭尽所能为大家带来良好的体验。

A*算法,又称A-Star算法,别名启发式搜索。是一种在静态路网图中求解最短路径的有效的方法之一,在接下来较长的一段时间里我将为大家带来A*算法以及基于A*算法的不同路径搜索策略。

以下,正文开始:

单个对象的移动看上去很简单,但其寻路的过程却是十分复杂的。那么我们为什么说寻路是复杂的呢?请各位考虑以下的这种情况:

如图,假设现在有一个需要进行移动的对象,其初始位置位于图形的底部,最终目标是到达图形的最上端。由于在对象的扫描范围内(以粉红色标识)并没有任何的障碍物,所以对象会一直向上移动。直到在接近图形顶部的时候,对象才发现障碍并改变前进方向,最终沿着红色路径绕过U型障碍物到达终点。但与此相反,拥有路径搜索的对象会在一开始就扫描一块较大的区域(以浅蓝色标识),并生成一条短的多的路径(以蓝色标识),引导对象从一开始就绕过障碍物达到目标。

当然,你也可以改进对象的移动策略,让其可以一开始就避免如上图一样的障碍,或者将障碍物标识成危险的(除非最终目标在其中):

路径搜索让对象从一开始就能计划好前进方向,而不是等到最后一刻才发现问题。但是在加入路径搜索和改进移动策略之间却有一个折衷之处。虽然预先的规划可以获得更好的结果,但是却会消耗较多的时间;尽管改进的移动策略通常会更快但是却有可能在移动过程中卡住。如果路网图经常需要进行变动(比如游戏地图),那么预先的规划的价值就比较 。我推荐复合的使用以上两种策略:路径搜索应用在那些整体规模较大,改动频率较少,路径较长的路网图上;而把改进的移动策略应用在那些整体规模相比较小,改动频率相比较快,路径相比较短的路网图上。

(更多…)