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

在前一部分的最后，我们给出了一个寻路的示例，在大多数情况下，运行还算良好，但是有一个小问题，如下图：

很明显，障碍物已经把路堵死了，但是小球仍然穿过对角线跑了出来！

问题在哪里：我们先回顾一下AStar.as中用于判断的if语句

//如果是当前节点，或者是不可通过的，则跳过
if (test == node || !test.walkable)
{
    continue;
}

在这个判断中，并没有规定说不允许走对象线。来看看如何修正：

在以node为中心考查四周节点时，如果遇到水平和垂直方向都是障碍物时，既使对角节点是可穿越的普通节点，也不能通过。所以只要再加二个条件判断即可

//如果是当前节点，或者是不可通过的，且排除水平和垂直方向都是障碍物节点时的特例情况
if (test == node || !test.walkable || !_grid.getNode(node.x, test.y).walkable || !_grid.getNode(test.x, node.y).walkable)
{
	continue;
}

再运行一下：

一切正常了!

前面提到的这些示例，终点与目标点都是固定的，但在实际游戏中，正好相反，比如"星际"，选定一个农民后，在地图上随便点击一下，农民就能自动找到去目标点的路径。

package
{
	import flash.display.Sprite;
	import flash.display.StageAlign;
	import flash.display.StageScaleMode;
	import flash.events.Event;
	import flash.events.MouseEvent;

	[SWF(width=600,height=600)]
	public class Game extends Sprite
	{
		private var _cellSize:int=20;
		private var _grid:Grid;
		private var _player:Sprite;
		private var _index:int;
		private var _path:Array;

		public function Game()
		{
			stage.align=StageAlign.TOP_LEFT;
			stage.scaleMode=StageScaleMode.NO_SCALE;
			makePlayer();
			makeGrid();
			stage.addEventListener(MouseEvent.CLICK, onGridClick);
		}

		/** 生成一个player角色(简单起见，就是一个圈) */
		private function makePlayer():void
		{
			_player=new Sprite();
			_player.graphics.beginFill(0xff0000);
			_player.graphics.drawCircle(0, 0, 5);
			_player.graphics.endFill();
			_player.x=Math.random() * 600;
			_player.y=Math.random() * 600;
			addChild(_player);
		}

		/** 生成网格，并随机放置一些障碍 */
		private function makeGrid():void
		{
			_grid=new Grid(30, 30);
			for (var i:int=0; i < 200; i++)
			{
				_grid.setWalkable(Math.floor(Math.random() * 30), Math.floor(Math.random() * 30), false);
			}
			drawGrid();
		}

		/** 画网格线以及为障碍物填充颜色*/
		private function drawGrid():void
		{
			graphics.clear();
			for (var i:int=0; i < _grid.numCols; i++)
			{
				for (var j:int=0; j < _grid.numRows; j++)
				{
					var node:Node=_grid.getNode(i, j);
					graphics.lineStyle(0);
					graphics.beginFill(getColor(node));
					graphics.drawRect(i * _cellSize, j * _cellSize, _cellSize, _cellSize);
				}
			}
		}

		/** 返回节点颜色 */
		private function getColor(node:Node):uint
		{
			if (!node.walkable)
				return 0;
			if (node == _grid.startNode)
				return 0xcccccc;
			if (node == _grid.endNode)
				return 0xff0000;
			return 0xffffff;
		}

		/** 鼠标点击时随机设置终点，并以player当前位置做为起点 */
		private function onGridClick(event:MouseEvent):void
		{
			var xpos:int=Math.floor(mouseX / _cellSize);
			var ypos:int=Math.floor(mouseY / _cellSize);
			_grid.setEndNode(xpos, ypos);
			xpos=Math.floor(_player.x / _cellSize);
			ypos=Math.floor(_player.y / _cellSize);
			_grid.setStartNode(xpos, ypos);
			drawGrid();
			findPath();
		}

		/** 寻路 */
		private function findPath():void
		{
			var astar:AStar=new AStar();
			if (astar.findPath(_grid))
			{
				_path=astar.path;
				_index=0;
				addEventListener(Event.ENTER_FRAME, onEnterFrame);
			}
		}

		/**每帧的动画处理*/
		private function onEnterFrame(event:Event):void
		{
			var targetX:Number=_path[_index].x * _cellSize + _cellSize / 2;
			var targetY:Number=_path[_index].y * _cellSize + _cellSize / 2;

			//把经过的点，涂上黄色
			var passedNode:Node=_path[_index];
			graphics.lineStyle(0);
			graphics.beginFill(0xffff00);
			graphics.drawRect(passedNode.x * _cellSize, passedNode.y * _cellSize, _cellSize, _cellSize);

			var dx:Number=targetX - _player.x;
			var dy:Number=targetY - _player.y;
			var dist:Number=Math.sqrt(dx * dx + dy * dy);
			if (dist < 1)
			{
				_index++;//索引加1，即取一个路径节点
				if (_index >= _path.length)//达到最后一个节点时，移除ENTER_FRAME监听
				{
					removeEventListener(Event.ENTER_FRAME, onEnterFrame);
				}
			}
			else
			{
				_player.x+=dx * .5;
				_player.y+=dy * .5;
			}
		}
	}
}

