AStar寻路1

Stella981
• 阅读 629

A星算法是一种启发式的搜索方法,通过一个路径评估函数,来动态确定最佳路径。这点和广度搜索不同。

基本思想是有2个列表,open和close,

open列表里面的节点表示待搜索周围点的节点,close列表里面记录着不需要搜索的节点。

启发式函数f=g+h;

f表示该路径的代价,g表示起点到搜索的点的该条路径的实际值,h表示该搜索的点到终点的估计值。h的估计值越接近当前点到终点的最短路径的实际值那么A星搜索出来的路径就越接近实际的最短路径,从这点来看A星是时间和精度的一个权衡改进的广度搜索算法。h值始终为0的话,那退化为广度搜索了(没有了估值,f的计算都是实际值,因此变为了暴力的广度搜索)。

进过以下测试,大约牺牲了10%的精度换来了10倍的速度。

AStar寻路1

上图为h值为0,退化为广度搜索。

AStar寻路1

上图为曼哈顿估值法(即横向和纵向距离之和),

AStar寻路1

上图为距离估值法。

AStar寻路1

上图为随机化地图遮挡的结果,

每次搜索都从open表中找出代价最小的节点进行搜索,在搜索当前点时,如果周围点已经存在于open列表中,那么就要重新计算f和g值,表示进过当前点到达 周围点会不会更近,重新计算后open列表将会重新排序,下个轮回再次从f值最小的开始广度搜索。

下篇主要是优化性能    AStar寻路2-性能优化

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Wesley13 Wesley13
3年前
java将前端的json数组字符串转换为列表
记录下在前端通过ajax提交了一个json数组的字符串,在后端如何转换为列表。前端数据转化与请求varcontracts{id:'1',name:'yanggb合同1'},{id:'2',name:'yanggb合同2'},{id:'3',name:'yang
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Wesley13 Wesley13
3年前
GoJS API学习
varnode{};node"key""节点Key";node"loc""00";//节点坐标node"text""节点名称";//添加节点通过按钮点击,添加新的节点到画布myDiagram.model.addNodeData(nod
Stella981 Stella981
3年前
Python3 中 的 绝对导入 与 相对导入
背景:在学习tf的时候,看到了from__future__importabsolute_import,所以登记学习一下。概览:一般模块导入规则:importxxx时搜索文件的优先级如下:1.在当前目录下搜索该模块2.在环境变量PYTHONPATH中指定的路径列表中依次搜索3.
Stella981 Stella981
3年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Stella981 Stella981
3年前
PHP+jQuery寥寥几行代码轻松实现百度搜索那样的无刷新PJAX的分页列表和导航链接
!(https://static.oschina.net/uploads/space/2016/1208/171419_U00R_561214.png)PHP寥寥几行代码轻松实现百度搜索那样的分页列表和导航链接,某些语言的拥趸哭晕在厕所.<?php$apparray('db_prefix''
Stella981 Stella981
3年前
LeetCode112
非商业,LeetCode链接附上:https://leetcodecn.com/problems/pathsum/进入正题。题目:给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。说明: 叶子节点是指没有子节点的节点。示例:给定如下二叉树,以及目标和
Wesley13 Wesley13
3年前
N数码问题的启发式搜索算法
一、启发式搜索:A算法1)评价函数的一般形式:f(n)g(n)h(n)g(n):从S0到Sn的实际代价(搜索的横向因子)h(n):从N到目标节点的估计代价,称为启发函数(搜索的纵向因子);特点:效率高,无回溯, 搜索算法OPEN表:存放待扩展的节点.CLOSED表:存放已被扩展过的节点