[FE战棋研究]移动范围算法及攻击范围算法讨论

艾薇

类似与火焰之纹章的战旗游戏,战斗时,当选择我方人物后,显示可移动范围(蓝)和可攻击范围(红)
说明一下我的移动算法吧：
首先要说明的是，本移动范围算法参考的是网上广为流传的寻路算法，有兴趣的人可以去网上搜一下。

本算法中有两个list和一个节点类：
movement_list：记录已经检查完确定为可移动格的节点的list
checkround_list：记录需要对周围四个继续探索的节点的list
节点类内有属性：
x：节点x坐标，
y：节点y坐标，
movement_cost：从起始位置到本节点的移动消耗，
计算方式是父节点的移动消耗+本次的移动消耗
       father_node：父节点，即探索该节点的节点
     
算法：
设起点位置为x0，y0. 移动能力为5步。本篇讨论的是4方向移动。一步的移动消耗为10.

1.取得起始坐标x0,y0，生成节点。如果移动能力不为0，那麽将起始节点放入checkround_list
2.取出checkround_list中的一个要检测的节点。因为checkround_list中的节点记录的是需要对周围四个继续探索的节点，也就是说它本身必然已经被判定为可移动的了。所以：
3.将要测的节点放入movement_list。
4.检测节点周围四格之前，我们先判断该节点的移动消耗是否已经到达它的移动能力极限（或十分接近以至于无法继续探索），也就是：判断节点的移动消耗movement_cost>（移动范围-1）。如果判断为真，跳过步骤5
5.检测节点（暂时可理解为父节点）周围四格（子节点）
          1）如果该节点不可通过（障碍物？敌人？）或已经是可移动格（父节点之类的）为真的话，跳过下面检测
          2）取得该节点所在位置的移动损耗（默认为10，但考虑到地形特性，比如沙漠，可设为20），
              如果 该地形移动损耗+父节点移动损耗>移动能力,那么，这一点已经是你到达不了的地方了，跳过下步吧
          3）通过以上验证，可判断其为可移动节点，放入checkround_list等待探索周围四格
6.如果checkround_list不为空，继续步骤2.否则，完成探索任务。movement_list内存入了所有可移动节点。

嗯，以上为移动范围算法求解

我已经得到可移动范围(一个包含可以动节点信息的list),想要求得可攻击范围.
可是,如果对每个可移动的位置,计算其可攻击范围的画……==，太耗时了
以最坏情况考虑：
某魔法骑士可移动范围为9（7原有移动力+2靴子），那她的最坏可移动格数为180格（9*18+18）
如果她碰巧拿着暴雷或者某暴强的加血道具（貌似攻击范围是魔力的一半），魔力又是顶（大概是25？），那么她的可攻击（可能是恢复血范围）将是：对每个格子而言，可攻击/恢复周围是312个格子(12*24+24)
那么计算她180格子每个格子的攻击格的次数加起来有：56160 ==|||||||||||||
还要判断这些格子有没有重复的，有没有和可移动格子冲突的，是不是已经是可攻击格子
……疯了…………
当然，以上为最坏估计

主要问题在这里：

问题A：56160个格子每个格子都要判断有没有和可移动格子冲突的，是不是已经是可攻击格子。

因为可移动格子放在了一个列表中，可攻击的格子也要放在一个列表中，那么：判断可移动格子是要遍历列表的……而且每次都要遍历表中全部可移动格子（本例是180个）。判断是否与已有可攻击范围格子重复也是要遍历列表的。最坏情况是遍历（312-180=122个）……这个是56160个格子每个格子每个格子都要做的检查……太囧了。绝对不能这样啊啊啊

已有解决方案：生成一个小的地图暂存器，呃，这个说法不知对不对撒
1.在计算可移动范围前初始化一个二维的数组map_table=Table.new(xsize, ysize)，它的一维和二维size是——(移动能力+攻击能力)*2+1=最大可攻击范围 ，其实还要考虑是否超出了你的地图范围，偶们为了简单pass。之所以选择table是因为它的取值方式粉遍历的：self[x, y] ，但注意它的只能存储数字啊
2.设其中心点为你的起始节点。值1为可移动节点，值2为可攻击节点。
当计算可移动格时，每次放入movement_list一个节点，记得在table的对应位置赋值为1.这样判断是否为可移动节点不用再遍历list了（泪~~太好啦）。而是直接取map_table[X1,Y1]的值，看它是否为1，判断是否为可攻击格时也是如此，直接取map_table[X1,Y1]的值，看它是否为2.
如果为nil，就是该点米被判断过。
本方案初步解决遍历list消耗的时间，而且table也比价容易维护撒

问题B：每次判断可攻击范围的格子还是要对每个可移动格判断其攻击范围

