抛砖引玉：我写的《AOI的实现的优化过程》

xjffj

AOI：Area of Interest
欢迎各位讨论
http://blog.csdn.net/xjffj/archive/2009/01/05/3713058.aspx

由于正在开发的游戏涉及到10万个移动角色，如果单服10000玩家的话，采用双向循环查找，那就是10亿的量级，太恐怖了，不得不对算法做优化。
考虑以下场景：
1000*1000的地图
10000客户端角色
两个角色间的距离是10时，有效。
使用语言：java，版本1.6

随机生成10000角色的位置信息，然后计算哪些角色的信息需要发给范围内的客户端。
原始：使用最简单的双向查找算法，两重For循环， 每找到一个时数量+1，结果如下
    找到40030个有效值，耗时880ms
优化一：很明显，位置是双向的， 也就是A在B的范围内，B也在A的范围内，因此只需要循环n*(n-1)/2次，优化结果耗时416ms

优化二：由于大部分的角色位置相距较远，因此对地图进行分区，以100为单位，整个地图被分成100个区域，创建区域数组Player[100][]，然后计算每个客户端的更新范围所在的区域， 并将客户端加入到区域中，注意客户端的四个顶点可能在不同的区域上，此时在几个区域就要加入几个区域。最后计算角色所在区域，并和区域内的Player计算距离。此算法得到的结果是22.5ms，为了避免java计时精度问题的影响，此处用了nanotime来计时。

优化三：区域大小用2^N来表示，从而在计算角色所在区域时可以用移位来处理，使用64作为区域大小，优化后平均耗时是：15.5ms

优化四：从算法的耗时来看，区域小一些，则区域数量变多，但每个区域内的角色数量就少了，需要计算的量也会变少，使用32作为区域大小后，耗时为：9.5ms

优化五：如果地图变大一些，角色更加稀疏，则计算量会更少，使用10000*10000的地图后， 同样64大小的区域，耗时是：1.8ms

自此，整个优化结束，基本满足需要。

kaikai

如果把整个地图空间对所有角色的位置使用三角剖分算法O(nlogn)
可以得到一个三角型组成网络，所有角色在三角形定点上，同时每个角色周围最近的若干个角色都与他有直接的一条边连接。需要找某人周围一定范围内的人可以用a*遍历。
判断2个人之间距离的复杂度为O(logn)
计算所有两两之间需要关联的信息的复杂度：O(nlogn)

xjffj

三角剖分法的基础算法计算外接圆包含插入点的三角形相对俺的算法还是比较复杂的，而且效率也没高多少。

kaikai

你的算法已经把空间划分为小块，复杂度已经降低为O（nlogn）。
固定划分的格子对角色聚集情况性能会下降。如果仅用来判断互相之间距离远近程度进行过滤，且该距离大于或与格子尺度相当则性能不受影响。

kaikai

我没实现过，只是想当然的分析：）
别见怪啊

wxhwhmanshan

upup