A*寻路详解

【基本概念】

寻路算法

寻路的结果是根据起始点S和目标点T,找到路径Path。

寻路中通常用栅形网格简化表示地图,周围八个格子表示可以通行的方向

游戏中通常需要最快找到该路径(A*算法),而不是找到最短的路径(Dijkstra算法)

距离度量

欧式距离,即两点间直线距离的计算

曼哈顿距离,有方向限制,只能水平或垂直移动

对角距离,在曼哈顿距离基础上,允许沿着对角线移动

切比雪夫距离,有方向限制,取水平或垂直移动两者的最大值

距离因子

在栅形网格下,可以认为上下左右的距离为1,但计算对角距离时为小数,为了都采用整形计算,乘以10的因子

因此,上下左右距离为10,对角距离为14

成本/代价

常用的说法是cost,从一个点到另外一个点的成本,通常成本就是距离的度量,在机器学习中,还会加上其他因素的度量,寻路算法中只有距离度量。

启发函数

搜索最基本的思路是穷举搜索,例如广度优先和深度优先搜索,但当搜索空间过大,也即可能性太多时,最好可以提供一种方式,对可能性做筛选,减少搜索空间,进而提高搜索效率。

如果有提供筛选方法,那么就是启发式搜索,这个方法也叫启发函数。

贪心策略

通常来说,搜索是一步步进行的,每一步会将新的可能加入到待处理队列中,如果每一步都从当前可能中选择一个最优的结果,这就是贪心的。

结果舍弃

在贪心策略下,如果在当前步得到了最优结果,可以将其他结果全部舍弃,以最优结果为基础做下一步搜索时,添加新的可能并从这些可能中找到找到最优结果。

也可以不做结果舍弃,在下一步搜索时,将添加的新的可能和已有的可能合在一起找当前步的最优结构。

寻路算法不做结果舍弃。

搜索结果

有的搜索中只需要知道路径是多大,而有的搜索需要知道路径是什么,寻路中需要知道路径是什么

【寻路算法】

常见的寻路算是迪杰斯特拉算法(Dijkstra)、最佳搜索搜索算法(BFS)、A*算法。他们都遵循相似的算法过程,只在计算和更新cost时有较大区别。算法主要流程如下:

  1. 确定一个起始点和目标点
  2. 将起点加入open队列中,open队列表示需要处理的可能性,这里用Point表示
  3. 从open队列中取出cost最小的Point。只有起点时就是起点,随着队列中的Point变多,要排序取出最小值
  4. 筛选open队列的邻近的Point并加入open队列中,此时open队列逐渐膨胀,在寻路算法中不做结果舍弃
    1. 栅形格子邻近的Point就是周围的八个
    2. 这8个中有的不能通行的格子要舍去
    3. 已经处理过的格子要舍弃
    4. 已经在open队列中的格子,需要更新cost
    5. 不在open队列中的格子,需要计算cost,并当如open队列中
  5. 将此次取出来的最小的Point放入close队列中,close队列表示已经处理过的Point
  6. 重复3-5步骤,直到open队列为空,或者取出来的最小的Point就是目标点

Dijkstra算法

Dijkstra算法是典型最短路径算法,可以计算一个起始节点到路径中其他所有节点的最短路径。

计算cost时:Point的cost是累加的,当前筛选出来的Point的cost = 当前从open队列中取出的Point的cost + 筛选Point到取出point的cost

因为计算cost是不断累加的,因此距离起点越远的点cost越大

更新cost时: 筛选的Point可能已经在open队列中存在,这表明有多条路径可以到达该Point。因为要找出来最短路径,所以需要比较筛选出来的Point与已经存在的Point谁的cost更低,将更低的cost作为新的cost。

如果已经存在的更低,说明之前的路径更短;如果筛选的更低,说明从起点到当前选择最小的Point再到当前筛选的Point的路径是从起点到Point的最短路径

算法特点:可以看到在搜索邻近的Point时,除了可以通行的Point外,没对Point做任何筛选,因为Point的cost是累加的,距离起点越近的点cost越小,也就越可能从open队列中取出来。

