当前位置: 首页 > news >正文

A星寻路算法

A星寻路算法简介
A星寻路算法(A* Search Algorithm)是一种启发式搜索算法,它在图形平面上进行搜索,寻找从起始点到终点的最短路径。A星算法结合了广度优先搜索(BFS)和最佳优先搜索(Best-First Search)的特点,通过使用启发式函数评估节点的重要性,优先选择最有希望达到目标节点的节点进行扩展,从而有效地缩小搜索范围。
A星寻路算法的核心概念

  1. 节点(Node):在图形平面上,每个可移动的点都可以被视为一个节点。节点可以是地图上的障碍物、可移动的实体等。
  2. 边(Edge):节点之间的连接称为边。在路径搜索中,边通常表示可移动的路径或移动方向。
  3. 代价函数(Cost Function):F=G+H,用于评估从起始节点到当前节点的代价。在A星算法中,代价函数通常由两个部分组成:实际代价(Actual Cost)和启发式代价(Heuristic Cost)。
  4. 父节点(Parent Node):在搜索过程中,每个节点都有一个指向其父节点的指针,表示该节点是如何从父节点扩展而来的。
  5. 开放列表(Open List):包含所有正在被考虑的节点。这些节点尚未被扩展,且具有最小的实际代价+启发式代价。
  6. 关闭列表(Closed List):包含所有已经扩展过的节点。这些节点不再被考虑。

A星寻路算法的步骤

  1. 初始化:设置起始节点和目标节点,将起始节点添加到开放列表中。
  2. 循环执行以下步骤,直到开放列表为空或找到目标点:
    a. 从开放列表中选择具有最小代价的节点n,并将其从开放列表中移除。
    b. 将节点n添加到关闭列表中,并遍历其所有相邻节点。对于每个相邻节点m:
  • 如果m不在关闭列表中,计算从起始节点到m的实际代价g(m)(g(m) = g(n)+n到m的代价)和启发式代价h(m)。如果m的代价小于其之前的代价,或者m尚未设置父节点,则将m的父节点设置为n,并更新m的代价g(m)。将m添加到开放列表中。如果节点m是目标节点,则找到了最短路径,结束算法。
  1. 如果开放列表为空而未找到最短路径,则说明存在无法达到目标的路径或目标不可达,结束算法。
  2. 输出最短路径:从目标节点回溯到起始节点,按照父节点指针依次访问节点,得到最短路径。

