A Star算法原理及其实现

article/2025/3/3 5:20:04

A －Star算法

A －Star算法

A*（A-Star)算法是一种求解最短路径最有效的直接搜索方法，也是许多其他问题的常用启发式算法。

一、简介

二、寻路方式

三、运行机制

四、常用估价算法

五、示例

一、简介

A*（A-Star)算法是一种求解最短路径最有效的直接搜索方法，也是许多其他问题的常用启发式算法。注意——是最有效的直接搜索算法，之后涌现了很多预处理算法（如ALT，CH，HL等等），在线查询效率是A*算法的数千甚至上万倍。

公式表示为： f(n)=g(n)+h(n),

其中，

f(n) 是从初始状态经由状态n到目标状态的代价估计，

g(n) 是在状态空间中从初始状态到状态n的实际代价，

h(n) 是从状态n到目标状态的最佳路径的估计代价。

（对于路径搜索问题，状态就是图中的节点，代价就是距离）

FGH示意图如下所示（图中格子左下角为G值，右下角为H值，左上角为F值）：

 

因此从当前格子周边的八个格子中找到下一步所走的格子，依据F值，当F值相同时随机选择。

当然在寻路过程中，会有障碍，不能通过，通过可以行走的格子走到终点。下图中绿色为起点，红色为终点，蓝色是障碍，浅蓝边框是参与计算的格子，A*就是通过这样的一系列计算完成的最优寻路。

 

二、寻路方式

A* 算法常用的寻路方式有三种：基于单元的导航图、基于可视点的导航图以及导航网格。

1) 基于单元的导航图：将地图划分为由多个正方形或者六边形组成的规则网格，网格点或往各单元的中心可以看作是寻路节点。此种方式适用于塔防、即时战略或者其他频繁动态更新场景的游戏中，但此种方式易造成巨大的内存开销，原因在于寻路过程中，对于复杂地形需要将可行走区域和不可行走区域进行标记，并且需要为单元格记录地形信息，需要消耗大量的存储空间，另外单元格的大小，也影响着寻路结果和内存消耗情况。如下图所示是基于单元的导航图：

2) 基于可视点的导航图实现时，一般先由场景设计者在场景中手工放置一些“路径点”， 然后由设计人员逐个测试这些“路径点”之间的可视性。此种导航方式最大优点在于它的灵活性，分散在各处的路径点是由场景设计者精心选择的，能覆盖绝大部分可行走的区域，还可以将其他一些重要位置的点包含进去。此种方式存在一定的缺点，首先，当场景很大时，手工放置路径点是非常繁琐的工作，也很容易出错，其次，此种方式主要是一些点和线段的集合，角色只能沿着那些边运动，无法表示出实际的二维可行走区域，最后，该种方式也存在组合爆炸的问题，例如：如果设置了100个路径点，就可能需要测试99 * 100条路径。如下图所示，即为基于可视点的导航图

 

3) 导航网格将游戏场景中的可行走区域划分成凸多边形。导航网格能够表示出可行走区域的真实几何关系，是一个非均匀网格。Unity3D自带的导航系统就简历在导航网格的基础上。导航网格的有点是可以进行精确的点到点移动，其次，非常高效，原因在于多边形的面积可以任意大，因此，只需要较少的多边形，就可以表示出很大的可行走区域，不但占用的内存较小，搜索路径的速度也会有很大的提高。另外，导航网格的生成无需人工干预，只需要通过实现设计好的算法，能够自动地将可行走区域划分成多边形，生成导航网格。导航网格的主要缺点在于生成导航网格需要较长的时间，因此，多用于静态场景中。如下图所示，即为导航网格：

三、运行机制

在A*算法中，使用了两个状态表，分别称为Open表和Closed表。Open表由待考察的节点组成，Closed表由已经考察过的节点组成。

什么样的节点才算是已考察过的呢？对于一个节点来说，当算法已经检查过与它相邻的所有节点，计算出了这些节点的f\g\h值，并把它们放入Open表以待考察，那么，这节点就是“已考察过”的节点。

