A*寻路 -- 更加真实 的路径（一）

对于A*寻路算法，可能是游戏开发者讨论最多的话题之一，很多游戏都会用到它来实现游戏角色的寻路。那么我这篇帖子的价值何在呢？先来看看传统A*算法存在的问题： 1.尴尬的Z型路径          当你在用A*算法实现了角色行走逻辑后，点击一个目标点，虽然你起点和目标点间没有任何障碍物，但角色还TMD蛋疼地进行了Z型行走路线，拐了好多次弯，他丫的那么风骚的走位，以为有人在用狙击枪——瞄准他呢！？ 2.无路可走          当你使用A*算法的时候你可能会发现，当你选择一个不可移动点或者一个被障碍物围住的“岛屿”点作为目标点的时候A*寻路算法会返回false的寻 路结果，通知你它没有找到一条通路，那么此时你怎么办？角色只能站在原地干瞪眼，用户见状可能还以为自己鼠标失灵了呢。“咦？我明明点了那里，这角色咋不 动捏？shit~！” 3.效率不高         你可能在网上或者书籍（如《ActionScript3 动画高级编程》）附赠光盘中下载过A*寻路源码，但运行后发现寻路一次会耗费10毫秒以上，有时候点击一个不可移动点或者一个封闭区域时更会耗费上百毫秒 （因为此时A*算法会遍历全部的格子直至最终无法找到路径）。       这些问题相信很多A*算法使用者都遇到过，但是有一些人因为水平不足，无法继续深究下去，而且网上对此问题的解决方案也是没有任何参考资料可循。另一部 分高手已找到解决之道，但是不愿意开源，以至于那么多年来网上依然缺乏对A*算法这些不足之处的解决之道。其实有时候想想，游戏公司的策划也蛮可怜的，他 的想法很不错，但是程序员往往会以一句“没办法解决”或者“实现不了”就给浇了冷水，唉，可能这也是国内缺乏优秀游戏的原因之一吧。              那么，废话少说，马上开始我们的讲解吧，希望我这篇帖子能给一些迷途的道友们指引一下方向。 更合理的行走方式       对于第一个问题，可以用下图来解释这一现象，当我们选择一个目标点后，即使目标点与起始点间无障碍物存在，A*寻路产生的路径依然是曲折的：

 

 这是由于A*寻路算法是基于格子进行寻路的，因此返回的寻路结果将是一个包含很多格子对象（假设格子对象的类名为Node）的数组，那么在行走的过程中 自然是根据“到达路径数组中一个Node对象的屏幕坐标所在处之后以数组中下一个Node对象的屏幕坐标所在处为下一个目的地”这样的行走过程进行行走 的.

        那么如何避免这种情况的发生呢？我想只在必要的时候调用A*寻路行不行呢？当终点与起点间无任何障碍物的时候直线行走，有障碍物了再进行寻路行走，如下图所示：

 

有想法就有可能，impossible is nothing!         首先要解决的问题是如何判断起点和终点间是否存在障碍物，如果你还记得初中数学中“直线”这一章的内容（很多人看到这里估计要骂一句“holy shit”）的话应该不难想到利用直线的数学特性来解决这一难题。什么？你数学学的东西全TMD忘光了？好吧好吧，还是让贫道来指引一下吧……       先看到下图，我们把两点的中心点用直线连接起来，直线经过的格子都以屎黄色标示（我就喜欢屎黄色），当然，不包含这两个当事点^_^

 

 此时我们就可以依次检查这些大便节点（即用屎黄色填充的点）中是否有一个是障碍点，若有任意一个是障碍点，那么就表示着我这两个当事点之间走直线是行不通地！      说着简单吧？那就做着吧……可是……用代码怎么写啊？说到这，我当初也确实被难住了，用代码实现这一数学思想的确有些困难，那么，我们一步步来吧。      首先我们要想正确地用代码获知这些大便节点并非易事，我首先想到的方案是以一个节点宽度为步长，从起点到终点横向遍历出它们之间连线（假设此连线叫 l ）与每个节点左边缘的交点，见下图：

图上绿色的点就是我们第一步需要求得的线段 l 与起点终点间所有节点的交点了，从图上我们发觉，由于 l 是起点与终点节点中心点的连线，所以第一次遍历时取的步长是半个节点宽，之后遍历的步长则是一个节点宽了。那么求得这些点有什么用呢？从图上看到，只要正 确地得到了这些关键点，之后就可以求每个关键点所毗邻的全部节点以最终得到全部的大便节点，如上图中最左边这个绿色的关键点它所毗邻的两个节点是起点（红 色圆球所在点）以及起点右边那个（1,0）号点。由此，我们可以先把循环体给定下来了，如果假设我们用来计算两点间是否存在障碍物的方法名叫做 hasBarrier,那么它的代码雏形如下：

 

Java代码  

1. /** 
2.  * 判断两节点之间是否存在障碍物  
3.  *  
4.  */                  
5. public function hasBarrier( startX:int, startY:int, endX:int, endY:int ):Boolean  
6. {  
7. //为了运算方便，以下运算全部假设格子尺寸为1，格子坐标就等于它们的行、列号  
8.         /** 循环递增量 */  
9.         var i:Number;         
10.   
11.         /** 循环起始值 */  
12.         var loopStart:Number;  
13.                           
14.         /** 循环终结值 */  
15.         var loopEnd:Number;  
16.   
17.        loopStart = Math.min( startX, endX );  
18.        loopEnd = Math.max( startX, endX );  
19.   
20.        //开始横向遍历起点与终点间的节点看是否存在障碍(不可移动点)   
21.         for( i=loopStart; i distY ? true : false;  
22.   
23. /** 循环递增量 */  
24. var i:Number;  
25.                           
26. /** 循环起始值 */  
27. var loopStart:Number;  
28.                           
29. /** 循环终结值 */  
30. var loopEnd:Number;  
31.                           
32. //为了运算方便，以下运算全部假设格子尺寸为1，格子坐标就等于它们的行、列号  
33. if( loopDirection )  
34. {                                  
35.                                   
36.         loopStart = Math.min( startX, endX );  
37.         loopEnd = Math.max( startX, endX );  
38.                                   
39.         //开始横向遍历起点与终点间的节点看是否存在障碍(不可移动点)   
40.         for( i=loopStart; i