http://bbs.66rpg.com/thread-133052-1-1.html这个人的思路很不错
我贴过来吧
说明一下我的移动算法吧:
首先要说明的是,本移动范围算法参考的是网上广为流传的寻路算法,有兴趣的人可以去网上搜一下。
本算法中有两个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内存入了所有可移动节点。
嗯,以上为移动范围算法求解