开始时，Closed表为空，Open表仅包括起始节点，每次迭代中，A*算法将Open表中具有最小代价之的节点去除进行检查，如果这个节点不是目标节点，那么考虑该节点的所有8个相邻节点。对于每个相邻节点按下列规则处理；

（1） 如果相邻节点既不在Open表中，又不在Closed表中，则将它加入Open表中；

（2） 如果相邻节点已经在Open表中，并且新的路径具有更低的代价值，则更新它的信息；

（3） 如果相邻节点已经在Closed表中，那么需要检查新的路径是否具有更低的代价值，如果是，那么将它从Closed表中移出，加入到Open表中，否则忽略。

重复上述步骤，直到到达目标节点。如果在到达目标之前，Open表就已经变空，则意味着在起始位置和目标位置之间没有可达的路径。

四、常用估价算法

（1）曼哈顿距离

标准的启发式函数是曼哈顿距离（Manhattan distance）。考虑你的代价函数并找到从一个位置移动到邻近位置的最小代价D。因此，我的游戏中的启发式函数应该是曼哈顿距离的D倍：

H(n) = D * (abs ( n.x – goal.x ) + abs ( n.y – goal.y ) )

你应该使用符合你的代价函数的衡量单位。

（2）对角线距离

如果在你的地图中你允许对角运动那么你需要一个不同的启发函数。（4 east, 4 north）的曼哈顿距离将变成8*D。然而，你可以简单地移动（4 northeast）代替，所以启发函数应该是4*D。这个函数使用对角线，假设直线和对角线的代价都是D：

h(n) = D * max(abs(n.x - goal.x), abs(n.y - goal.y))

如果对角线运动的代价不是D，但类似于D2 = sqrt(2) * D，则上面的启发函数不准确。你需要一些更准确（原文为sophisticated）的东西：

h_diagonal(n) = min(abs(n.x - goal.x), abs(n.y - goal.y))

h_straight(n) = (abs(n.x - goal.x) + abs(n.y - goal.y))

h(n) = D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n)))

这里，我们计算h_diagonal(n)：沿着斜线可以移动的步数；h_straight(n)：曼哈顿距离；然后合并这两项，让所有的斜线步都乘以D2，剩下的所有直线步(注意这里是曼哈顿距离的步数减去2倍的斜线步数)都乘以D。

（3） 欧几里得距离

如果你的单位可以沿着任意角度移动（而不是网格方向），那么你也许应该使用直线距离：

h(n) = D * sqrt((n.x-goal.x)^2 + (n.y-goal.y)^2)

然而，如果是这样的话，直接使用A*时将会遇到麻烦，因为代价函数g不会match启发函数h。因为欧几里得距离比曼哈顿距离和对角线距离都短，你仍可以得到最短路径，不过A*将运行得更久一些：

（4）平方后的欧几里得距离

我曾经看到一些A*的网页，其中提到让你通过使用距离的平方而避免欧几里得距离中昂贵的平方根运算：

h(n) = D * ((n.x-goal.x)^2 + (n.y-goal.y)^2)

不要这样做！这明显地导致衡量单位的问题。当A*计算f(n) = g(n) + h(n)，距离的平方将比g的代价大很多，并且你会因为启发式函数评估值过高而停止。对于更长的距离，这样做会靠近g(n)的极端情况而不再计算任何东西，A*退化成BFS：

五、示例

