文档章节

AStar寻路2-性能优化

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

码上生花,ECharts 作品展示赛正式启动!>>>

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表的有序

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

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

 

© 著作权归作者所有

梦想游戏人
粉丝 43
博文 491
码字总数 194264
作品 0
成都
私信 提问
加载中
请先登录后再评论。
Unity NavMesh 动态烘焙绘制与随机取点

最初的Unity导航系统很不完善,只能静态烘焙场景图的可行走区域,而且必须在本地保存场景的NavMesh数据,难以运行时动态计算;这使得鲜有开发者愿意再尝试Unity内置的导航功能,转向了AStar...

osc_y8w65yuq
01/15
11
0
使用A*寻路插件实现最基础的平面两点之间寻路

A寻路作为一个插件,最重要的就是如何使用,所以跟着书本上的案例实现了最简单的使用方式—一个起始点和一个目标点之间来寻路。 现在先懂得基础用法 1.如何使用 在这里插入图片描述 1.插件导...

小萌新大四要工作
06/03
0
0
A*算法golang实现的open、close列表的实现调研

https://github.com/beefsack/go-astar 有完整的测试案例,代码全面性最好。 实现在 https://github.com/beefsack/go-astar/blob/master/astar.go 集成 open 和 close 在node类,然后用map管...

蝈蝈俊
02/29
0
0
百度2010年 Astar程序设计大赛启动

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

红薯
2010/05/18
992
5
基于HTML5的WebGL呈现A星算法的3D可视化

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

xhload3d
2015/11/17
448
0

没有更多内容

加载失败,请刷新页面

加载更多

springboot单元测试配置

##SpringBoot进行单元测试 ####需要的依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-test</artifactId><scope>test</scope><excl......

RandomObject
13分钟前
17
0
看了同事的代码,我忍不住写了这份代码指南

❝ 作者:xybaby 链接:https://www.cnblogs.com/xybaby/p/11335829.html ❞ 前言 写出整洁的代码,是每个程序员的追求。《clean code》指出,要想写出好的代码,首先得知道什么是肮脏代码、...

osc_fvp5wdwk
21分钟前
24
0
Flutter基础篇(2)-- 老司机用一篇博客带你快速熟悉Dart语法

版权声明:本文为博主原创文章,未经博主允许不得转载。https://www.jianshu.com/p/3d927a7bf020 转载请标明出处: https://www.jianshu.com/p/3d927a7bf020 本文出自 AWeiLoveAndroid的博客...

osc_dg21zk4i
22分钟前
18
0
如何在小程序制作表单活动?

比起纸质的表单,电子版表单更加受市场的青睐,尤其是随着越来越多的东西都被赋予了营销属性,不只是只有广告才能够做宣传,比如说表单也不仅仅只是一个收集信息的工具,我们对表单加以包装,...

osc_9bje7o1h
23分钟前
10
0
Intel x710万兆 SR-IOV 网卡驱动升级

目录 文章目录 目录 环境 获取最新驱动 安装 环境 CentOS7 Intel x710 获取最新驱动 官方地址:https://downloadcenter.intel.com/zh-cn/product/83967/Intel-Ethernet-Converged-Network-A...

osc_b9r67jnt
24分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部