Project1

标题: [FE战棋研究]移动范围算法及攻击范围算法讨论 [打印本页]

作者: 艾薇 时间: 2009-9-1 16:58
标题: [FE战棋研究]移动范围算法及攻击范围算法讨论
本帖最后由艾薇于 2009-9-7 18:33 编辑

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

本算法中有两个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 时间: 2009-9-1 18:00
- -bbbbb
难道55160,范围很大么？？？

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

作者: saterick 时间: 2009-9-1 21:58
本帖最后由 saterick 于 2009-9-2 08:54 编辑

诚如楼主所说，非常要命的计算量，用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％。
这种判定方法应该和火纹系统的数学计算也不算很违和……

作者: 艾薇 时间: 2009-9-2 11:08
To dbshy 君：请问你米看懂的原因是我描述的不清楚还是没玩过火焰？

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

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

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

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

作者: 艾薇 时间: 2009-9-2 19:20

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

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

作者: dbshy 时间: 2009-9-2 20:12
偶理解能力有问题，虽然详细了很多，还是看的一头雾水

等高手帮lz解决吧

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

作者: 九夜神尊 时间: 2009-9-3 08:03
虽然我还写不出来什么寻路脚本，不过我试着提出一些新的方法
也许能给LZ带来灵感……

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

作者: 九夜神尊 时间: 2009-9-3 08:25
之前讲到的我要表述的意思是，对于简单的大量重复的东西
并不需要每一个都要去记录，去计算。想只需要记录下来关键的地方！

以下是我对范围思路的一些想法
这里我考虑的是运动消耗完全相同的地形。
可能会用到的词
关键点：用于记录一些关键信息的点，这个点可以以列表方式记录。
关键点属性：每一个关键点都可能会有上下左右属性，当然可以用一个数字代表拥有不同的属性。
因为组合就那么几个。
发一个图看看什么是关键点
[attach]6054[/attach]
这图里面深蓝色的就是关键点，这些关键点都有向外3个方向的属性

我向外扩充2步之后的关键点，

要补充的是扩充的时候可以扩充到障碍物上。每一次扩充的时候，都是检测能不能由前一个点
移动过来。如果不能由前一个点扩充过来那么按照一定的方法生成关键点（郁闷发不了图了）

作者: 九夜神尊 时间: 2009-9-3 08:50
没有图讲个毛，论坛发图难啊！
我的大致思路，相信每个人如果是用手画范围
都是从中间扩充出去而每次都首先只看最外围的一圈的。
然后在去算这一圈向外扩充一下什么样子！
我的方法大概就是用几个关键点，把整个外围的形状记录下来
每一次扩充都会描绘一个新的外围形状，而每一次扩充都是只算外围那一圈
的点。
如果是很平的地面，那么范围一开始是一个菱形(这个菱形我们只记录它上下左右4个点的位置就可以了)
然后这个菱形一次次扩大，当遇到障碍物的时候可能会改变菱形的形状，我们再添加几个点用来记录新的形状，当然添加这点的方法可以很轻松的就得到了。
好了扩充到最后完成了，就是你要的范围。这时候的范围只是几个点描述的外围形状。
接下来要解决的就是怎么样通过一个数组（外围形状）
来确认里面的点是否是可移动（攻击）呢？

作者: 九夜神尊 时间: 2009-9-3 09:24
接下来是要为可以移动的点填色了吧！
这时候就用到一开始的废话了。
先利用已得到的关键点，描绘出来外围形状，这样的外围形状是一个布尔二维数组
然后用到我一开始讲的号码的返回方式导出一个可以移动的范围。

作者: 艾薇 时间: 2009-9-3 11:08
TO dbshy君：嗯，说计算数量多也不多，其实就是想知道有米有更好的算法。本帖是偶对好算法的执念啊。

To 九夜神尊君 :十分感谢你的建议,研究ing.不过米图好难理解……研究研究~~~

