文档章节

AStar寻路2-性能优化

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

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

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

 

© 著作权归作者所有

共有 人打赏支持
梦想游戏人
粉丝 34
博文 420
码字总数 119565
作品 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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

git +STS使用问题解决一

1. 2.点以一个pull就是更新代码 3.synchronize workSpace 同步代码,同SVN一致

森火
9分钟前
0
0
powerBi odbc 连接impala 实现自助分析

配置Impala以使用ODBC 可以将第三方产品设计为使用ODBC与Impala集成。为获得最佳体验,请确保支持您打算使用的任何第三方产品。验证支持包括检查Impala,ODBC,操作系统和第三方产品的版本是...

hblt-j
14分钟前
0
0
Purism FAQ

<font size="37" color="#006248" face="幼圆"> <p align="center"> Purism FAQ </p> </font> 原文:https://puri.sm/faq/ 原作者:Purism Team 翻译者:冰焰火灵X 1079092922@qq.com 文章许......

ICE冰焰火灵X
29分钟前
0
0
nginx+webdav

1、配置Nginx以支持WebDav: Webdav是nginx一个组件,默认编译nginx时是没有安装这个组件的。 如果跟应用公用一个nginx,需要重新编译安装nginx,重新安装前需要备份好原来的nginx.conf。 1....

yaukie
35分钟前
0
0
spring 事件

ContextRefreshedEvent Event raised when an {@code ApplicationContext} gets initialized or refreshed. ContextClosedEvent Event raised when an {@code ApplicationContext} gets clos......

Canaan_
46分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部