文档章节

AStar寻路1-实现基本功能

梦想游戏人
 梦想游戏人
发布于 2017/06/08 20:02
字数 470
阅读 46
收藏 0

A星算法是一种启发式的搜索方法,通过一个路径评估函数,来动态确定最佳路径。这点和广度搜索不同。

基本思想是有2个列表,open和close,

open列表里面的节点表示待搜索周围点的节点,close列表里面记录着不需要搜索的节点。

启发式函数f=g+h;

f表示该路径的代价,g表示起点到搜索的点的该条路径的实际值,h表示该搜索的点到终点的估计值。h的估计值越接近当前点到终点的最短路径的实际值那么A星搜索出来的路径就越接近实际的最短路径,从这点来看A星是时间和精度的一个权衡改进的广度搜索算法。h值始终为0的话,那退化为广度搜索了(没有了估值,f的计算都是实际值,因此变为了暴力的广度搜索)。

进过以下测试,大约牺牲了10%的精度换来了10倍的速度。

上图为h值为0,退化为广度搜索。

上图为曼哈顿估值法(即横向和纵向距离之和),

上图为距离估值法。

上图为随机化地图遮挡的结果,

每次搜索都从open表中找出代价最小的节点进行搜索,在搜索当前点时,如果周围点已经存在于open列表中,那么就要重新计算f和g值,表示进过当前点到达 周围点会不会更近,重新计算后open列表将会重新排序,下个轮回再次从f值最小的开始广度搜索。

下篇主要是优化性能    AStar寻路2-性能优化

© 著作权归作者所有

共有 人打赏支持
梦想游戏人
粉丝 36
博文 433
码字总数 123540
作品 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
Android SELinux avc dennied权限问题解决方法

概述 SELinux是Google从android 5.0开始,强制引入的一套非常严格的权限管理机制,主要用于增强系统的安全性。 然而,在开发中,我们经常会遇到由于SELinux造成的各种权限不足,即使拥有“万...

TreasureWe
11/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

GIT 常用命令

Git图形化界面我用的还可以,但是命令就不太会了,索性和大家一起学习下Git命令的用法... 一般来说,日常使用只要记住下图6个命令,就可以了。但是熟练使用,恐怕要记住60~100个命令。 下面...

神勇小白鼠
22分钟前
2
0
可编程着色器---OpenGL渲染流水线

固定功能流水线 改变流水线结构 顶点着色器 片元着色器 几何着色器 曲面细分着色器

中国龙-扬科
24分钟前
1
0
qs.parse()、qs.stringify()、JSON.parse()、JSON.stringify()使用方法

qs.parse()、qs.stringify()、JSON.parse()、JSON.stringify()使用方法 1 qs.parse() 将url中的参数字符串转换成json对象。 var qs = require('qs');var url = 'method=query_sql_dataset_......

neumeng
37分钟前
3
0
需要注意的new Date 时区问题

(1)、Date中保存的是什么 Date对象里存的只是一个long型的变量,其值为自1970年1月1日0点至Date对象所记录时刻经过的毫秒数。调用Date对象getTime()方法就可以返回这个毫秒数。 (2)、时区...

为了美好的明天
43分钟前
1
0
java cache

##基本原理 ###核心内容 java cache API的5个核心接口:CachingProvider,CachingManager,Cache,Entry,ExpiryPolicy CachingProvider: 缓存提供者定义建立,配置,获得,管理,控制一个或者多...

zzx10
43分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部