拿鼠标在空白节点上随便点点，看看会发生些什么？ 

考虑最后一个问题：实际游戏地图中有平地，有高坡，有沙地，有雪地...不同的路面状况，行走的难度(即代价)应该不同吧？而我们刚才的所有示例中，对所有可穿越的节点都是平等对待的。如何区分出不同情况的地形呢？

关注一下：Node.as中的

public var costMultiplier:Number=1.0;//代价因子

以及AStar.as中的

//计算test节点的总代价
var g:Number=node.g + cost * test.costMultiplier;

聪明的你一定看出端倪了！没错，costMultiplier就是代价的权重因子，如果让每个节点的权重因子不同，就能体现出不同地形的行走难度程度。

package
{
	import flash.display.Sprite;
	import flash.events.MouseEvent;

	public class GridView2 extends Sprite
	{
		private var _cellSize:int = 20;
		private var _grid:Grid;

		public function GridView2(grid:Grid)
		{
			_grid = grid;
			for(var i:int = 0; i < _grid.numCols; i++)
			{
				for(var j:int = 0; j < _grid.numRows; j++)
				{
					//为每个节点设置不同的“代价权重因子”
					var mult:Number = Math.sin(i * .50) + Math.cos(j * .2 + i * .05);
					_grid.getNode(i, j).costMultiplier = Math.abs(mult) + 1;
				}
			}
			drawGrid();
			findPath();
			addEventListener(MouseEvent.CLICK, onGridClick);
		}

		//画网格
		public function drawGrid():void
		{
			graphics.clear();
			for(var i:int = 0; i < _grid.numCols; i++)
			{
				for(var j:int = 0; j < _grid.numRows; j++)
				{
					var node:Node = _grid.getNode(i, j);
					graphics.lineStyle(0);
					graphics.beginFill(getColor(node));
					graphics.drawRect(i * _cellSize, j * _cellSize, _cellSize, _cellSize);
				}
			}
		}

		//取得单元格的颜色(与权重因子关联，costMultiplier越小，颜色越深)
		private function getColor(node:Node):uint
		{
			if(!node.walkable) return 0;
			if(node == _grid.startNode) return 0x666666;
			if(node == _grid.endNode) return 0x666666;
			var shade:Number = 300 - 70 * node.costMultiplier;
			return shade << 16 | shade << 8 | shade;
		}

		//单元格点击时，切换节点为普通节点或障碍物节点
		private function onGridClick(event:MouseEvent):void
		{
			var xpos:int = Math.floor(event.localX / _cellSize);
			var ypos:int = Math.floor(event.localY / _cellSize);

			_grid.setWalkable(xpos, ypos, !_grid.getNode(xpos, ypos).walkable);
			drawGrid();
			findPath();
		}

		//找路
		private function findPath():void
		{
			var astar:AStar = new AStar();
			if(astar.findPath(_grid))
			{
				//showVisited(astar);
				showPath(astar);
			}
		}

		private function showVisited(astar:AStar):void
		{
			var visited:Array = astar.visited;
			for(var i:int = 0; i < visited.length; i++)
			{
				graphics.beginFill(0xcccccc);
				graphics.drawRect(visited[i].x * _cellSize, visited[i].y * _cellSize, _cellSize, _cellSize);
				graphics.endFill();
			}
		}

		private function showPath(astar:AStar):void
		{
			var path:Array = astar.path;
			for(var i:int = 0; i < path.length; i++)
			{
				graphics.lineStyle(0);
				graphics.beginFill(0);
				graphics.drawCircle(path[i].x * _cellSize + _cellSize / 2,
					path[i].y * _cellSize + _cellSize / 2,
					_cellSize / 3);
			}
		}
	}
}

