文档章节

AStar寻路2-性能优化

梦想游戏人
 梦想游戏人
发布于 2017/07/05 15:39
字数 517
阅读 74
收藏 0
点赞 0
评论 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
博文 402
码字总数 115594
作品 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

如何制作RTS游戏的寻路系统?

原文链接:https://blog.uwa4d.com/archives/TechSharing107.html 这是第107篇UWA技术知识分享的推送。今天我们继续为大家精选了若干和开发、优化相关的问题,建议阅读时间15分钟,认真读完必...

uwa4d ⋅ 04/17 ⋅ 0

RCP:gef智能寻路算法(A star)

本路由继承自AbstactRouter,参数只有EditPart(编辑器内容控制器),gridLength(寻路用单元格大小),style(FLOYD,FLOYDFLAT,FOURDIR)。 字符集编码为GBK,本文只做简单的代码解析,源码...

anrainie ⋅ 2014/06/12 ⋅ 0

Hont/AStar3DSpacePathfinding

#3D Space AStar Pathfinding 简介 3D空间A*寻路实现,可以运用在3D空间的飞船寻路或者战机空中寻路,支持自定义中心点,支持Mask,动态障碍物,自由旋转缩放,八叉树优化的坐标转换等等。满...

Hont ⋅ 2016/08/11 ⋅ 0

A*/A星/AStar算法 视频笔记,Unity代码实现

视频来源:https://www.bilibili.com/video/av23095766?from=search&seid=5873495875101903731 代码来源:https://www.jianshu.com/p/22dfcca70064 平面划分若干方块,假设红色是起点紫色是终......

qq_36718838 ⋅ 05/12 ⋅ 0

人工智能Pacman(一)(2018-05-22)

实验内容: 实验要求采用且不限于课程第四章内各种搜索算法此编写一系列吃豆人程序解决以下列出的问题1-8,包括到达指定位置以及有效的吃豆等。 代码下载地址: search.zip 简介: 参考网址:...

kolongmashin ⋅ 05/22 ⋅ 0

AS3 做webGame 地图寻路实例 .

总结目的 在地图中,通过鼠标或者由程序自动运行,让一个人物自动从地图的一点走到另一点。需要计算两点之间的最优路线,要实现这样的寻路算法。最常规和最简单的方法,使用A算法。本篇总结不...

小木头的冬天 ⋅ 2016/07/27 ⋅ 0

javascript的游戏自动寻路算法(一)

如今一些人更喜欢玩一些网页HTML5游戏,必不可少的会应用到自动寻路升级打怪的算法... 本系列会从零开始解析一个AStar自动寻路算法: 首先看一下一个可视化demo 这个由google大神完成的可视化...

颜卿今天Coding了吗 ⋅ 2016/06/24 ⋅ 0

C#开发WPF/Silverlight动画及游戏系列教程(Game Tutorial):(三十九)向Silverlight移植①

深蓝Silverlight-MMORPG游戏引擎单机部分即将开源;这两节里,我将为大家讲解本教程示例游戏从WPF向Silverlight移植的一些关键性优化与性能提升技巧,以及新增加的内容等等。接下来的时间里,...

晨曦之光 ⋅ 2012/03/09 ⋅ 0

Unity3D架构设计NavMesh寻路(未完待续)

国庆闲来没事把NavMesh巩固一下。以Unity3D引擎为例写一个底层c# NavMesh寻路。由于Unity3D中本身自带的NavMesh寻路不能非常好的融入到游戏项目其中,所以重写一个NavMesh寻路是个必经之路。...

技术mix呢 ⋅ 2017/12/06 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Spring | IOC AOP 注解 简单使用

写在前面的话 很久没更新笔记了,有人会抱怨:小冯啊,你是不是在偷懒啊,没有学习了。老哥,真的冤枉:我觉得我自己很菜,还在努力学习呢,正在学习Vue.js做管理系统呢。即便这样,我还是不...

Wenyi_Feng ⋅ 今天 ⋅ 0

博客迁移到 https://www.jianshu.com/u/aa501451a235

博客迁移到 https://www.jianshu.com/u/aa501451a235 本博客不再更新

为为02 ⋅ 今天 ⋅ 0

win10怎么彻底关闭自动更新

win10自带的更新每天都很多,每一次下载都要占用大量网络,而且安装要等得时间也蛮久的。 工具/原料 Win10 方法/步骤 单击左下角开始菜单点击设置图标进入设置界面 在设置窗口中输入“服务”...

阿K1225 ⋅ 今天 ⋅ 0

Elasticsearch 6.3.0 SQL功能使用案例分享

The best elasticsearch highlevel java rest api-----bboss Elasticsearch 6.3.0 官方新推出的SQL检索插件非常不错,本文一个实际案例来介绍其使用方法。 1.代码中的sql检索 @Testpu...

bboss ⋅ 今天 ⋅ 0

informix数据库在linux中的安装以及用java/c/c++访问

一、安装前准备 安装JDK(略) 到IBM官网上下载informix软件:iif.12.10.FC9DE.linux-x86_64.tar放在某个大家都可以访问的目录比如:/mypkg,并解压到该目录下。 我也放到了百度云和天翼云上...

wangxuwei ⋅ 今天 ⋅ 0

PHP语言系统ZBLOG或许无法重现月光博客的闪耀历史[图]

最近在写博客,希望通过自己努力打造一个优秀的教育类主题博客,名动江湖,但是问题来了,现在写博客还有前途吗?面对强大的自媒体站点围剿,还有信心和可能型吗? 至于程序部分,我选择了P...

原创小博客 ⋅ 今天 ⋅ 0

IntelliJ IDEA 2018.1新特性

工欲善其事必先利其器,如果有一款IDE可以让你更高效地专注于开发以及源码阅读,为什么不试一试? 本文转载自:netty技术内幕 3月27日,jetbrains正式发布期待已久的IntelliJ IDEA 2018.1,再...

Romane ⋅ 今天 ⋅ 0

浅谈设计模式之工厂模式

工厂模式(Factory Pattern)是 Java 中最常用的设计模式之一。这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式。 在工厂模式中,我们在创建对象时不会对客户端暴露创建逻...

佛系程序猿灬 ⋅ 今天 ⋅ 0

Dockerfile基础命令总结

FROM 指定使用的基础base image FROM scratch # 制作base image ,不使用任何基础imageFROM centos # 使用base imageFROM ubuntu:14.04 尽量使用官方的base image,为了安全 LABEL 描述作...

ExtreU ⋅ 昨天 ⋅ 0

存储,对比私有云和公有云的不同

导读 说起公共存储,很难不与后网络公司时代的选择性外包联系起来,但尽管如此,它还是具备着简单和固有的可用性。公共存储的名字听起来也缺乏专有性,很像是把东西直接堆放在那里而不会得到...

问题终结者 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部