代码实现

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;//节点
public class AstarNode:IComparable<AstarNode> //继承接口实现重载排序方式
{public int x;//x坐标public int y;//y坐标public Vector2Int pos;//x,y坐标public int G;//起点到该点的距离public int H;//该点到终点的曼哈顿距离public int F;//F = G + Fpublic AstarNode()   //无参构造函数{}public AstarNode(Vector2Int pos) //有参构造函数{this.pos = pos;this.x = pos.x;this.y = pos.y;}public int CompareTo(AstarNode other) //排序方式{return this.F-other.F; //F小排在前}
}//A星
public class AStar 
{bool result =false;//单例模式public static AStar instance;public static AStar Instance{get{if(instance==null){instance = new AStar();}return instance;}}//上右下左四个方向private Vector2Int[] directions = new Vector2Int[]{new Vector2Int(1,0),new Vector2Int(0,1),new Vector2Int(-1,0),new Vector2Int(0,-1)};//上右下左//开放表private List<AstarNode> openList = new List<AstarNode>();//关闭表,但这里没用到,用cameFrom代替了它的作用//private HashSet<Vector2Int> closeList = new HashSet<Vector2Int>();//路径字典,用来存储路径以及作为关闭表来判断该点是否已经走过private Dictionary<Vector2Int,Vector2Int> cameFrom = new Dictionary<Vector2Int, Vector2Int>();//记录最终路径,作为返回值private List<Vector2Int> path = new List<Vector2Int>();//寻路方法public List<Vector2Int> FindPath(List<List<Transform>> map,Vector2Int startP,Vector2Int targetP)//地图,起点,终点{Debug.Log("开始寻路");//计算起点G,H,F,将起点加入开放表,AstarNode rNode = new AstarNode(startP);rNode.G = 0;rNode.H = Manhattan(rNode.pos,targetP);rNode.F = rNode.G+rNode.H;openList.Add(rNode);cameFrom[startP] = new Vector2Int(-1,-1); //记录路径,当前点坐标作为key,上一个点的坐标作为value,表示从上一个点坐标到达该点//循环直到找到路径,或者开放表没有节点while(openList.Count>0&&!result){//开放表以F为标准排序,F小在前openList.Sort(); //取出开放表中F最小的节点AstarNode curNode = openList[0];//取出的节点要从开放表中移除,加入到关闭表openList.RemoveAt(0);//遍历这个点周围的四个方向foreach(Vector2Int dir in directions){Vector2Int newP = curNode.pos+dir;//判断边界,有没有超出地图范围if(newP.x<0||newP.x>=map.Count||newP.y<0||newP.y>=map[0].Count) //边界点判断{continue;}//判断是否在关闭表if(cameFrom.ContainsValue(newP)){continue;}//判断该点是否是障碍物if(!map[newP.x][newP.y].gameObject.GetComponent<Tile>().CheckObstacle()){continue;}//查看是否在开放表AstarNode node = openList.FirstOrDefault(p => p.pos == newP);//linq查询openlist中是否有该点的节点//不在开放表就计算G,H,F,加入开放表,边的代价默认为1if(node==null){//Debug.Log("添加");AstarNode newNode = new AstarNode();newNode.pos = newP;newNode.G = curNode.G+1;newNode.H = Manhattan(newNode.pos,targetP);newNode.F = newNode.G+newNode.H;cameFrom[newNode.pos] = curNode.pos; //记录路径openList.Add(newNode);}else    //在开放表,判断当前路径代价是否更小,是否要更新代价{//如果当前路径代价更小,更新代价和路径if(node.G > curNode.G+1) {node.G = curNode.G+1;node.F = node.G+node.H;cameFrom[node.pos] = curNode.pos;}}//如果当前点就是目标点,则停止寻路if(curNode.pos == targetP){result = true;break;}}}//如果找到路径,通过终点与cameFrom,从后往前找到整条路径。if(result){//通过栈把路径节点转成从起点到终点Stack<Vector2Int> path_stack = new Stack<Vector2Int>();Vector2Int pos = targetP;path_stack.Push(targetP);//将节点压入栈内while(pos!=startP){Vector2Int newP = cameFrom[pos];pos = newP;path_stack.Push(pos);}//将栈内节点弹出while(path_stack.Count>0){pos = path_stack.Pop();path.Add(pos);//Debug.Log(pos);}}else{Debug.Log("没找到");}return path;}public int Manhattan(Vector2Int a,Vector2Int b) //获取两点曼哈顿距离{return Mathf.Abs(a.x -b.x)+Mathf.Abs(a.y-b.y);}}

这段代码通过传递地图网格,地点和终点,实现了简单的A星寻路算法。首先构建一个新的Astar节点,设置为起点节点。起点的G为0,H采用曼哈顿距离,F = G + H。将起点节点加入到开放表。要取到开放表中F最小的节点,因为数据量较小,这里在每次从开放表取节点前都以F进行一次排序得到F最小节点(用优先队列会更好)。通过该节点访问其上右下左的四个点,并判断这些点是否能够加入开放表(坐标超出网格范围,节点在关闭表,节点是障碍点。都不能加入开放表)关闭表使用字典存储,在实现关闭表的同时还记录了节点之间的路径信息。最后判断坐标点是否在开放表,不在开放表的点构建节点并加入开放表,这里默认两点间的代价为1;在开放表中的则判断新的路径中代价是否更小,更小则更新代价和路径信息,否则不做处理。最后判断坐标点是否为目标坐标,如果是目标坐标即停止寻路。最后通过存储的路径信息找到完整路径。
A星寻路算法的优化技巧

  1. 合理选择启发式函数:启发式函数用于估计从当前节点到目标节点的代价。选择合适的启发式函数能够提高算法的性能和准确性。常见的启发式函数有曼哈顿距离、欧几里得距离等。
  2. 权重调整:根据实际应用场景和需求,可以对边的权重进行调整,以优化搜索效率和找到更符合特定要求的路径。
  3. 动态调整开放列表的大小:在搜索过程中,可以根据需要动态调整开放列表的大小,以平衡搜索效率和内存消耗。
  4. 利用优先队列进行节点排序:将开放列表中的节点按照代价从小到大排序,可以利用优先队列数据结构实现高效的排序操作,从而提高算法性能。
  5. 预处理和缓存:在某些情况下,可以对地图进行预处理或使用缓存机制来提高搜索效率。例如,可以将一些已知的信息存储起来以便快速访问,或者预先计算某些节点的代价等。
  6. 多线程并行处理:在多核处理器环境下,可以利用多线程技术对不同区域或方向的搜索进行并行处理,以提高算法的整体性能。
  7. 局部搜索和回溯策略:在搜索过程中,可以结合局部搜索和回溯策略来优化路径选择和调整方向。当遇到局部最优解时,可以通过回溯或尝试其他方向来寻找更好的解。
  8. 增量式更新地图:对于动态变化的地图环境,可以采用增量式更新地图的方法来提高算法的适应性。当地图发生变化时,只对变化区域进行重新搜索和处理,而保持其他区域的搜索

A星寻路算法的应用
A星寻路算法广泛应用于游戏开发、机器人导航、路径规划等领域。以下是一些具体的应用场景:

