Egret寻路算法Astar

news/2024/11/8 5:57:31/

        A*算法是很经典的只能启发式搜索算法，那么下面我们具体看看A*算法！

                                                    


我们要想从绿色的点到红色的点，需要启发式得去找一条路径，到底怎么去找呢，开始没有办法，只能从开始点慢慢尝试！我们需要定义一个OPEN表，OPEN表中放的是什么呢？就是当前考虑的点，及其周边的点需要添加进来，作为可能的路径上的点。这样说可能有点抽象，那么先看下面：

                                                                  

我们从起始点开始搜索：

   1：从点A开始，并且把它作为待处理点存入一个OPEN表。你的路径可能会通过它包含的方格，也可能不会。基本上，这是一个待检查方格的列表。
   2：寻找起点周围(邻居)所有可到达或者可通过的方格，如果有障碍物方格。那么就不需要考虑他们，对于其他的吕剧节点也把他们加入OPEN表。这些邻居节点认当前点为父节点。(父节点的保存是必须的！因为当我们找到最后一个点的时候，需要通过父节点回溯，找到所有点直到开始节点！那么就是一个完整的路径！)
   3：从开启列表中删除点A，把它加入到一个CLOSE列表，列表中保存所有不需要再次检查的方格。

在这一点，你应该形成如图的结构。在图中，暗绿色方格是你起始方格的中心。它被用浅蓝色描边，以表示它被加入到关闭列表中了。所有的相邻格现在都在开启列表中，它们被用浅绿色描边。每个方格都有一个灰色指针反指他们的父方格，也就是开始的方格。

                                                                    


结下来我们应该选择哪一个点继续考虑呢！我想大家应该知道所谓的启发函数，所谓权值之类(此处所谓的权值就是路劲的长度)。YES，我们需要OPEN表中权值F最小的那个点！为什么呢，当然是权值越小，越靠近目标点咯！

对于权值我们设为F，那么F怎么计算到的！我们有两个项！G和H， 

G = 从起点A，沿着产生的路径，移动到网格上指定方格的路径耗费。
H = 从网格上那个方格移动到终点B的预估移动耗费。这经常被称为启发式的。这样叫的原因是因为它只是个猜测。

例如：H值的估计采用“曼哈顿”法，也就是当前的点，到目标点，横向和纵向的格子数相加，就是H值！

           ( 注意：对于障碍物我们是不考虑是否跳过的问题！即，障碍物也当做正常的一个格子！这也是H值仅仅是预测的而已的原因！即所谓启发式！ )

那么对于第一幅图，起始点离终点的H值是：横向相差4个格子，纵向相差0个格子，那么H=4+0=4；

当然也有其他的办法，例如使用直线距离，sqrt( pow( des.x - src.x ) + pow( des.y - src.y ) )也是可以的~


对于G值！在这个例子，令水平或者垂直移动的耗费为10，对角线方向耗费为14。我们取这些值是因为沿对角线的距离是沿水平或垂直移动耗费的的根号2约1.414倍。为了简化，我们用10和14近似。有时候简化是很重要的~

( 其实距离只要反应了基本的倍数关系就可以了！ )

对于起始点以及周围点的G值，H值和F值，下图可以很清晰的看到！( 左上角是F，左下角是G，右下角是H )

                                          

对于G值，只要是横向和竖向的邻居，设为+10，斜向的邻居+14就可以了~计算真的很easy吧~呵呵~

对于H值，就是数格子就是咯~

F = G + H

注意上面的邻居节点都加入OPEN表了哦~~~   起点从OPEN中删除，加入CLOSE中~

接着计算：

然后从OPEN表中选择一个F值最小的然后考虑其周围邻居，再循环处理！直到终点加入CLOSE中，寻路结束！或者OPEN空了，没找到路径！

( 至于我们怎么选出最小的那个点呢！？我们使用堆排序处理的，对于选出最小值是很快的~ )

可以看到，F最小的是起始点右边的那个点，下面框框表示的~

                                  

然后再考虑其邻居：

此时对于其邻居有几种可能性！

1：邻居已经在CLOSE表中了，那么不需要考虑了~

2：邻居是障碍物，不需要考虑了e

3：邻居不在OPEN表中，那么将邻居加入OPEN，并将次邻居的父节点赋值为当前节点

4：邻居在OPEN中，那么需要看看此邻居点的G值与当前点的(G值+当前点到邻居点的距离(10或者14))的大小，如果从此点走更近(即G值更小)，那么将此点的父节点换成当前点！(注意：对于同一个点，G值下，那么F必须小！因为H是相同的！)

下面是进一步的图示： 

                                             

