下载文档原格式
ActionScript3.0（as3）实现的A*寻路算法...-电脑资料曾经写过A*寻路算法的教程，但没有贴出任何代码，这次代码全都贴出，大家可以进一步学习我只是按照A*的基本思想，将A*寻路算法用AS3实现了一下，没有做太多的寻路优化等如果你本身已经会用A*寻路算法了，那么下面的代码也不必研究了代码中注释很多，就不贴过多的解释看代码以前，可以先看看下面这两篇文章，或者看代码的时候配合例子和教程来看A*（A星）寻路算法讲解A*寻路算法，DEMO展示在DEMO展示中，有三个版本，由于代码写了很久了，我也不记得下面贴出的代码是哪个版本的了，见谅，。
首先是文档类Index.as：package code{import flash.display.Sprite;import flash.text.T extField;import flash.text.T extFormat;public class Index extends Sprite{private var road:Road;public function Index(){stage.align = "TL";stage.scaleMode = "noScale";stage.showDefaultContextMenu = false;init();}//初始化private function init():void{road = new Road;addChild(road);road.x = GV.ROAD_INIT_X;road.y = GV.ROAD_INIT_Y;//地图规格申明var text:TextField = new TextField;text.htmlText = "地图规格：50*50方格，障碍物500方格寻路算法：A*（星）制作：sunbright";addChild(text);text.x = 25;text.y = 530;text.width = 500;text.selectable = false;text.mouseEnabled = false;text.setTextFormat(new TextFormat("宋体",12,0xffffff));text = null;}}}定义参数的类：GV.aspackage{public class GV{public function GV(){throw new Error("变量");}//Road创建的初始x、y坐标public static const ROAD_INIT_X:int = 25;public static const ROAD_INIT_Y:int = 25;//纵横方块参数public static const WIDTH_NUMBER:int = 50; public static const HEIGHT_NUMBER:int = 50; public static const WIDTH_TOTAL:int = 500; public static const HEIGHT_TOTAL:int = 500; public static const GRID_WIDTH:int = 10;public static const GRID_HEIGHT:int = 10;//障碍物个数public static const THING_NUMBER:int = 500;//state状态参数表示public static const HAVE_THING:int = 1;public static const IMPASSE_VALUE:int = 2; public static const MAIN_VALUE:int = 8;//路径耗费固定值public static const BIAS_VALUE:int = 14;public static const LINE_VALUE:int = 10;//文本表示public static const IMPASSE:String = "死路！"; public static const RESULT_FRONT:String = "用时 "; public static const RESULT_BACK:String = " 毫秒"; }}主要算法所存在的Road.as类package code{import flash.display.Sprite;import flash.events.MouseEvent;import flash.text.T extField;import flash.text.T extFormat;import flash.utils.clearInterval;import flash.utils.getTimer;import flash.utils.setInterval;public class Road extends Sprite{private var lands:Sprite;private var things:Sprite;private var c:Coordinate;private var main:Main;private var click:Sprite;private var drawPath:Sprite;private var result:TextField;private var unlockList:Array;private var lockList:Object;private var targetIX:int;private var targetIY:int;private var intervalID:int = 0;private var startTime:int;private var endTime:int;public function Road(){init();}//初始化private function init():void{//创建坐标c = new Coordinate;//创建文本框result = new TextField;result.mouseEnabled = false;result.autoSize = "left";result.y = -20;result.selectable = false;result.defaultTextFormat = new TextFormat("宋体",12,0xffffff); addChild(result);result.text = "结果";//创建平原lands = new Sprite;lands.mouseChildren = false;lands.mouseEnabled = false;addChild(lands);lands.graphics.beginFill(0xff0000);lands.graphics.lineStyle(0);lands.graphics.drawRect(0,0,GV.WIDTH_TOTAL,GV.HEIGHT_T OTAL);for(var i:int = 1; i < GV.WIDTH_NUMBER; i ++){lands.graphics.moveTo(GV.GRID_WIDTH * i,0);lands.graphics.lineTo(GV.GRID_WIDTH * i,GV.HEIGHT_TOTAL);lands.graphics.endFill();lands.graphics.moveTo(0,GV.GRID_HEIGHT * i);lands.graphics.lineTo(GV.WIDTH_TOTAL,GV.GRID_HEIGHT * i);lands.graphics.endFill();}//创建障碍层things = new Sprite;things.mouseChildren = false;things.mouseEnabled = false;addChild(things);//创建路线绘制层drawPath = new Sprite;addChild(drawPath);//创建操控人main = new Main;addChild(main);//创建控制区click = new Sprite;click.graphics.beginFill(0,0);click.graphics.drawRect(0,0,GV.WIDTH_TOTAL,GV.HEIGHT_TO TAL);addChild(click);click.addEventListener(MouseEvent.CLICK,clickHandle);//开始初始化randomState();createRoad();}//随机生成障碍private function randomState():void{var ix:int;var iy:int;var i:int = 0;//随机障碍while(i < GV.THING_NUMBER){ix = int(Math.random() * GV.WIDTH_NUMBER);iy = int(Math.random() * GV.HEIGHT_NUMBER);if(c[ix][iy] == null){i ++;c[ix][iy] = GV.HAVE_THING;}}//随机摆放操控人while(true){ix = int(Math.random() * GV.WIDTH_NUMBER);iy = int(Math.random() * GV.HEIGHT_NUMBER);if(c[ix][iy] == null){c[ix][iy] = GV.MAIN_VALUE;break;}}}//创建马路现状private function createRoad():void{for(var i:int = 0; i < GV.WIDTH_NUMBER * GV.HEIGHT_NUMBER; i ++){var state:State = new State;var ix:int = i % GV.WIDTH_NUMBER;var iy:int = Math.floor(i / GV.HEIGHT_NUMBER);state.value = c[ix][iy];switch(state.value){case GV.HAVE_THING://如果等于1表示有障碍var thing:Thing = new Thing;thing.x = ix * GV.GRID_WIDTH;thing.y = iy * GV.GRID_HEIGHT;things.addChild(thing);thing = null;break;case GV.IMPASSE_VALUE://如多等于2表示死路//死路只需将value设置成2即可！break;case GV.MAIN_VALUE://如果等于8表示操控人main.x = ix * GV.GRID_WIDTH;main.y = iy * GV.GRID_HEIGHT;break;}c[ix][iy] = state;}}//点击触发private function clickHandle(e:MouseEvent):void{drawPath.graphics.clear();targetIX = Math.floor(e.localX / GV.GRID_WIDTH);targetIY = Math.floor(e.localY / GV.GRID_HEIGHT);//时间记录startTime = getTimer();var path:Array = seekRoad();endTime = getTimer();//根据路径开始走路walkRoad(path);path = null;}//开始走路private function walkRoad(path:Array):void{//显示寻路消耗时间result.text = GV.RESULT_FRONT + (endTime - startTime) + GV.RESULT_BACK;//判断是否为死路if(path.length == 0){result.text = GV.IMPASSE + result.text;}drawPath.graphics.lineStyle(2,0xffffff);path.just = true;intervalID = setInterval(walkRoadHandle,50,path);}//走路处理private function walkRoadHandle(path:Array):void{//是否路已经走完if(path.length == 0){//结束走路clearInterval(intervalID);//开启触发器click.mouseEnabled = true;return;}//开始走路var obj:Object = path.shift();main.x = obj.x;main.y = obj.y;bj = null;//绘制路径if(path.just){path.just = false;drawPath.graphics.moveTo(main.x + 5,main.y + 5);}else{drawPath.graphics.lineTo(main.x + 5,main.y + 5);}}//开始寻路private function seekRoad():Array{//关闭触发器click.mouseEnabled = false;//判断目标点是不是有障碍，或者是不是死路if(c[targetIX][targetIY].isThing c[targetIX][targetIY].isWalk){ return new Array;}//寻路初始化var path:Array = new Array;unlockList = new Array;lockList = new Object;//初始标记var ix:int = main.ix;var iy:int = main.iy;//创建开始标记var sign:Sign = new Sign(ix,iy,0,0,null);lockList[ix + "_" + iy] = sign;while(true){//生成八个方向的标记开启addUnlockList(createSign(ix + 1,iy - 1,true ,sign)); addUnlockList(createSign(ix + 1,iy ,false,sign)); addUnlockList(createSign(ix + 1,iy + 1,true ,sign)); addUnlockList(createSign(ix - 1,iy + 1,true ,sign)); addUnlockList(createSign(ix ,iy + 1,false,sign)); addUnlockList(createSign(ix - 1,iy ,false,sign)); addUnlockList(createSign(ix - 1,iy - 1,true ,sign)); addUnlockList(createSign(ix ,iy - 1,false,sign));//判断开启列表是否已经为空if(unlockList.length == 0){break;}//从开启列表中取出h值最低的标记unlockList.sortOn("f",Array.NUMERIC);sign = unlockList.shift();lockList[sign.ix + "_" + sign.iy] = sign;ix = sign.ix;iy = sign.iy;//判断是否找出路径if(ix == targetIX && iy == targetIY){while(sign != null){path.push(sign.getSign());sign = sign.p;}break;}}sign = null;return path.reverse();}//添加到开启标记列表private function addUnlockList(sign:Sign):void{if(sign){unlockList.push(sign);unlockList[sign.ix + "_" + sign.iy] = sign;}}//生成标记private function createSign(ix:int,iy:int,p:Boolean,_p:Sign):Sign{//是否出格if(ix < 0 iy < 0 ix >= GV.WIDTH_NUMBER iy >= GV.HEIGHT_NUMBER){return null;}//是否有障碍物if(c[ix][iy].isThing){return null;}//是否已经加入关闭标记列表if(lockList[ix + "_" + iy]){return null;}//是否已经加入开启标记列表if(unlockList[ix + "_" + iy]){return null;}//判断当斜着走的时候，它的上下或者左右是否有障碍物if(p){if(c[_p.ix][iy].isThing c[ix][_p.iy].isThing){return null;}}var cx:Number = Math.abs(targetIX - ix);var cy:Number = Math.abs(targetIY - iy);return new Sign(ix,iy,p ? GV.BIAS_VALUE : GV.LINE_VALUE,(cx + cy) * 10,_p);}}}标记数据记录，Sign.as类package code{public class Sign{private var _ix:Number;private var _iy:Number;private var _p:Sign;private var _f:int = 0;private var _g:int = 0;private var _h:int = 0;//f表示路径评分、g表示当前移动耗费、h表示当前估计移动耗费//公式：f = g + h，表示路径评分的算法//ng值表示以父标记为主标记的g值//nh值表示当前估计移动耗费public function Sign(_ix:Number,_iy:Number,ng:int,nh:int,_p:Sign = null){ this._ix = _ix;this._iy = _iy;this._p = _p;if(_p){_g = _p.g + ng;_h = nh;_f = _g + _h;}}//获取该标记的坐标public function getSign():Object{return {x:_ix * GV.GRID_WIDTH,y:_iy * GV.GRID_HEIGHT};}//获取它表示的x坐标public function get ix():int{return _ix;}//获取它表示的y坐标public function get iy():int{return _iy;}//获取父标记public function get p():Sign{return _p;}//获取路径评分public function get f():int{return _f;}//获取当前路径移动耗费public function get g():int{return _g;}//获取当前路径耗费估值public function get h():int{return _h;}//重写toString值public function toString():String{ return ix + "," + iy;}}}某点状态类，State.aspackage code{public class State{public var value:int = 0;public function State(){}//获取是否障碍public function get isThing():Boolean{ return value == GV.HAVE_THING;}//获取是否死路public function get isWalk():Boolean{return value == GV.IMPASSE_VALUE;}//重写toStringpublic function toString():String{return value.toString();}}}物体类：Thing.aspackage code{import flash.display.Sprite;public class Thing extends Sprite{public function Thing(){init();}//初始化private function init():void{graphics.beginFill(0);graphics.drawRect(0,0,GV.GRID_WIDTH,GV.GRID_HEIGHT); mouseEnabled = false;mouseChildren = false;}}}坐标系类，Coordinate.aspackage code{public dynamic class Coordinate extends Array{public function Coordinate(){init();}//初始化private function init():void{for(var i:int = 0; i < GV.WIDTH_NUMBER; i ++){push(new Array(GV.HEIGHT_NUMBER));}}}}主角类，Main.aspackage code{import flash.display.Sprite;public class Main extends Sprite{public function Main(){init();}//初始化private function init():void{graphics.beginFill(0x0000ff);graphics.drawRect(0,0,GV.GRID_WIDTH,GV.GRID_HEIGHT); mouseEnabled = false;mouseChildren = false;}//获取ix坐标public function get ix():int{return int(x / GV.GRID_WIDTH);}//获取iy坐标public function get iy():int{return int(y / GV.GRID_HEIGHT);}}}源文件打包下载下载源文件，直接打开move.fla运行即可。
浅谈游戏中自动寻路算法的实现与应用作者：蒋恺来源：《中国新通信》 2018年第2期在信息技术的支持下，互联网进入了迅猛发展期，各种网游、页游大量出现，受到不同玩家的喜爱与青睐。
当然为了逐步扩大受众群，需要不断的优化游戏，满足玩家对游戏的需求，其中自动寻路算法就是十分关键的技术之一，提升了游戏角色在虚拟游戏环境中的灵活性，更利于对游戏角色的控制，是判断游戏质量的重要标准之一”1。
一、关于自动寻路算法的概述1.1自动寻路算法的原理在自动寻路算法中最常用的为A*算法，这属于启发式的算法，被广泛应用于游戏中的路径搜索【21。
主要是节点的设置，具有记录、搜索进度的功能，通过节点在游戏地图中移动，当搜寻到目标位置时就结算，否则会进一步搜索记录目标位置周围相邻的位置。
举例而言，游戏角色最初的位置就是开始节点，将要到达的目标位置设置为目标节点，在两者之间存在一定的障碍物和可以顺利通行的路径，黑色部分为障碍物，白色部分为可通行路径，具体如下图1所示：在设计A*算法时采用的基本原理，其实为最短路径算法，在整个游戏地图中，从起始节点到目标节点的路径多种多样，将这些全部读入到开放式列表中，再通过与目标节点距离最近的节点进行对比，从而找到最优路径”1。
将上图1中的起始节点设置为A，目标节点力B，在计算最优路径节点C时需要在考虑几何距离基础上使用计算公式：(A—C)2+fB—C)2在A*算法中通过对各个不同节点的计算，从而找出路径最短最优的节点，但这一算法具有一定的缺陷，很可能要将整个地图上的节点都计算完了才能得出结果，当游戏场景复杂且节点数量过多的话，会大大增加游戏设计制作中的寻路算法的费用。
为此，就要对A*算法进行优化改进，以便扩大应用范围，满足玩家的游戏需求。
1.2自动寻路算法的实现为了最快的找到游戏地图中的最优路径，需要将游戏场景进行网格划分，让每个网路成为大小相同的正方形，成为游戏中的导航网格，就可以选择一个节点起始位置，进行目标节点位置的广度搜索，在确定区域后在计算最佳路径。
会者不难，A*(念作A星)算法对初学者来说的确有些难度。
这篇文章并不试图对这个话题作权威的陈述。
取而代之的是，它只是描述算法的原理，使你可以在进一步的阅读中理解其他相关的资料。
最后，这篇文章没有程序细节。
你尽可以用任意的计算机程序语言实现它。
如你所愿，我在文章的末尾包含了一个指向例子程序的链接。
压缩包包括C++和Blitz Basic 两个语言的版本，如果你只是想看看它的运行效果，里面还包含了可执行文件。
我们正在提高自己。
让我们从头开始。
序：搜索区域假设有人想从A点移动到一墙之隔的B点，如下图，绿色的是起点A，红色是终点B，蓝色方块是中间的墙。
[图1]你首先注意到，搜索区域被我们划分成了方形网格。
像这样，简化搜索区域，是寻路的第一步。
这一方法把搜索区域简化成了一个二维数组。
数组的每一个元素是网格的一个方块，方块被标记为可通过的和不可通过的。
路径被描述为从A到B我们经过的方块的集合。
一旦路径被找到，我们的人就从一个方格的中心走向另一个，直到到达目的地。
这些中点被称为“节点”。
当你阅读其他的寻路资料时，你将经常会看到人们讨论节点。
为什么不把他们描述为方格呢？因为有可能你的路径被分割成其他不是方格的结构。
他们完全可以是矩形，六角形，或者其他任意形状。
节点能够被放置在形状的任意位置－可以在中心，或者沿着边界，或其他什么地方。
我们使用这种系统，无论如何，因为它是最简单的。
开始搜索正如我们处理上图网格的方法，一旦搜索区域被转化为容易处理的节点，下一步就是去引导一次找到最短路径的搜索。
在A*寻路算法中，我们通过从点A开始，检查相邻方格的方式，向外扩展直到找到目标。
我们做如下操作开始搜索：1，从点A开始，并且把它作为待处理点存入一个“开启列表”。
开启列表就像一张购物清单。
尽管现在列表里只有一个元素，但以后就会多起来。
你的路径可能会通过它包含的方格，也可能不会。
基本上，这是一个待检查方格的列表。
2，寻找起点周围所有可到达或者可通过的方格，跳过有墙，水，或其他无法通过地形的方格。
使⽤AStar算法实现⾃动寻路详解@⽬录前些⽇⼦我有兄弟给我打电话，问我会不会⼈⼯智能，来实现⼀个机器⼈在仓库⾃动寻路的功能。
因为没有接触过这样的场景，但是⾃⼰⼜⽐较对此兴趣，所以就看了⼀些⾃动寻路的算法，⽐如：基于⼆叉树的深度优先遍历、D Star、A Star算法，其中我感觉A Star算法最好。
下⾯我给⼤家介绍⼀下，⾸次实现的语⾔是Java，但是Java不太直观，⼜不想使⽤Java的图形界⾯，所以就使⽤JS+HTML来实现的，⾸先展⽰⼀下效果图。
效果图如下：1、什么是A Start算法A*搜索算法是求出在⼀个⼆维平⾯中从起点到终点最低运算代价的算法，它可以算出A点到B点的最短距离，也就是最优路径。
常见的应有主要是在游戏中，⼈物的⾃动寻路；机器⼈探路；交通路线导航等。
2、A Star算法的原理和流程2.1 前提在讲述A Star算法之前，需要声明下列这些属性：（1）从起点开始扩散的节点；（2）最短距离计算公式：F = G + H；（3）欧⼏⾥得距离计算公式：p = $\sqrt (x_2 - x_1)^2+(y_2 - y_1)^2$（其实就是勾股定理）；（4）OPENLIST 和 CLOSELIST；上⾯的属性和公式不懂没关系，下⾯我会对他们⼀⼀进⾏详细介绍。
⾮常简单！2.1.1 从起点开始扩散的节点我们在HTML页⾯上使⽤横和竖画出来的格⼦。
所谓扩散就是以起点为基点向上、下、左、右四个放向进⾏扩散，这些扩展的节点就是可以⾛的“路”。
如下图所⽰黄⾊的⽅格就是扩散的点：PS:A Star有四个⽅向和⼋个⽅向的扩散。
扩展四个⽅向的节点就是⽬前我们所说的；⼋个⽅向是还包含了，上左、上右、下左、下右四个⽅向的节点。
我们通篇使⽤的是四个⽅向的扩展。
2.1.2 最短距离计算公式：F = G + H如何在扩散的节点中找到最优也就是最短的⼀条路呢？就需要⽤到这个公式：F=G+H。
那么这个公式⾥⾯的属性都代表什么意识呢？下⾯我们就说明⼀下：（1）G:表⽰从起点到扩散的四个节点的距离，换句话说就是从起点到扩散的四个节点需要移动的格⼦。
astar.js用法-回复astar.js是一种用于图形和路径搜索的JavaScript库，它提供了一种实现A*搜索算法的简便方法。
A*算法是一种常用的寻找最短路径的算法，它在很多领域都有广泛的应用，例如游戏开发、地图导航等。
在本文中，我将逐步介绍astar.js的使用方法，并解释一些关键概念和步骤，以帮助读者更好地理解和应用这个库。
第一步：安装和引入astar.js库要使用astar.js，首先需要将其文件下载到本地。
你可以在GitHub上找到并下载最新版本的astar.js文件。
一旦下载完成，将其放置在你的项目目录中，并通过<script>标签将其引入到你的HTML文件中，如下所示：html<script src="path/to/astar.js"></script>一旦你成功引入astar.js文件，你就可以开始使用这个库了。
第二步：创建地图在使用astar.js进行路径搜索之前，我们需要先创建一个地图。
地图通常可以表示为一个二维数组，其中每个元素代表了地图上的一个坐标点。
例如，我们可以使用以下代码来创建一个5x5的地图：javascriptvar map = [[0, 0, 0, 0, 0],[0, 1, 1, 0, 0],[0, 0, 1, 0, 0],[0, 1, 1, 0, 0],[0, 0, 0, 0, 0]];在这个地图中，0代表可以通过的路径，1代表障碍物或不可通过的区域。
第三步：创建搜索器对象使用astar.js进行路径搜索需要创建一个搜索器对象。
搜索器对象是astar.js的核心，它将负责执行A*搜索算法并返回最短路径。
要创建一个搜索器对象，你可以使用以下代码：javascriptvar searcher = new AStarSearcher(map);这里的map参数是我们在前一步创建的地图。
通过创建搜索器对象，我们准备好执行A*搜索算法以找到起点到终点的最短路径。
astar寻路算法原理
A（A星）寻路算法是一种常用的启发式搜索算法，用于在图中
找到从起点到终点的最短路径。
它结合了Dijkstra算法和启发式搜
索的优点，具有较高的搜索效率。
A算法基于图的搜索，其中每个节点表示一个状态，边表示从
一个状态到另一个状态的转移。
算法使用两个函数来评估每个节点
的重要性，g(n)表示从起点到节点n的实际代价，h(n)表示从节点
n到终点的估计代价。
A算法通过综合考虑这两个函数来选择下一个
要扩展的节点。
具体来说，A算法通过维护一个开放列表和一个关闭列表来进
行搜索。
它首先将起点加入开放列表，然后重复以下步骤直到找到
终点或者开放列表为空：
1. 从开放列表中选择f(n)=g(n)+h(n)最小的节点n进行扩展。
2. 将节点n从开放列表中移入关闭列表。
3. 对节点n的相邻节点进行检查，更新它们的g值和f值，并
将它们加入开放列表中。
A算法的关键在于如何选择合适的启发函数h(n)以及如何高效地维护开放列表和关闭列表。
合适的启发函数可以大大提高搜索效率，而高效的列表维护可以减少搜索时间。
总的来说，A算法是一种高效的寻路算法，能够在图中找到最短路径，并且可以通过调整启发函数来适应不同的问题。
A星算法中文详解A*算法是一种图算法，用于找到从起始节点到目标节点的最短路径。
它是一种启发式算法，根据每个节点的估计成本来进行。
本文将详细介绍A*算法的原理、步骤和实现。
A* 算法的基本思想是在 Dijkstra 算法的基础上引入启发式函数，目的是在过程中尽量选择离目标节点更接近的路径。
启发式函数通常使用两个估计函数的和：g(n) 是从起始节点到当前节点的实际代价，h(n) 是当前节点到目标节点的估计代价。
通过评估 f(n) = g(n) + h(n) 的值，选择 f(n) 最小的节点作为下一步的节点。
这样，方向就会倾向于更接近目标节点的路径。
A*算法的步骤如下：1. 创建两个空集合：Open 集合和 Closed 集合。
Open 集合存储待考虑的节点，Closed 集合存储已经考虑过的节点。
2. 将起始节点添加到 Open 集合中，并初始化 g(n) 和 h(n) 的值。
3. 从 Open 集合中选择 f(n) 最小的节点作为当前节点，并将其移出 Open 集合，放入 Closed 集合中。
4.对当前节点的相邻节点进行遍历：- 如果相邻节点已经在 Closed 集合中，则忽略它。
- 如果相邻节点不在 Open 集合中，将其添加到 Open 集合，并计算g(n) 和 h(n) 的值。
- 如果相邻节点已经在 Open 集合中，计算经过当前节点到达相邻节点的 g(n) 值。
如果计算得到的 g(n) 值更小，则更新相邻节点的 g(n) 值。
5. 重复步骤 3 和 4，直到找到目标节点或者 Open 集合为空。
如果Open 集合为空且没有找到目标节点，则表示无法到达目标节点。
6.如果找到目标节点，可以通过回溯从目标节点到起始节点的路径。
路径上的节点可以通过每个节点的父节点指针找到。
以上就是A*算法的详细步骤。
A*算法的时间复杂度取决于启发式函数的选择和问题的规模。
通常情况下，A*算法的时间复杂度为O(b^d)，其中b是分支因子，d是目标节点的最短路径长度。
一劳永逸的固定寻路平时我尽我所能，以避免可能被解释为一个在行业中的其他游戏或开发的批评说的事情。
但在这种情况下，我不得不做出一个异常的位。
我要谈谈我们与寻路面临的一些问题。
为了证明，这些问题仍然存在，我觉得有必要使这个视频... ...在幽默和轻松愉快的精神，它的目的是，希望在采取所有这些片段在上周录得最新，最最近修补的每场比赛的版本。
正如你可以看到，我们仍然是一个强大的寻路全线长的路要走... ...它甚至在一些万元的单位销售，AAA级质量职称的问题。
它不一定是一个普遍性的问题。
许多现代游戏有高品质的寻路，寻路经常在这里显示的一些游戏。
但仍有太多的游戏，寻路，游戏在20世纪90年代，以同样的方式。
（注：只是你看到大量的PC角色扮演游戏的唯一原因归结到便利，这些都是我当时安装的游戏，问题是不特定的任何类型或任何发挥想象力的平台。
有类似的问题，大量的游戏机游戏）。
据我所知，这些游戏大多使用寻路航点图。
我认为这几个寻路的问题，您在这个视频中看到，许多我们在整个行业面临的寻路问题的原因。
我相信航点图现在已经过时。
这篇文章解释了航点图方法的局限性，并勾画出了一个更好的方法五点的说法。
曾经有一段时间，这是有意义的，使用寻路航点。
早在20世纪80年代和90年代，我们的工作受到严重的技术限制，我们不得不削减了很多弯道。
但是我们现在一个多亿美元的产业。
我们的目标平台多内核和日益增加的大量的内存，我们可以做不起寻路正确。
有一个行业AI开发中说：“寻路是解决了。
”我们每一个寻路的问题，面临着现代游戏的好方法。
我们只是不经常使用它们。
我们没有理由不寻路，在每场比赛，每次。
打跳了详细的解释。
为什么航点对于寻路让我告诉你什么是一个典型的航点图看起来。
下面是一个在魔兽世界暴风城的小片：图1。
魔兽世界暴风城的一部分，下面是一个典型的航点图可能看起来在这方面想。
图2。
同一地区的一个航点图注释还有另一种方式做到这一点，它涉及使用凸多边形来描述AI角色可以旅行。
简易的A星算法⾃动寻路（C#）路径计算⽅式（详见参考：堪称最好最全的A*算法详解（译⽂））：1. 曼哈顿距离，横向和纵向直线距离，仅限于横向纵向移动2. 对⾓线距离，对⾓线 + 直线，可以横向、纵向、对⾓线⽅向移动3. 欧⼏⾥得距离，任意⾓度直线，任意⽅向移动using System.Collections;using System.Collections.Generic;using UnityEngine;using System.Linq;public class AStartTest{AStarNode[,] nodeMap = new AStarNode[10, 10];void CheckAndFindPath(AStarNode startNode, AStarNode endNode){//计算路径List<AStarNode> pathNodes = FindNodePath(startNode, endNode, nodeMap);if (pathNodes == null || pathNodes.Count == 0)return;//计算路径折点List<AStarNode> pathPoints = GetPathPoint(pathNodes);}//计算路径折点List<AStarNode> GetPathPoint(List<AStarNode> path){List<AStarNode> tmpPointList = new List<AStarNode>();//⽆折点if (path.Count <= 2)return tmpPointList;//当前节点与前⼀节点的位置关系(X坐标相同或Y坐标相同)bool lastDirIsX = path[1].pos.x == path[0].pos.x;//计算折点for (int i = 2; i < path.Count; i++){//若与前⼀节点X坐标相同if (path[i].pos.x == path[i - 1].pos.x){//前两个节点时Y坐标相同，即为折点if (!lastDirIsX){//记录折点，记录当前节点关系tmpPointList.Add(path[i - 1]);lastDirIsX = true;}}else{if (lastDirIsX){tmpPointList.Add(path[i - 1]);lastDirIsX = false;}}}//路径最后节点也视为折点tmpPointList.Add(path[path.Count - 1]);//return tmpPointList;}#region --- A*算法 ---//计算最短有效路径List<AStarNode> openList = new List<AStarNode>();List<AStarNode> closeList = new List<AStarNode>();List<AStarNode> aroundNodes;List<AStarNode> FindNodePath(AStarNode startNode, AStarNode endNode, AStarNode[,] allNodes) {//计算范围内的节点openList.Clear();//不在计算范围内的节点closeList.Clear();//添加起点openList.Add(startNode);AStarNode curNode;//从起点开始循环判断while (openList.Count > 0){//初始当前位置curNode = openList[0];//计算最优当前位置for (int i = 0; i < openList.Count; i++){//F:从起点到⽬标点的移动步数//H:从当前位置到⽬标位置的移动步数if (openList[i].CostF < curNode.CostF && openList[i].costH < curNode.costH){curNode = openList[i];}}//锁定当前位置节点openList.Remove(curNode);closeList.Add(curNode);////已经计算到⽬标点//if (curNode.Equals(endNode))//{// //返回最优路径// return GetPathWithNode(startNode, endNode);// }//未计算到⽬标点, 继续//获取当前点的周围节点, 在周围节点中查找下⼀步的最优节点aroundNodes = GetAroundNodes(curNode, allNodes);for (int i = 0; i < aroundNodes.Count; i++){//计算到⽬标点if (aroundNodes[i].Equals(endNode)){//设置上⼀节点aroundNodes[i].lastNode = curNode;//返回最优路径return GetPathWithNode(startNode, endNode);}//不是⽬标点, 继续计算, 剔除周围节点不可通过、在不可计算范围内的节点if (!aroundNodes[i].isWall && !closeList.Contains(aroundNodes[i])){//计算 G H F//F:从起点到⽬标点的移动步数//G:从起点到当前位置的移动步数int newCostG = curNode.costG + GetNodesDistance(curNode, aroundNodes[i]);if (newCostG <= aroundNodes[i].costG || !openList.Contains(aroundNodes[i])){//刷新赋值aroundNodes[i].costG = newCostG;//H:从当前位置到⽬标位置的移动步数aroundNodes[i].costH = GetNodesDistance(aroundNodes[i], endNode);//设置上级节点aroundNodes[i].lastNode = curNode;//添加到计算范围内if (!openList.Contains(aroundNodes[i])){openList.Add(aroundNodes[i]);}}}}}return null;}//计算距离int GetNodesDistance(AStarNode startNode, AStarNode endNode){return Mathf.Abs(startNode.pos.x - endNode.pos.x) + Mathf.Abs(startNode.pos.y - endNode.pos.y);}//周围节点只取上下左右四个, 不取对⾓线（根据实际需求设置周围节点）Vector2Int[] aroundPos = { new Vector2Int(0, 1), new Vector2Int(0, -1), new Vector2Int(1, 0), new Vector2Int(-1, 0) }; //获取周围NodeList<AStarNode> tmpAroundList = new List<AStarNode>();List<AStarNode> GetAroundNodes(AStarNode curNode, AStarNode[,] allNodes){tmpAroundList.Clear();for (int i = 0; i < aroundPos.Length; i++){//计算周围节点坐标int x = curNode.pos.x + aroundPos[i].x;int y = curNode.pos.y + aroundPos[i].y;//剔除不在取值范围内的数据if (x >= 0 && x < allNodes.GetLength(0) && y >= 0 && y < allNodes.GetLength(1)){if (allNodes[x, y] != null)tmpAroundList.Add(allNodes[x, y]);}}return tmpAroundList;}//获取路径(包含起点)List<AStarNode> tmpNodePath = new List<AStarNode>();List<AStarNode> GetPathWithNode(AStarNode startNode, AStarNode endNode){tmpNodePath.Clear();if (endNode != null){//逆向查找路径AStarNode temp = endNode;while (temp != startNode){tmpNodePath.Add(temp);temp = stNode;}tmpNodePath.Add(startNode);//路径数据反向tmpNodePath.Reverse();}return tmpNodePath;}#endregion}public class AStarNode{//A*算法节点类//是否能通过public bool isWall;//位置坐标public Vector2Int pos;//上个节点public AStarNode lastNode;//从起点到当前位置的移动步数public int costG;//从当前位置到⽬标位置的移动步数public int costH;//从起点到⽬标点的移动步数public int CostF{get { return costG + costH; }}public AStarNode(bool _isWall, Vector2Int _pos) {isWall = _isWall;pos = _pos;}//重写Equalspublic override bool Equals(object obj){if (obj is AStarNode){AStarNode objNode = (AStarNode)obj;return objNode.pos == pos;}return false;}public override int GetHashCode(){return base.GetHashCode();}}。
astar寻路算法原理-回复A*寻路算法原理及步骤一、简介A*（A-Star）寻路算法是一种常用的路径规划算法，用于找到两个点之间的最短路径。
它综合了Dijkstra算法和贪心算法的优点，既考虑了每个节点的代价，也考虑了每个节点到目标节点的预估代价。
本文将一步一步详细介绍A*寻路算法的原理和步骤。
二、原理A*算法的核心思想是使用一个估算函数来预测从起始节点到目标节点的代价，并在遍历过程中选择最小代价节点来进行扩展。
该算法综合了代价函数和启发函数的信息，以更快地找到最短路径。
其具体步骤如下：1. 初始化将起始节点添加到一个开放列表(open list)中，开放列表存放待扩展的节点。
同时，创建一个空的闭合列表(closed list)，用于存放已扩展过的节点。
2. 循环操作进入循环操作，直到开放列表为空或找到目标节点。
在每次循环中，选择开放列表中代价最小的节点进行扩展。
3. 节点扩展取开放列表中代价最小的节点，将其从开放列表中删除，并加入到闭合列表中。
然后，获取该节点的相邻节点，计算它们的代价和预估代价，并更新它们的代价值和路径。
4. 判断相邻节点对于每个相邻节点，判断它们是否在开放列表或闭合列表中。
若在闭合列表，则跳过该节点；若在开放列表，比较新路径与旧路径的代价，若新路径更好，则更新代价和路径；否则，不做任何操作。
5. 添加新节点对于不在开放列表中的相邻节点，将它们添加到开放列表中，并计算它们的代价和预估代价。
6. 重复操作重复步骤2至5，直到开放列表为空或找到目标节点。
若开放列表为空，则无法找到路径；若找到目标节点，则回溯路径，回到起始节点。
三、关键要点在上述步骤中，有几个关键要点需要注意：1. 代价函数代价函数用于计算节点到起始节点的实际代价，包括走过的距离、障碍物等影响因素。
根据具体情况，可以自定义代价函数。
2. 启发函数启发函数用于估算节点到目标节点的代价，即预测代价。
常见的启发函数有曼哈顿距离、欧几里得距离等，根据实际情况选择合适的启发函数。
