A*寻路之路径优化（一）

2023-05-16

目前项目中寻路是通过A*来实现的，实际应用时候发现存在以下问题：

1.生成的Z型折线路径

用A*算法得到的路径，在起点和目标点间没有任何障碍物的情况下路径仍可能是 Z型折线型。
2.目标点无法到达情况
使用A*算法，选择一个不可移动点或者一个被障碍物围住的“岛屿”点作为目标点的时候A*寻路算法会返回false的寻路结果，通知你它没有找到一条通路，此时角色会停止不动，而不是移动到距离目标点最近的可移动点。
3.效率不高
A*算法会遍历全部的格子直至最终找到路径，遍历全局，效率较低。

1,更合理的行走方式
对于第一个问题，可以用下图来解释这一现象，当我们选择一个目标点后，即使目标点与起始点间无障碍物存在，A*寻路产生的路径依然是曲折的：

这是由于A*寻路算法是基于格子进行寻路的，（当前也有使用三角网格进行寻路的但是会引入新的问题如绕远路，绕大圈的情况）因此返回的寻路结果将是一个包含很多格子对象（假设格子对象的类名为Node）的数组，那么在行走的过程中自然是根据“到达路径数组中一个Node对象的屏幕坐标所在处之后以数组中下一个Node对象的屏幕坐标所在处为下一个目的地”这样的行走过程进行行走的.

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

首先要解决的问题是如何判断起点和终点间是否存在障碍物，先看到下图，我们把两点的中心点用直线连接起来，直线经过的格子都以黄色标示，当然，不包含这两个当事点

此时我们就可以依次检查这些绿色的点中是否有一个是障碍点，若有任意一个是障碍点，那么就表示着我这两个当事点之间走直线是行不通地！
，我首先想到的方案是以一个节点宽度为步长，从起点到终点横向遍历出它们之间连线（假设此连线叫 l ）与每个节点左边缘的交点，见下图：

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

/**
* 判断两节点之间是否存在障碍物
*
*/
public function hasBarrier( startX:int, startY:int, endX:int, endY:int ):Boolean
{
//为了运算方便，以下运算全部假设格子尺寸为1，格子坐标就等于它们的行、列号
/** 循环递增量 */
var i:Number;
/** 循环起始值 */
var loopStart:Number;
/** 循环终结值 */
var loopEnd:Number;
loopStart = Math.min( startX, endX );
loopEnd = Math.max( startX, endX );
//开始横向遍历起点与终点间的节点看是否存在障碍(不可移动点)
for( i=loopStart; i<=loopEnd; i++ )
{
//由于线段方程是根据终起点中心点连线算出的，所以对于起始点来说需要根据其中心点
//位置来算，而对于其他点则根据左上角来算
if( i==loopStart )i += .5;
............
if( i == loopStart + .5 )i -= .5;
}
}

但是这样根据x值横向遍历会不会漏掉一些节点呢？答案是肯定的，看下图这种情况

按上面我所说的横向遍历的规则，第一次遍历我求得了上图左边这个绿色点，第二次遍历求得了右边这个绿色点，在求得此二关键点后求出它们各自所毗邻的节点并在图上以屎黄色标示，发现遍历结果中漏掉了中间这块节点。
处理时，我们倾斜角大于45度角的情况（此时起点与终点间纵向距离大于横向距离）使用纵向遍历，而对倾斜角小于45度的情况（此时起点与终点间横向距离大于纵向距离）使用横向遍历，这样就不会漏掉任何一个点了。

oh, yeah, perfect!
既然遍历的方向要根据情况而定，所以原先代码将更改为下面这样：

//根据起点终点间横纵向距离的大小来判断遍历方向
var distX:Number = Math.abs(endX - startX);
var distY:Number = Math.abs(endY - startY);
/**遍历方向，为true则为横向遍历，否则为纵向遍历*/
var loopDirection:Boolean = distX > distY ? true : false;
/** 循环递增量 */
var i:Number;
/** 循环起始值 */
var loopStart:Number;
/** 循环终结值 */
var loopEnd:Number;
//为了运算方便，以下运算全部假设格子尺寸为1，格子坐标就等于它们的行、列号
if( loopDirection )
{
loopStart = Math.min( startX, endX );
loopEnd = Math.max( startX, endX );
//开始横向遍历起点与终点间的节点看是否存在障碍(不可移动点)
for( i=loopStart; i<=loopEnd; i++ )
{
//由于线段方程是根据终起点中心点连线算出的，所以对于起始点来说需要根据其中心点
//位置来算，而对于其他点则根据左上角来算
if( i==loopStart )i += .5;
…………
if( i == loopStart + .5 )i -= .5;
}
}
else
{
loopStart = Math.min( startY, endY );
loopEnd = Math.max( startY, endY );
//开始纵向遍历起点与终点间的节点看是否存在障碍(不可移动点)
for( i=loopStart; i<=loopEnd; i++ )
{
if( i==loopStart )i += .5;
…………
if( i == loopStart + .5 )i -= .5;
}
}

好了，接下来该做的就是决定循环体中应该执行的逻辑了。

要求得绿点的 y 值，只需要将它们的 x 值代入线段 l 的直线方程（假设直线方程为 y = ax + b ）中即可。所以接下来要做的事情就是先求出这个直线方程中的未知数 a 与 b 的值。
既然我们已知了该线段两段的端点坐标，把它们的坐标值代入方程即可求得未知数 a 与 b。我把这一数学求解方程的代码放在一个数学类MathUtil.as中，代码如下：

