一个链接：

(99+ 封私信 / 5 条消息) 四叉树 - 搜索结果 - 知乎 (zhihu.com)

但这个太水了，经过我一番仔细思考，还是有很多细节值得记录的

首先写一个平面四叉树类，提供三个API：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Tree {
    
    // 将一个对象添加到树中
    function addObject(Object) {

    }
	
    // 从一个树种移除一个对象，如果对象不在树中，返回false。
    function removeObject(Object) -> bool {

    }

	// 获取和这个对象相碰撞的所有对象。
    function getCollishObjects(ObjectNode) -> Object[] {

    }    
}

上面是伪代码，什么语言都不是

四叉树有节点。四叉树是完美四叉树，要么有孩子，要么没有孩子，一旦有孩子，就是四个孩子。

每个节点都能容纳N个物体。树高度H层，这两个参数可以自定义调节。

但是当物体在当前框框的十字线相接触了，那么只能塞到当前节点里了，不能再往下赛了。这个情况超过N也无所谓。

一开始树里面没有什么物品，对象，所以第一个进来的对象会直接塞到根节点上，而不是细化到某个非常小的区域所对应的节点上。

可以设计一个挂载物品对象类型

1
2
3
4
5
6
interface NodeObjectCircle {
   x: float
   y: float
   r: float
   object: Object
}

可能要挂载的敌人对象或者子弹对象本身内部有xyr属性，但是为了统一类型格式，外面又包上了三个属性，自己自身绑定到了object字段上，形成一个新的对象。

然后，四叉树里的每个节点可能 是这样定义的

1
2
3
4
5
6
7
8
interface treeNode {
	leftTop: NodeObjectCircle[],
	rightTop: NodeObjectCircle[],
	leftDown: NodeObjectCircle[],
	rightDown: NodeObjectCircle[],
	
	current: NodeObjectCircle[],  // 如果和十字线交叉了，或者第一次来到这里，会进入到这里。
}

实际上可以考虑优化性能，把数组改成集合，或者字典类型，优化的是remove方法。

add方法

一开始啥都没有，肯定放在根节点的current里。满了才往下新创建四个子节点。兜住了就不创建，撑爆了才创建。

add的时候首先判断一下当前方框里的十字线是否和自己这个对象相交，相交了就只能放在current里。即使超过了N。

然后写四个if或者两个两个嵌套的if，判断四个子框。

然后一直深入下去，直到到底。或者触碰到十字。

remove方法

用递归来写。因为可能涉及到删除回收节点，防止长时间使用整个树里节点过多占用内存过多。并且这个删除回收节点不是只删除一个，可能是多层的链式的，删除好几个。只要把删除写在递归口的下面就行。

如果四个子节点都是空的，就删除所有的子节点。将他们设置为null。

在删除之前肯定要先找到。对于一个父节点和四个子节点，先看父节点的current里是否有当前这个对象，如果用哈希优化了，O1就能看到是否存在。然后判断一下要删除对象的位置处于哪个子框中。继续深入下去递归。

getCollish方法

传入一个对象，获取和这个对象碰撞的所有对象。

最理想情况：

如果所有的对象都没有和十字相交，那好说了，就看传入的这个对象所在的框框里，直接和所有其他的对象一一配对，看看是否发生相交，例如就调用圆和圆的相交的方法就行了。

但是还是要把这个节点所在的所有子孙节点的current里的对象都扫描一一检测一下碰撞。

还要考虑其他上层十字上的或者current上的对象。

如果传入的对象是在框里的，但是有其他对象和框框相交。那就看，在一路找下来，树上经过的节点，所有节点的current里，是否有节点和当前对象相碰。

也就是看所有上层的current里的所有对象是否和自己碰撞。因为这是一个递归过程，可以在找到之后返回的过程中进行一一比较。

缺点：

当节点本来就在根节点上的current里的时候，这无异于和全部对象都一一比了一下。

当圆形对象半径太大了的时候，那几乎是必定触碰最大的十字线的。