文档章节

AStar寻路1-实现基本功能

梦想游戏人
 梦想游戏人
发布于 2017/06/08 20:02
字数 470
阅读 39
收藏 0
点赞 0
评论 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-性能优化

© 著作权归作者所有

共有 人打赏支持
梦想游戏人
粉丝 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

Hont/AStar3DSpacePathfinding

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

Hont ⋅ 2016/08/11 ⋅ 0

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

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

anrainie ⋅ 2014/06/12 ⋅ 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

Silverlight MMORPG网页游戏开发课程[一期] 第七课:场景之地形与寻径

引言 在上一课实现场景遮挡效果的基础上如能融合相应的地形系统,那么整个场景才能算做是个有机整体。传统的2D-RPG游戏场景按视角划分可分为横向、纵向与斜向的,本节我将分别向大家介绍如何...

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

数百个 HTML5 例子学习 HT 图形组件 – WebGL 3D 篇

《数百个 HTML5 例子学习 HT 图形组件 – 拓扑图篇》一文让读者了解了 HT 的 2D 拓扑图组件使用,本文将对 HT 的 3D 功能做个综合性的介绍,以便初学者可快速上手使用 HT 构建例如电信网管 ...

xhload3d ⋅ 2016/08/26 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

JavaScript零基础入门——(八)JavaScript的数组

JavaScript零基础入门——(八)JavaScript的数组 欢迎大家回到我们的JavaScript零基础入门,上一节课我们讲了有关JavaScript正则表达式的相关知识点,便于大家更好的对字符串进行处理。这一...

JandenMa ⋅ 今天 ⋅ 0

sbt网络问题解决方案

转自:http://dblab.xmu.edu.cn/blog/maven-network-problem/ cd ~/.sbt/launchers/0.13.9unzip -q ./sbt-launch.jar 修改 vi sbt/sbt.boot.properties 增加一个oschina库地址: [reposit......

狐狸老侠 ⋅ 今天 ⋅ 0

大数据,必须掌握的10项顶级安全技术

我们看到越来越多的数据泄漏事故、勒索软件和其他类型的网络攻击,这使得安全成为一个热门话题。 去年,企业IT面临的威胁仍然处于非常高的水平,每天都会看到媒体报道大量数据泄漏事故和攻击...

p柯西 ⋅ 今天 ⋅ 0

Linux下安装配置Hadoop2.7.6

前提 安装jdk 下载 wget http://mirrors.hust.edu.cn/apache/hadoop/common/hadoop-2.7.6/hadoop-2.7.6.tar.gz 解压 配置 vim /etc/profile # 配置java环境变量 export JAVA_HOME=/opt/jdk1......

晨猫 ⋅ 今天 ⋅ 0

crontab工具介绍

crontab crontab 是一个用于设置周期性被执行的任务工具。 周期性执行的任务列表称为Cron Table crontab(选项)(参数) -e:编辑该用户的计时器设置; -l:列出该用户的计时器设置; -r:删除该...

Linux学习笔记 ⋅ 今天 ⋅ 0

深入Java多线程——Java内存模型深入(2)

5. final域的内存语义 5.1 final域的重排序规则 1.对于final域,编译器和处理器要遵守两个重排序规则: (1)在构造函数内对一个final域的写入,与随后把这个被构造对象的引用赋值给一个引用...

江左煤郎 ⋅ 今天 ⋅ 0

面试-正向代理和反向代理

面试-正向代理和反向代理 Nginx 是一个高性能的反向代理服务器,但同时也支持正向代理方式的配置。

秋日芒草 ⋅ 今天 ⋅ 0

Spring 依赖注入(DI)

1、Setter方法注入: 通过设置方法注入依赖。这种方法既简单又常用。 类中定义set()方法: public class HelloWorldOutput{ HelloWorld helloWorld; public void setHelloWorld...

霍淇滨 ⋅ 昨天 ⋅ 0

马氏距离与欧氏距离

马氏距离 马氏距离也可以定义为两个服从同一分布并且其协方差矩阵为Σ的随机变量之间的差异程度。 如果协方差矩阵为单位矩阵,那么马氏距离就简化为欧氏距离,如果协方差矩阵为对角阵,则其也...

漫步当下 ⋅ 昨天 ⋅ 0

聊聊spring cloud的RequestRateLimiterGatewayFilter

序 本文主要研究一下spring cloud的RequestRateLimiterGatewayFilter GatewayAutoConfiguration @Configuration@ConditionalOnProperty(name = "spring.cloud.gateway.enabled", matchIfMi......

go4it ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部