package
{
import flash.geom.Point;
/**
* 寻路算法中使用到的数学方法
*
*/
public class MathUtil
{
/**
* 根据两点确定这两点连线的二元一次方程 y = ax + b或者 x = ay + b
* @param ponit1
* @param point2
* @param type 指定返回函数的形式。为0则根据x值得到y，为1则根据y得到x
*
* @return 由参数中两点确定的直线的二元一次函数
*/
public static function getLineFunc(ponit1:Point, point2:Point, type:int=0):Function
{
var resultFuc:Function;
// 先考虑两点在一条垂直于坐标轴直线的情况，此时直线方程为 y = a 或者 x = a 的形式
if( ponit1.x == point2.x )
{
if( type == 0 )
{
throw new Error("两点所确定直线垂直于y轴，不能根据x值得到y值");
}
else if( type == 1 )
{
resultFuc = function( y:Number ):Number
{
return ponit1.x;
}
}
return resultFuc;
}
else if( ponit1.y == point2.y )
{
if( type == 0 )
{
resultFuc = function( x:Number ):Number
{
return ponit1.y;
}
}
else if( type == 1 )
{
throw new Error("两点所确定直线垂直于y轴，不能根据x值得到y值");
}
return resultFuc;
}
// 当两点确定直线不垂直于坐标轴时直线方程设为 y = ax + b
var a:Number;
// 根据
// y1 = ax1 + b
// y2 = ax2 + b
// 上下两式相减消去b, 得到 a = ( y1 - y2 ) / ( x1 - x2 )
a = (ponit1.y - point2.y) / (ponit1.x - point2.x);
var b:Number;
//将a的值代入任一方程式即可得到b
b = ponit1.y - a * ponit1.x;
//把a,b值代入即可得到结果函数
if( type == 0 )
{
resultFuc = function( x:Number ):Number
{
return a * x + b;
}
}
else if( type == 1 )
{
resultFuc = function( y:Number ):Number
{
return (y - b) / a;
}
}
return resultFuc;
}
}
}

这个方法将会根据两个参数点求得它们连线的直线方程并返回一个函数实例，如果你第三个参数type传入的是0，那么将会得到一个类似于 y = ax + b这样的函数实例，假设此实例名为fuc，那么你可以传一个 x 值作为 fuc 的参数，它会返回给你一个在直线 l 上横坐标等于此 x 值的点的纵坐标 y = fuc( x ); 如果你第三个参数传入的是1，那么将会得到一个类似于 x = ay + b这样的函数实例，可以根据你传入的 y 值得到直线 l 上纵坐标为 y 的点的横坐标 x = fuc( y )。设置type这样一个参数是因为我们可能横向遍历也可能纵向遍历，横向遍历时我需要根据 x 值来求 y，纵向遍历时则相反。
好了，有了这个方法以后我们要求出绿色的关键点应该是没有问题了，接下来要做的就是根据一个关键点求出它所毗邻的节点有几个，它们分别是哪些。一般来说，最多可能有4个节点共享一个关键点，最少则是一个节点拥有一个关键点：

如果假设一个节点的宽、高均为1，那么如果一个点的 x 、y 值都不是整数那就可以判定它只可能由一个节点拥有；如果 x 值为整数则表示此点会落在两个节点横向的临边上；如果 y 值为整数则表示此点会落在两个节点纵向的临边上。由此可得getNodesUnderPoint方法：

/**
* 得到一个点下的所有节点
* @param xPos 点的横向位置
* @param yPos 点的纵向位置
* @param exception 例外格，若其值不为空，则在得到一个点下的所有节点后会排除这些例外格
* @return 共享此点的所有节点
*
*/
public function getNodesUnderPoint( xPos:Number, yPos:Number, exception:Array=null ):Array
{
var result:Array = [];
var xIsInt:Boolean = xPos % 1 == 0;
var yIsInt:Boolean = yPos % 1 == 0;
//点由四节点共享情况
if( xIsInt && yIsInt )
{
result[0] = getNode( xPos - 1, yPos - 1);
result[1] = getNode( xPos, yPos - 1);
result[2] = getNode( xPos - 1, yPos);
result[3] = getNode( xPos, yPos);
}
//点由2节点共享情况
//点落在两节点左右临边上
else if( xIsInt && !yIsInt )
{
result[0] = getNode( xPos - 1, int(yPos) );
result[1] = getNode( xPos, int(yPos) );
}
//点落在两节点上下临边上
else if( !xIsInt && yIsInt )
{
result[0] = getNode( int(xPos), yPos - 1 );
result[1] = getNode( int(xPos), yPos );
}
//点由一节点独享情况
else
{
result[0] = getNode( int(xPos), int(yPos) );
}
//在返回结果前检查结果中是否包含例外点，若包含则排除掉
if( exception && exception.length > 0 )
{
for( var i:int=0; i<result.length; i++ )
{
if( exception.indexOf(result[i]) != -1 )
{
result.splice(i, 1);
i--;
}
}
}
return result;
}

万事具备，只欠东风了，最后把之前写的两个方法用到hasBarrier方法的循环体中去。下面是完整的hasBarrier方法代码：