本案例采用基于单元的导航图寻路方式以及曼哈顿距离估价法进行实现。首先需要创建一个格子类Grid：using UnityEngine;using System.Collections;using System.Collections.Generic;using System;/// <summary>/// 格子类型/// </summary>public enum GridType{//正常类型Normal,//障碍物类型Obstacle,//起点类型Start,//终点类型End}/// <summary>/// 格子类（实现IComparable方便排序）/// </summary>public class Grid : IComparable{//格子坐标x-ypublic int x;public int y;//格子A*三属性f-g-hpublic int f;public int g;public int h;//格子类型public GridType type;//格子的归属（父格子）public Grid parent;//构造赋值public Grid (int x, int y){this.x = x;this.y = y;}/// <summary>/// 实现排序接口方法/// </summary>/// <returns>The to.</returns>/// <param name="obj">Object.</param>public int CompareTo (object obj){Grid grid = (Grid)obj;if (this.f < grid.f) {//升序return -1;}if (this.f > grid.f) {//降序return 1;}return 0;}}然后主逻辑AStar类：using UnityEngine;using System.Collections;using System.Collections.Generic;public class MyAStar : MonoBehaviour{/// <summary>/// 单例脚本/// </summary>public static MyAStar instance;//参考物体预设体public GameObject reference;//格子数组public Grid[,] grids;//格子数组对应的参考物（方块）对象public GameObject[,] objs;//开启列表public ArrayList openList;//关闭列表public ArrayList closeList;//目标点坐标public int targetX;public int targetY;//起始点坐标public int startX;public int startY;//格子行列数private int row;private int colomn;//结果栈private Stack<string> parentList;//基础物体private Transform plane;private Transform start;private Transform end;private Transform obstacle;//流颜色参数private float alpha = 0;private float incrementPer = 0;void Awake (){instance = this;plane = GameObject.Find ("Plane").transform;start = GameObject.Find ("Start").transform;end = GameObject.Find ("End").transform;obstacle = GameObject.Find ("Obstacle").transform;parentList = new Stack<string> ();openList = new ArrayList ();closeList = new ArrayList ();}/// <summary>/// 初始化操作/// </summary>void Init (){//计算行列数int x = (int)(plane.localScale.x * 20);int y = (int)(plane.localScale.z * 20);row = x;colomn = y;grids = new Grid[x, y];objs = new GameObject[x, y];//起始坐标Vector3 startPos =new Vector3 (plane.localScale.x * -5, 0, plane.localScale.z * -5);//生成参考物体（Cube）for (int i = 0; i < x; i++) {for (int j = 0; j < y; j++) {grids [i, j] = new Grid (i, j);GameObject item = (GameObject)Instantiate (reference,new Vector3 (i * 0.5f, 0, j * 0.5f) + startPos,Quaternion.identity);item.transform.GetChild (0).GetComponent<Reference> ().x = i;item.transform.GetChild (0).GetComponent<Reference> ().y = j;objs [i, j] = item;}}}/// <summary>/// A*计算/// </summary>IEnumerator Count (){//等待前面操作完成yield return new WaitForSeconds (0.1f);//添加起始点openList.Add (grids [startX, startY]);//声明当前格子变量，并赋初值Grid currentGrid = openList [0] as Grid;//循环遍历路径最小F的点while (openList.Count > 0 && currentGrid.type != GridType.End) {//获取此时最小F点currentGrid = openList [0] as Grid;//如果当前点就是目标if (currentGrid.type == GridType.End) {Debug.Log ("Find");//生成结果GenerateResult (currentGrid);}//上下左右，左上左下，右上右下，遍历for (int i = -1; i <= 1; i++) {for (int j = -1; j <= 1; j++) {if (i != 0 || j != 0) {//计算坐标int x = currentGrid.x + i;int y = currentGrid.y + j;//如果未超出所有格子范围，不是障碍物，不是重复点if (x >= 0 && y >= 0 && x < row && y < colomn&& grids [x, y].type != GridType.Obstacle&& !closeList.Contains (grids [x, y])) {//计算G值int g = currentGrid.g + (int)(Mathf.Sqrt ((Mathf.Abs (i) + Mathf.Abs (j))) * 10);//与原G值对照if (grids [x, y].g == 0 || grids [x, y].g > g) {//更新G值grids [x, y].g = g;//更新父格子grids [x, y].parent = currentGrid;}//计算H值grids [x, y].h = Manhattan (x, y);//计算F值grids [x, y].f = grids [x, y].g + grids [x, y].h;//如果未添加到开启列表if (!openList.Contains (grids [x, y])) {//添加openList.Add (grids [x, y]);}//重新排序openList.Sort ();}}}}//完成遍历添加该点到关闭列表closeList.Add (currentGrid);//从开启列表中移除openList.Remove (currentGrid);//如果开启列表空，未能找到路径if (openList.Count == 0) {Debug.Log ("Can not Find");}}}/// <summary>/// 生成结果/// </summary>/// <param name="currentGrid">Current grid.</param>void GenerateResult (Grid currentGrid){//如果当前格子有父格子if (currentGrid.parent != null) {//添加到父对象栈（即结果栈）parentList.Push (currentGrid.x + "|" + currentGrid.y);//递归获取GenerateResult (currentGrid.parent);}}/// <summary>/// 显示结果/// </summary>/// <returns>The result.</returns>IEnumerator ShowResult (){//等待前面计算完成yield return new WaitForSeconds (0.3f);//计算每帧颜色值增量incrementPer = 1 / (float)parentList.Count;//展示结果while (parentList.Count != 0) {//出栈string str = parentList.Pop ();//等0.3秒yield return new WaitForSeconds (0.3f);//拆分获取坐标string[] xy = str.Split (new char[]{ '|' });int x = int.Parse (xy [0]);int y = int.Parse (xy [1]);//当前颜色值alpha += incrementPer;//以颜色方式绘制路径objs [x, y].transform.GetChild (0).GetComponent<MeshRenderer> ().material.color= new Color (1 - alpha, alpha, 0, 1);}}/// <summary>/// 曼哈顿方式计算H值/// </summary>/// <param name="x">The x coordinate.</param>/// <param name="y">The y coordinate.</param>int Manhattan (int x, int y){return (int)(Mathf.Abs (targetX - x) + Mathf.Abs (targetY - y)) * 10;}void Start (){Init ();StartCoroutine (Count ());StartCoroutine (ShowResult ());}}最后是参考预设体方块的简单实现：using UnityEngine;using System.Collections;using UnityEngine.UI;public class Reference : MonoBehaviour{//颜色材质区分public Material startMat;public Material endMat;public Material obstacleMat;//显示信息Textprivate Text text;//当前格子坐标public int x;public int y;void Awake (){text = GameObject.Find ("Text").GetComponent<Text> ();}//判断当前格子的类型void OnTriggerEnter (Collider other){if (other.name == "Start") {GetComponent<MeshRenderer> ().material = startMat;MyAStar.instance.grids [x, y].type = GridType.Start;MyAStar.instance.openList.Add (MyAStar.instance.grids [x, y]);MyAStar.instance.startX = x;MyAStar.instance.startY = y;} else if (other.name == "End") {GetComponent<MeshRenderer> ().material = endMat;MyAStar.instance.grids [x, y].type = GridType.End;MyAStar.instance.targetX = x;MyAStar.instance.targetY = y;} else if (other.name == "Obstacle") {GetComponent<MeshRenderer> ().material = obstacleMat;MyAStar.instance.grids [x, y].type = GridType.Obstacle;}}/// <summary>/// 鼠标点击显示当前格子基础信息/// </summary>void OnMouseDown (){text.text = "XY(" + x + "," + y + ")" + "\n" +"FGH(" + MyAStar.instance.grids [x, y].f + "," +MyAStar.instance.grids [x, y].g + "," +MyAStar.instance.grids [x, y].h + ")";text.color = GetComponent<MeshRenderer> ().material.color;}}

 

 


