四叉树空间管理

简介

在游戏开发的过程中，我们要对空间进行管理，一个比较常用的方法就是用四叉树进行管理，采用的是分治的思路，把一个大的空间分为若干小空间进行管理。

原理

四叉树的思路很简单，和二分查找类似

首先我们要定义一个范围，作为空间管理的基础。
然后把这个范围划分为四块。
所有操作都按照这个空间来进行，当前格子不满足条件的情况就向下拓展。

现在，我们要找到空间中的一个物体，我们就不需要从大的黑色的这个范围全部遍历物体，而是在红色分割线划分出来的小空间里面遍历该空间中存储的物体。

如图所示，下面就是一个最基础的四叉树分割。我们把一个大的空间分为了四个小的空间。

四叉树定义

现在，我们遇到了第一个问题，要通过什么规则来决定是否需要划分空间呢？

这里就要引入节点深度和节点容量的概念。

节点深度决定四叉树能够拓展到多深
节点容量决定非最深节点能存储对象的最大数量。

当非最深节点的节点容量未满的时候，节点不进行分割，所有的对象都存储在当前的节点；当容量满了之后，节点分割为更小的四块，并且节点中存储的对象通过查询比较包围盒大小，满足条件的存入新的节点中，不满足条件的则继续存放在该节点。

现在，我们往这个空间里放入一些对象。我们假设深度为 2，容量也为 2。那么就有如下图所示的情况。

image.png

橙色代表插入的对象，我们可以观察到，在红色分割线划分的右上角格子中，我们插入了 4 个对象。此时该节点深度为 1，对象为 4 超过了节点的最大容量，因此我们继续分割，分割出粉色线四个格子。右上粉色格子对象数量为 3，此时虽然超出了最大容量，但由于格子的深度为 2，已经达到最大深度，因此无法继续分割，所有的对象都存储在该节点。

四叉树的数据结构可以根据以上概念得出

QTree

/** 最大深度 */
public _maxDepth = 0;
/** 最大数量 */
public _maxObjCount = 0;
/** 包围盒 */
public _bound = {};
/** 根节点 */
public _root: Qnode;

此处有一个 QNode 为四叉树节点，四叉树节点的数据结构如下

QNode

/** 包围盒 */
public _bound: { x, z, w, h, maxX, minX, maxZ, minZ };
/** 宽松包围盒 */
public _looseBound: any = {};
/** 父节点 */
public _parent: Qnode;
/** 所属四叉树 */
public _belongTree: Qtree;
/** 对象列表 */
public _objList = [];
/** 子节点字典 */
public _childDic = {};
/** 深度 */
public _depth: number;
/** 对象数量 */
public _objCount = 0;

四叉树节点数据结构中的宽松包围盒为松散四叉树所使用，接下来会介绍。对象存储在数组中，子节点可以存为数组，也可以存为字典，最终的结果都是一样存放下一深度的四个节点，可以按照自己的喜好调整。

四叉树操作

开始之前，我们要解决一个问题，如何进行对象插入的条件判断？

在讨论方法之前，我们要先思考一个问题，如果四叉树切线边缘存在物体的情况该如何解决？这里有两种方法，一种是存在父节点，一种是每一个压到的节点都存放一个该对象。

假设这个蓝色的对象插入的时候压到了粉色边线，用第一种方法的时候，我们查找右上角粉色格子内的对象的时候，查找的结果必定会包含蓝色对象，因为蓝色对象本身是属于红色格子的。用第二种方法的时候，左下角和右下角的粉色格子都有保存蓝色对象的信息，占用了两份数据，如果是在粉色十字正中间的时候，存储的数据要变成四份。

这个时候，我们要引入一个松散四叉树的概念。我们在上面的四叉树定义中也提到过松散四叉树，松散四叉树是指每一个分割的格子的包围盒并不一定要严格分割四分之一父节点空间。