/**
* 判断两节点之间是否存在障碍物
*
*/
public function hasBarrier( startX:int, startY:int, endX:int, endY:int ):Boolean
{
//如果起点终点是同一个点那傻子都知道它们间是没有障碍物的
if( startX == endX && startY == endY )return false;
//两节点中心位置
var point1:Point = new Point( startX + 0.5, startY + 0.5 );
var point2:Point = new Point( endX + 0.5, endY + 0.5 );
//根据起点终点间横纵向距离的大小来判断遍历方向
var distX:Number = Math.abs(endX - startX);
var distY:Number = Math.abs(endY - startY);
/**遍历方向，为true则为横向遍历，否则为纵向遍历*/
var loopDirection:Boolean = distX > distY ? true : false;
/**起始点与终点的连线方程*/
var lineFuction:Function;
/** 循环递增量 */
var i:Number;
/** 循环起始值 */
var loopStart:Number;
/** 循环终结值 */
var loopEnd:Number;
/** 起终点连线所经过的节点 */
var passedNodeList:Array;
var passedNode:Node;
//为了运算方便，以下运算全部假设格子尺寸为1，格子坐标就等于它们的行、列号
if( loopDirection )
{
lineFuction = MathUtil.getLineFunc(point1, point2, 0);
loopStart = Math.min( startX, endX );
loopEnd = Math.max( startX, endX );
//开始横向遍历起点与终点间的节点看是否存在障碍(不可移动点)
for( i=loopStart; i<=loopEnd; i++ )
{
//由于线段方程是根据终起点中心点连线算出的，所以对于起始点来说需要根据其中心点
//位置来算，而对于其他点则根据左上角来算
if( i==loopStart )i += .5;
//根据x得到直线上的y值
var yPos:Number = lineFuction(i);
//检查经过的节点是否有障碍物，若有则返回true
passedNodeList = getNodesUnderPoint( i, yPos );
for each( passedNode in passedNodeList )
{
if( passedNode.walkable == false )return true;
}
if( i == loopStart + .5 )i -= .5;
}
}
else
{
lineFuction = MathUtil.getLineFunc(point1, point2, 1);
loopStart = Math.min( startY, endY );
loopEnd = Math.max( startY, endY );
//开始纵向遍历起点与终点间的节点看是否存在障碍(不可移动点)
for( i=loopStart; i<=loopEnd; i++ )
{
if( i==loopStart )i += .5;
//根据y得到直线上的x值
var xPos:Number = lineFuction(i);
passedNodeList = getNodesUnderPoint( xPos, i );
for each( passedNode in passedNodeList )
{
if( passedNode.walkable == false )return true;
}
if( i == loopStart + .5 )i -= .5;
}
}
return false;
}

通常人物的行走是由鼠标点击触发的，那么在鼠标点击事件的处理函数中，需要根据点击的目的地来选择是否启用A*寻路算法来进行寻路。

private function onGridClick(event:MouseEvent):void
{
//起点是玩家对象所在节点位置，终点是鼠标点击的节点
var startPosX:int = Math.floor(_player.x / _cellSize);
var startPosY:int = Math.floor(_player.y / _cellSize);
var endPosX:int = Math.floor(mouseX / _cellSize);
var endPosY:int = Math.floor(mouseY / _cellSize);
//判断起终点间是否存在障碍物，若存在则调用A*算法进行寻路，通过A*寻路得到的路径是一个个所要经过的节点数组；否不存在障碍则直接把路径设置为只含有一个终点元素的数组
var hasBarrier:Boolean = _grid.hasBarrier(startPosX, startPosY, endPosX, endPosY);
if( hasBarrier )
{
_grid.setStartNode(startPosX, startPosY);
_grid.setEndNode(endPosX, endPosY);
findPath();
}
else
{
_path = [_grid.getNode(endPosX, endPosY)];
_index = 0;
addEventListener(Event.ENTER_FRAME, onEnterFrame);//开始行走
}
}
private function findPath():void
{
var astar:AStar = new AStar();
if(astar.findPath(_grid))
{
_path = astar.path;
_index = 0;
addEventListener(Event.ENTER_FRAME, onEnterFrame);//开始行走
}
}

另一种思路：

MMO游戏中角色行走的概念中其实是没有格子的。游戏中行走其实是根据给出的路径中的两点，判断朝向，播放相应的行走动画，移动（可以是地图动人不动，或人动地图不动）。

为了保证精度，我们使用的格子很小，得到的路径上点也就很多了。实际行走中将会发现角色行走时会不停抖动，其实是因为格子太小，路径点太近，人物不停在改变朝向。

只要保证路径上两点间的距离足够远就行了。我们需要在A*给出的由格子序列组成的路径上进行过滤。

取其中两个格子，判断两个点之间有无不可行走区域，如果没有，这两个格子之间的格子都可以从路径中移除。

例子：格子12345678910。

我们采用分治的方法，先取中间点5，看1-5和5-10直线连接上有没有不可行走区域。

如可以则把两个端点加入路径，中间的格子去掉，不可以就继续对两个端点之间进行分治。

private function getRoute(startX : int,startY : int,endX : int,endY : int,aStarPath : Array,wall:Wall):void {
var xDistance : int = endX - startX;
var yDistance : int = endY - startY;
var distance : int = Math.round(Math.pow(xDistance * xDistance + yDistance * yDistance, 1 / 2));
var i : int;
var tempX : int,tempY : int;
var flag : Boolean = false;
var isExistStart : Boolean = false;
var isExistEnd : Boolean = false;
var note : Array;
// 这一步作为递归的出口
for (i = 1;i < distance;i += KEY_POINT_LENGTH) {
tempX = Math.round(startX + i * xDistance / distance);
tempY = Math.round(startY + i * yDistance / distance);
if (wall.isWall(tempX,tempY)) {
flag = true;
break;
}
}
// 如果没有障碍物，则将起始点加入到新路径并返回
if (! flag) {
for (i = 0;i < route.length;i ++) {
note = route[i];
if (note[ 0] == startX && note[ 1] == startY) isExistStart = true;
if (note[ 0] == endX && note[ 1] == endY) isExistEnd = true;
}
if (! isExistStart) route.push([startX,startY]);
if (! isExistEnd) route.push([endX,endY]);
return;
}
var tmpDistance : Number;
var a : int,b : int,c : int,tmpX : int = startX,tmpY : int = startY,tmpPos : int;
a = endY - startY;
b = startX - endX;
c = endX * startY - startX * endY;
tmpPos = 0;
tmpDistance = 0;
distance = 0;
var length: int = aStarPath.length;
//有碰撞点则选择高度最大的点为关键点
for (i = 0;i < length;i ++) {
note = aStarPath[i];
tmpDistance = Math.abs((a * note[ 0] + b * note[ 1] + c) / Math.sqrt(a * a + b * b));
if (distance < tmpDistance) {
distance = tmpDistance;
tmpX = note[ 0];
tmpY = note[ 1];
tmpPos = i + 1;
}
}
//防止栈溢出
if (distance == 0){
return;
}
//如果起始点不在路径中将起始点加入新路径
for (i = 0;i < route.length;i ++) {
note = route[i];
if (note[ 0] == startX && note[ 1] == startY) isExistStart = true;
}
if (! isExistStart) route.push([startX,startY]);
//递归计算关键坐标并加入到路径数组
var tmpFirstArray : Array = new Array();
for (i = 0;i < tmpPos;i ++) {
tmpFirstArray[i] = aStarPath[i];
}
var tmpLastArray : Array = new Array();
for (i = tmpPos;i < length;i ++) {
tmpLastArray[i - tmpPos] = aStarPath[i];
}
if (tmpFirstArray.length > 0) getRoute(startX,startY,tmpX,tmpY,tmpFirstArray,wall);
if (tmpLastArray.length > 0) getRoute(tmpX,tmpY,endX,endY,tmpLastArray,wall);
//如果目标点不在路径中，将目标点坐标加入到新的路径
for (i = 0;i < route.length;i ++) {
note = route[i];
if (note[ 0] == endX && note[ 1] == endY) isExistEnd = true;
}
if (! isExistEnd) route.push([endX,endY]);
return;
}