http://chatgpt.dhexx.cn/article/u2pA4lDC.shtml

相关文章

sift算法原理，按步骤记录

sift算法原理，按步骤记录

sitf算法是一种描述图像特征的&#xff0c;重要的&#xff0c;基础的方法。主要由以下几个步骤构成&#xff1a; 0.尺度空间理论 尺度空间理论认为&#xff0c;人眼在认知画面时&#xff0c;在不同的尺度上使用的是不同特征&#xff0c;例如观察树叶时使用的是小尺度特征&…
阅读更多...
DQN算法流程及原理

DQN算法流程及原理

相关名词解释&#xff1a; Agent&#xff1a;智能体&#xff1b;s—state&#xff1a;状态&#xff08;放在格子游戏中&#xff0c;就是智能体的位置坐标(x,y))a—action&#xff1a;智能体采取的动作&#xff08;例如上下左右&#xff09;r—reward&#xff1a;奖励&#xff…
阅读更多...
D*算法原理与程序详解（Python）

D*算法原理与程序详解（Python）

提示&#xff1a;前文写了D搜索算法&#xff0c;是一种贪心算法。 文章目录 一、D*算法是什么&#xff1f;二、原理以及代码步骤1.原理分析2.代码解释 总结 一、D*算法是什么&#xff1f; D*算法也是用于机器人路径规划问题的启发式方法&#xff0c;它是一种局部规划方法&…
阅读更多...
unityA星寻路算法基础原理