如图所示，右下角这个绿色的空间，就是右下角格子的松散包围盒。每一个格子都有自己的松散包围盒。当松散包围盒的大小是格子大小的 2 倍的时候会产生一个特性，那就是插入对象的中心点只要在格子中，那他必定在这个格子的松散包围盒之内 。因此一般常用 2 倍大小的松散包围盒。

这个时候，对象压线的问题就得到了解决，只要判断对象的中心属于哪个格子即可。

如图所示，假如橙色部分是插入对象的大小，当他的大小为最大，即红色格子大小时，他的中心点在红色格子的左下角时，依然不会超出绿色松散包围盒大小。

前期工作

首先，我们要构造两个方法，一个是判断对象中心是否在格子内，还有一个是判断两个包围盒是否相交。

判断对象中心是否在格子内很简单，只要判断中心点的 x 和 z 是否大于包围盒最小值并且小于包围盒最大值即可。

中心点检测

/**
     * 检测是否在包围盒内
     * @param rect
     * @returns
     */
    private checkInAreaStrict(rect: RectBean, child: RectBean) {
        if (rect.minX > child.minX && rect.maxX < child.maxX &&
            rect.minZ > child.minZ && rect.maxZ < child.maxZ) {
            return true;
        }
        return false;
    }

检测包围盒是否相交的时候只要判断包围盒 A 的最大值是否小于包围盒 B 的最小值或者包围盒 A 的最小值是否大于包围盒 B 的最大值，这种情况下两包围盒必定不相交。这种方法即 AABB（Axially Aligned Bounding Box，按坐标轴排列的包围盒）检测。

AABB相交检测

/**
     * 检测是否相交
     * @param rect
     * @param child
     * @returns
     */
    private checkIntractive(rect: RectBean, child: RectBean) {
        if (rect.maxX < child.minX ||
            rect.minX > child.maxX ||
            rect.maxZ < child.minZ ||
            rect.minZ > child.maxZ) {
            return false;
        }
        return true;
    }

四叉树插入

首先，我们先判断是否需要拓展子节点，就按照上面说的，在不存在子节点并且是根节点，或者当前节点对象数量超出限制数量并且当前节点深度不是最大深度的时候拓展。

然后我们根据规则把对象插入到四叉树中即可。先判断对象是否可以插入当前格，然后判断当前格有无子节点，有子节点尽量把对象插入子节点，同时标记当前格（如果有子节点的话也包括子节点）存储的对象数量。

插入

/**
 * 插入对象
 * @param obj
 * @returns
 */
public insert(obj: QtreeObj) {
    //判断是否创建子节点
    if (!this._childDic["tl"] && (this._depth == 0 ||
        this._objCount >= this._belongTree._maxObjCount &&
        this._depth < this._belongTree._maxDepth)) {
        this.createChild();
        //填充对象到新创建的子节点中
        for (let i = this._objList.length - 1; i >= 0; i--) {
            //遍历子节点
            for (let prop in this._childDic) {
                //对象满足子节点条件的，插入到子节点中
                if (this.checkInAreaStrict(this._objList[i].rect, this._childDic[prop]._bound)) {
                    this._childDic[prop].insert(this._objList[i]);
                    this._objList.splice(i, 1);
                    break;
                }
            }
        }
    }

    if (this._childDic["tl"]) {
        //尽可能地分到子节点
        for (let key in this._childDic) {
            if (this.checkInAreaStrict(obj.rect, this._childDic[key]._bound)) {
                this._objCount++;
                return this._childDic[key].insert(obj);
            }
        }
    }

    this._objList.push(obj);
    ++this._objCount;
    return this;
}

四叉树移除

四叉树的移除和插入类似，每个查找到的节点都和需要移除的对象进行对比，如果该节点没有需要移除的对象，就进入到子节点去继续查找，直到找到或者最大深度。移除之后要对插入该对象的每一层的对象数量进行减 1。如果四个子节点的对象数量都为 0 的情况下，父节点可以进行坍缩，即移除四个子节点。

