专栏首页菩提树下的杨过“AS3.0高级动画编程”学习:第四章 寻路(AStar/A星/A*)算法 (上)

“AS3.0高级动画编程”学习:第四章 寻路(AStar/A星/A*)算法 (上)

一提到“A*算法”,可能很多人都有"如雷贯耳"的感觉。用最白话的语言来讲:把游戏中的某个角色放在一个网格环境中,并给定一个目标点和一些障碍物,如何让角色快速“绕过障碍物”找出通往目标点的路径。(如下图)

在寻路过程中,角色总是不停从一个格子移动到另一个相邻的格子,如果单纯从距离上讲,移动到与自身斜对角的格子走的距离要长一些,而移动到与自身水平或垂直方面平行的格子,则要近一些。为了描述这种区别,先引入二个概念:

节点(Node):每个格子都可以称为节点。

代价(Cost):描述角色移动到某个节点时所走的距离(或难易程度)。

如上图,如果每水平或垂直方向移动相邻一个节点所花的代价记为1,则相邻对角节点的代码为1.4(即2的平方根--勾股定理)

通常寻路过程中的代价用f,g,h来表示

g代表(从指定节点到相邻)节点本身的代价--即上图中的1或1.4

h代表从指定节点到目标节点(根据不同的估价公式--后面会解释估价公式)估算出来的代价。

而 f = g + h 表示节点的总代价,为了方便后面的代码描述,这里把节点封装成一个类Node.as

package {	
	public class Node
	{
		public var x:int;
		public var y:int;
		public var f:Number;
		public var g:Number;
		public var h:Number;
		public var walkable:Boolean=true;//是否可穿越(通常把障碍物节点设置为false)
		public var parent:Node;
		public var costMultiplier:Number=1.0;//代价因子

		public function Node(x:int, y:int)
		{
			this.x=x;
			this.y=y;
		}
	}
}

注意:这里有二个新的东东walkable和parent。

通常障碍物本身也可以看成是由若干个不可通过的节点所组成,所以walkable实际上是用来标记该节点是否为障碍物(节点)。

另外:在考查从一个节点移动到另一个节点时,总是拿自身节点周围的8个相邻节点来说事儿,相对于周边的节点来讲,自身节点称为它们的父节点(parent).

前面一直在提“网格,网格”,干脆把它也封装成类Grid.as

package
{

	public class Grid
	{
		private var _startNode:Node;//开始节点
		private var _endNode:Node;//目标节点
		private var _nodes:Array;//节点数组
		private var _numCols:int;//列数
		private var _numRows:int;//行数

		public function Grid(numCols:int, numRows:int)
		{
			_numCols=numCols;
			_numRows=numRows;
			_nodes=new Array();
			for (var i:int=0; i < _numCols; i++)
			{
				_nodes[i]=new Array();
				for (var j:int=0; j < _numRows; j++)
				{
					_nodes[i][j]=new Node(i, j);
				}
			}
		}

		public function getNode(x:int, y:int):Node
		{
			return _nodes[x][y] as Node;
		}


		public function setEndNode(x:int, y:int):void
		{
			_endNode=_nodes[x][y] as Node;
		}


		public function setStartNode(x:int, y:int):void
		{
			_startNode=_nodes[x][y] as Node;
		}


		public function setWalkable(x:int, y:int, value:Boolean):void
		{
			_nodes[x][y].walkable=value;
		}


		public function get endNode():Node
		{
			return _endNode;
		}


		public function get numCols():int
		{
			return _numCols;
		}


		public function get numRows():int
		{
			return _numRows;
		}


		public function get startNode():Node
		{
			return _startNode;
		}
	}
}

然而,在寻路的过程中“条条道路通罗马”,路径通常不止一条,只不过所花的代价不同而已

如上图,如果按照黄色路径走,所花的总代价是14,而按照粉红色路径走,所花的总代价是16,所以我们要做的事情,就是要尽最大努力找一条代价最小的路径。

但是,“好事总多磨”,即使是代价相同的最佳路径,也有可能出现不同的走法:

上图中三种不同的走法,总代价都是4.8,就上图而言,最佳路径(最小代价)用肉眼就能很快找出来,但是用代码如何估算起点与终点之间的代价呢?

//曼哈顿估价法
private function manhattan(node:Node):Number
{
	return Math.abs(node.x - _endNode.x) * _straightCost + Math.abs(node.y + _endNode.y) * _straightCost;
}

//几何估价法
private function euclidian(node:Node):Number
{
	var dx:Number=node.x - _endNode.x;
	var dy:Number=node.y - _endNode.y;
	return Math.sqrt(dx * dx + dy * dy) * _straightCost;
}

//对角线估价法
private function diagonal(node:Node):Number
{
	var dx:Number=Math.abs(node.x - _endNode.x);
	var dy:Number=Math.abs(node.y - _endNode.y);
	var diag:Number=Math.min(dx, dy);
	var straight:Number=dx + dy;
	return _diagCost * diag + _straightCost * (straight - 2 * diag);
}

