AStar寻路2

Stella981
• 阅读 617

AStar寻路1-实现基本功能  的性能优化篇

优化方法,因为为了查看代码的profiler,因此用Unity来实现图形化,VS的c#有性能测试工具,根据热点函数来寻找瓶颈点和优化策略。

通过VS的性能测试工具,得出了上篇的热点函数是排序相关和估值函数。

A星寻路得到的路径,大部分情况下不会是最短路径,但是肯定是接近最短路径,只有每次的估计值是真实最短路径的值,那么得出的才会是最短路径。

原因是A星选择的贪心策略存在的误差是估值得来的,而该点的f值只会计算一次会一直用到寻路点直到终点,而不会随时调整,然后排序。

因此A星的精度和速度和估值函数的算法很重要,常见的几种估值方法

1.曼哈顿距离法,目标点和垂直距离与纵向距离之和,

2.直线距离法,直接是2点的距离,缺点是开方CPU代价太大。但是得到的路径较为平滑,开销大概是曼哈顿的2倍左右

3.还有一种方法,综合了2和1的特点,基本思想是如下图的A到B点

AStar寻路2

搜索过程中,从空间来说,因为不确定是否存在路径,因此要保存完整的节点信息,最坏情况是没有路径,空间占用就是节点总数。重复寻路的话Node对象的复用避免new的频繁开销也是一个优化点

open表的排序从时间来说,每次插入操作都要保证open列表中是有序的,一种优化方案是使用二叉堆来保证open表的有序

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
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
2个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Java修道之路,问鼎巅峰,我辈代码修仙法力齐天
<center<fontcolor00FF7Fsize5face"黑体"代码尽头谁为峰,一见秃头道成空。</font<center<fontcolor00FF00size5face"黑体"编程修真路破折,一步一劫渡飞升。</font众所周知,编程修真有八大境界:1.Javase练气筑基2.数据库结丹3.web前端元婴4.Jav
Souleigh ✨ Souleigh ✨
3年前
前端性能优化 - 雅虎军规
无论是在工作中,还是在面试中,web前端性能的优化都是很重要的,那么我们进行优化需要从哪些方面入手呢?可以遵循雅虎的前端优化35条军规,这样对于优化有一个比较清晰的方向.35条军规1.尽量减少HTTP请求个数——须权衡2.使用CDN(内容分发网络)3.为文件头指定Expires或CacheControl,使内容具有缓存性。4.避免空的
Wesley13 Wesley13
2年前
Java日期时间API系列31
  时间戳是指格林威治时间1970年01月01日00时00分00秒起至现在的总毫秒数,是所有时间的基础,其他时间可以通过时间戳转换得到。Java中本来已经有相关获取时间戳的方法,Java8后增加新的类Instant等专用于处理时间戳问题。 1获取时间戳的方法和性能对比1.1获取时间戳方法Java8以前
Stella981 Stella981
2年前
Android So动态加载 优雅实现与原理分析
背景:漫品Android客户端集成适配转换功能(基于目标识别(So库35M)和人脸识别库(5M)),导致apk体积50M左右,为优化客户端体验,决定实现So文件动态加载.!(https://oscimg.oschina.net/oscnet/00d1ff90e4b34869664fef59e3ec3fdd20b.png)点击上方“蓝字”关注我
Stella981 Stella981
2年前
JS 对象数组Array 根据对象object key的值排序sort,很风骚哦
有个js对象数组varary\{id:1,name:"b"},{id:2,name:"b"}\需求是根据name或者id的值来排序,这里有个风骚的函数函数定义:function keysrt(key,desc) {  return function(a,b){    return desc ? ~~(ak
Stella981 Stella981
2年前
AStar寻路1
A星算法是一种启发式的搜索方法,通过一个路径评估函数,来动态确定最佳路径。这点和广度搜索不同。基本思想是有2个列表,open和close,open列表里面的节点表示待搜索周围点的节点,close列表里面记录着不需要搜索的节点。启发式函数fgh;f表示该路径的代价,g表示起点到搜索的点的该条路径的实际值,h表示该搜索的点到终点的估计值。h的
Wesley13 Wesley13
2年前
C++程序性能分析
最近要对推送程序进行性能优化,找出程序的hotspots,程序是用VS2005,C写的,所以直接使用VS2005自带的性能分析工具对程序做了一次profiling。准备工作使用VS2005打开工程,在菜单“工具”下面有个“性能工具”的选项,点击右边的“性能向导”就可以开始新建一个性能测试项了。如:!性能测试的菜单项(http: