Project1

标题: SRPG 格子的算法 [打印本页]

作者: 枫の叶 时间: 2015-12-9 21:50
标题: SRPG 格子的算法
本帖最后由枫の叶于 2015-12-10 16:12 编辑

最近在弄一个SRPG游戏脚本，角色移动需要在地图上绘出移动范围的格子。

已知角色坐标 x, y ，角色最大移动距离 6 格。
求计算出在这个距离内，角色能移动到的所有坐标，并剔除角色本身坐标和地图不通行的坐标，以及角色不能到达的坐标。
本来自己弄了一个，觉得有点臃肿，求更精简的算法。

作者: RyanBern 时间: 2015-12-9 23:39
本帖最后由 RyanBern 于 2015-12-10 00:13 编辑

首先我要问一下「角色不能到达的坐标」的含义，按照我的理解，你所给出的图最上方那个位置虽然可以通行，但是角色只能绕过限制的区域然后到达，这个位置就是所谓不可到达的地方。或者，角色上方有一条很细的墙，长度超过了13，那么墙上方的位置应该视为不可到达。
如果我的理解正确，那么建议你使用bfs方法，具体请在技术区搜索我的帖子「dijkstra算法在地图上的应用」（名字可能不准确，但是前面dijkstra算法这几个字应该有），那里面有详细的算法说明。值得注意的是，由于楼主只需要搜索的部分，所以算法中有关寻路的地方都可以去掉，换句话说，这种情况只需要进行bfs6层即可。具体细节如果不太清楚，等我电脑修好之后再详细回答。

作者: myownroc 时间: 2016-1-16 22:04
帖子有讨论价值于是挖个坟（如有讨论请点评）

寻路/移动范围的算法通常可以参考图的广度优先（百度搜索“广度优先”的结果适用于更一般的图，初学者看起来比较吃力）。
具体思路就是不断搜索待搜索节点周围的节点直至满足约束条件搜索结束。

首先要有一个列表openlist，用来储存待搜索的节点。
当然还要有closelist列表，储存已搜索的节点。
最初，这两个表都是空的。

一开始，往openlist里塞进起点。
以下是核心
从openlist里拎出一个节点设为当前节点，
寻找周围尚未搜索（即closelist均无的节点）并可以到达的节点。
如果周围的点存在于openlist，则要判断如果从当前节点到达该点是否更省力，如果是则修改该点的消耗。
将找到的点塞进openlist，并记录各个点的消耗。
当openlist为空时，中断循环；否则，以上循环。
核心结束

来张图助助兴……

注释：
图1：紫色为起点，执行第一次循环后的结果。红色表示openlist的点，绿色钩表示closelist已经存在该点；
图2：新的一轮循环。3号图块由于已经存在于closelist，故未添加至openlist；
图3：若干次循环后；
图4：由于灰色块不可到达，故也没有添加至openlist。

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