移除

/**
 * 移除对象
 * @param obj
 * @returns
 */
public remove(obj: QtreeObj) {
    //父节点坍缩
    if (this._parent._objCount <= 0) {
        this._parent._childDic = {};
    }
    //遍历移除
    for (let i = this._objList.length - 1; i >= 0; i--) {
        //比较对象id是否相等，该条件可根据需要自行修改
        if (this._objList[i].objId == obj.objId) {
            this._objList.splice(i, 1);
            this._objCount--;
            return;
        }
    }

    //如果当前节点没有匹配对象，则遍历子节点寻找需要移除的对象
    if (this._childDic["tl"]) {
        for (let key in this._childDic) {
            if (this.checkInAreaStrict(obj.rect, this._childDic[key]._bound)) {
                this._childDic[key].remove(obj);
                this._objCount--;
                return;
            }
        }
    }
}

四叉树查找

接下来是四叉树的查找，四叉树的查找可以只查找当前源对象所在的区块，或者也可以进一步筛选和源对象相交的对象，即检测与查找范围包围盒相交的对象。本案例采取进一步筛选的模式。

在四叉树遍历的过程中，先对每个节点的对象进行相交检测，相交的物体加入查找结果数组。然后对于每个子节点，我们都要比较源对象的范围和子节点的松散包围盒是否相交。由于每个子节点都有可能和源对象交汇，因此四个子节点都要进行判断。

查找

/**
 * 查找范围内所有节点
 * @param rect
 */
public findObjFromRect(rect: RectBean): QtreeObj[] {
    let objs = [];
    //查找匹配对象
    for (let key in this._objList) {
        if (this.checkIntractive(rect, this._objList[key].rect)) {
            objs.push(this._objList[key]);
        }
    }
    //遍历子节点
    for (let key in this._childDic) {
        if (this._childDic[key].checkIntractive(rect, this._childDic[key]._looseBound)) {
            objs = objs.concat(this._childDic[key].findObjFromRect(rect));
        }
    }
    return objs;
}

四叉树动态更新

四叉树节点的更新也很简单。具体的逻辑如下图所示：

更新

/**
 * 刷新对象在四叉树中的位置
 * @param obj
 * @returns
 */
public refresh(obj: QtreeObj) {
    if (this.checkInAreaStrict(obj.rect, this._bound)) {
        return this;
    } else {
        this.remove(obj);
        return this._belongTree.insert(obj);
    }
}

代码

包围盒数据结构

export default class RectBean {
  constructor(x?, z?, w?, h?, maxX?, minX?, maxZ?, minZ?) {
    this.x = x;
    this.z = z;
    this.w = w;
    this.h = h;
    this.maxX = maxX;
    this.minX = minX;
    this.maxZ = maxZ;
    this.minZ = minZ;
  }
  public x;
  public z;
  public w; //宽 -- x方向
  public h; //高 -- z方向
  public maxX;
  public minX;
  public maxZ;
  public minZ;
}

四叉树对象数据结构

import { BoxCollider } from "../../../../../libs/Collider";

export default class QtreeObj {
  constructor(id?, objId?, rect?, node?) {
    this.id = id;
    this.objId = objId;
    this.rect = rect;
    this.node = node;
  }
  /** id 一般只需要这个就够了 必要属性 */
  public id: number;
  /** 对象id 此处为项目需要而增加的id */
  public objId: number;
  /** 范围 必要属性 */
  public rect;
  /** 节点 必要属性 */
  public node: Laya.Sprite3D;
}

四叉树脚本

import QtreeObj from "./Bean/QtreeObj";
import Qnode from "./Qnode";

export default class Qtree {
  public _maxDepth = 0;

  public _maxObjCount = 0;

  public _bound = {};
  /** 子节点 */
  public _root: Qnode;