  1. 游戏开发:在角色扮演游戏、策略游戏等类型中,A星算法常被用于实现智能角色的寻路和移动。通过找到最短路径,玩家可以更流畅地控制角色,提高游戏的可玩性和体验。
  2. 机器人导航:在机器人领域,A星算法用于指导机器人从起点到目标点的路径规划。这种算法能够帮助机器人避开障碍物,选择最佳路径,从而实现高效、安全的导航。
  3. 路径规划:在交通、物流等领域,A星算法用于规划最短或最优路径。例如,在物流配送中,通过使用A星算法,可以找到从起点到目的地的最短路径,从而提高配送效率。
  4. 图形编辑和可视化:在处理复杂的图形数据时,A星算法可以帮助找到从一个节点到另一个节点的最短路径,从而进行高效的编辑和可视化操作。

总结
A星寻路算法是一种高效、实用的路径搜索算法,它结合了广度优先搜索和最佳优先搜索的特点,通过启发式函数评估节点的重要性,从而快速找到最短路径。通过合理的优化技巧,A星算法能够适多种应用场景,提高性能和准确性。

相关文章:

A星寻路算法

A星寻路算法简介 A星寻路算法&#xff08;A* Search Algorithm&#xff09;是一种启发式搜索算法&#xff0c;它在图形平面上进行搜索&#xff0c;寻找从起始点到终点的最短路径。A星算法结合了广度优先搜索&#xff08;BFS&#xff09;和最佳优先搜索&#xff08;Best-First S…...

QDialog

属性方法 样式表 background-color: qlineargradient(spread:reflect, x1:0.999896, y1:0.494136, x2:1, y2:1, stop:0 rgba(0, 0, 0, 255), stop:1 rgba(255, 255, 255, 255));border: 1px groove rgb(232, 232, 232);border-radius: 20px; QDialog 的常用方法&#xff1a; e…...

Spark中使用DataFrame进行数据转换和操作

Apache Spark是一个强大的分布式计算框架&#xff0c;其中DataFrame是一个核心概念&#xff0c;用于处理结构化数据。DataFrame提供了丰富的数据转换和操作功能&#xff0c;使数据处理变得更加容易和高效。本文将深入探讨Spark中如何使用DataFrame进行数据转换和操作&#xff0…...

windows11新装机,简单评测系统自带软件(基本涵盖日常所需应用)

新年将近&#xff0c;由于当年安排的失误&#xff0c;系统盘&#xff08;100G&#xff09;和照片视频盘&#xff08;4T&#xff09;容量不够了&#xff0c;大容量的那块机械盘放在机箱里就在耳朵根吵吵&#xff0c;烦得很&#xff0c;于是狠狠心决定扩容后重配重装。 2023年最后…...

概念解析 | Shapley值及其在深度学习中的应用

注1:本文系“概念解析”系列之一,致力于简洁清晰地解释、辨析复杂而专业的概念。本次辨析的概念是:Shapley值及其在深度学习中的应用。 1 背景介绍 在机器学习和数据分析中,理解模型的预测是非常重要的。尤其是在深度学习黑盒模型中,我们往往难以直观地理解模型的预测行为。为…...

ajax的完整写法——success/error/complete+then/catch/done+设置请求头两种方法——基础积累

ajax的完整写法——success/error/completethen/catch/done设置请求头两种方法——基础积累 1.完整写法——success/error/complete1.1 GET/DELETE——query传参1.2 GET/DELETE——JSON对象传参1.3 PUT/POST——JSON对象传参 2.简化写法——then/catch/done2.1 GET/DELETE——q…...

《Linux详解:深入探讨计算机基础》

《Linux详解&#xff1a;深入探讨计算机基础》 引言&#xff1a; 在计算机科学领域&#xff0c;操作系统是一个至关重要的概念&#xff0c;而Linux作为一种开源的Unix-like操作系统&#xff0c;不仅在服务器领域广泛应用&#xff0c;也在嵌入式系统、超级计算机等多个领域发挥…...

HarmonyOS 实践之应用状态变量共享

平时在开发的过程中&#xff0c;我们会在应用中共享数据&#xff0c;在不同的页面间共享信息。虽然常用的共享信息&#xff0c;也可以通过不同页面中组件间信息共享的方式&#xff0c;但有时使用应用级别的状态管理会让开发工作变得简单。 根据不同的使用场景&#xff0c;ArkTS…...

ThreadLocal共享变量

一、ThreadLocal 我们知道多线程访问同一个共享变量时&#xff0c;会出现线程安全问题&#xff0c;为了保证线程安全开发者需要对共享变量的访问操作进行适当的同步操作&#xff0c;如加锁等同步操作。 除此之外&#xff0c;Java提供了ThreadLocal类&#xff0c;当一个共享变…...

前端crypto-js 库: MD5

文章目录 什么是crypto-js安装依赖MD5 什么是crypto-js github地址: https://github.com/brix/crypto-js cryptojs文档: https://cryptojs.gitbook.io/docs/#encoders CryptoJS (crypto.js) 为 JavaScript 提供了各种各样的加密算法。 CryptoJS是一个JavaScript加密算法库&a…...

2024新年快乐

2024-1-1 祝福大家和自己健康喜乐&#xff0c;升职加薪&#xff0c;新年快乐 页面加载事件load 我们页面加载事件的触发是等所有的资源加载完毕时触发该事件。和click一样是事件&#xff0c;但是触发时机是等资源加载&#xff08;浏览器&#xff09;完毕。这个事件我们可以将…...

OpenCV-Python(21):轮廓特征及周长、面积凸包检测和形状近似

2. 轮廓特征 轮廓特征是指由轮廓形状和结构衍生出来的一些特征参数。这些特征参数可以用于图像识别、目标检测和形状分析等应用中。常见的轮廓特征包括&#xff1a; 面积&#xff1a;轮廓所包围的区域的面积。周长&#xff1a;轮廓的周长&#xff0c;即轮廓线的长度。弧长&…...

连接progressql报错Cannot load JDBC driver class ‘org.postgresql.Driver‘,亲测有效!!!

Jmeter连接progressql报错Cannot load JDBC driver class ‘org.postgresql.Driver’ 1.到官方下载驱动注意&#xff1a;根据项目的JDK版本来下载对应的驱动Download | pgJDBC 2.将postgresql-42.2.27.jar复制到lib目录下面&#xff0c; 然后重新启动 连接driver信息如下&#…...

SQLAlchemy快速入门

安装依赖 pip install sqlalchemy pip install pymysql创建数据库和表 # 创建数据库 drop database if exists sqlalchemy_demo; create database sqlalchemy_demo character set utf8mb4; use sqlalchemy_demo;# 创建表 drop table if exists user; create table user (id …...

java 纯代码导出pdf合并单元格

java 纯代码导出pdf合并单元格 接上篇博客 java导出pdf&#xff08;纯代码实现&#xff09; 后有一部分猿友叫我提供一下源码&#xff0c;实际上我的源码已经贴在帖子上了&#xff0c;都是同样的步骤&#xff0c;只是加多一点设置就可以了。今天我再次上传一下相对情况比较完整…...

Linux自己的应用商店yum

&#x1f4ab;Linux系统如何安装软件 在Linux系统中我们可以通过多种方式安装软件&#xff0c;常见方式有以下三种&#xff1a;   1.源代码安装   2.rpm包安装   3.使用yum软件包管理器安装   早期人们通过下载软件源代码&#xff0c;然后再经过交叉编译等一系列工作下…...

集成电路模拟设计——【基于Serdes 应用的 串化/解串器 时钟与数据恢复电路CDR】

串化/解串器 & 时钟与数据恢复电路CDR&#xff08;可提供实现过程、仿真波形与具体参数细节 本文内容摘要背景串化/解串器全速树形串化器半速树形串化器全速移位寄存器串化器多级树形解串器 PLL型CDR整体架构实现结果 Bang-Bang型CDR整体架构 PS/PI型CDR电路PS电路设计PI电…...

OpenWrt 编译入门(小白版)

编译环境 示例编译所用系统为 Ubuntu 22.04&#xff0c;信息如下 编译时由于网络问题&#xff0c;部分软件包可能出现下载问题&#xff0c;还请自备网络工具或尝试重新运行命令 编译步骤 下图为官网指示 编译环境设置&#xff08;Build system setup&#xff09; 这里根据我…...

嵌入式视频播放器(mplayer)

1.文件准备&#xff1a; MPlayer-1.0rc2.tar.bz2 libmad-0.15.1b.tar.gz 直接Git到本地 git clone https://gitee.com/zxz_FINE/mplayer_tarball.git 2.文件夹准备&#xff1a; src存放解压后的源码文件&#xff0c;target_Mplayer存放编译安装的目标文件 mkdir src targe…...

对房价数据集进行处理和数据分析

大家好&#xff0c;我是带我去滑雪&#xff0c;每天教你一个小技巧&#xff01; 房价数据集通常包含各种各样的特征&#xff0c;如房屋面积、地理位置、建造年份等。通过对数据进行处理和分析&#xff0c;可以更好地理解这些特征之间的关系&#xff0c;以及它们对房价的影响程度…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

vue3 daterange正则踩坑

<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...

五子棋测试用例

一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏&#xff0c;有着深厚的文化底蕴。通过将五子棋制作成网页游戏&#xff0c;可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家&#xff0c;都可以通过网页五子棋感受到东方棋类…...