基于宽度优先搜索的最短路径接寻路

唐门草楹 · 发表于 2013-2-26 23:40:38

您需要登录才可以下载或查看，没有账号？注册会员

×

心血来潮花了一晚上的时间写了一个最短路径寻路搜索的脚本。具体功能参见附件
游戏中的四个NPC在游戏开始时生成到达主角所在位置(0,0)坐标的最短路径并生成移动路线。当到达(0,0)坐标后，如果此时主角的位置发生了变化，则会再次侦查到主角的新位置并生成新的一定路线靠近主角。

九夜神尊 · 发表于 2013-2-27 13:20:33

我想：
你能不能这样改这个脚本。

在每次目标移动的时候，都会对应更改目标点。
当然如果每次都从新计算的话，效率很低。
所以，就是基于递推法的多次寻路。
因为主角每次移动都只有一格。

yangff · 发表于 2013-2-27 19:53:13

本帖最后由 yangff 于 2013-2-27 19:56 编辑

九夜神尊发表于 2013-2-27 13:20
我想：
你能不能这样改这个脚本。

预处理全图之间的最n^4短路，然后动态维护一个传递闭包……这是最好想的。至于有没简单的我就不了解了

gonglinyuan · 发表于 2013-2-27 21:09:31

真厉害，不会也是搞信息学竞赛的吧
用A*寻路会快很多哦，就是有点小复杂

[RMXP发布] 基于宽度优先搜索的最短路径接寻路