  constructor(bound, maxDepth, maxObjCount) {
    this._bound = bound;
    this._maxDepth = maxDepth;
    this._maxObjCount = maxObjCount;
    this._root = new Qnode(bound, 0, this, this);
  }

  public insert(obj: QtreeObj): void {
    return this._root.insert(obj);
  }

  public remove(obj: QtreeObj) {
    this._root.remove(obj);
  }

  public findObjFromRect(rect): QtreeObj[] {
    return this._root.findObjFromRect(rect);
  }
}

四叉树节点脚本

import ModelFactory from "../../Common/ModelFactory";
import QtreeObj from "./Bean/QtreeObj";
import RectBean from "./Bean/RectBean";
import Qtree from "./Qtree";

export default class Qnode {
  /** 包围盒 */
  public _bound: { x; z; w; h; maxX; minX; maxZ; minZ };
  /** 宽松包围盒 */
  public _looseBound: any = {};
  /** 父节点 */
  public _parent: Qnode;
  /** 所属四叉树 */
  public _belongTree: Qtree;
  /** 对象列表 */
  public _objList = [];
  /** 子节点字典 */
  public _childDic = {};
  /** 深度 */
  public _depth: number;
  /** 对象数量 */
  public _objCount = 0;

  private _debugColor: Laya.Color = new Laya.Color(1, 0, 0, 1);
  private _debugColor2: Laya.Color = new Laya.Color(0, 1, 1, 1);
  private _debugView: Laya.PixelLineSprite3D;

  constructor(bound, depth, parent, belongTree) {
    this._bound = bound;
    this._depth = depth;
    this._parent = parent;
    this._belongTree = belongTree;

    this._looseBound = {
      x: bound.x,
      z: bound.z,
      w: bound.w * 2,
      h: bound.h * 2,
      maxX: bound.x + bound.w,
      minX: bound.x - bound.w,
      maxZ: bound.z + bound.h,
      minZ: bound.z - bound.h,
    };
    //绘制四叉树范围
    // this.showDebugMode();
  }

  /**
   * 绘制四叉树范围 Laya版本
   * @param loose 是否绘制松散范围
   */
  private showDebugMode(loose?) {
    Laya.timer.once(1000, this, () => {
      //场景中插入线段
      this._debugView = new Laya.PixelLineSprite3D(99999);
      ModelFactory.getScene().addChild(this._debugView);

      for (let t = this._debugView.lineCount - 1; t >= 0; t--)
        this._debugView.removeLine(t);
      //紧凑四叉树
      this._debugView.addLine(
        new Laya.Vector3(this._bound.maxX, 0.1, this._bound.maxZ),
        new Laya.Vector3(this._bound.maxX, 0.1, this._bound.minZ),
        this._debugColor,
        this._debugColor
      );

      this._debugView.addLine(
        new Laya.Vector3(this._bound.minX, 0.1, this._bound.maxZ),
        new Laya.Vector3(this._bound.minX, 0.1, this._bound.minZ),
        this._debugColor,
        this._debugColor
      );

      this._debugView.addLine(
        new Laya.Vector3(this._bound.maxX, 0.1, this._bound.maxZ),
        new Laya.Vector3(this._bound.minX, 0.1, this._bound.maxZ),
        this._debugColor,
        this._debugColor
      );

      this._debugView.addLine(
        new Laya.Vector3(this._bound.maxX, 0.1, this._bound.minZ),
        new Laya.Vector3(this._bound.minX, 0.1, this._bound.minZ),
        this._debugColor,
        this._debugColor
      );
      if (loose) {
        //松散四叉树
        this._debugView.addLine(
          new Laya.Vector3(this._looseBound.maxX, 0.1, this._looseBound.maxZ),
          new Laya.Vector3(this._looseBound.maxX, 0.1, this._looseBound.minZ),
          this._debugColor2,
          this._debugColor2
        );

        this._debugView.addLine(
          new Laya.Vector3(this._looseBound.minX, 0.1, this._looseBound.maxZ),
          new Laya.Vector3(this._looseBound.minX, 0.1, this._looseBound.minZ),
          this._debugColor2,
          this._debugColor2
        );

        this._debugView.addLine(
          new Laya.Vector3(this._looseBound.maxX, 0.1, this._looseBound.maxZ),
          new Laya.Vector3(this._looseBound.minX, 0.1, this._looseBound.maxZ),
          this._debugColor2,
          this._debugColor2
        );

        this._debugView.addLine(
          new Laya.Vector3(this._looseBound.maxX, 0.1, this._looseBound.minZ),
          new Laya.Vector3(this._looseBound.minX, 0.1, this._looseBound.minZ),
          this._debugColor2,
          this._debugColor2
        );
      }
    });
  }