已有解决方案：在计算可移动范围时，检测每个节点的四周子节点时，如果该节点四周子节点均可通行，那么我们就不必要计算它的可攻击范围了。因为它的四周子节点的攻击范围包括了该节点的攻击范围。
当然，该理论只是对非弓箭手通用。因为弓箭手是攻击不到他的近身的一格（长弓的话是两个格）的。这导致四周子节点不能覆盖攻击父节点的攻击范围……其实这个也还好办啦。我们还是只对周围四个并非全部是可移动格的节点A计算其可攻击范围，如果不能攻击近身一格的话，请对节点A的父节点B再计算其可攻击范围。如果不能攻击近身两格的话，请对节点B的父节点C再计算其可攻击范围。明白？
酱就减少了对可移动节点的可攻击范围的求解量。最好的情况下是非弓箭手移动范围内无阻碍的情况。还是拿魔法骑士（可移动范围为9）为例，原来要判断180个格子，现在只需判断36个格子，已经比较省力了……

当然，这样还是有问题的。如果是大范围魔法的话，还是要判断很多的重复的可攻击格子的。呃……建议将攻击能力大于3 的判断为大范围魔法，单独计算可攻击范围（呃，还好大范围魔法米有近身几格不能攻击一说）。这个计算下场再说。
欢迎更好的算法意见。偶现在正在做类似火焰之纹章的战旗游戏。需要大家多多支持呀。

dbshy

- -bbbbb
难道55160,范围很大么？？？

另外没听懂。。。╮(╯_╰)╭

saterick

诚如楼主所说，非常要命的计算量，用RM做出来之后要是敌人中有个把拿着程光、远愈之类RP物的，估计会掉帧到让人不爽。
老实说，出于对FE的爱，想了至少10分钟如何在RM里计算射程……可惜，吾辈能力不济，没辙（跟没说似的-   -|||）。好像在用RM里真的很难实现所谓的优化算法……
个人建议……放弃远愈、程光、程暗什么的吧……
方式是“类火纹”，要不就稍微改进一下（偷懒一下-     -|||），这些远程魔法范围是全地图，命中每隔一个格子减5%，最小命中10%。角色魔力超过10的，每多一点就补正1％的命中，也对最小命中也生效。例如一个魔力20的角色，假定他拿着程光基础命中为70％，攻击5格外的敌人命中就是70－5×5+（20-10）＝55％，攻击20格开外的就是20×5-（20-10）-10＝80>70，取最小命中10+（20-10）＝20％。
这种判定方法应该和火纹系统的数学计算也不算很违和……

艾薇

To dbshy 君：请问你米看懂的原因是我描述的不清楚还是没玩过火焰？

To saterick 君：首先，非常感谢你后半部分的关于命中率的建议撒，老实说，我还米有想到那里……
                呃……可是我还不无法放弃对远程魔法的爱呀。最近一直在研究这个，已经可以优化
                部分了，具体等偶整理好思路，会发上来让大家点评的
To uvwx649 君：米看懂咩……

dbshy

真的，范围一点都不大，LZ你是已写完觉得效率低，还是纯理论觉得.....
与其一直纠结于此，还不如去想想更高效率的寻路，那才是要真正要关注的地方

艾薇

高效率的寻路?
第一:我用的移动距离求解不同于寻路
第二:我的寻路用的是网上普遍推荐的A*算法
第三:这个范围……真的会卡，不是我非要纠结……==

saterick

这个和寻路没关系吧……
其实一直觉得SRPG的核心问题是AI问题，怎样才能做出像berwick那种掉血知道往祭师那跑身边、看到路口知道拿罐头堵门的敌军AI？像机战、SD高达那种仗着人多一股脑的冲锋，实在是很难让人觉得有“策略感”。能够突出这种策略感，游戏就已经成功了。
楼主加油，参与有心无力，吾辈也就只能作为FE粉丝给楼主应援了……-   -|||

艾薇

这个和寻路没关系吧……
其实一直觉得SRPG的核心问题是AI问题，怎样才能做出像berwick那种掉血知道往祭师那跑身边、看到路口知道拿罐头堵门的敌军AI？像机战、SD高达那种仗着人多一股脑的冲锋，实在是很难让人觉得有 ...
saterick 发表于 2009-9-2 19:16

偶……太感动了……
偶努力呀~~~~~

dbshy

偶理解能力有问题，虽然详细了很多，还是看的一头雾水
等高手帮lz解决吧

另外偶觉得运算次数不过5w，数据量还是很小的，比如A star的估价函数没有选好，有时就变成BFS，这个运算次数就大大超过5w了  = =

九夜神尊

虽然我还写不出来什么寻路脚本，不过我试着提出一些新的方法
也许能给LZ带来灵感……

先废话一通……
如果需要记 555588888这样的号码，你会怎么记
相信每个人都会是4个5，5个8。
那如果是 1588689336这样的号码呢？
按之前的方法要记双倍的数
如果是算法是这样记
第1个数为 关键数  =  5
第5个数为 关键数   =  8
第12个数为 关键数  =  nil
先讲一下这样做的特点
如果要删除一个5，那么不需要删除的那个5之后的数全部往前移动
只需要将第 11(12-1) 位的数 改为nil
         将第  4(5-1)    位的数 改为 8
就完成了！
废话完毕！
大量的输入可能会遭受发帖失败的郁闷，下帖继续！