游戏算法（2）：查找优化之四叉树的应用
本文主要介绍四叉树的应用场景和实现。
本文链接 游戏算法（2）：查找优化之四叉树的应用
相关文章 游戏算法（1）：实现AStar寻路算法
一、四叉树概念
在二分查找算法中，整个查找对象结构化关联起来，就是一棵二叉树。在线性数据快速查找中，二分查找有着不错的性能。
同理，我们可以应用到N叉树。
那么在平面中，我们则可以利用到四叉树。这是因为平面时二维的，x、y两个轴刚好将平面空间分成四份。因此在平面查找算法中，四叉树被广泛应用，来优化查找的效率。四叉树或四元树也被称为Q树（Q-Tree）。
那八叉树呢？没错，三维空间中，x、y、z轴将空间划分为8个部分，来优化查找效率。
二、四叉树的应用
四叉树或四元树也被称为Q树（Q-Tree）。四叉树广泛应用于图像处理、空间数据索引、2D中的快速碰撞检测、存储稀疏数据等
图像处理：比如像素分象限区间剔除
空间数据索引：2d场景中的对象查找、地图元素查找。如查找在屏幕范围内的随想集合，则只需先判断屏幕窗口在场景的哪个子树中。
2D中的快速碰撞检测：碰撞检测中对大量碰撞对象的查找、剔除。如不在同一子树区间的对象集合，不可能碰撞，可直接剔除。
存储稀疏数据：可以存储MxN的矩阵。M和N的维度和树的高度直接相关。为0的区域，可以做成空节点树。
八叉树则应用在三维空间货期它场景。
N叉树同理。
以上的应用都至少带来了，比直接遍历所有对象数据，更优的效率。
例如下图的四叉树碰撞应用，A区域的物体和B区域的物体不可能发生碰撞，那么他们之间就不用进行碰撞判断逻辑了。仅需检测每个区域内的物体之间的碰撞。大幅降低碰撞检测压力。
四叉树碰撞应用
三、四叉树的实现
实现四叉树QuadTree。这里采用x、y轴进行区域划分，节点进行矩形均分，来实现较为标准的分割，对象是否在区域内是以点是否在矩形内的判定为例。
当然，这些分割标准是可以完全自定义的，不一定要是矩形或者x、y轴分割。甚至是各种形状的图形。
因为四叉树只需要保证逻辑节点有四个子节点即可。至于节点对象的定义完全由开发者决定，几点是否在某个区域内的判定函数也可以是自定义的。
1、实现四叉树节点QuadTreeNode
/**
* 四叉树节点数据结构
* 四叉树或四元树也被称为Q树（Q-Tree）。
* 四叉树广泛应用于图像处理、空间数据索引、2D中的快速碰撞检测、存储稀疏数据等
*/
export class QuadTreeNode<T> {
/** 绑定的四叉树树对象引用 */
protected _tree: QuadTree<T>;
/** 节点的高度 */
protected _height: number;
/** 节点的深度 */
protected _depth: number;
/** 父节点 */
protected _parentNode: QuadTreeNode<T>;
/** 邻节点指针 */
public _nextNode: QuadTreeNode<T>;
/** 子节点链表 */
protected _childLinkList: LinkList<QuadTreeNode<T>>;
/** 对象 */
protected _data: QuadTreeNodeData<T>;
/** 矩形区域 */
protected _rect: Rectangle;
/** 本节点是否禁用搜索 */
protected _disableSearch: boolean = false;
public leftTop: {x: number, y: number} = null;
public leftBottom: {x: number, y: number} = null;
public rightBottom: {x: number, y: number} = null;
public rightTop: {x: number, y: number} = null;
/** 数据是否为空 */
protected _isDataEmpty: boolean = true;
/**
* 构造函数
* @param rect 二维空间数据
* @param depth 节点的深度
*/
constructor(tree: QuadTree<T>, parentNode: QuadTreeNode<T>, rect: Rectangle, depth: number) {
this._data = new QuadTreeNodeData<T>();
this._tree = tree;
this._parentNode = parentNode;
this._childLinkList = new LinkList<QuadTreeNode<T>>();
this._rect = rect;
this._depth = depth;
this._height = this._depth;
this.leftTop = {x: this._rect.x, y: this._rect.y};
this.leftBottom = {x: this._rect.x, y: this._rect.y + this._rect.height};
this.rightBottom = {x: this._rect.x + this._rect.width, y: this._rect.y + this._rect.height};
this.rightTop = {x: this._rect.x + this._rect.width, y: this._rect.y};
if (depth > 0) {
this._createChildNode();
}
}
/**
* 创建子节点
*/
protected _createChildNode(): void {
if (this._rect.width > 0 && this._rect.height > 0) {
let leftTop = new QuadTreeNode<T>(this._tree, this,
new Rectangle(this._rect.x, this._rect.y, this._rect.width / 2, this._rect.height / 2), this._depth - 1);
this._childLinkList.insert(leftTop);
let rightTop = new QuadTreeNode<T>(this._tree, this,
new Rectangle(this._rect.x + this._rect.width / 2, this._rect.y, this._rect.width / 2, this._rect.height / 2), this._depth - 1);
this._childLinkList.insert(rightTop);
leftTop._nextNode = rightTop;
let rightDown = new QuadTreeNode<T>(this._tree, this,
new Rectangle(this._rect.x + this._rect.width / 2, this._rect.y + this._rect.height / 2, this._rect.width / 2, this._rect.height / 2), this._depth - 1);
this._childLinkList.insert(rightDown);
rightTop._nextNode = rightDown;
let leftDown = new QuadTreeNode<T>(this._tree, this,
new Rectangle(this._rect.x, this._rect.y + this._rect.height / 2, this._rect.width / 2, this._rect.height / 2), this._depth - 1);
this._childLinkList.insert(leftDown);
rightDown._nextNode = leftDown;
}
}
/**
* 获取数据
*/
public get data(): QuadTreeNodeData<T> {
return this._data;
}
/**
* 获取对象集合
*/
public get targets(): T[] {
return this._data.getTargets();
}
/**
* 获取左上区域对象集合
*/
public get leftTopTargets(): T[] {
return this._childLinkList.getItemByIndex(0).value.targets;
}
/**
* 获取右上区域对象集合
*/
public get rightTopTargets(): T[] {
return this._childLinkList.getItemByIndex(1).value.targets;
}
/**
* 获取右下区域对象集合
*/
public get rightDownTargets(): T[] {
return this._childLinkList.getItemByIndex(2).value.targets;
}
/**
* 获取左下区域对象集合
*/
public get leftDownTargets(): T[] {
return this._childLinkList.getItemByIndex(3).value.targets;
}
/**
* 获取左边第一个子节点
*/
public getLeftChild(): QuadTreeNode<T> {
return this._childLinkList.head();
}
/**
* 获取区域数据
*/
public get rect(): Rectangle {
return this._rect;
}
/**
* 获取节点的高度
*/
public get height(): number {
return this._height;
}
/**
* 获取节点的深度
*/
public get depth(): number {
return this._depth;
}
/**
* 获取节点的邻节点
*/
public get nextNode(): QuadTreeNode<T> {
return this._nextNode;
}
/**
* 获取节点的父节点
*/
public get parentNode(): QuadTreeNode<T> {
return this._parentNode;
}
/**
* 获取节点数据是否为空
*/
public get isDataEmpty() {
return this._isDataEmpty;
}
/**
* 设置节点数据是否为空
*/
public set isDataEmpty(isEmpty) {
this._isDataEmpty = isEmpty;
}
/**
* 获取子节点数组
*/
public getChildsAsArray(): QuadTreeNode<T>[] {
return this._childLinkList.toArray();
}
/**
* 是否根节点
*/
public isRoot(): boolean {
return !this._parentNode;
}
/**
* 是否叶节点
*/
public isLeaf(): boolean {
return this._childLinkList.size() <= 0;
}
/**
* 设置开启或关闭搜索
*/
public set disableSearch(disable: boolean) {
this._disableSearch = disable;
}
/**
* 获取开启或关闭搜索
*/
public get disableSearch() {
return this._disableSearch;
}
/**
* 是否包含某个坐标点
*/
public isContains(x: number, y: number): boolean {
return this._rect.contains(x, y);
}
/**
* 移除对象
*/
public removeTarget(target: T): void {
this._data.removeTarget(target);
this.isDataEmpty = true;
this.updateParentEmptyState();
}
/**
* 增加对象
*/
public addTarget(target: T): void {
this._data.addTarget(target);
this.isDataEmpty = false;
this.updateParentEmptyState();
}
/**
* 获取rect的四个坐标
*/
public getVertexPoints() {
let leftTop: {x: number, y: number} = {x: this._rect.x, y: this._rect.y};
let leftBottom: {x: number, y: number} = {x: this._rect.x, y: this._rect.y + this._rect.height};
let rightBottom: {x: number, y: number} = {x: this._rect.x + this._rect.width, y: this._rect.y + this._rect.height};
let rightTop: {x: number, y: number} = {x: this._rect.x + this._rect.width, y: this._rect.y};
return {
leftTop: leftTop,
leftBottom: leftBottom,
rightBottom: rightBottom,
rightTop: rightTop,
x: this._rect.x,
y: this._rect.y,
width: this._rect.width,
height: this._rect.height,
};
}
/** 更新父节点数据是否为空 */
public updateParentEmptyState() {
let parentNode = this.parentNode;
while (parentNode) {
if (!this.isDataEmpty) {
parentNode.isDataEmpty = false;
}else {
parentNode.calcEmptyState();
}
parentNode = parentNode.parentNode;
}
}
/** 计算空状态 */
public calcEmptyState() {
let isEmpty = true;
this._childLinkList.foreach2((value: QuadTreeNode<T>) => {
isEmpty = isEmpty && value.isDataEmpty;
if (!isEmpty) {
return true;
}
});
this.isDataEmpty = isEmpty;
}
}
/**
* 四叉树节点数据对象
* by longhui
* (c) copyright 2014 - 2035
* All Rights Reserved.
*/
export class QuadTreeNodeData<T> {
/** 对象集合 */
protected _targets: T[] = [];
constructor() {
}
/** 获取对象集合 */
public getTargets(): T[] {
return this._targets;
}
/** 从集合中移除对象 */
public removeTarget(target: T): boolean {
let index = this._targets.indexOf(target);
if (index < 0) {
return false;
}
this._targets.splice(index, 1);
}
/** 添加一个对象到集合中 */
public addTarget(target: T): void {
this._targets.push(target);
}
}
2、实现四叉树对象QuadTree
/**
* 四叉树（基于2D平面空间分割）数据结构
* 四叉树或四元树也被称为Q树（Q-Tree）。
* 四叉树广泛应用于图像处理、空间数据索引、2D中的快速碰撞检测、存储稀疏数据等
* 为提升性能
* 1、广度优先搜索
* 2、仅搜索叶节点
*/
export class QuadTree<T> {
/** 树的高度 */
protected _height: number;
/** 树的深度 */
protected _depth: number;
/** 根节点 */
protected _rootNode: QuadTreeNode<T>;
/** 矩形区域 */
protected _rect: Rectangle;
/** 广度搜索队列(仅包含叶节点) */
public breadthSearchQueue: Queue<QuadTreeNode<T>>;
/** 对象与叶节点的映射表 */
public targetNodeMap: HashTable<QuadTreeNode<T>>;
/**
* 构造函数
* @param rect 二维空间数据
* @param depth 树的深度
*/
constructor(rect: Rectangle, depth: number, targets?: T[]) {
this._rect = rect;
this._depth = depth;
this._height = this._depth;
this.breadthSearchQueue = new Queue<QuadTreeNode<T>>();
this.targetNodeMap = new HashTable<QuadTreeNode<T>>();
if (depth >= 0) {
this._rootNode = new QuadTreeNode<T>(this, null, rect, depth);
}
this.initBreadthSearchQueue();
}
/**
* 创建广度搜索队列
* 仅包含叶节点
*/
protected initBreadthSearchQueue(): void {
let node: QuadTreeNode<T>;
let findFromLeft = function(nodes: QuadTreeNode<T>[]) {
if (nodes.length <= 0) {
return;
}
let childsArr = [];
// 先遍历邻节点
for (let i = 0; i < nodes.length; i++) {
node = nodes[i];
if (node.isLeaf()) {
this.breadthSearchQueue.push(node);
}
childsArr = childsArr.concat(node.getChildsAsArray());
}
// 再访问子节点数组
findFromLeft(childsArr);
}.bind(this);
findFromLeft([this._rootNode]);
}
// /**
// * 绑定对象集合
// */
// public bindTargets(targets: T[]): void {
// for (let i = 0; i < targets.length; i++) {
// const target = targets[i];
// let node = this.find(target["x"], target["y"]);
// if (node) {
// this.targetNodeMap.insert(target["hashCode"], node, true);
// }else {
// console.debug(this, "未找到关联的节点1", target["x"], target["y"], this._rootNode);
// }
// }
// }
/**
* 获取对象所属节点
*/
public getTargetNode(target: T): QuadTreeNode<T> {
// LogUtils.debug(this, "状态表", target["x"], target["y"], this.targetNodeMap.get(target["hashCode"]));
return this.targetNodeMap.get(target["hashCode"]);
}
/**
* 获取所有对象合集
*/
public get targets(): T[] {
return this._rootNode.targets;
}
/**
* 获取树的高度
*/
public get height(): number {
return this._height;
}
/**
* 获取树的深度
*/
public get depth(): number {
return this._depth;
}
/**
* 搜索目标对象所在区域节点
* @param x 目标对象x坐标
* @param y 目标对象y坐标
* @param skipEmpty 是否忽略空数据节点
*/
public find(x: number, y: number, skipEmpty: boolean = false): QuadTreeNode<T> {
let node: QuadTreeNode<T> = null;
let findFromNode: Function = (pNode: QuadTreeNode<T>): QuadTreeNode<T> => {
if (!pNode) {
return null;
}
if (skipEmpty && pNode.isDataEmpty) {
return null;
}
if (!pNode.isContains(x, y)) {
return null;
}
if (pNode.isLeaf()) {
return pNode;
}
let leftChild = pNode.getLeftChild();
while (leftChild) {
node = findFromNode(leftChild);
if (node) {
return node;
}else {
leftChild = leftChild.nextNode;
}
}
};
// 从根节点开始查找
return findFromNode(this._rootNode);
}
/**
* 搜索圆形目标对象所在树根区域节点
* @param x 目标对象x坐标
* @param y 目标对象y坐标
* @param skipEmpty 是否忽略空数据节点
*/
public findNodesInCircle(x: number, y: number, radius: number, skipEmpty: boolean = false): QuadTreeNode<T>[] {
let nodes: QuadTreeNode<T>[] = [];
let findFromNode: Function = (pNode: QuadTreeNode<T>): QuadTreeNode<T> => {
if (!pNode) {
return null;
}
if (skipEmpty && pNode.isDataEmpty) {
return null;
}
if (pNode.isLeaf()) {
if (BaseTool.isPointsInCircle(x, y, radius, [pNode.leftTop.x, pNode.leftTop.y, pNode.leftBottom.x, pNode.leftBottom.y,
pNode.rightBottom.x, pNode.rightBottom.y, pNode.rightTop.x, pNode.rightTop.y])) {
nodes.push(pNode);
}
return;
}
let leftChild = pNode.getLeftChild();
while (leftChild) {
findFromNode(leftChild);
leftChild = leftChild.nextNode;
}
};
// 从根节点开始查找
findFromNode(this._rootNode);
return nodes;
}
/**
* 搜索矩形目标对象所在树根区域节点
* @param x 目标对象x坐标
* @param y 目标对象y坐标
* @param width 目标对象宽
* @param height 目标对象高
* @param skipEmpty 是否忽略空数据节点
*/
public findNodesInRect(x: number, y: number, width: number, height: number, skipEmpty: boolean = false): QuadTreeNode<T>[] {
let nodes: QuadTreeNode<T>[] = [];
let findFromNode: Function = (pNode: QuadTreeNode<T>): QuadTreeNode<T> => {
if (!pNode) {
return null;
}
if (skipEmpty && pNode.isDataEmpty) {
return null;
}
// if (pNode.isLeaf()) {
// if (BaseTool.isRectIntersect(x, y, width, height, pNode.rect.x, pNode.rect.y, pNode.rect.width, pNode.rect.height)) {
// nodes.push(pNode);
// }
// return;
// }
if (BaseTool.isRectIntersect(x, y, width, height, pNode.rect.x, pNode.rect.y, pNode.rect.width, pNode.rect.height)) {
if (pNode.isLeaf()) {
nodes.push(pNode);
}else {
let leftChild = pNode.getLeftChild();
while (leftChild) {
findFromNode(leftChild);
leftChild = leftChild.nextNode;
}
}
}else {
// console.log("不相交====", x, y, width, height, "///", pNode.rect.x, pNode.rect.y, pNode.rect.width, pNode.rect.height);
}
};
// 从根节点开始查找
findFromNode(this._rootNode);
return nodes;
}
/**
* 搜索凸多边形目标对象所在树根区域节点
* @param x 目标对象x坐标
* @param y 目标对象y坐标
* @param width 目标对象宽
* @param height 目标对象高
* @param skipEmpty 是否忽略空数据节点
*/
public findNodesInPolygon(polygonPoints: number[], skipEmpty: boolean = false): QuadTreeNode<T>[] {
let nodes: QuadTreeNode<T>[] = [];
let findFromNode: Function = (pNode: QuadTreeNode<T>): QuadTreeNode<T> => {
if (!pNode) {
return null;
}
if (skipEmpty && pNode.isDataEmpty) {
return null;
}
// if (pNode.isLeaf()) {
// if (BaseTool.isRectIntersect(x, y, width, height, pNode.rect.x, pNode.rect.y, pNode.rect.width, pNode.rect.height)) {
// nodes.push(pNode);
// }
// return;
// }
if (BaseTool.isPointsInRect(pNode.rect.x, pNode.rect.y, pNode.rect.width, pNode.rect.height, polygonPoints)) {
if (pNode.isLeaf()) {
nodes.push(pNode);
}else {
let leftChild = pNode.getLeftChild();
while (leftChild) {
findFromNode(leftChild);
leftChild = leftChild.nextNode;
}
}
}else {
// console.log("不相交====", x, y, width, height, "///", pNode.rect.x, pNode.rect.y, pNode.rect.width, pNode.rect.height);
}
};
// 从根节点开始查找
findFromNode(this._rootNode);
return nodes;
}
/**
* 搜索椭圆形目标对象所在树根区域节点
* @param cx 椭圆中心x坐标
* @param cy 椭圆中心y坐标
* @param rx 椭圆横半轴
* @param ry 椭圆纵半轴
* @param angle 旋转角度
* @param skipEmpty 是否忽略空数据节点
*/
public findNodesInEllipse(cx: number, cy: number, rx: number, ry: number, angle: number, skipEmpty: boolean = false): QuadTreeNode<T>[] {
let nodes: QuadTreeNode<T>[] = [];
let findFromNode: Function = (pNode: QuadTreeNode<T>): QuadTreeNode<T> => {
if (!pNode) {
return null;
}
if (skipEmpty && pNode.isDataEmpty) {
return null;
}
// if (pNode.isLeaf()) {
// if (BaseTool.isRectIntersect(x, y, width, height, pNode.rect.x, pNode.rect.y, pNode.rect.width, pNode.rect.height)) {
// nodes.push(pNode);
// }
// return;
// }
if (BaseTool.isRectIntersectEllipse(pNode.rect.x, pNode.rect.y, pNode.rect.width, pNode.rect.height, cx, cy, rx, ry, angle)) {
if (pNode.isLeaf()) {
nodes.push(pNode);
}else {
let leftChild = pNode.getLeftChild();
while (leftChild) {
findFromNode(leftChild);
leftChild = leftChild.nextNode;
}
}
}else {
// console.log("不相交====", x, y, width, height, "///", pNode.rect.x, pNode.rect.y, pNode.rect.width, pNode.rect.height);
}
};
// 从根节点开始查找
findFromNode(this._rootNode);
return nodes;
}
/**
* 对象坐标发生更新的通知
*/
public onTargetPosUpdate(target: T): void {
// let x = target["x"];
// let y = target["y"];
// let curNode = this.targetNodeMap.get(target["hashCode"]);
// if (curNode && curNode.isContains(x, y)) {
// return;
// }else {
// let node = this.find(x, y);
// if (node) {
// this.targetNodeMap.insert(target["hashCode"], node, true);
// this._onTargetNodeChanged(target, curNode, node);
// }else {
// console.debug(this, "未找到关联的节点2", x, y, this._rootNode);
// }
// }
}
/**
* 通知对象 节点发生切换
*/
public _onTargetNodeChanged(target: T, oldNode: QuadTreeNode<T>, newNode: QuadTreeNode<T>): void {
if (oldNode) {
oldNode.removeTarget(target);
}
if (newNode) {
newNode.addTarget(target);
}
if (target["onTreeNodeChanged"]) {
target["onTreeNodeChanged"](oldNode, newNode);
}
}
}
本文链接 游戏算法（2）：查找优化之四叉树的应用
相关文章 游戏算法（1）：实现AStar寻路算法