unityA星寻路算法基础原理

作者&#xff1a; 风不停息丶 文章目录 &#x1f9d1;‍&#x1f4bb;A星寻路简介&#x1f449;代码基础架构&#x1f44d;代码实现格子类寻路管理类效果 结尾总结 &#x1f9d1;‍&#x1f4bb;A星寻路简介 A*寻路就是用来计算玩家行进路径的&#xff0c;通过它可以计算出避开…
阅读更多...
【YOLO系列】YOLO.v1算法原理详解

【YOLO系列】YOLO.v1算法原理详解

YOLO(You Only Look Once)系列算法原理 前言 &#xff1a;详细介绍了yolo系列目标检测算法的原理和发展过程。 系列&#xff1a; 【YOLO系列】YOLO.v1算法原理详解 【YOLO系列】YOLO.v2算法原理详解 【YOLO系列】YOLO.v3算法原理详解 【YOLO系列】YOLO.v4 & YOLO.v5算法原…
阅读更多...
A*算法原理与实现

A*算法原理与实现

前言 A*算法最初发表于1968年&#xff0c;由Stanford研究院的Peter Hart, Nils Nilsson以及Bertram Raphael发表。它可以被认为是Dijkstra算法的扩展。 由于借助启发函数的引导&#xff0c;A*算法通常拥有更好的性能。 一、 A*吸取了Dijkstra 算法中的cost_so_far&#xff0c;为…
阅读更多...
激光SLAM之NDT算法（1）算法原理

激光SLAM之NDT算法（1）算法原理

/在激光SLAM之NDT算法&#xff08;2&#xff09;-建图中我会给出实测可用的建图代码,并予以解释代码结构,这里就先讲讲原理吧!!!/ 无人车激光SLAM系统简单可以分为建图和定位两部分&#xff0c;无人车的定位问题&#xff0c;实际上就是要找出无人车当前在地图的那个位置&#x…
阅读更多...
A*算法的原理及应用

A*算法的原理及应用

A*算法的原理 A* 算法是一种高效的启发式搜索算法&#xff0c;在二维的栅格地图上寻路效果好&#xff0c;它通过估算节点的代价评估函数值并作为节点的综合优先级&#xff0c;当选择下一个需要遍历的节点时&#xff0c;再选取综合优先级最高的节点&#xff0c;逐步地找到最优路…
阅读更多...
Bresenham 画圆算法原理

Bresenham 画圆算法原理

文章目录 前言Bresenham 画圆算法原理两个近似构造判别式圆与网格点的关系关系由来关系含义p i p_i pi​ 递推画圆程序伪码圆与网格点的关系图示前言 首先简要介绍一下生成圆的方法： 直接利用圆的方程生成圆利用圆的对称性生成圆方法一由于会涉及到浮点运算等因素，不采取该方…
阅读更多...
Js中读取、移除属性及隐藏组件方法研究

Js中读取、移除属性及隐藏组件方法研究

添加、移除组件属性方法: $(".class名").attr("属性名","属性值");//设置指定属性 $(".class名").attr("属性名");//读取指定属性值 or document.getElementById("id值").getAttribute("属性名…
阅读更多...
js获取属性值,自定义属性，修改移除属性值

js获取属性值,自定义属性，修改移除属性值

补充&#xff1a;由于不清楚一些属性是内置属性还是自定义属性 所以h5规定 自定义属性使用date-开头作为属性并赋值 案例1: <body><div date-index"1"></div> </body> <script>var div document.querySelector(div);console.log(div…
阅读更多...
获取/移除属性值

获取/移除属性值