那么我们按照上面的思路，知道终点加入CLOSE表！（ 终极图示如下 ）

                                                  

最终我们可以得到路径：( 之前我们说过，由父节点往前回溯就很easy的得到路径了~ )

                                    

说了这么多，也不知道说的行不行，还是需要总结一下！

总结：

1：将起始点加入OPEN表中

2：循环直到OPEN为空或者终点加入CLOSE表中

否则：找到OPEN表中F值最小的节点(使用堆排序得到小值点)，将此点从OPEN删除，加入CLOSE！

  (此时最小点已经取出，那么需要从新排序OPEN表，是的第一个点是最小F的点！)

   对8个邻居进行处理：

若：1：邻居已经在CLOSE表中了，那么不需要考虑了~

2：邻居是障碍物，不需要考虑了e

3：邻居不在OPEN表中，那么将邻居加入OPEN，并将次邻居的父节点赋值为当前节点

4：邻居在OPEN中，那么需要看看此邻居点的G值与当前点的(G值+当前点到邻居点的距

     离 (10或者14))的大小，如果从此点走更近(即G值更小)，那么将此点的父节点换成当前           点！  (注意：对于同一个点，G值下，那么F必须小！因为H是相同的！)

     注意：当父节点改变后，OPEN表中的最小点可能会变化，那么需要再次排序得到最

        小点！

3：结束，根据退出循环的条件可以知道到底有没有找到路径！所以下面的工作就easy了~


二、关于游戏中中的使用   下面我们来看TS代码吧！

首先我们要制作tileMap地图：http://blog.csdn.net/egret_or_unity/article/details/69390707


2.Astar类