如果所有的点都可以通行,被取出来的点基本就是沿着起点一圈圈往外扩散的。

随着搜索的进行,目标Point的cost可能是open队列中最小,被取出来,此时就已经找到了通向这个点的最短路径了。

时间复杂度:所有可能点都会被放入到open队列中,也会被选择出来,如果可能的点总数为N,最外层循环次数为N,内层有一个获取邻近点的循环,这里的次数为8,同时还有一个排序的计算,如果用最小堆,时间复杂度为logN,总的时间复杂度为(N+8)logN

BFS

最佳优先搜索算法中每个Point的cost是不变的,其cost是该Point到目标Point的路径cost,不需要更新cost

其特点为:每次都会选择距离目标点最近的Point,如果起始点和目标点有凹形阻挡,将会导航进入凹形内部很长时间后才出来,实际表现为角色来回转圈

A*

A*寻路算法在计算cost时即会像Dijkstra一样考虑累积路径cost,也会像BFS一样考虑到目标点的cost。其cost计算公式为:

F = G + H 。其中G表示累积路径cost,H表示到目标点的cost

计算cost时,需先按照累积路径方式计算G,H只需在首次计算一次

更新cost时,H保持不变,实际就是更新G,只有当前计算的G更小时才做更新

其特点为:此时cost表示从起点到该点的最短路径+该点到目标点的估计距离,这种计算cost的方式更为科学,能更快更好的找到接近目标点的点位,也即寻路速度更快

在游戏中,更快寻路往往更重要,通过计算合适的cost,引导点位选择是寻路算法的核心所在。

当起点和终点距离很远时,刚开始寻路,H远大于G,此时相当于按照BFS的方式寻路;邻近终点时,G远大于H,此时相当于按照Dijkstra方式寻路

【代码实现】

下文是最原始的版本实现,不足以用到实际项目中,后文针对A*看一看如何优化