1.获取属性值&#xff1a; element.属性 获取属性值 element.getAttribute&#xff08;‘属性’&#xff09;&#xff1b; 2.区别&#xff1a; element.属性 获取内置属性值&#xff08;元素本身自带的属性&#xff09; element.getAttribute&#xff08;‘属性’&#xff09;&…
阅读更多...
JavaScript移除对象中不必要的属性

JavaScript移除对象中不必要的属性

Thinking系列&#xff0c;旨在利用10分钟的时间传达一种可落地的编程思想。 业务开发中&#xff0c;我们经常会遇到&#xff1a;基于后端返回接口数据&#xff0c;前端保存到对象 Object 中&#xff0c;前端开发过程中为了一些场景的便利性&#xff0c;需要在该对象中增加相应的…
阅读更多...
js移除属性

js移除属性

一、效果 代码 <style>div{width:100px;height: 100px;background-color: red;}.clsP{background-color: #00FF00;}</style><body><input type"button" value"移除属性" id"btn" /><div id"dv" score&q…
阅读更多...
合天网安实验室CTF-解密100-Funny Crypto

合天网安实验室CTF-解密100-Funny Crypto

合天网安实验室CTF-解密100-Funny Crypto 题目描述 tgbnjuy 8ujko9 5rfgy6 相关附件 题目链接 参考解题步骤 字母被围起来的字母图示颜色tgbnjuyh红8ujko9i绿5rfgy6t蓝 提交flag&#xff1a;hit
阅读更多...
数字取证之Autopsy ——合天网安实验室学习笔记

数字取证之Autopsy ——合天网安实验室学习笔记

实验链接 Autopsy Forensic Browser 是数字取证工具-The Sleuth Kit&#xff08;TSK&#xff09;的图形界面&#xff0c;用于对文件系统和卷进行取证。通过本实验学习文件系统取证的思想与方法&#xff0c;掌握Autopsy的使用。 链接&#xff1a;http://www.hetianlab.com/exp…
阅读更多...
【合天网安】CONN.ASP暴库漏洞实验

【合天网安】CONN.ASP暴库漏洞实验

0x01预备知识 1、概念&#xff1a; 相对路径和绝对路径 绝对路径&#xff1a;例如D&#xff1a;/test/test.mdb 相对路径&#xff1a;例如/test/test.mdb 2、%5C暴库 简单点说&#xff0c;就是在打开页面的时候把网页中的/换成%5C&#xff0c;然后提交就可以得到数据库地址…
阅读更多...
【合天网安】FCKeditor 2.4.3文件上传漏洞

【合天网安】FCKeditor 2.4.3文件上传漏洞

【合天网安实验室】FCKeditor 2.4.3文件上传漏洞 编辑器漏洞 常见的文本编辑器有FCKeditor、Ewebeditor、UEditor、KindEditor、XHeditor等&#xff0c;它们包含的功能类似&#xff0c;如图片上传、视频上传、远程下载等。使用这类编辑器减少了程序开发的时间&#xff0c;但也…
阅读更多...
摩尔斯电码和栅栏密码 ——合天网安实验室学习笔记

摩尔斯电码和栅栏密码 ——合天网安实验室学习笔记

实验链接 通过学习本实验理解摩尔斯电码和栅栏密码的编码解码过程&#xff1b;掌握编写摩尔斯电码的编码解码程序和编写多功能栅栏密码的编码解码程序。 链接&#xff1a;http://www.hetianlab.com/expc.do?ce64d3e661-ebbb-41fd-a220-a17d608f994e 实验简介 实验所属系列…
阅读更多...
【合天网安】DoraBox之文件包含及任意文件读取漏洞

【合天网安】DoraBox之文件包含及任意文件读取漏洞

【合天网安实验室】DoraBox之文件包含及任意文件读取漏洞 目的&#xff1a; 过DoraBox靶场系列练习&#xff0c;学习任意文件包含、目录限制文件包含及任意文件读取漏洞的利用过程。 实验过程&#xff1a; 1.确保Apache、MySQL服务正常开启 2、查看.txt文本内容 3.使用includ…
阅读更多...
推荐文章

Copyright @ 2022~2023