文档章节

AStar寻路2-性能优化

梦想游戏人
 梦想游戏人
发布于 2017/07/05 15:39
字数 517
阅读 82
收藏 0

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

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

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

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

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

 

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

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

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

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

 

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

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

通过数组实现,来快速索引节点在堆中的位置做插入操作

二叉堆的相关知识不在展开。

 

© 著作权归作者所有

共有 人打赏支持
梦想游戏人
粉丝 35
博文 435
码字总数 123998
作品 0
成都
私信 提问
基于HTML5的WebGL呈现A星算法的3D可视化

最近搞个游戏遇到最短路径的常规游戏问题,一时起兴基于HT for Web写了个A算法的WebGL 3D呈现,算法基于开源 https://github.com/bgrins/javascript-astar 的javascript实现,其实作者也有个...

xhload3d
2015/11/17
0
0
百度2010年 Astar程序设计大赛启动

5月18日午间消息,由中文搜索引擎百度举办的“2010 Astar百度之星程序设计大赛”正式面向全国高校学生和广大编程爱好者启动,本届“Astar大赛”主题为“乐CODE乐CODE”。 除延续往届的赛程及...

红薯
2010/05/18
972
5
2011 Astar 百度之星程序设计大赛开幕

5月20日消息,由中文搜索引擎百度举办的“2011 Astar百度之星程序设计大赛”正式面向全国高校学生和广大编程爱好者正式拉开帷幕。 百度技术副总裁王劲出席启动仪式,与北大、清华、北邮等国内...

红薯
2011/05/20
2.5K
14
基于HT for Web的3D呈现A* Search Algorithm

最近搞个游戏遇到最短路径的常规游戏问题,一时起兴基于HT for Web写了个A算法的WebGL 3D呈现,算法基于开源 https://github.com/bgrins/javascript-astar 的javascript实现,其实作者也有个...

xhload3d
2014/11/24
0
0
A*寻路算法在Unity中的简单应用

前言 在使用Unity开发游戏项目时,经常会遇到一些角色的导航需求,然而Unity提供给我们的NavMesh+NavMeshAgent并不能很好帮我们实现,且寻路网格的烘焙,以及在导航过程中寻路网格的检测,都...

欣羽馨予
2016/06/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

防御CSRF攻击

跨站请求伪造(CSRF)是一种安全漏洞,攻击者利用受害者的 session 来通过受害者的浏览器发出请求。攻击者通过受害者的浏览器发送请求,并伪造成是受害者自己发出的请求。 建议你先熟悉CSRF,...

Landas
28分钟前
1
0
【双12首发】终于等来了!PhalApi-iView-admin 开源后台框架

PhalApi-iView-admin 开源后台框架 码云地址:https://gitee.com/dogstar/phalapi-iview-admin Github地址:https://github.com/phalapi/phalapi-iview-admin 主要采用的技术: PhalApi 开源......

暗夜在火星
28分钟前
1
0
JavaScript面试题大坑之隐式类型转换实例代码

1.1-隐式转换介绍 在js中,当运算符在运算时,如果两边数据不统一,CPU就无法计算,这时我们编译器会自动将运算符两边的数据做一个数据类型转换,转成一样的数据类型再计算 这种无需程序员手...

peakedness丶
30分钟前
0
0
示例vue 的keep-alive缓存功能的实现

本篇文章主要介绍了vue 的keep-alive缓存功能的实现,写的十分的全面细致,具有一定的参考价值,对此有需要的朋友可以参考学习下。如有不足之处,欢迎批评指正。 #Vue 实现组件信息的缓存 当...

前端攻城老湿
31分钟前
0
0
解析Vue.js中的computed工作原理

我们通过实现一个简单版的和Vue中computed具有相同功能的函数来了解computed是如何工作的。写的十分的全面细致,具有一定的参考价值,对此有需要的朋友可以参考学习下。如有不足之处,欢迎批...

前端攻城小牛
33分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部