Project1

标题: RGSS3下A星寻路的解说与实现 [打印本页]

作者: 余烬之中 时间: 2014-8-14 18:30
标题: RGSS3下A星寻路的解说与实现
本帖最后由余烬之中于 2014-9-14 16:19 编辑

写在前面

A星寻路算法

在RGSS3的实现

更好地应用到游戏

成品

结语

作者: taroxd 时间: 2014-8-14 18:33
本帖最后由 taroxd 于 2014-8-14 18:48 编辑

你知道我怎么更新github脚本的吧……不知道的话就看一下“输出脚本.rb"

于是非原创的脚本就被加进来了（事实上这也是github作为脚本仓库的一个目的：备份）

这种非原创的东西我不会塞到群组里就是了= =

原帖在此：https://rpg.blue/thread-228259-1-1.html

判断通行度别用 $game_map.passable? 用 CharacterBase#passable?

作者: 蓝儿 时间: 2014-8-14 18:55
触哭了。。太长不看【误
本殿下是事件党但是还是大致的看了一下。
窝也研究过这些东西【捂脸
一对比窝就弱爆了啊qwq
刚把爹！

作者: 喵呜喵5 时间: 2014-8-14 19:47
~~最终的脚本呢~~

~~太长不看~~

~~要糖的姿势太明显~~

~~删除线好评啦~~

作者: kuerlulu 时间: 2014-8-14 20:08
~~为什么要叫上我我只是什么都不懂的渣渣~~

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

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

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

作者: myownroc 时间: 2014-8-14 23:07
话说我VB里A*比广度优先还慢？还是我没做好……

作者: Sion 时间: 2014-8-15 20:58
不错，研究得挺仔细的样子。

作者: myownroc 时间: 2014-8-25 15:02
本帖最后由 myownroc 于 2014-8-25 15:24 编辑

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

作者: 国产吃货 时间: 2014-11-27 11:58
感谢大大分享，正在寻找这方面的资源。
没想到余烬大大直接拿出成品来分享了。
省了不少劲。

作者: 喵呜喵5 时间: 2015-9-4 20:31
本帖最后由喵呜喵5 于 2015-9-4 22:46 编辑

时隔许久过来说一个BUG

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

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

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

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

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

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

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

我的A*

欢迎光临 Project1 (https://rpg.blue/)