2.让点击障碍物或者死路时可以走到离障碍物最近的点
我查了一下，网上给出的所有A*寻路算法都忽略了这点，即点击一个障碍物或死路（四周被障碍物环绕）时寻路者/玩家就停在原地不动了，这样会让玩家有受挫、受限感，或者产生“你这个游戏有bug”的错觉。那么对于一些斜45度等角投影视角类游戏来说你玩家站原地不动是没有多大关系的，谁叫你点了一个明显的障碍物格呢（如河流、山岭、建筑物等）

但若是对一些横版纯2D游戏来说，采用原始A*寻路这种方式就有点不能接受了……

那么要想解决这个问题，首先得找到问题的源头出在哪里，打开《动画高级教程》中提供的A*寻路源码，寻路部分代码如下：

public function search():Boolean
{
var node:Node = _startNode;
while(node != _endNode)
{
var startX:int = Math.max(0, node.x - 1);
var endX:int = Math.min(_grid.numCols - 1, node.x + 1);
var startY:int = Math.max(0, node.y - 1);
var endY:int = Math.min(_grid.numRows - 1, node.y + 1);
for(var i:int = startX; i <= endX; i++)
{
for(var j:int = startY; j <= endY; j++)
{
var test:Node = _grid.getNode(i, j);
if(test == node ||
!test.walkable ||
!_grid.getNode(node.x, test.y).walkable ||
!_grid.getNode(test.x, node.y).walkable)
{
continue;
}
var cost:Number = _straightCost;
if(!((node.x == test.x) || (node.y == test.y)))
{
cost = _diagCost;
}
var g:Number = node.g + cost * test.costMultiplier;
var h:Number = _heuristic(test);
var f:Number = g + h;
if(isOpen(test) || isClosed(test))
{
if(test.f > f)
{
test.f = f;
test.g = g;
test.h = h;
test.parent = node;
}
}
else
{
test.f = f;
test.g = g;
test.h = h;
test.parent = node;
_open.push(test);
}
}
}
for(var o:int = 0; o < _open.length; o++)
{
}
_closed.push(node);
if(_open.length == 0)
{
trace("no path found");
return false
}
_open.sortOn("f", Array.NUMERIC);
node = _open.shift() as Node;
}
buildPath();
return true;
}

了解A*算法的人都知道，所有可能被设置为路径的格子都会被放入开放列表_open中去，但是你再看16-19行这个判断：

if(test == node ||
!test.walkable ||
!_grid.getNode(node.x, test.y).walkable ||
!_grid.getNode(test.x, node.y).walkable)
{
continue;
}

这个判断会把walkable为false的点（即障碍物点）以及不可穿越点（即与上一路径点处于对角线却不可直接从对角线上通过的点，如下图）

直接用 continue 语句给跳过了，这样的话不论是障碍物点还是不可穿越点都永远没有资格被加入到开启列表中去，那自然就不可能成为路径中的一员了。所以，当你点击一个障碍物点作为终点时，你的目的是让此障碍物点成为路径中的一员，然而A*算法的上述语句却直接把障碍物点给否定掉了，那自然最终会找不出路径来了……
那么如何解决这个问题呢？首先想到的方案是寻找“替代点 ”来替代我们点击的不可移动点作为终点，但是实践证明，你永远也无法正确地找到一个“替代点”。比如，你想从你点击的那个障碍物点开始向四周遍历寻找“替代点”，如果发现了一个walkable为true的点那就把它作为“替代点”吧，这个过程如下图所示：

这种方案的结果可能是上面这种情况，找到了一个位于原目标点周围的一个替代点，这有可能是正确的一个替代点，但是如果此替代点周围又被围了一圈围墙怎么办呢？

那么既然用“替代点”的方式行不通，就只能想点别的办法。在《动画高级教程》“寻路”这一章的末尾部分讲到了对一些不易行的路径（如沼泽、高地等）增大寻路代价g值来让A*算法寻出的路径能够绕过这些不易行的路径。

但是如果实在没有路走了，A*还是会选择走这些难走的路的。

而实现这一切只需要使用一句代码：

Java代码

var g:Number = node.g + cost * test.costMultiplier;

上面这个costMultiplier变量是每一个节点都具备的属性，不易走的路径costMultiplier的值大，好走的路径costMultiplier值小。