作者: 九夜神尊 时间: 2009-9-3 14:23
可以直接跟我讨论，
这个论坛现在囧的发不了图，有图太好说了！

作者: Flyingpww 时间: 2009-9-3 16:50
移动算法就是菱形算法,至于远程武器..可以用无障碍算法还是蛮快的.一般20格菱形范围内可以了!

作者: 艾薇 时间: 2009-9-3 17:39
远程武器用无障碍算法？虾米意思呀？

作者: Flyingpww 时间: 2009-9-3 19:28
具体说也说不清楚! 就是跟飞行系算法类似!只不过范围大而已!
我写过好几个这样的脚本!呵呵

作者: 艾薇 时间: 2009-9-4 09:28
听这样子??飞行系算法要单写吗？

作者: saterick 时间: 2009-9-4 12:36
雷子和夏娜做过一个RM版FE，可以参考下那个的系统，好像一些复刻程度颇高。

作者: 艾薇 时间: 2009-9-6 13:43

雷子和夏娜做过一个RM版FE，可以参考下那个的系统，好像一些复刻程度颇高。
saterick 发表于 2009-9-4 12:36

嗯嗯，偶知道撒。但是不是完全版是吧。而且那个米有在移动时计算攻击哦。我会作为一个后辈虚心钻研前辈的成果滴，嘿嘿。目标是做出属于自己的FE游戏哦~~~

作者: IamI 时间: 2009-9-6 13:47
本帖最后由 IamI 于 2009-9-6 13:56 编辑

好长的帖子……留个名字先看一会儿改> <
囧，就不能按到那一格然后计算1格的攻击范围咩

作者: ONEWateR 时间: 2009-9-6 14:51

雷子和夏娜做过一个RM版FE，可以参考下那个的系统，好像一些复刻程度颇高。
saterick 发表于 2009-9-4 12:36

那个是加密的~
站上有两个RM版的火纹~ 国外有一个~
雷子的那个属于半成品，曾经很不厚道解密看里面的内容~ 感觉设置方面颇有些麻烦~
后者那个咱也忘了是虾米名了仿真度较高~ 也属半成品~
国外的那个仿真度最高，系统基本完成~ 但也还是属于半成品~
且国外的那个的图块貌似是16*16~
以上纯属吐槽~

作者: 艾薇 时间: 2009-9-6 22:52
本帖最后由艾薇于 2009-9-6 23:05 编辑

好长的帖子……留个名字先看一会儿改> <
囧，就不能按到那一格然后计算1格的攻击范围咩

那个是最坏的选择了。处于对FE的爱，偶不能舍弃梦想啊啊啊啊啊

那个是加密的~
站上有两个RM版的火纹~ 国外有一个~
雷子的那个属于半成品，曾经很不厚道解密看里面的内容~ 感觉设置方面颇有些麻烦~
后者那个咱也忘了是虾米名了仿真度较高~ 也属半成品~
国外的那个仿真度最高，系统基本完成~ 但也还是属于半成品~
且国外的那个的图块貌似是16*16~
以上纯属吐槽~

雷子的那个是加密的？？我下的解密呀，难道不是雷子的吗？？？

不知道耶？分不太清楚啊。
话说国外的那个米见过呢~~偶去找找看吧
PS：其实是偶内心最想说的话：加密的游戏咋解密呀~~~

偶闷想知道耶~~（如此无良滴问话大家可以尽情滴无视偶……）

作者: 九夜神尊 时间: 2009-9-6 22:56
实际上解密就像解压那么简单！！！！（有那个软件的条件下，虽然我有办法入手，但是我很有良）

作者: 艾薇 时间: 2009-9-6 23:07

实际上解密就像解压那么简单！！！！（有那个软件的条件下，虽然我有办法入手，但是我很有良）
九夜神尊发表于 2009-9-6 22:56

看到这个星星眼了吗，所以，你明白我的意思了吧……

明白了吗？！！！

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