用二叉平衡树法实现快速A*算法

小小C

至于什么是A*算法,这里就不再重述了.A*算法里的重点,影响算法速度的重要一步就是搜索OPEN表的最小值,普通的A*用链表建立OPEN表,求最小值时,要遍历整个链表.而如果用平衡二叉树代替链表,可以省去时间,并且寻路越远,越省时.

什么是二叉平衡树呢?其实是一个数组,数组的头元素A0为树根,A1,A2是A0的子节点,A3,A4是A1的子节点,以此类推.

这样,每加入一个子节点时,就和它的父节点比较,如果它比父节点小,则两者交换.这样,就不用搜索整个树,而只搜索了树的一半,但包证了树根是整个树最小的节点.如果要取出树根,那么用最末的一个元素代替树根,反向判断.

如果知道一个父节点为N,则它的两个子节点为2*N和2*N+1.
如果知道一个子节点为s,则它的父节点为( s - ( s % 2 ) ) >> 1

这个算法日本人早就提出,很多人都说它行不通,我做了一个演示证明它是可行的,演示可以在我的网站   http://mysticc.icpcn.com下载

Jeminai

小小C: 用二叉平衡树法实现快速A*算法

很多人都说它行不通...

谁说行不通啊？理由是什么？
这个方法我一直在用啊。

FlyMagic

分析问题太浅了，不是一个东西做出来能用他就是行得通的。
还要分析它在各个情况下的表现，做出综合的判断。

Enigmaya

光做出来不一定就能证明是可行的。

得和其他的又一个比较才有说服力。

http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html

有各种方法的比较。但一般都推荐堆排序。

write2murphy

哈哈，看见小小C的文章了，我来支持顶一下！

月下临风

建议用stl的heep最小堆做,写一个A*的算法,只用十几行代码.

小小C

月下临风: Re:用二叉平衡树法实现快速A*算法

建议用stl的heep最小堆做,写一个A*的算法,只用十几行代码.

不会吧,这么容易?你还要考虑地图的结构吧,地图有45度的TILE,或是纵版,横版方格拼起的.还要考虑精灵类的结构吧.还有,OPEN表满了但还没找到目的点怎么办?目的点是不可走的怎么办?

月下临风

我说的是通用性算法,而且还是核心的部分,不包括其他的.
当然解决具体问题不可能10多行出来的.
就像你说的目标点不可走,就有不少种做法.
如果是我,我会预处理,建一个map数据结构mark所有图的连通性,根据图的连通性原则可以直接判断出,出发地是否可以到达目的地.但是如果场景的物体会经常变化的,导致连通性也会随着变化,那么要经常更新这个map了.
还有A*在处理静态场景上的寻路是不错,不过如果场景是动态的A*就很没用.
从目前的游戏来看,大部分的搜索深度是很浅的,也就是说他的OPEN表存的数据是不多的,只能是走着瞧,不可能用A*直接找到最短的路,这样如果地图很大就挂了.一般最好用IDA*.
只要领悟A*,或者其他什么*的思想就行了,不管2D,斜45,还是3D都是一样的.

月下临风

偏题了
找出估价权值最小的结点,还是用stl的最少堆最方便.效率又高,0(logN),何必吃饱了撑着去写什么平衡二叉树?

write2murphy

我顶，继续顶！顶8楼的"只要领悟A*,或者其他什么*的思想就行了,不管2D,斜45,还是3D都是一样的."
偶封装的A*就可以处理2D和3D的地图，偶们关心的是算法，不是使用方法！