文档章节

AStar寻路2-性能优化

梦想游戏人
 梦想游戏人
发布于 2017/07/05 15:39
字数 517
阅读 80
收藏 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表的有序

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

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

 

© 著作权归作者所有

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

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

xhload3d
2015/11/17
0
0
基于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
考研复试系列——第十一节 map的使用

考研复试系列——第十一节 map的使用 前言 map基础 #pragma warning(disable:4786)//消除4786警告 include include include using namespace std; int main(){string str = "wangcan";rever......

cassiepython
2017/03/12
0
0
Silverlight游戏设计(Game Design):(四)从零开始搭建游戏主体框架

思路已俨然清晰,接下来要做的是从零开始搭建游戏的主体框架。Silverlight作为RIA界的新宠儿,不仅在游戏开发方面性能优越,在企业开发领域的优异表现同样日益显著。像我们这些长期从事.NET开...

晨曦之光
2012/03/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Swagger中配置了@ApiModelProperty的allowableValues属性但不显示的问题

现在用Swagger来生成API文档的例子已经非常多了,今天碰到开发同事问了一个问题,帮着看了一下,主要还是配置方法的问题,所以记录一下。如果您也碰到了同样的问题,希望本文对您有用。 问题...

程序猿DD
30分钟前
1
0
sql 命令

show variables like '%general%'; show variables like '%log_output%'; show variables like '%quer%'; show global status like '%slow%';...

JavaSon712
38分钟前
0
0
Django修改默认数据库引擎

Django默认数据库引擎为sqlite3,除了sqlite3,还支持postgresql、mysql、oracle 配置如下:其中postgresql_psycopg2为postgresql的适配器。 'django.db.backends.postgresql' 'django.db.bac......

MichaelShu
43分钟前
0
0
动画源码解析

目录介绍 1.Animation和Animator区别 2.Animation运行原理和源码分析 2.1 基本属性介绍 2.2 如何计算动画数据 2.3 什么是动画更新函数 2.4 动画数据如何存储 2.5 Animation的调用 3.Animator...

潇湘剑雨
49分钟前
4
0
Mac OS 最强鼠标改键软件:BetterAndBetter

官网: http://www.better365.cn 话不多说,先上你们最喜欢的软件界面截图。 通用: 触摸板: 鼠标: 键盘: 情景模式: 文本跳窗(自动跳窗): 四角触发: 工具箱: 脚本: 关于: 说下我目...

故国有明
今天
20
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部