本文主要介绍四叉树的应用场景和实现。

本文链接  游戏算法（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寻路算法