四叉树场景管理

B ID

0

bool isLeaf = false

1

TreeNode parent = null

A

四叉树在几何上的表示是一颗只有一个根节点，除了根节点以外每个节点都只有一个父节点，而且除了叶子几点外每个节点都由四个子节点。那么在代码中我们该如何设计这样的一棵树呢？

bool isRoot

1024

TreeNode parent = ref TreeNode

4

这里按照四叉树的规则，把父节点划分成4去区域，这里自己定义一个存储规则，这里的规则对应每个格子的数字标号，对应数据结构中的child数组的0-3的位置

B

TreeNode

bool isLeaf = true

bool isRoot = false

第四位的值为所在第三层（2*2）的哪个序号，这里明显应该为4

bool isLeaf

第一位的值固定为-1，这个-1表示根节点

bool isRoot = true

3、后来进来了第三位玩家C

TreeNode parent

2、后来又进来了一个玩家B

如果玩家的位置在两个或者4个格子的交界怎么办？方案一：设计成不存在交界，交界都属于四个格子中的某两个格子。方案二：树结构上把这个玩家的数据存储在交接的格子的父节点上，序号上数据在哪一层哪一层的序号就为0

2

3

父亲节点的引用

第四位的值为所在第三层（4*4）的哪个序号，这里明显应该为1

A ID

孩子节点（按照规则顺序来划分）

C ID

是否为叶子节点

1、假设有一个1024*1024的地图，在地图中只有一个玩家A的时候

-1

得到这个标号之后，按照这个规则在第一层找child数组中找第一个元素 -> 在第二层找child数组中的第一个元素 -> 在第三层中找到child数组中的第三个元素，直到找到叶子节点为止，数据就在叶子节点中。图中可以计算出扇形覆盖的所有格子笛卡尔坐标，根据这个方式就可以得到每个格子的序列号，这样就可以找到视野中的所有玩家。

通过这个过程可以清晰地知道，一个区域中存在两个及以上的玩家的时候就需要对该区域进行分割成四个区域，在代码上的表现为树的该区域节点的child数组分别创建和存储对应序号的TreeNode孩子节点的引用，我们只有动态维护好这棵树即可在游戏运行的时候我们该如何快速找到对应自己的视野的所有玩家呢？这里我们设计四叉树有5层，假设每个格子都有人的情况下，这颗树有1024个叶子节点，几何表示如下图，每个格子是32*32，即最小的格子为32*32的，并且在树的第五层

这里的扇形表示这个玩家的视野范围，那么我们可以计算得知扇形覆盖的最小格子是什么，那么我们该如何表示每个格子的坐标呢？举例子这里我们想知道绿色的格子（有具体坐标之后可以确定在笛卡尔坐标的位置）（5，6）的坐标表示，我们设置一种规则，用一个6位数的标号即可在树中找到对应的格子

第三位的值为所在第二层（16*16）的哪个序号，这里明显应该为1

C

是否为根节点

第二位的值为所在第一层（32*32）的哪个序号，这里明显应该为1

第四位的值为所在第三层（8*8）的哪个序号，这里明显应该为3

玩家ID列表容器

在mmo游戏中经常会使用到四叉树或者八叉树进行场景管理，因为一个服务器中可能由上万的玩家，如果每次都遍历一次所有玩家来判断其他玩家是否在AOI范围内的话效率非常低，所以使用四叉树或者八叉树来对场景来进行管理是非常有必要的。