/**** @author **/
'use strict';
module gtm{export class AstarPathStep{m_tilePos: egret.Point;m_gScore: number = 0;m_hScore: number = 0;m_parent: AstarPathStep;m_inOpen = false;m_inClose = false;public constructor(tilePos: egret.Point) {this.m_tilePos = tilePos;this.m_parent = null;}/*** 返回这个点的f评分   Astar 权值 F=G+H * */public fScore(): number {return this.m_gScore + this.m_hScore;}/*** 是同一个AstarPathStep* */public isEqual(setp: AstarPathStep): boolean {if(this.m_tilePos.x == setp.m_tilePos.x && this.m_tilePos.y == setp.m_tilePos.y) {return true;}return false;}/*** 是同一个点* */public isEqualByPos(pos: egret.Point): boolean {if(this.m_tilePos.x == pos.x && this.m_tilePos.y == pos.y) {return true;}return false;}/*** 设置为开放节点* */public setInOpen(flag) {this.m_inOpen = flag;}/*** 设置为关闭节点* */public setInClose(flag) {this.m_inClose = flag;}}export class Astar {private static _instance: Astar;static get instance(): Astar {if(!this._instance) {this._instance = new Astar();}return this._instance;}/*** 开放节点列表* */m_openList: Array<AstarPathStep>/* = new Array<AstarPathStep>()*/;/*** 关闭节点列表* */m_closeList: gtm.HashMap = new gtm.HashMap();  //<Map>/*** 横向移动一格的评分* */public static COST_HORIZONTAL = 20;    //根据实际的TileMap定义值/*** 竖向移动一格的路劲评分* */public static COST_VERTICAL = 10;	  //根据实际的TileMap定义值/*** 斜向移动一格的路劲评分* */public static COST_DIAGONAL = 12;     //根据实际的TileMap定义值public constructor() {}/*** 地图类对象* */public tileMap: gtm.TiledMap;/*** 寻路* */public findPath(startPos: egret.Point,endPos: egret.Point,tileMap: gtm.TiledMap) {this.tileMap = tileMap;//地图var isFind = false;var starTime = egret.getTimer();//开始寻路的时间if(egret.Point.distance(startPos,endPos) < 0.5) {if(Global.logLevel > Global.logLevelInfo) {console.log("You're already there! :P");}return null;}if(tileMap.isPass(endPos.x,endPos.y) != true) {if(Global.logLevel > Global.logLevelInfo) {console.log("blocf or beyond the range");}return null;}if (!this.m_openList)this.m_openList = new Array<AstarPathStep>();this.m_closeList.clear();var endStep = new AstarPathStep(endPos);var startStep = new AstarPathStep(startPos);startStep.m_hScore = this.getHValue(startStep,endStep);this.insertAndSort(startStep);var curStep: AstarPathStep;do { var elapesTime = egret.getTimer() - starTime;
//                if(elapesTime > 600) {
//                    isFind = false;
//                    //寻路超时
//                    break;
//                }curStep = this.m_openList.shift();curStep.setInClose(true);curStep.setInOpen(false);this.m_closeList.put(curStep.m_tilePos.x + "_" + curStep.m_tilePos.y,true);if(curStep.isEqualByPos(endPos)) {isFind = true;break;}var arundNodes = this.getAroundsNode(curStep.m_tilePos);for(var i = 0;i < arundNodes.length;i++) {var onePos = arundNodes[i];var nextStep = new AstarPathStep(onePos);var gValue = this.getGValue(curStep,nextStep);var hValue = this.getHValue(endStep,nextStep);if(nextStep.m_inOpen == true) {if(gValue < nextStep.m_gScore) {nextStep.m_gScore = gValue;nextStep.m_hScore = hValue;nextStep.m_parent = curStep;this.findAndSort(nextStep);}} else {nextStep.m_gScore = gValue;nextStep.m_hScore = hValue;nextStep.m_parent = curStep;this.insertAndSort(nextStep);}}} while(this.m_openList.length > 0);if(isFind) {var path = this.createPath(curStep);//this.m_openList = new Array<AstarPathStep>();this.m_openList.length = 0;this.m_closeList.clear();return path;} else {//this.m_openList = new Array<AstarPathStep>();this.m_openList.length = 0;this.m_closeList.clear();return null;}}public createPath(step: AstarPathStep) {var path: Array<egret.Point> = new Array<egret.Point>();do{if(step.m_parent != null){var curPos: egret.Point = step.m_tilePos;path.unshift(curPos);}step = step.m_parent;} while(step != null) return path;}//private findAndSort(step: AstarPathStep) {var openCount = this.m_openList.length;if(openCount < 1) {return}var stepFScore = step.fScore();for(var i = 0;i < openCount;i++) {var oneStep = this.m_openList[i];if(step.isEqual(oneStep) == false) {if(stepFScore <= oneStep.fScore()) {this.m_openList.splice(i,0,step);}if(step.isEqual(oneStep)) {this.m_openList.splice(i,1);}}}}/*** 获取G值* */public getGValue(curStep: AstarPathStep,nextStep: AstarPathStep): number {var extaScore = 0;var curPos = curStep.m_tilePos;var nextPos = nextStep.m_tilePos;var G = 0;if(curPos.y == nextPos.y) {//横向移动G = curStep.m_gScore + Astar.COST_HORIZONTAL;} else if(((curPos.y + 2) == nextPos.y) || ((curPos.y - 2) == nextPos.y)) {G = curStep.m_gScore + Astar.COST_VERTICAL * 2;} else {G = curStep.m_gScore + Astar.COST_DIAGONAL;}return G;}/*** 获取周围的节点* */public getAroundsNode(tpt: egret.Point): Array<egret.Point> {var aroundNodes: Array<egret.Point> = new Array();var p: egret.Point = new egret.Point();//左下p = new egret.Point(tpt.x - 1 + tpt.y % 2,tpt.y + 1);if(this.isWalkable(p) && this.isInClosed(p) == false) {aroundNodes.push(p);}p = new egret.Point(tpt.x + tpt.y % 2,tpt.y - 1);//右上if(this.isWalkable(p) && this.isInClosed(p) == false) {aroundNodes.push(p);}var p: egret.Point = new egret.Point();//下p.x = tpt.xp.y = tpt.y + 2;if(this.isWalkable(p) && this.isInClosed(p) == false) {aroundNodes.push(p);}//左p = new egret.Point(tpt.x - 1,tpt.y);if(this.isWalkable(p) && this.isInClosed(p) == false) {aroundNodes.push(p);}//右p = new egret.Point(tpt.x + 1,tpt.y);if(this.isWalkable(p) && this.isInClosed(p) == false) {aroundNodes.push(p);}//上p = new egret.Point(tpt.x,tpt.y - 2);if(this.isWalkable(p) && this.isInClosed(p) == false) {aroundNodes.push(p);}p = new egret.Point(tpt.x - 1 + (tpt.y % 2),tpt.y - 1);//左上if(this.isWalkable(p) && this.isInClosed(p) == false) {aroundNodes.push(p);}//右下p = new egret.Point(tpt.x + (tpt.y % 2),tpt.y + 1);if(this.isWalkable(p) && this.isInClosed(p) == false) {aroundNodes.push(p);}return aroundNodes;}public isInClosed(tpt: egret.Point): boolean {//if(AStarPathFinder.instance.m_closeList.keys.length > 0){if(this.m_closeList.get(tpt.x + "_" + tpt.y)) {return true;} else {return false;}//        }else{//            return false;//        }}public isWalkable(tpt: egret.Point): boolean {if(this.tileMap.isPass(tpt.x,tpt.y)) {return true;}return false;}/*** 获取H值* */public getHValue(endStep: AstarPathStep,nextStep: AstarPathStep): number {var to0 = nextStep.m_tilePos.x * Astar.COST_HORIZONTAL + (Math.floor(nextStep.m_tilePos.y) % 2) * Astar.COST_HORIZONTAL / 2;var endTo0 = endStep.m_tilePos.x * Astar.COST_HORIZONTAL + (Math.floor(endStep.m_tilePos.y) % 2) * Astar.COST_HORIZONTAL / 2;return Math.abs(endTo0 - to0) + Math.abs(endStep.m_tilePos.y - nextStep.m_tilePos.y) * Astar.COST_VERTICAL;}/*** 插入* */private insertAndSort(step: AstarPathStep) {step.setInOpen(true);var stepFScore = step.fScore();var openCount = this.m_openList.length;if(openCount == 0) {this.m_openList.push(step);} else {for(var i = 0;i < openCount;i++) {var oneStep = this.m_openList[i];if(stepFScore <= oneStep.fScore()) {this.m_openList.splice(i,0,step);return}}}}/*** 返回移动方向* */public judgeNextDirection(curPos,nextPos): number {var p = new egret.Point(curPos.x - 1,curPos.y);if(egret.Point.distance(p,nextPos) < 0.1) {return EnumManager.DIRECTION_ENUM.DIR_LEFT;}var p = new egret.Point(curPos.x,curPos.y - 2);if(egret.Point.distance(p,nextPos) < 0.1) {return EnumManager.DIRECTION_ENUM.DIR_UP;}var p = new egret.Point(curPos.x + 1,curPos.y);if(egret.Point.distance(p,nextPos) < 0.1) {return EnumManager.DIRECTION_ENUM.DIR_RIGHT;}var p = new egret.Point(curPos.x,curPos.y + 2);if(egret.Point.distance(p,nextPos) < 0.1) {return EnumManager.DIRECTION_ENUM.DIR_DOWN;}var p = new egret.Point(curPos.x - 1 + curPos.y % 2,curPos.y - 1);if(egret.Point.distance(p,nextPos) < 0.1) {return EnumManager.DIRECTION_ENUM.DIR_UP_LEFT;}var p = new egret.Point(curPos.x + curPos.y%2,curPos.y - 1);if(egret.Point.distance(p,nextPos) < 0.1) {return EnumManager.DIRECTION_ENUM.DIR_UP_RIGHT;}var p = new egret.Point(curPos.x + curPos.y%2,curPos.y + 1);if(egret.Point.distance(p,nextPos) < 0.1) {return EnumManager.DIRECTION_ENUM.DIR_DOWN_RIGHT;}var p = new egret.Point(curPos.x - 1 + curPos.y%2,curPos.y+1);if(egret.Point.distance(p,nextPos) < 0.1) {return EnumManager.DIRECTION_ENUM.DIR_DOWN_LEFT;}console.log("方向解析失败");//方向解析失败后直接使用角度进行方向解析var angleSpeed: number = Math.atan2(curPos.y - nextPos.y,curPos.x - nextPos.x);var N = angleSpeed * 180 / Math.PI;if(N <= 20 && N >= -20) {return EnumManager.DIRECTION_ENUM.DIR_LEFT;} else if(N <= 110 && N >= 70) {return EnumManager.DIRECTION_ENUM.DIR_UP;} else if(N <= -170 || N >= 170) {return EnumManager.DIRECTION_ENUM.DIR_RIGHT;} else if(N <= -70 && N >= -110) {return EnumManager.DIRECTION_ENUM.DIR_DOWN;} else if(N < 70 && N > 20) {return EnumManager.DIRECTION_ENUM.DIR_UP_LEFT;} else if(N < 170 && N > 110) {return EnumManager.DIRECTION_ENUM.DIR_UP_RIGHT;} else if(N < -110 && N > -170) {return EnumManager.DIRECTION_ENUM.DIR_DOWN_RIGHT;} else if(N < -20 && N > -70) {return EnumManager.DIRECTION_ENUM.DIR_DOWN_LEFT;}return EnumManager.DIRECTION_ENUM.DIR_DOWN;}}
}






HashMap 
HashMap 
module gtm {export class HashMap extends egret.HashObject {constructor() {super();}/*** 加入数据* @param key 键* @param value 值*/put(key:any, value:any):void {this[key] = value;}/*** 获得数据* @param key 键*/get(key:any):any {return this[key];}/*** 移除数据* @param key 键*/remove(key:any):any {var value = this[key];if (value) {this[key] = null;chengongwei add at 2016-08-15delete this[key];//then undefined}return value;//should outter be = null, for clear memory}/*** 是否存在* @param key 键*/contains(key:any):boolean {return this[key] != null;}/*** 获得所有键值*/keys():string[] {var keys = Object.keys(this);var index = keys.indexOf("$hashCode");//4.0版本更新将"_hashCode"更改为"$hashCode"，Egret  3.23以前版本用“_hashCode”；if (index > -1) {keys.splice(index, 1)}return keys;}/*** 清空*/clear():void {var keys = this.keys();var len = keys.length;for (var i = 0; i < len; i++) {let value = this.remove(keys[i]);value = null;}}}
}





























    













http://www.ppmy.cn/news/644118.html












相关文章










高斯金字塔和拉普拉斯金字塔









高斯金字塔和拉普拉斯金字塔




转自https://www.cnblogs.com/sddai/p/10330756.html 
1、图像金字塔 图像金字塔是图像中多尺度表达的一种&#xff0c;最主要用于图像的分割&#xff0c;是一种以多分辨率来解释图像的有效但概念简单的结构。 
图像金字塔最初用于机器视觉和图像压缩&#xff0c;一幅图像的金字…




阅读更多...

















15. 图像金字塔-高斯金字塔、拉普拉斯金字塔、DOG金字塔









15. 图像金字塔-高斯金字塔、拉普拉斯金字塔、DOG金字塔




1.  什么是图像金字塔 
图像金字塔是图像处理和计算机视觉中常用到的概念&#xff0c;常常用于多尺度处理领域&#xff08;multiscale processing)&#xff0c;尤其早年的图像匹配、识别、图像分割等算法中都用到了图像金字塔。一幅图像的金字塔是一系列以金字塔形状排列的分辨…




阅读更多...

















Lucas定理推导过程(全网最全,哈哈哈哈)









Lucas定理推导过程(全网最全,哈哈哈哈)




和大家一起学习Lucas定理,在网上找了好久都没有找到详细的推导过程,这大概就是传说中的的一血了吧 
求证  C n m  C n / p m / p ∗ C n % p m % p ( m o d ( p ) ) C_n^m  C_{n/p}^{m/p} * C_{n\%p}^{m\%p}\quad\quad\quad(mod(p)) Cnm​Cn/pm/p​∗Cn%pm%p​(mod(p)) p为素数…




阅读更多...

















电脑群控Android手机技术，免费实现电脑端控制多台手机









电脑群控Android手机技术，免费实现电脑端控制多台手机




需要集线器&#xff0c;链接usb链接手机&#xff0c; 软件都是免费的&#xff1a; 两款软件实现 一个是沙盒 一个是airdroid电脑客户端




阅读更多...

















Scrcpy -用电脑控制 Android 手机-安卓投屏控制软件









Scrcpy -用电脑控制 Android 手机-安卓投屏控制软件




https://www.iplaysoft.com/scrcpy.html 
Scrcpy – 用电脑控制 Android 手机 
https://www.appinn.com/scrcpy-remote-android-from-computer/




阅读更多...

















【安卓】电脑执行脚本控制安卓手机









【安卓】电脑执行脚本控制安卓手机




电脑执行脚本控制安卓手机 一、通过安卓的ADB&#xff08;需要会安卓开发&#xff09; 二、Total Control&#xff08;推荐/简单&#xff09; 
http://tc.sigma-rt.com.cn/index.php 三、待补充




阅读更多...

















Windows电脑如何控制安卓手机









Windows电脑如何控制安卓手机




大家可能都知道电脑控制电脑&#xff0c;手机控制手机&#xff0c;是否尝试过用电脑控制手机呢&#xff1f; 
其实很简单&#xff0c;一款免费的远控软件就能实现&#xff0c;今天就教大家如何用实现Windows电脑控制安卓手机的案例。被控安卓手机需要先领取安卓授权&#xff1a…




阅读更多...

















wifi下adb连接电脑控制手机屏幕









wifi下adb连接电脑控制手机屏幕




​ 
先连接adb后打开scrcpy就能看到并控制小米8手机了&#xff0c;用一下数据线。后wifi连接。 
​​ 
打开手机设置&#xff0c;点击“我的设备”&#xff0c;选择“全部参数” 
连续点击MIUI版本几次&#xff0c;返回到设置主界面&#xff0c;点击“更多设置” 
点击“开发者…




阅读更多...















 
 
 
 










最新文章







 





















Copyright @ 2022~2023