跟上一部分里的GridView.as比较起来，GridView2.as在构造函数里根据sin与cos函数，为节点设置了不同的权重因子，而且在节点着色上，深色的代价要比浅色的代价大，测试一下：

package
{
	import flash.display.Sprite;
	import flash.display.StageAlign;
	import flash.display.StageScaleMode;
	import flash.events.MouseEvent;

	[SWF(backgroundColor=0xffffff,width=440,height=440)]
	public class Pathfinding_2 extends Sprite
	{
		private var _grid:Grid;
		private var _gridView:GridView2;

		public function Pathfinding_2()
		{
			stage.align=StageAlign.TOP_LEFT;
			stage.scaleMode=StageScaleMode.NO_SCALE;
			_grid=new Grid(20, 20);
			_grid.setStartNode(1, 1);
			_grid.setEndNode(18, 18);

			_gridView=new GridView2(_grid);
			_gridView.x=20;
			_gridView.y=20;
			addChild(_gridView);
		}
	}
}

可以看出，调整权重因子后，路径尽量在靠近浅色的区域前进！可能这样对比还不强烈，把上面测试代码中的GridView2换回GridView，对比看下没有权重因子干扰时的路径

当然，在具体游戏开发过程中，A*算法还要结合其它很多技术(比如加载地图，配合地图设置权重因子，把地图分配到网格单元等)才能最终做出不错的游戏，我们在这里只是讨论寻路算法的原理，其它方面留给大家自行去完善吧.

时间： 2024-09-30 02:50:55

“AS3.0高级动画编程”学习：第四章 寻路（AStar/A星/A*）算法 (下)的相关文章

“AS3.0高级动画编程”学习：第一章高级碰撞检测