public class Navigate
{public SearchType searchType;public enum SearchType{Dijkstra,BFS,AStar,}public HCostType costType = HCostType.Diagonal;public enum HCostType{Manhattan,Euclidean,Diagonal,}public static int DisFactor = 10;public static int DiagonalDisFactor = 14;public Dictionary<SearchType, ISearch> algorithm = new Dictionary<SearchType, ISearch>();public bool FindPath(int2 start, int2 target, List<int2> path){if (path == null || path.Count > 0) return false;if (!algorithm.TryGetValue(searchType, out var algo)){algorithm[searchType] = CreateSearch(searchType);}return algo.FindPath(start, target, path);}public ISearch CreateSearch(SearchType searchType){ISearch res = null;switch (searchType){case SearchType.Dijkstra: res = new Dijkstra(GetCost); break;case SearchType.BFS: res = new BFS(GetHCost); break;case SearchType.AStar: res = new AStar(GetCost, GetHCost); break;}return res;}public int GetCost(int2 cur, int2 next){if (next.x == -1 && next.y == -1){return -1;}int cost = 0;if (cur.x == next.x || cur.y == next.y){cost = DisFactor;}else{cost = DiagonalDisFactor;}return cost;}public int GetHCost(int2 pos, int2 target){int hCost = 0;if (costType == HCostType.Manhattan){hCost = Mathf.Abs(pos.x - target.x) * DisFactor + Mathf.Abs(pos.y - target.y) * DisFactor;}else if (costType == HCostType.Euclidean){hCost = (int)Mathf.Sqrt(Mathf.Pow((pos.x - target.x) * DisFactor, 2) + Mathf.Pow((pos.y - target.y) * DisFactor, 2));}else if (costType == HCostType.Diagonal){int x = Mathf.Abs(pos.x - target.x);int y = Mathf.Abs(pos.y - target.y);int a = Mathf.Min(x, y);hCost = a * DiagonalDisFactor + Mathf.Abs(x - y) * DisFactor;}return hCost;}
}public interface ISearch
{bool FindPath(int2 start, int2 target, List<int2> path);
}public class Dijkstra : ISearch
{private Dictionary<int2, Point> openDic = new Dictionary<int2, Point>();private Dictionary<int2, Point> closeDic = new Dictionary<int2, Point>();private Dictionary<int2, Point> pos2Point = new Dictionary<int2, Point>();public bool FindPath(int2 startPoint, int2 targetPoint, List<int2> path){if (path == null || path.Count > 0) return false;var start = GetOrCreatePoint(startPoint);var target = GetOrCreatePoint(targetPoint);openDic.Clear();closeDic.Clear();openDic.Add(startPoint, start);start.Reset();target.Reset();bool res = false;while (openDic.Count > 0){var point = openDic.First().Value;if (point == target){res = true;break;}//删除该点openDic.Remove(point.pos);ProcessNeighbouringPoints(point, target);//该点已被处理过closeDic.Add(point.pos, point);openDic = openDic.OrderBy(kv => kv.Value.cost).ToDictionary(p => p.Key, o => o.Value);}foreach (var point in target.path){path.Add(point.pos);}res = true;return res;}private Func<int2, int2, int> getCost;private static int2 NullPos = new int2(-1, -1);public Dijkstra(Func<int2, int2, int> getCost){this.getCost = getCost;}private Point GetOrCreatePoint(int2 pos){if (!pos2Point.TryGetValue(pos, out var point)){pos2Point[pos] = point = new Point();point.pos = pos;}return point;}private List<int2> nPoints = new List<int2>();public void ProcessNeighbouringPoints(Point point, Point target){nPoints.Clear();point.GetNeighbouringPoints(nPoints);foreach (var item in nPoints){if (closeDic.TryGetValue(item, out var npoint)){continue;}if (getCost(item, NullPos) == -1)//-1表示点不可通行{continue;}UpdateCost(point, item, target);}}public void UpdateCost(Point point, int2 pos, Point target){int cost = getCost(point.pos, pos);if (openDic.TryGetValue(pos, out var npoint)){if (cost + point.cost < npoint.cost){npoint.cost = cost + point.cost;npoint.path.Clear();npoint.path.AddRange(point.path);}}else{npoint = GetOrCreatePoint(pos);npoint.Reset();npoint.cost = cost + point.cost;npoint.path.AddRange(point.path);openDic[pos] = npoint;}}public class Point{public int2 pos;public int cost;public List<Point> path = new List<Point>();public void Reset(){path.Clear();cost = int.MaxValue;}public bool GetNeighbouringPoints(List<int2> points){if (points == null || points.Count > 0) return false;for (int i = -1; i < 2; i++){for (int j = -1; j < 2; j++){if (i == 0 && j == 0) continue;int2 newpos = new int2(pos.x + i, pos.y + j);//超出地图范围if (newpos.x < 0 || newpos.x >= MapM || newpos.y < 0 || newpos.y >= MapN)continue;points.Add(newpos);}}return true;}}
}public class BFS : ISearch
{private Dictionary<int2, Point> openDic = new Dictionary<int2, Point>();private Dictionary<int2, Point> closeDic = new Dictionary<int2, Point>();private Dictionary<int2, Point> pos2Point = new Dictionary<int2, Point>();public bool FindPath(int2 startPoint, int2 targetPoint, List<int2> path){if (path == null || path.Count > 0) return false;var start = GetOrCreatePoint(startPoint);var target = GetOrCreatePoint(targetPoint);openDic.Clear();closeDic.Clear();openDic.Add(startPoint, start);start.Reset();target.Reset();bool res = false;while (openDic.Count > 0){var point = openDic.First().Value;path.Add(point.pos);if (point == target){               res = true;break;}openDic.Remove(point.pos);ProcessNeighbouringPoints(point, target);closeDic.Add(point.pos, point);openDic = openDic.OrderBy(kv => kv.Value.cost).ToDictionary(p => p.Key, o => o.Value);}return res;}private Func<int2, int2, int> getCost;private static int2 NullPos = new int2(-1, -1);public BFS(Func<int2, int2, int> getCost){this.getCost = getCost;}private Point GetOrCreatePoint(int2 pos){if (!pos2Point.TryGetValue(pos, out var point)){pos2Point[pos] = point = new Point();point.pos = pos;}return point;}private List<int2> nPoints = new List<int2>();public void ProcessNeighbouringPoints(Point point, Point target){nPoints.Clear();point.GetNeighbouringPoints(nPoints);foreach (var item in nPoints){if (closeDic.TryGetValue(item, out var npoint)){continue;}if (getCost(item, NullPos) == -1)//-1表示点不可通行{continue;}UpdateCost(point, item, target);}}public void UpdateCost(Point point, int2 pos, Point target){int cost = getCost(target.pos, pos);if (!openDic.TryGetValue(pos, out var npoint)){npoint = GetOrCreatePoint(pos);npoint.Reset();npoint.cost = cost;openDic[pos] = npoint;}}public class Point{public int2 pos;public int cost;public void Reset(){cost = int.MaxValue;}public bool GetNeighbouringPoints(List<int2> points){if (points == null || points.Count > 0) return false;for (int i = -1; i < 2; i++){for (int j = -1; j < 2; j++){if (i == 0 && j == 0) continue;int2 newpos = new int2(pos.x + i, pos.y + j);//超出地图范围if (newpos.x < 0 || newpos.x >= MapM || newpos.y < 0 || newpos.y >= MapN)continue;points.Add(newpos);}}return true;}}
}
public class AStar : ISearch
{private Dictionary<int2, Point> openDic = new Dictionary<int2, Point>();private Dictionary<int2, Point> closeDic = new Dictionary<int2, Point>();private Dictionary<int2, Point> pos2Point = new Dictionary<int2, Point>();public bool FindPath(int2 startPoint, int2 targetPoint, List<int2> path){if (path == null || path.Count > 0) return false;var start = GetOrCreatePoint(startPoint);var target = GetOrCreatePoint(targetPoint);openDic.Clear();closeDic.Clear();openDic.Add(startPoint, start);start.Reset();target.Reset();bool res = false;while (openDic.Count > 0){var point = openDic.First().Value;path.Add(point.pos);if (point == target){res = true;break;}openDic.Remove(point.pos);ProcessNeighbouringPoints(point, target);closeDic.Add(point.pos, point);openDic = openDic.OrderBy(kv => kv.Value.F).ThenBy(kv => kv.Value.H).ToDictionary(p => p.Key, o => o.Value);}return res;}private Func<int2, int2, int> getCost;private Func<int2, int2, int> getHCost;private static int2 NullPos = new int2(-1, -1);public AStar(Func<int2, int2, int> getCost, Func<int2, int2, int> getHCost){this.getCost = getCost;this.getHCost = getHCost;}private Point GetOrCreatePoint(int2 pos){if (!pos2Point.TryGetValue(pos, out var point)){pos2Point[pos] = point = new Point();point.pos = pos;}return point;}private List<int2> nPoints = new List<int2>();public void ProcessNeighbouringPoints(Point point, Point target){nPoints.Clear();point.GetNeighbouringPoints(nPoints);foreach (var item in nPoints){if (closeDic.TryGetValue(item, out var npoint)){continue;}if (getCost(item, NullPos) == -1)//-1表示点不可通行{continue;}UpdateCost(point, item, target);}}public void UpdateCost(Point point, int2 pos, Point target){int cost = getCost(target.pos, pos);int gCost = point.G + cost;if (openDic.TryGetValue(pos, out var npoint)){if (npoint.G < gCost){npoint.G = gCost;}}else{npoint = GetOrCreatePoint(pos);npoint.G = gCost;npoint.H = getHCost(pos, target.pos);openDic[pos] = npoint;}}public class Point{public int2 pos;public int H{get => _h;set{_h = value;_f = _h + _g;}}private int _h;public int G{get => _g;set{_g = value;_h = _g + _h;}}private int _g;public int F => _f;private int _f;public void Reset(){H = 0;G = 0;}public bool GetNeighbouringPoints(List<int2> points){if (points == null || points.Count > 0) return false;for (int i = -1; i < 2; i++){for (int j = -1; j < 2; j++){if (i == 0 && j == 0) continue;int2 newpos = new int2(pos.x + i, pos.y + j);//超出地图范围if (newpos.x < 0 || newpos.x >= MapM || newpos.y < 0 || newpos.y >= MapN)continue;points.Add(newpos);}}return true;}}
}

【参考】

(七)通俗易懂理解——dijkstra算法求最短路径

https://zhuanlan.zhihu.com/p/385733813

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/15996.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

分层解耦-IOC DI 入门

步骤 ①.Service层及 Dao层的实现类&#xff0c;交给I0C容器管理。 ②.为Controller及Service注入运行时&#xff0c;依赖的对象。 ③.运行测试。 添加注解进行分层耦合 Component 会将当前类交给IOC容器管理,成为IOC容器中的bean - 控制反转 Autowired 运行时,IOC容器…

SQL Server 逻辑查询处理阶段及其处理顺序

在 SQL Server 中&#xff0c;查询的执行并不是按照我们编写的 SQL 语句的顺序进行的。相反&#xff0c;SQL Server 有自己的一套逻辑处理顺序&#xff0c;这个顺序决定了查询的执行方式和结果集的生成。了解这些处理阶段和顺序对于优化查询性能和调试复杂查询非常重要。 SQL …

问题:通过策略模式+工厂模式+模板方法模式实现ifelse优化

项目场景&#xff1a; 提示&#xff1a;这里简述项目相关背景&#xff1a; 示例&#xff1a;商城系统有会员系统&#xff0c;不同会员有不同优惠程度&#xff0c;普通会员不优惠&#xff1b;黄金会员打8折&#xff1b;白金会员优惠50元&#xff0c;再打7折&#xff1b; 问题描…

MYSQL利用PXC实现高可用

PXC常用端口 3306&#xff1a;数据库对外服务端口号 4444&#xff1a;请求SST的端口 4567&#xff1a;组成员之间进行沟通的端口号 4568&#xff1a;用于传输IST 搭建PXC集群 服务配置&#xff1a; 主机系统&#xff1a;rocky8.0 主机1&#xff1a;172.25.254.101 主机…

2.11寒假作业

web&#xff1a;[SWPUCTF 2022 新生赛]js_sign 打开环境是这样的&#xff0c;随便输入进行看看 提示错误&#xff0c;看源码其中的js代码 这个代码很容易理解&#xff0c;要让输入的内容等于对应的字符串&#xff0c;显然直接复制粘贴是错的 这串字符看起来像是base64加密&…

innovus如何分步长func和dft时钟

在Innovus工具中&#xff0c;分步处理功能时钟&#xff08;func clock&#xff09;和DFT时钟&#xff08;如扫描测试时钟&#xff09;需要结合设计模式&#xff08;Function Mode和DFT Mode&#xff09;进行约束定义、时钟树综合&#xff08;CTS&#xff09;和时序分析。跟随分…

《DeepSeek技术应用与赋能运营商办公提效案例实操落地课程》

大模型算法实战专家—周红伟老师 法国科学院数据算法博士/曾任阿里巴巴人工智能专家/曾任马上消费企业风控负责人 课程背景 随着大模型技术的迅猛发展&#xff0c;企业面临着提升工作效率、降低运营成本和优化资源配置的巨大压力。DeepSeek做出十三项革命性的大模型技术突破…

大模型基本原理(二)——ChatGPT的工作原理

如何得到一个ChatGPT&#xff1f; 1、无监督预训练&#xff1a;通过大量的文本数据集进行无监督训练&#xff0c;得到一个基座模型&#xff08;只会续写文本&#xff09; 2、监督微调&#xff1a;通过一些人类撰写的高质量对话数据对基座模型进行监督微调&#xff0c;得到一个…

示例代码:C# MQTTS双向认证(客户端)(服务器EMQX)

初级代码游戏的专栏介绍与文章目录-CSDN博客 我的github&#xff1a;codetoys&#xff0c;所有代码都将会位于ctfc库中。已经放入库中我会指出在库中的位置。 这些代码大部分以Linux为目标但部分代码是纯C的&#xff0c;可以在任何平台上使用。 源码指引&#xff1a;github源…

mosquitto配置桥接

同一终端中两个broker&#xff0c;其中一个做桥将1883端口的消息导出到1884&#xff1a; mosq.conf 多个服务器搭建mosquitto集群&#xff1a; mosquitto配置桥接_mosquitto 桥接-CSDN博客

通过Chatbox和API实现本地使用DeepSeek(R1满血版)

1、注册用户&#xff0c;申请API DeepSeek满血版api注册链接&#xff08;注册即送2000万Token&#xff09; 1.1 注册&#xff1a;https://cloud.siliconflow.cn/i/yl6uVodF 1.2 注册完成之后&#xff0c;申请API密钥 2、下载Chatbox 2.1 下载安装包&#xff1a;https://cha…

[学习笔记] Kotlin Compose-Multiplatform

Compose-Multiplatform 原文&#xff1a;https://github.com/zimoyin/StudyNotes-master/blob/master/compose-multiplatform/compose.md Compose Multiplatform 是 JetBrains 为桌面平台&#xff08;macOS&#xff0c;Linux&#xff0c;Windows&#xff09;和Web编写Kotlin UI…

【deepseek-r1本地部署】

首先需要安装ollama,之前已经安装过了&#xff0c;这里不展示细节 在cmd中输入官网安装命令&#xff1a;ollama run deepseek-r1:32b&#xff0c;开始下载 出现success后&#xff0c;下载完成 接下来就可以使用了&#xff0c;不过是用cmd来运行使用 可以安装UI可视化界面&a…

(篇六)基于PyDracula搭建一个深度学习的软件之新版本ultralytics-8.3.28调试

ultralytics-8.3.28版本debug记录 1传入文件 代码太多不粘贴在这里了&#xff0c;完整代码写在了篇三 def open_src_file(self):config_file config/fold.jsonconfig json.load(open(config_file, r, encodingutf-8))open_fold config[open_fold]if not os.path.exists(op…

寒假2.8

题解 web&#xff1a;[RoarCTF 2019]Easy Calc 打开&#xff0c;是一个计算界面 看一下源代码&#xff0c;提示设置了WAF&#xff0c;并且有一个calc.php文件 访问一下calc.php文件&#xff0c;得到源码&#xff0c;使用get方式传参赋值给num&#xff0c;设置了黑名单&#x…

pytest测试专题 - 1.2 如何获得美观的测试报告

<< 返回目录 1 pytest测试专题 - 1.2 如何获得美观的测试报告 1.1 背景 虽然pytest命令的报文很详细&#xff0c;用例在执行调试时还算比较方便阅读和提取失败信息&#xff0c; 但对于大量测试用例运行时&#xff0c;可能会存在以下不足 报文被冲掉测试日志没法归档 …

让office集成deepseek,支持office和WPS办公软件!(体验感受)

导读 AIGC:AIGC是一种新的人工智能技术&#xff0c;它的全称是Artificial Intelligence Generative Content&#xff0c;即人工智能生成内容。 它是一种基于机器学习和自然语言处理的技术&#xff0c;能够自动产生文本、图像、音频等多种类型的内容。这些内容可以是新闻文章、…

QML布局和信号槽

目录 一、定位器&#xff08;Positioners&#xff09; 1.Row&#xff08;行定位器&#xff09; 2.Column&#xff08;列定位器&#xff09; 3.Grid&#xff08;表格定位器&#xff09; 二、Layout布局 1.RowLayout&#xff08;行布局&#xff09; 2.ColumnLayout&#x…

C++ Primer 类型转换

欢迎阅读我的 【CPrimer】专栏 专栏简介&#xff1a;本专栏主要面向C初学者&#xff0c;解释C的一些基本概念和基础语言特性&#xff0c;涉及C标准库的用法&#xff0c;面向对象特性&#xff0c;泛型特性高级用法。通过使用标准库中定义的抽象设施&#xff0c;使你更加适应高级…

.Net使用EF Core框架如何连接Oracle

目录 一、Nutget包添加 二、 配置文件 三、创建实体类 四、创建数据库上下文类 五、将数据库上下文服务注册到容器 六、测试数据库数据 &#xff08;1&#xff09;编写PeopleController &#xff08;2&#xff09;编写People页面 一、Nutget包添加 一定要安装Oracle.Ma…