这样就给了我一个启发，既然我的目的是让我点击的障碍物点能够有机会被加到开启列表_open中，但是在路上碰到的障碍物点还是能够正常地绕开的话，不妨把障碍物点和不可穿越点的代价costMultiplier设为一个极大的值，当A*寻路实在找不到更佳的路径时它还是会回头来找我这个障碍物点的！这个过程如下图所示：

有人说，那按你这样子走的话，我寻路者不是要走到障碍物里头去啦？那就是当你寻路完毕返回一个路径数组path后，我会从前往后对path进行遍历，一旦遇到walkable为false或是不可穿越点就把path中位于这一点之后的全部点都给我飞掉去

最后，看看代码的实现过程吧，下面给出的是经过修改的search方法以及buildPath方法：

Java代码

public function search():Boolean
{
var startTime:int=getTimer();
var node:Node = _startNode;
var sortTime:int = 0;
var tryCount:int = 0;
while(node != _endNode)
{
tryCount++;
var startX:int = Math.max(0, node.x - 1);
var endX:int = Math.min(_grid.numCols - 1, node.x + 1);
var startY:int = Math.max(0, node.y - 1);
var endY:int = Math.min(_grid.numRows - 1, node.y + 1);
for(var i:int = startX; i <= endX; i++)
{
for(var j:int = startY; j <= endY; j++)
{
var test:Node = _grid.getNode(i, j);
if(test == node)
{
continue;
}
if( !test.walkable || !isDiagonalWalkable(node, test) )
{
//设其代价为超级大的一个值，比大便还大哦~
test.costMultiplier = 1000;
}
else
{
test.costMultiplier = 1;
}
var cost:Number = _straightCost;
if(!((node.x == test.x) || (node.y == test.y)))
{
cost = _diagCost;
}
var g:Number = node.g + cost * test.costMultiplier;
var h:Number = _heuristic(test);
var f:Number = g + h;
if( isOpen(test) || isClosed(test)))
{
if(test.f > f)
{
test.f = f;
test.g = g;
test.h = h;
test.parent = node;
}
}
else
{
test.f = f;
test.g = g;
test.h = h;
test.parent = node;
_open.push( test );
}
}
}
_closed.push(node);
if(_open.length == 0)
{
trace("no path found");
return false
}
var sortStartTime:int = getTimer();
_open.sortOn("f", Array.NUMERIC);
sortTime += (getTimer() - sortStartTime);
node = _open.shift() as Node;
}
trace( "time cost: " + (getTimer() - startTime) + "ms");
trace( "sort cost: " + sortTime);
trace( "try time: " + tryCount);
buildPath();
return true;
}
private function buildPath():void
{
_path = new Array();
var node:Node = _endNode;
_path.push(node);
//不包含起始节点
while(node.parent != _startNode)
{
node = node.parent;
_path.unshift(node);
}
//排除无法移动点
var len:int = _path.length;
for( var i:int=0; i<len; i++ )
{
if( _path[i].walkable == false )
{
_path.splice(i, len-i);
break;
}
//由于之前排除了起始点，所以当路径中只有一个元素时候判断该元素与起始点是否是不可穿越关系，若是，则连最后这个元素也给他弹出来~
else if( len == 1 && !isDiagonalWalkable(_startNode, _endNode) )
{
_path.shift();
}
//判断后续节点间是否存在不可穿越点，若有，则把此点之后的元素全部拿下
else if( i < len - 1 && !isDiagonalWalkable(_path[i], _path[i+1]) )
{
_path.splice(i+1, len-i-1);
break;
}
}
}
/** 判断两个节点的对角线路线是否可走 */
private function isDiagonalWalkable( node1:Node, node2:Node ):Boolean
{
var nearByNode1:Node = _grid.getNode( node1.x, node2.y );
var nearByNode2:Node = _grid.getNode( node2.x, node1.y );
if( nearByNode1.walkable && nearByNode2.walkable )return true;
return false;
}

上面的代码中我只改了几句，所以应该很容易就看出来差别在哪，我还加了几句测试语句用来测试寻路总耗时、排序耗时以及寻路过程中的试探次数以便之后进行效率探讨。我还对buildPath方法做了更改，原始A*算法会在最终返回的path中包含起始点，其实这是没有必要的，如果你包含了起始点的话会造成下图这种走回头路的结果：

之后，对寻路返回路径进行刚才所说的处理，去掉无效路径后就能得到正确的路径了。

3.算法效率优化
上面代码中加了几句测试效率的语句，在debug时候可以打印出寻路总耗时、对开放列表进行排序的总耗时以及寻路总尝试次数。当你按照我刚才给出的算法去点击一个障碍物点进行寻路的时候，虽然能够找到正确的路径，但是会发现try time的值非常大，总耗时也不低。这是因为我把障碍物点的代价设置为很大后A*寻路会先掠过此点并找寻更佳的点，它不找完剩余全部的节点是不会甘心的。对于这种情况，网上有一些解决方案，比如将整个网格划分成几个区域等方法，这些方案我没有尝试过，因为怕会出现什么差错。那么既然不能降低尝试次数，只好从代码执行效率上来做做功课。在《动画高级教程》中提供的AStar.as源码中存在一些会减慢效率的代码：
1.将代码中的Math.abs()方法、Math.max()、Math.min()方法用 ? : 这个三元运算符来替代；

Java代码

if(isOpen(test) || isClosed(test))

使用了isOpen和isClosed两个函数来判断test点是否存在于_open和_close这两个数组中，然而我们看看isOpen和isClosed这两个函数中是怎么做的：

Java代码

private function isOpen(node:Node):Boolean
{
for(var i:int = 0; i < _open.length; i++)
{
if(_open[i] == node)
{
return true;
}
}
return false;
}

