ARPG中角色之间互动如何判断

一马平川

我正在写一个APRG的开发工具。现在在做角色之间互动（也就是角色之间的攻击等动作）的判断。如何判断才能保证效率？
我想最直接的方法，莫过于角色A和其它角色一一进行判断处理，看看是否发生了战斗；然后角色B再和其它角色一一进行判断处理。这样的话，程序应该比较直观，但是效率是否太低了？如果有1000个角色，至少要进行0.5×1000×1000＝50万个判断处理，目前的主流PC能流畅跑起来吗？
另外一个办法就是使用地图信息，专门生成一个角色的地图信息（比如每个点都保存占据该点的角色的指针）。那么角色A只需要判断相应的地图点上是否有其它角色指针就可以了。
是否还有其它方法可以提高判断效率？

Deen

用最大包围框来减少比较次数。

如果角色能重复叠合的话就不知道了。

KeenBlue

楼主说的ARPG应该是暗黑破坏神那种视角的游戏吧，上千人的对战，呵呵，是网络游戏？我玩过暗黑，我觉得没有必要用遍历的方法来进行检测，在这类的游戏中攻击应该是分单体和群体攻击（有攻击范围），对于单体攻击的检测，把地图分成菱形的块，对他门编号，鼠标在那个块的范围内点下，就对那个块上的玩家作用，不用对其他块上的玩家进行判断，因为是单体攻击嘛，只打一人！对于群体攻击，有个攻击范围，只对在这个范围里的玩家进行判断就行了！
我现在还没作个此类游戏，想法是否正确，还请各位高手斧正！！

一马平川

但是你怎么知道指定的块上有精灵？这个精灵又是具体的哪一个精灵？
这是否也还是要用遍历的方法来实现？
或者象我说的第二种方法，用精灵指针的地图信息？

noslopforever

碰撞检测的方法很多，我只写一个自己接触过的方法，物件索引表法：也就是楼主的第二种方法。

如果地图是按照格子的，且一个格子内只有一个物件，就根据地图格子生成同比大小的一张索引表（如Array［64］［64］）。
循环内部：
1清空索引表。
2物件逻辑－》将物件按照自己的位置把ID或者指针存入这个索引表。
3碰撞检测时只要知道碰撞所发生的位置（如14，17），就可以在索引表内唯一对应到某个Cell内（Array［14］［17］），这时查找此Cell内存储的数值是否为0，如果不为0，就是物件的ID或者指针。指针可能会方便一些，但是ID更加安全。

但是如果不按照格子来组织呢？或者地图很大呢？
例如地图1280X1280，我们可以这样生成一个Cell表：10X10为一个Cell，每一个Cell内部放一个物件链表。
循环内部：
1，物件按照位置和上一步的位置更新Cell
如一个物件从0，0Cell到了0，1Cell，就把自己的指针从Cell[0][0]的链表中清掉，放入Cell[0][1]的物件链表中。如果没有跨越Cell，就不变。
2，物件需要做碰撞检测时，按照如下方式：
根据物件所处的Cell和碰撞要求，在本Cell及邻近Cell内遍历物件链表，对物件链表中的每一个物件做碰撞检测。
例如物件绝对坐标是125,125，就是在Cell[9][9]内，那么会发生什么情况呢？如果碰撞不需要越界（不是爆炸性质的碰撞），则只在Cell[9][9]内部遍历链表检测碰撞就可以了，但如果是需要越界，那就需要算上邻近的Cell了。边界和边角的也需要考虑越界。

这样的办法有些拙劣，期待更好的方法。

PS：ARPG的物件碰撞不仅仅考虑的是角色，可能更多需要考虑的是“飞行道具”例如魔法、弓箭等。如果要求比较低一些，最好能绕过这些飞行道具的实时检测。

kingmark

楼上的Cell方法不错，采纳。
幸好我的弓箭和魔法都比较简单，否则头大了。

kongbu

顶一下，　回家后再仔细看