上面的代码给出了三种基本的估价算法(也称估价公式),其算法示意图如下:

如上图,对于“曼哈顿算法”最贴切的描述莫过于孙燕姿唱过的那首成名曲“直来直往”,笔直的走,然后转个弯,再笔直的继续。

“几何算法”的最好解释就是“勾股定理”,算出起点与终点之间的直线距离,然后乘上代价因子。

“对角算法”综合了以上二种算法,先按对角线走,一直走到与终点水平或垂直平行后,再笔直的走。

我们可以针对刚才的情况做下测试:

package
{
	import flash.display.Sprite;

	public class GridTest extends Sprite
	{
		private var _endNode:Node;
		private var _startNode:Node;
		private var _straightCost:Number=1.0;
		private var _diagCost:Number = 1.4;


		public function GridTest()
		{
			var g:Grid=new Grid(5, 5);
			g.setStartNode(0, 3);
			g.setEndNode(4, 1);
			
			_endNode = g.endNode;
			_startNode = g.startNode;
			
			var c1:Number = manhattan(_startNode);//8 
			var c2:Number = euclidian(_startNode);//4.47213595499958
			var c3:Number = diagonal(_startNode);//4.8
			
			trace(c1,c2,c3);
		}

		//曼哈顿估价法
		private function manhattan(node:Node):Number
		{
			return Math.abs(node.x - _endNode.x) * _straightCost + Math.abs(node.y - _endNode.y) * _straightCost;
		}

		//几何估价法
		private function euclidian(node:Node):Number
		{
			var dx:Number=node.x - _endNode.x;
			var dy:Number=node.y - _endNode.y;
			return Math.sqrt(dx * dx + dy * dy) * _straightCost;
		}

		//对角线估价法
		private function diagonal(node:Node):Number
		{
			var dx:Number=Math.abs(node.x - _endNode.x);
			var dy:Number=Math.abs(node.y - _endNode.y);
			var diag:Number=Math.min(dx, dy);
			var straight:Number=dx + dy;
			return _diagCost * diag + _straightCost * (straight - 2 * diag);
		}
	}
}

从输出结果可以看到“对角线估价法”跟肉眼预测的实际结果完全一致,总代价为4.8,以后默认情况下就用它了,不过这里提醒一下:这种代价是大概估计出来的,没有考虑到障碍物的因素,并非寻路过程中的实际代价,所以这也是“估价计算公式”而非“代价计算公式”得名的由来。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • “AS3.0高级动画编程”学习:第二章转向行为(下)

    在上一篇里,我们学习了“自主角色”的一些基本行为:寻找(seek)、避开(flee)、到达(arrive)、追捕(pursue)、躲避(evade)、漫游(wa...

    菩提树下的杨过
  • java:多线程基础之Runnable、Callable与Thread

    java.lang包下有二个非常有用的东西:Runnable接口与Thread类,Thread实现了Runnable接口(可以认为Thread是Runnable...

    菩提树下的杨过
  • flash:二次贝塞尔曲线应用-生成飞机路径示意图

    本周听到公司其它项目组同事在讨论一个小需求: 给定3个点(其实是飞机经过的航站,比如:从浦东-西安-北京),在UI上生成一段曲线,用来示意飞机的路线图(其实用直...

    菩提树下的杨过
  • springBoot学习(三)springBoot事件监听和部分注解的运用

    1.springBoot启动类会使用@SpringBootApplication 2.点进入源代码发现改注解是一个复合注解,由好几个注解共同组合而成

    乱敲代码
  • 5.触摸事件、侧滑菜单

    六月的雨
  • springBoot学习(三)springBoot事件监听和部分注解的运用

    1.springBoot启动类会使用@SpringBootApplication 2.点进入源代码发现改注解是一个复合注解,由好几个注解共同组合而成

    杨小杰
  • Spring注解浅入浅出——不吹牛逼不装逼

    上文书咱们说了《Spring浅入浅出》,对Spring的核心思想看过上篇的朋友应该已经掌握了,此篇用上篇铺垫,引入注解,继续深入学习。

    泰斗贤若如
  • 聊聊skywalking的spring-webflux-plugin

    skywalking-6.6.0/apm-sniffer/optional-plugins/optional-spring-plugins/spring-web...

    codecraft
  • Java并发编程实战系列15之原子遍历与非阻塞同步机制(Atomic Variables and Non-blocking Synchronization)

    近年来,在并发算法领域的大多数研究都侧重于非阻塞算法,这种算法用底层的原子机器指令来代替锁来确保数据在并发访问中的一致性,非阻塞算法被广泛应用于OS和JVM中实...

    JavaEdge
  • Spring Boot整合Ehcache实现缓存功能

    这里介绍Spring Boot结合JPA,MySQL和Ehcache实现缓存功能,提高程序访问效率。

    itlemon

扫码关注云+社区

领取腾讯云代金券