  /**
   * 插入对象
   * @param obj
   * @returns
   */
  public insert(obj: QtreeObj) {
    //判断是否创建子节点
    if (
      !this._childDic["tl"] &&
      (this._depth == 0 ||
        (this._objCount >= this._belongTree._maxObjCount &&
          this._depth < this._belongTree._maxDepth))
    ) {
      this.createChild();
      //填充对象到新创建的子节点中
      for (let i = this._objList.length - 1; i >= 0; i--) {
        //遍历子节点
        for (let prop in this._childDic) {
          //对象满足子节点条件的，插入到子节点中
          if (
            this.checkInAreaStrict(
              this._objList[i].rect,
              this._childDic[prop]._bound
            )
          ) {
            this._childDic[prop].insert(this._objList[i]);
            this._objList.splice(i, 1);
            break;
          }
        }
      }
    }

    if (this._childDic["tl"]) {
      //尽可能地分到子节点
      for (let key in this._childDic) {
        if (this.checkInAreaStrict(obj.rect, this._childDic[key]._bound)) {
          this._objCount++;
          return this._childDic[key].insert(obj);
        }
      }
    }

    this._objList.push(obj);
    ++this._objCount;
    return this;
  }

  /**
   * 移除对象
   * @param obj
   * @returns
   */
  public remove(obj: QtreeObj) {
    //父节点坍缩
    if (this._parent._objCount <= 0) {
      this._parent._childDic = {};
    }
    //遍历移除
    for (let i = this._objList.length - 1; i >= 0; i--) {
      //比较对象id是否相等，该条件可根据需要自行修改
      if (this._objList[i].objId == obj.objId) {
        this._objList.splice(i, 1);
        this._objCount--;
        return;
      }
    }

    //如果当前节点没有匹配对象，则遍历子节点寻找需要移除的对象
    if (this._childDic["tl"]) {
      for (let key in this._childDic) {
        if (this.checkInAreaStrict(obj.rect, this._childDic[key]._bound)) {
          this._childDic[key].remove(obj);
          this._objCount--;
          return;
        }
      }
    }
  }

  /**
   * 查找范围内所有节点
   * @param rect
   */
  public findObjFromRect(rect: RectBean): QtreeObj[] {
    let objs = [];
    //查找匹配对象
    for (let key in this._objList) {
      if (this.checkIntractive(rect, this._objList[key].rect)) {
        objs.push(this._objList[key]);
      }
    }
    //遍历子节点
    for (let key in this._childDic) {
      if (
        this._childDic[key].checkIntractive(
          rect,
          this._childDic[key]._looseBound
        )
      ) {
        objs = objs.concat(this._childDic[key].findObjFromRect(rect));
      }
    }
    return objs;
  }

  /**
   * 刷新对象在四叉树中的位置
   * @param obj
   * @returns
   */
  public refresh(obj: QtreeObj) {
    if (this.checkInAreaStrict(obj.rect, this._bound)) {
      return this;
    } else {
      this.remove(obj);
      return this._belongTree.insert(obj);
    }
  }

