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

myownroc

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

点击展开／收起

1. 伪代码
   
2. 
   
3. 获得起始点、终止点；
   
4. 
   
5. 设置一个空数组checked，用于存放已经检测过的节点；
   
6. 
   
7. 当终止点位于地图外 或 终止点从任何一个方向都不能到达时，返回空；
   
8. 否则，继续；
   
9. 
   
10. 设置当前节点为起始点；
    
11. 
    
12. 循环：
    
13.   将当前节点放入checked；
    
14.   如果当前节点是终止点，返回真；
    
15.   如果当前节点周围（四方向）不存在一个未检测过（checked中不存在）、并且可以到达的节点，则
    
16.     如果当前节点是起始点，则
    
17.       返回空；
    
18.     否则
    
19.       回溯到当前节点的父节点；
    
20.       跳过本次循环；
    
21.     结束判断；
    
22.   否则
    
23.     获取当前节点的子节点；
    
24.     计算各个子节点的F值；
    
25.     如果存在一个未检测的子节点，则
    
26.       选择F值最小、且未检测过的子节点：
    
27.         设置该点的父节点为当前节点；
    
28.         设置该点为当前节点；
    
29.       结束选择；
    
30.     否则
    
31.       设置当前节点为当前节点的父节点；
    
32.       跳过本次循环；
    
33.     结束判断；
    
34.   结束判断；
    
35. 回到循环；

复制代码

国产吃货

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

喵呜喵5

时隔许久过来说一个BUG

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

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




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

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

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

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

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

我的A*