AdvancED ActionScript 3.0 Animation 是Keith Peters大师继"Make Things Move"之后的又一力作,网上已经有中文翻译版本了,打算下一阶段开始啃这本书. 今天开始学习高级碰撞检测,所用到的预备知识: 1.BitmapData的透明与不透明区别 位图数据(BitmapData)有二种模式,一种支持透明(即每个像素的值采用AARRGGBB这种32位颜色表示):另一种不支持透明度(即传统的RRGGBB这种24位颜色表示,简单点讲就是al

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

因为这一章的内容基本上都是涉及向量的,先来一个2D向量类:Vector2D.as (再次强烈建议不熟悉向量运算的童鞋,先回去恶补一下高等数学-07章空间解释几何与向量代数.pdf) package { import flash.display.Graphics; public class Vector2D { private var _x:Number; private var _y:Number; //构造函数 public function Vector2D(x:Number=0,y:Num

“AS3.0高级动画编程”学习：第三章等角投影(上)

什么是等角投影(isometric)? 刚接触这个概念时,我也很茫然,百度+google了N天后,找到了一些文章: [转载]等角(斜45度)游戏与数学 [转载]使用illustrator和正交投影原理以及基本三视图制图 以及这篇ppt:http://files.cnblogs.com/yjmyzz/Isometric.rar 建议先耐心看完这三篇文章,再往下看: 在之前学习的3D基础.3D线条与填充.背面剔除与 3D 灯光 中,我们所采用的3D坐标系,基本上都属于3D透视投影坐标.通俗点讲:就是

“AS3.0高级动画编程”学习：第三章等角投影(下)

在上一篇的最后,我们成功的用"等角投影"模拟出了立体空间的盒子模型,但是很快你就会发现这个示例的bug bug1:在已经有box的地方,再点击,将会重复创建box新实例. bug2:后面添加的box,会挡住前面添加的box. bug3:在边缘部分,如果用鼠标小心的点击,可以创建出很多超出world范围之外的盒子(即:看起来好象挂出去了) 我们按轻重缓急来处理吧: bug2最严重,它直接影响了最终的3D视觉效果.产生它的原因是显示列表中,后添加的物体,其index值会比 前面添加物体的i

as3.0啊~~动画背景移动与角色移动问题

问题描述 as3.0啊~~动画背景移动与角色移动问题 timer实现和监听进入下一帧都用了,都是一个问题,运行一段时间,不超过10秒,角色位置还有判断的flag都被初始化了.但是背景mc却是停留在当前帧.贴上代码(使用监听下一帧的方法)import flash.utils.Timer;import flash.events.TimerEvent;//var timer:Timer = new Timer(100); //100毫秒一跳stage.displayState = StageDispl

3D编程：第四章 Hello，Shaders

第四章 Hello,Shaders 本章,会编写第一个shaders.介绍HLSL语法,FX文件格式,数据结构等等.学完本章,你就具备了深入学习图形编程的基础知识. Your First Shader 使用一种新的编程语言编写第一个程序时都会使用经典的编程例子"Hello,World!",程序输出就是一行文字"Hello,World!".我们遵守这一历史悠久的传统,编写第一个shader程序"Hello,Shaders!",但是这次的输出是一种固

《点睛：ActionScript3.0游戏互动编程》——第2章 融会贯通—大话图层样式与滤镜2.1　Photoshop图层样式初体验

第2章 融会贯通-大话图层样式与滤镜 Photoshop和Flash都是杰出的软件,前者静得从容,后者动得洒脱,它们以不同的方式诠释着计算机时代的艺术.下面我们就从Photoshop的图层样式开始我们的艺术创作之路吧! 2.1 Photoshop图层样式初体验 我们打开Photoshop CS5,新建一个尺寸为600*100(单位:像素)的空白文档,使用[横排文字工具]E:\desktop\AS3 Text Effects\snapshots\第4章\4.1\横排文字工具.tif在画布上拖出一个

JavaScript Event学习第四章 传统的事件注册模型_javascript技巧

在最古老的JavaScript浏览器里注册事件只能通过内联模式.自从DHTML从根本上改变了你操作页面的方法,事件的注册就必须有扩展性而且要有很强的适应性.所以就必须有相应的事件模型.Netscape在第三代浏览器中就开始了,IE在第四代浏览器开始. 因为Netscape 3就开始支持这种新的事件注册模型,在浏览器战争前就是事实上的标准.所以微软不得不也是最后一次为了网上那些数不清的使用了Netscape事件处理模型的页面在兼容性上做出了让步. 所以这两个浏览器,事实上也是所有的浏览器都支持下面

JavaScript DOM学习第四章 getElementByTagNames_基础知识

getElementByTagNames(注意是复数的names)会获得一些tag的元素,然后按照他们的顺序保存在一个数组中.这非常的有用,比如在上一章的TOCScript中,就需要获得整个文章里面的所有的H3和H4. 我非常希望在node原型中加入这个功能,但是在IE和Safari里面不行.所以只能把他当做一个普通函数. 使用 getElementByTagNames有两个参数: 1.一个用逗号分隔的tag名称字符串. 2.一个可选的开始元素.如果存在则在该元素的子元素中查找这些tag,如果不