Rust 元宇宙 2 — 邻居
分而治之 永远是处理复杂问题的不二法门
上一章我们定义了 基础的 角色信息 RoleInfo
里面除了位置之外，还有一个最重要的数据结构，邻近角色列表 neighbor
那么，怎么获得这个邻近角色列表呢
最简单的方法，当然是遍历除了自己以外场所内所有角色，找到距离自己在一定范围之内的角色 ID，然后刷新这个列表，但是当角色数量非常巨大的时候，遍历的开销将变得不能忽视了。
很多网络游戏在线人数非常高的时候，会出现各种卡顿和掉线，魔兽世界经常出现技能超级延迟的情况，多半都是因为服务器资源都在计算邻近角色列表了。
这个时候，我们就需要分而治之，引入区域的概念了。
我们知道，正常情况下，人类是会分区域聚集的，当一个地方的人太多，需要排队的时候，我们经常要换个地方，所以我们将整个场所 World 分解成很多个区域，每个区域保存自己区域的角色的 ID 集合，这样计算邻近玩家列表的时候，最多只需要计算相邻 9 个区域内所有的角色就行了。
当然，作为数学上一个经典的划分问题，正六边形的区域划分看起来是一个理想的选择，能完全覆盖整个二维平面，所有区域内的角色近似的可以认为距离都在某一个限制内。
但是考虑到算法的复杂度，我们还是选择了简单的正方形方案，有兴趣的童鞋，可以考虑实现一个正六边形划分的 区域自治方案。
我们以区域的中心坐标作为区域的唯一标识，考虑到区域的大小和边界不需要很高的精度，使用 i32 足够了，所以我们可以用 Rust 的 tuple (i32, i32) 作为 区域的标识。
我们不需要一次性的创建所有的区域，因为没有人的区域，是可以不存在的，也就是说，区域可以 Lazy 创建。
所以在世界中，区域集合具有下面的结构
采用这种分而治之的方法，我们可以将查找临近角色的计算开销极大的化简，当然，简单的仅查找角色所在的区域，从而获得临近角色的想法是幼稚的，当角色处于区域边界附近的时候，临近的区域很可能包括了比本区域角色更接近自己的角色。
根据区域中心的坐标和角色所在的象限，我们可以得到需要检查的四个区域。
为了避免复杂的判断，我们使用下面的函数获取 某一个坐标所在区域中心点的坐标和该坐标所在的象限
其中 CENTER_QUADRANT 是预先设定的 取模的 中心距离和象限的对照表
一般情况下，我们设定区域的大小和可视的距离是一致的，这样通过查表，我们能获得某个位置的 中心坐标和象限之后，需要搜索的区域列表：
象限 0 （原点），只需要检查本区域，象限 1，需要检查 自己 上面 右上 和 右边区域，象限 2 需要检查自己 上面 左上和左边的区域，象限 3 。。。
这样，通过下面的代码，我们可以获得 指定坐标可视范围内的所有角色
注意，我们在获得临近角色的列表之后进行了排序，这样可以快速的查找 某一个 角色是否在临近列表中。
还未添加个人签名 2019.10.25 加入
还未添加个人简介
评论