文档章节

关于寻路算法的一些思考(8):长期和短期目标

oschina_00
 oschina_00
发布于 2017/02/24 10:16
字数 1827
阅读 22
收藏 0

我已经集中讲过了从一个地方到另一个地方寻找路径的任务。然而,一个与之同等重要的问题是:一旦我有一个路径,我该怎样沿着它移动?最明显的答案是从一个位置到另一个的位置的直线移动。然而,你可能想在曲线上移动,或者多次的移动。你可能想把位置偏离成为低优先级的目标。一个更高层次的问题是:你要去哪里?除非你先回答的是高层次的问题,路径规划不是很有用。当然,目标设定的一个形式就是让用户点击目的地。不过,你可能已经自动执行了任务——探索,间谍活动,攻击和建设都是常见的方式。

单元移动

我已经集中讲解了在寻路问题,它减少了从一个位置移动到另一个位置中的问题,也减少了从一个空间到相邻空间的许多小问题。

你可以从一个位置到另一个位置的直线上移动,但有很多可选方案。考虑一下这幅图上的四个移动路径:

红色路径是标准方法:从一个正方形的中心移动到另一个正方形的中心移动。绿色路径比较好些:代替了在瓷砖的中心,而在瓷砖边沿之间的直线上移动。你也可以尝试在瓷砖的对角的连线上移动。蓝色的路径使用样条曲线,深蓝色的是低阶样条曲线,浅蓝色是高阶样条曲线(这需要花更长时间来计算)。

对角线和瓷砖边沿之间的连线是最短的解决方案。但是,曲线能使你的单元格看起来少了些机械化,多了些“活力”。这是一个低级的把戏,但不是最好的。

如果您的单位不能轻易转向,你可能在绘制运动路径时,要考虑到这一点。克雷格·雷诺兹有一个关于转向的网页,其中有一页是关于转向和用Java小程序来演示各种各样的行为。如果你有不止一个的单元沿着路径移动时,你可能还需要研究群集。克雷格建议,你应该将路径当做一个指导路线,它反应出了你偏离了条件要求,而不是作为你的单元必须要访问的位置清单。

如果你正在使用网格寻路,你的单位是不受约束的网格,这和移动成本是一致的, 当两点没有障碍物的时候,你可能希望把路径伸直,然后在两点之间的直线上运动就可以遥遥领先。如果你使用的导航网格,去看看漏斗算法。

行为标志或堆栈

你的单位也许有一个以上的目标。例如,你可能有一个像“间谍活动”的总体目标,但也可能是一个更直接的目标,像“去敌人司令部”。此外,还有可能是暂时的目标,如“避开巡逻卫士”。下面是一些目标的说明:

  • 停止:留在当前位置

  • 停留:停留在一个区域

  • 逃跑:移动到安全区域

  • 撤退:移动到安全区域,同时击退敌方单位

  • 探索:查找并了解了这一点信息是已知的领域

  • 游荡:漫无目的的四处移动

  • 搜索:寻找一个特定的对象

  • 间谍:靠近一个对象或单位来更多地了解它,而不被发现

  • 巡逻:反复走过某个区域,以确保没有敌方单位通过它

  • 保卫:停留在一些对象或单位附近,使敌方单位离开

  • 警卫:入口附近保持在一定区域,以保持敌军单位出

  • 攻击:移动到一些对象或单位,以捕获或消灭它

  • 环绕:与其他单位一起,尽量包围一个敌方单位或对象

  • 回避:从某些对象或单元移开 避免:与任何其他单位烤翅距离

  • 跟随:保持近一些单位,因为它到处移动

  • 群组:寻求和形成群组单位

  • 工作:执行一些任务,如采矿,耕种,或搜集

对于每一个单位,你可以用一个标志来表明该行为是执行。用多个层次来保持一个行为堆栈。该堆栈的顶部是最直接的目标,堆栈的底部将是总体目标。当你需要做一些新的东西,但后来想回去你过去正在做的东西,那就压入栈中一个新的行为。如果你需要做一些新的东西,但不想再回到老的行为,那就清除栈。一旦你的完成了某些目标,把它从栈中弹出,并开始执行堆栈中的下一个行为。

等待移动

运动算法会碰上那些曾被认为不会出现在寻路过程中的障碍,这是不可避免的。一个容易实施的技术是基于其他障碍物会首先移动的假设。当障碍物是一个友好的单位时,这是特别有用的。当一个障碍挡住了去路,并且它只是等待一段时间后才移动。如果那段时间之后它还是没有移动,就要重新计算它周围或到目的地的路径。如果提前检测障碍物,你的单位只需简单地走慢一点来给其他单位更多时间离开挡你的道路。