作者使用这种逐个遍历的方式来查找一个元素是否在一个数组中，这种方式的效率远远比数组自带的indexOf方法低下，因此，用Array.indexOf方法来替代isOpen与isClosed方法：

Java代码

if(_open.indexOf(test) != -1 || _closed.indexOf(test) != -1)

经过上面两步优化之后，调试一下，发现效率有所提高，但是我们发现排序时间依然花了不少，占总耗时的50%左右，那么我想到使用网上流行的二叉堆法来替代数组自带的sortOn方法。

什么是二叉堆法呢？先看看有关二叉堆这个数据结构的介绍：http://www.blueidea.com/tech/multimedia/2007/4665_3.asp
二叉堆这个数据结构的好处在于它始终能够保证堆顶的那个元素是所有元素中最小的，当堆内元素发生改变时就会进行一系列的运算以确保堆内结构一致（添加、删除、修改时该做什么工作在上面给出的链接文章中都已说明），但是这“一系列的运算”的运算量远比直接使用数组自带的sortOn方法小，
当元素数量极大的时候，二叉堆的这种排序上的效率优势就更加明显了。
根据二叉堆的原理得到我们的Binary.as类：

Java代码

package
{
/**
* 二叉堆数据结构
* @author S_eVent
*
*/
public class Binary
{
private var _data:Array;
private var _compareValue:String;
/**
* @param compareValue 排序字段，若为空字符串则直接比较被添加元素本身的值
*
*/
public function Binary( compareValue:String="" )
{
_data = new Array();
_compareValue = compareValue;
}
/** 向二叉堆中添加元素
* @param node 欲添加的元素对象
*/
public function push( node:Object ):void
{
//将新节点添至末尾先
_data.push( node );
var len:int = _data.length;
//若数组中只有一个元素则省略排序过程，否则对新元素执行上浮过程
if( len > 1 )
{
/** 新添入节点当前所在索引 */
var index:int = len;
/** 新节点当前父节点所在索引 */
var parentIndex:int = index / 2 - 1;
var temp:Object;
//和它的父节点（位置为当前位置除以2取整，比如第4个元素的父节点位置是2，第7个元素的父节点位置是3）比较，
//如果新元素比父节点元素小则交换这两个元素，然后再和新位置的父节点比较，直到它的父节点不再比它大，
//或者已经到达顶端，及第1的位置
while( compareTwoNodes(node, _data[parentIndex]) )
{
temp = _data[parentIndex];
_data[parentIndex] = node;
_data[index - 1] = temp;
index /= 2;
parentIndex = index / 2 - 1;
}
}
}
/** 弹出开启列表中第一个元素 */
public function shift():Object
{
//先弹出列首元素
var result:Object = _data.shift();
/** 数组长度 */
var len:int = _data.length;
//若弹出列首元素后数组空了或者其中只有一个元素了则省略排序过程，否则对列尾元素执行下沉过程
if( len > 1 )
{
/** 列尾节点 */
var lastNode:Object = _data.pop();
//将列尾元素排至首位
_data.unshift( lastNode );
/** 末尾节点当前所在索引 */
var index:int = 0;
/** 末尾节点当前第一子节点所在索引 */
var childIndex:int = (index + 1) * 2 - 1;
/** 末尾节点当前两个子节点中较小的一个的索引 */
var comparedIndex:int;
var temp:Object;
//和它的两个子节点比较，如果较小的子节点比它小就将它们交换，直到两个子节点都比它大
while( childIndex < len )
{
//只有一个子节点的情况
if( childIndex + 1 == len )
{
comparedIndex = childIndex;
}
//有两个子节点则取其中较小的那个
else
{
comparedIndex = compareTwoNodes(_data[childIndex], _data[childIndex + 1]) ? childIndex : childIndex + 1;
}
if( compareTwoNodes(_data[comparedIndex], lastNode) )
{
temp = _data[comparedIndex];
_data[comparedIndex] = lastNode;
_data[index] = temp;
index = comparedIndex;
childIndex = (index + 1) * 2 - 1;
}
else
{
break;
}
}
}
return result;
}
/** 更新某一个节点的值。在你改变了二叉堆中某一节点的值以后二叉堆不会自动进行排序，所以你需要手动
* 调用此方法进行二叉树更新 */
public function updateNode( node:Object ):void
{
var index:int = _data.indexOf( node ) + 1;
if( index == 0 )
{
throw new Error("！更新一个二叉堆中不存在的节点作甚！？");
}
else
{
var parentIndex:int = index / 2 - 1;
var temp:Object;
//上浮过程开始喽
while( compareTwoNodes(node, _data[parentIndex]) )
{
temp = _data[parentIndex];
_data[parentIndex] = node;
_data[index - 1] = temp;
index /= 2;
parentIndex = index / 2 - 1;
}
}
}
/** 查找某节点所在索引位置 */
public function indexOf( node:Object ):int
{
return _data.indexOf(node);
}
public function get length():uint
{
return _data.length;
}
/**比较两个节点，返回true则表示第一个节点小于第二个*/
private function compareTwoNodes( node1:Object, node2:Object ):Boolean
{
if( _compareValue )
{
return node1[_compareValue] < node2[_compareValue];
}
else
{
return node1 < node2;
}
return false;
}
}
}

所有二叉堆对外开放的API命名规范都效仿Array。那么有了这个类之后就开始使用它来替代原先A*算法中的Array实例吧，在A*算法中，需要排序的只有开放列表_open这一个实例，所以只需要将_open的类型改成Binary就可以了。下面列出更改了的一些语句：

Java代码