  /**
   * 创建子节点
   */
  private createChild() {
    let bound1 = {
      x: this._bound.x + this._bound.w * 0.25,
      z: this._bound.z + this._bound.h * 0.25,
      w: this._bound.w * 0.5,
      h: this._bound.h * 0.5,
      maxX: this._bound.x + this._bound.w * 0.25 + this._bound.w * 0.25,
      minX: this._bound.x + this._bound.w * 0.25 - this._bound.w * 0.25,
      maxZ: this._bound.z + this._bound.h * 0.25 + this._bound.h * 0.25,
      minZ: this._bound.z + this._bound.h * 0.25 - this._bound.h * 0.25,
    };
    this._childDic["tl"] = new Qnode(
      bound1,
      this._depth + 1,
      this._parent,
      this._belongTree
    );

    let bound2 = {
      x: this._bound.x - this._bound.w * 0.25,
      z: this._bound.z + this._bound.h * 0.25,
      w: this._bound.w * 0.5,
      h: this._bound.h * 0.5,
      maxX: this._bound.x - this._bound.w * 0.25 + this._bound.w * 0.25,
      minX: this._bound.x - this._bound.w * 0.25 - this._bound.w * 0.25,
      maxZ: this._bound.z + this._bound.h * 0.25 + this._bound.h * 0.25,
      minZ: this._bound.z + this._bound.h * 0.25 - this._bound.h * 0.25,
    };
    this._childDic["tr"] = new Qnode(
      bound2,
      this._depth + 1,
      this._parent,
      this._belongTree
    );

    let bound3 = {
      x: this._bound.x + this._bound.w * 0.25,
      z: this._bound.z - this._bound.h * 0.25,
      w: this._bound.w * 0.5,
      h: this._bound.h * 0.5,
      maxX: this._bound.x + this._bound.w * 0.25 + this._bound.w * 0.25,
      minX: this._bound.x + this._bound.w * 0.25 - this._bound.w * 0.25,
      maxZ: this._bound.z - this._bound.h * 0.25 + this._bound.h * 0.25,
      minZ: this._bound.z - this._bound.h * 0.25 - this._bound.h * 0.25,
    };
    this._childDic["bl"] = new Qnode(
      bound3,
      this._depth + 1,
      this._parent,
      this._belongTree
    );

    let bound4 = {
      x: this._bound.x - this._bound.w * 0.25,
      z: this._bound.z - this._bound.h * 0.25,
      w: this._bound.w * 0.5,
      h: this._bound.h * 0.5,
      maxX: this._bound.x - this._bound.w * 0.25 + this._bound.w * 0.25,
      minX: this._bound.x - this._bound.w * 0.25 - this._bound.w * 0.25,
      maxZ: this._bound.z - this._bound.h * 0.25 + this._bound.h * 0.25,
      minZ: this._bound.z - this._bound.h * 0.25 - this._bound.h * 0.25,
    };
    this._childDic["br"] = new Qnode(
      bound4,
      this._depth + 1,
      this._parent,
      this._belongTree
    );
  }

  /**
   * 检测是否在包围盒内
   * @param rect
   * @returns
   */
  private checkInAreaStrict(rect: RectBean, child: RectBean) {
    if (
      rect.minX > child.minX &&
      rect.maxX < child.maxX &&
      rect.minZ > child.minZ &&
      rect.maxZ < child.maxZ
    ) {
      return true;
    }
    return false;
  }

  /**
   * 检测是否相交
   * @param rect
   * @param child
   * @returns
   */
  private checkIntractive(rect: RectBean, child: RectBean) {
    if (
      rect.maxX < child.minX ||
      rect.minX > child.maxX ||
      rect.maxZ < child.minZ ||
      rect.minZ > child.maxZ
    ) {
      return false;
    }
    return true;
  }
}