两个单元会互相碰撞,并且每个将等待另一个继续行进,这种情况是非常有可能的。在这种情况下,优先级方案可以派上用场:分配给每个单元一个唯一的编号,然后使编号较低的单元等待更高编号的单元。如果两者都在等待,这将迫使其中一个单元继续前行。当提前检测到障碍物,编号较低的单元应该到达碰撞的预期点之前减速。

协调移动

当单位试图要穿越一条狭窄的通道时,上面所描述的技术将不起作用。如果一个单位静止不动,而其他单位试图绕过去,通道不能同时使用这两个单位。一个单位将阻塞住它,而另一个将花费一段漫长的道路。

第二个单元与第一个单元进行通信,并要求其退回来,这种情况应该是可能的。一旦通道畅通无阻,第二单元就可以穿过,然后第一单元就可以通过。这可能是复杂的实现,除非你能事先能确定这些通道。对于随机生成的地图,通道在哪里和在多远的地方第一个单位需要退回来,这将是非常难以确定的。

 

英文:theory.stanford.edu

译文:伯乐在线 - 唯一小时

链接:http://blog.jobbole.com/83458/

本文转载自:http://blog.jobbole.com/83458/

oschina_00
粉丝 5
博文 101
码字总数 0
作品 0
廊坊
私信 提问
游戏开发与程序设计知识总结05——游戏前端开发

更新日志 每此对思维导图有改动或者在github中有了对应的实现,则增加一条更新日志。 前言 这是游戏开发与程序设计知识总结系列文章的第五篇游戏前端开发。本系列文章的初衷源于我正在找工作...

kashiwa
2017/09/07
0
0
开发成功手机应用所需的8大技巧

原文连接:http://www.eoeandroid.com/industry/2012/0502/1503.html 虽然很少人认为手机应用开发是最热门的设计领域之一,但是眼看着这里如此强势的竞争局面,你更需要抱以正确的心态与现实的...

DannyZhou
2012/05/06
71
0
黑色星期四,今天全世界都在陪你亏,在亏损这条路上你并不孤独!

大家好!我是hyrik老师,微信:hyrik2020,今天直接来和大家谈谈就目前这个黑色的星期四! 今天的金融市场让一觉醒来的很多人在恐慌中重新思考人生! 今天是悲伤的一天,是愤怒的一天,是惨无...

Hyrik
2018/10/11
0
0
未经检视的人生不值得活

最近,公司 HR 部门在组织大家制定个人的 IDP —— Individual Development Plan,也就是个人发展计划。其实早在年初我就已经写好了自己一年的计划,但那只包括个人学习成长的部分,而公司安...

mindwind
2017/04/09
0
0
三分钟了解山寨币之普维币(PIVX)

大家好!我是hyrik老师(hyrik2020),七年虚拟货币玩家,大牛谈不上,但是也带着一千来号学生做了几年投资了,没错过比特币,没错过以太坊,没错过山寨币,没错过艾希欧,回报在1000倍左右了...

Hyrik
2018/09/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

JavaScript设计模式——适配器模式

  适配器模式是设计模式行为型模式中的一种模式;   定义:   适配器用来解决两个已有接口之间不匹配的问题,它并不需要考虑接口是如何实现,也不用考虑将来该如何修改;适配器不需要修...

有梦想的咸鱼前端
32分钟前
3
0
Andorid SQLite数据库开发基础教程(1)

Andorid SQLite数据库开发基础教程(1) Android数据库访问方式 SQLite是Android系统默认支持的文件数据库。该数据库支持SQL语言,适合开发人员上手。本教程将讲解如何开发使用SQLite的Andro...

大学霸
35分钟前
3
0
Handler简解

Handler 这里简化一下代码 以便理解 Handler不一定要在主线程建 但如Handler handler = new Handler(); 会使用当前的Looper的, 由于要更新UI 所以最好在主线程 new Handler() { mLooper = Lo...

shzwork
57分钟前
4
0
h5获取摄像头拍照功能

完整代码展示: <!DOCTYPE html> <head> <title>HTML5 GetUserMedia Demo</title> <meta charset="utf-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum......

诗书易经
今天
3
0
正向代理和反向代理

文章来源 运维公会:正向代理和反向代理 1、正向代理 (1)服务对象不同 正向代理服务器的服务对象是客户端,可以将客户端和代理服务器看作一个整体。 (2)配置方法不同 需要在客户端配置代...

运维团
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部