// private var _open:Array
private var _open:Binary;
……
public function findPath(grid:Grid):Boolean
{
_grid = grid;
// _open = new Array();
_open = new Binary("f");
……
return search();
}
public function search():Boolean
{
……
while(node != _endNode)
{
……
for(var i:int = startX; i <= endX; i++)
{
for(var j:int = startY; j <= endY; j++)
{
……
var g:Number = node.g + cost * test.costMultiplier;
var h:Number = _heuristic(test);
var f:Number = g + h;
var isInOpen:Boolean = _open.indexOf(test) != -1;
if( isInOpen || _closed.indexOf(test) != -1)
{
if(test.f > f)
{
test.f = f;
test.g = g;
test.h = h;
test.parent = node;
if( isInOpen )
_open.updateNode( test );
}
}
else
{
……
}
}
}
……
// _open.sortOn("f", Array.NUMERIC);
node = _open.shift() as Node;
}
buildPath();
return true;
}

最后，测试一下效率，提高了排序速率2-3倍以上……

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

A*寻路之路径优化（一）的相关文章

进程和线程的区别与联系

1 共同点功能上都是用于实现多任务并发程序设计的技术手段 xff0c 线程的状态包括就绪执行与阻塞 xff0c 与进程类似从系统实现的角度看 xff0c 进程实体和线程实体在Linux内核中都是有task struct实现的 xff0
AD9的pcb 里面怎样才能从TOP层视图换成从BOTTOM层网上面看，相当于把板子翻过来看

AD9中更改PCB的视角切换到3D xff08 view gt switch To 3D xff09 视图 xff0c 然后点击 view gt Orthogonal Rotation 然后在切换到2D视图 xff08 view gt s
opencv中三种像素访问方式的运行速度比较

本文目的 xff1a 在opencv中有三种方式可以读写图像的像素 xff0c 分别为 xff1a 指针读写迭代器读写动态地址计算读写虽然三种方式都可以完成同样的目的 xff0c 但是运行速度却有快有慢 xff0c 尤其是在实现一些复
如何确认系统是采用大端还是小端

如何确认系统是采用大端还是小端 1 大小端大端 xff08 存储 xff09 模式 xff1a 是指一个数据的低位字节序的内容放在高地址处 xff0c 高位字节序存的内容放在低地址处如 xff1a 一个数0x12345678存放在一个4
C++ Primer Plus 第六版所有章节课后编程练习答案

我的独立博客地址 xff1a www blog4jimmy com xff0c 欢迎大家关注下面的是C 43 43 Primer Plus 第六版所有章节的课后编程练习的答案 xff0c 都是博主自己写的 xff0c 有不对的地方请大家留
串口发送大数组

用stm32f4XX发送采集到的数据时 xff0c 如果数据量特别大 xff0c 直接发送一个大数组可能比较占内存这时候 xff0c 可以逐个发送数据最好将大数组定义为全局变量定义在函数内时 xff0c 可能导致栈不够深而报错其模式
IP数据包校验过程

1 算法思路 xff1a IP ICMP IGMP TCP UDP等协议的校验和算法都是相同的 xff0c 算法如下 xff1a 在发送数据时 xff0c 为了计算IP数据包的校验和应该按如下步骤 xff1a xff08 1 xff09
CMake 和makefile

1 gcc 它是GNU Compiler Collection xff08 就是GNU编译器套件 xff09 xff0c 也可以简单认为是编译器 xff0c 它可以编译很多种编程语言 xff08 括C C 43 43 Objective C
ROS CMakeLists中target_link_libraries相对路径设置

希望大家收藏 xff1a 本文更新地址 xff1a https haoqchen site 2018 04 26 CMakeLists setting relative path 左侧专栏还在更新其他ROS实用技巧哦 xff0c 关注一波
AD10 复制问题（复制方法和智能粘贴拼版）

ad10PCB复制不成功频繁的遇到过在PCB界面复制不成功的情况 xff0c 今天终于搞明白了是什么原因造成的当我们选中元件的时候 xff0c 鼠标箭头就会有一个十字架的形状 xff0c 这时候直接按下CTRL 43 C然后再在其他的地
Postman中文版，竟如此简单，秒变中文

好多小伙伴 xff0c 尤其是刚入门软件测试的 xff0c 对英文版本的Postman很抵触 xff0c 希望有个中文版的 xff0c 不过很遗憾的是Postman只有英文版本 xff0c 但凡事都有例外 xff0c 某天在逛github的
Http协议报文格式

一整体介绍 Http协议在传输层基于TCP协议 xff0c 在Http1 1之前每次请求在TCP层都需进行一轮连接和释放 xff08 三次握手四次握手 xff09 xff0c 从Http1 1开始默认使用长连接 Http报文分为两种 x
记录一次json_decode 返回NULL解决过程

后台返回数据 xff0c 前端收到数据之后 xff0c 在调用json decode 之后 xff0c 返回null 用json last error 报错 3 在解码前 xff0c 对字符串进行处理 data 61 preg replac
mybatis-plus之saveBatch开启批量插入

背景 MyBatis Puls的saveBatch默认并没有批量添加 xff0c 实际上在插入的时候仍然是一条条记录的插开启在jdbc的url连接参数中添加 rewriteBatchedStatements 61 true
PHP 之问题记录一

临时设置时区 date default timezone set 39 PRC 39 获取当前毫秒数 span class token comment 1670834581421 span span class token keyword
HTTPS 之请求头缺少HTTPOnly和Secure属性解决方案

1 如果使用php 修改 php ini 的 session cookie httponly 和 session cookie secure 为 1 xff0c 重启php 2 如果使用nginx nginx conf 文件中设置 http
Linux 之恢复删除文件

方法一如果进程ID还存在 xff0c 可以直接恢复 span class token number 1 span lsof span class token operator span span class token function
mybatis-plus 之 find_in_set使用

MP中使用find in set函数 span class token class name LambdaQueryWrapper span span class token generics span class token punctu
springboot 之常用jackson配置

