Project1»广场 › 技术讨论 › 综合技术讨论区 › RPG Maker 技术区 › RGSS3下A星寻路的解说与实现

RGSS3下A星寻路的解说与实现

查看数: 8846 | 评论数: 12 | 收藏 17

关灯 | 提示：支持键盘翻页<-左右->

帖子模式

余烬之中

发布时间: 2014-8-14 18:30

正文摘要:

本帖最后由余烬之中于 2014-9-14 16:19 编辑写在前面 RM中，事件的移动模式有三种：随机、接近、自定义（事实上这是前几天我帮忙翻译F1的时候才注意到的），其中的接近常用于各种各样的追逐战……但是事件的 ...

喵呜喵5 发表于 2015-9-4 20:31:28

本帖最后由喵呜喵5 于 2015-9-4 22:46 编辑

时隔许久过来说一个BUG

RGSS3中图块有一个叫通行方向的混帐玩意儿，这个通行方向呢……无比操蛋的居然能够把某个行走图设置成从某个方向走过去时不可通行

于是，类似下面这样的情况下，目前代码中从终点逆向回到起点的寻路方式就吃瘪了

=================

仔细想想好像也不对，因为自己写的A*脚本没有遇到这个问题能够正常寻路，但是你的脚本却不行……让我想想到底是哪里不对…………

=================

虽然说不清楚，但是感觉差不多明白你的脚本寻路算法为什么用问题了，我这边是直接用要寻路的事件本身的检查能否通行方法进行判断的，这个方法里面会自动检查某个特定图块的某方向是否都能够双向正常通行来保证不会钻进封闭的图块中，而你定义的检查通行的方法只检查了其中一个方向，因此出错了，附带一张测试图片：

地图上那个梯子图块是个下方向无法通行的图块
你的A*

我的A*

评分

参与人数 1	星屑 +166	收起理由
余烬之中	+ 166	我很赞同

查看全部评分

国产吃货 发表于 2014-11-27 11:58:18

感谢大大分享，正在寻找这方面的资源。
没想到余烬大大直接拿出成品来分享了。
省了不少劲。

myownroc 发表于 2014-8-25 15:02:00

本帖最后由 myownroc 于 2014-8-25 15:24 编辑

给深度优先加了个启发判断，总觉得少了什么……

点评

myownroc

绕路实在不能看！发表于 2014-8-25 15:26

Sion 发表于 2014-8-15 20:58:08

不错，研究得挺仔细的样子。

myownroc 发表于 2014-8-14 23:07:16

话说我VB里A*比广度优先还慢？还是我没做好……

点评

晴兰

取最小的时候可能拖慢速度，一般是用堆来取最小，排序或者遍历都慢了发表于 2014-12-2 11:07

余烬之中

那我就不知道了…… 发表于 2014-8-15 11:43

myownroc

估值函数没变…… 发表于 2014-8-15 11:14

余烬之中

不会吧……也许是上面的估值函数的问题？发表于 2014-8-15 11:14

无脑之人 发表于 2014-8-14 21:16:27

啊看起来好厉害【
刚和兰触学了SPFA，我感觉我现在什么都不会写了【噗
不过以前看过一篇关于A*的文章，估值函数可以仅仅选择曼哈顿距离，但也可以通过一些相对复杂的处理来实现一些复杂的东西，比如避免多个对象都走一条路（次优解），以及更加复杂的消耗（我觉得对不同类别的消耗统一比较本身就是一种估值了），反正这些东西我都不会【大雾
祝你们翻译文档做的更好咯☆

评分

参与人数 1	星屑 +100	收起理由
余烬之中	+ 100	我很赞同

查看全部评分

菜鸟飞呀飞 发表于 2014-8-14 20:44:10: 提示: 作者被禁止或删除内容自动屏蔽

myownroc 发表于 2014-8-14 20:31:10

唯一看得懂的A*……
A*应该是加了一定筛选的广度优先（个人感觉），然后效率因此提高很多。
不过广度优先搜索的一定是最短路径，但是效率相对较低。
另外，估值函数那么处理一直感觉欠妥当（但又找不到更方便的了）。
最后问一下：例如战棋中移动到某个节点就要消耗一定体力（体力有上限），这样估值函数是不是会变得复杂许多？