时区 spring jackson time zone 61 GMT 43 8 日期格式 spring jackson date format 61 yyyy MM dd HH mm ss 默认转json的属性 xff0c 这里设置为非空才
linux 之服务器关于TIME_WAIT

TIME WAIT 服务端大量处于 TIME WAIT 状态连接的原因 TCP 四次挥手的流程下面这个图 xff0c 是由客户端作为主动关闭方的 TCP 四次挥手的流程从上图我们可以知道 xff0c TIME WAIT 状态是

随机推荐

PADS原理图与PCB转到AD或者高版本PADS转出文件给低版本使用

本文摘录于 xff1a http blog sina com cn s blog 63e7da9801011uz2 html pads2007原理图转换Altium Designer6 9的方法如下 xff1a 1 在PADS logic使
centos使用yum安装redis最新版

centos使用yum安装redis最新版 yum span class token function install span y epel release yum span class token function install sp
ERROR 1205 (HY000): Lock wait timeout exceeded； try restarting transaction

问题 ERROR 1205 HY000 Lock wait timeout exceeded xff1b try restarting transaction 方法查看innodb的事务表INNODB TRX xff0c 看下里面是否有正
ORACLE 之使用oracle客户端工具连接远程oracle服务器

前言之前写了如何用Navicat连接oracle数据库 xff0c 今天写一下如何使用官方提供的工具连接下载官网下载这里要说一下 xff0c 下载的64位或者32位不是你的windows系统 xff0c 而是oracle服务器安装
Mysql 之 Json字段类型实践

前言 JSON类型是MySQL5 7 8中新加入的一种数据类型 xff0c 并在后续版本尤其是MySQL8 0中得到了大幅增强 xff0c 现在的JSON类型的功能十分强大 xff0c 合理使用能让我们的开发更加有效本文注重实践 xff0
Lombok 之 @RequiredArgsConstructor 注解

概念 spring注入对象有三种方法 xff0c 属性注入 xff0c 构造器注入 xff0c setter注入但是如果属性太多 xff0c 一个个写太麻烦 xff0c 所以lombok提供了一个注解 xff0c 使用 64 Requir
查看SSL证书信息

查看证书有效期 openssl x509 in server crt noout dates 查看证书ID等信息 openssl x509 in server crt noout text
html 之显示内容超过部分隐藏，鼠标放上之后显示全部内容

如题 xff1a CSS span class token selector lt style gt lt gridBoxContentSelf span span class token punctuation span span cla
Mysql 之死锁问题如何排查和解决

Mysql死锁问题如何排查和解决
mybatis-plus 之 and()和or()连用

1 and 方法 span class token class name List span span class token generics span class token punctuation lt span span class
PHP 之从文件获取指定数据生成Excel的功能

功能数据 111111 22222222 xxx 22222 33333333 xxx 取出第一列和第二列数据生成Excel 代码 span class token delimiter important lt php span span
AD10 BOM制作

首先在原理图文件点击 xff1a Reports gt Bill of Meterials 然后作如下操作 xff1a 选择上value xff0c 并把他作为分组依据 xff1a 把Comment这个列去掉 xff0c 这个是元件注释列
cmake Could NOT find OpenSSL

问题使用cmake编译一个软件时 xff0c 因为需要使用到openssl xff0c 且有指定版本需要 xff0c 但是系统中的是低版本 xff0c 不支持升级高版本 xff0c 只能自行安装 xff0c cmake指定使用哪个版本的o
linux 之查找相关内容的文件并批量修改

场景如题相关命令 grep xargs awk 实践将原有项目使用的IP改成新IP grep 39 10 150 132 93 39 tmp text R awk F 39 39 39 print 1 39 xargs n 1 sed
串口数据解析（c语言）

64 brief 从一段字符串中解析期望的字符串 64 param pBuff 要解析的字符串地址 64 param pLeft 目标字符串左边的字符串 64 param pRight 目标字符串右边的字符串 64 param pRes 接
带你玩转Jetson Xavier NX系列教程 | Xavier NX 环境变量配置，风扇控制以及Jtop安装

写在最前 xff1a 转载请注明文章出处本期文章分为三部分内容 xff0c 均为刷机以后需要配置的小细节 xff0c 建议大家刷机以后立刻进行配置 xff0c 没有配置的后续再配置也没什么大问题 Session 1 Xavier NX风扇
大电流走线阻焊开窗,锡量美观可控方案开窗上锡

大电流走线阻焊开窗锡量美观可控方案这里要注意的两点 xff0c 1 Paste 是焊锡层 xff0c 2 Solder是阻焊层绿油的 PCB板厂按照阻焊层做完阻焊后才做喷锡沉金工艺所以需要走线上开窗只需要在 Solder是
OpenGL Bresenhan画线法

include lt GL glut h gt include lt stdio h gt include lt stdlib h gt void swap int a int b int temp temp 61 a a 61 b b 6
http 基础认证(Basic Authentication)

还是几个月前的老东西计算机网络作业需要一个http基础认证的网站来学习http协议本身以及它的安全性实在找不到这种网站 xff0c 应该是过时了的技术吧由于认证过程仅仅是Base64加密 xff08 其实这个不算加密吧 xff0c 仅
A*寻路之路径优化（一）

目前项目中寻路是通过A 来实现的 xff0c 实际应用时候发现存在以下问题 xff1a 1 生成的Z型折线路径用A 算法得到的路径 xff0c 在起点和目标点间没有任何障碍物的情况下路径仍可能是 Z型折线型 2 目标点无法到达情况使用

A*寻路之路径优化（一）

另一种思路：

A*寻路之路径优化（一） 的相关文章

随机推荐

热门标签

A*寻路之路径优化（一）的相关文章