JS乞丐版四叉树(一)

常用场景

  • 图像处理
  • 空间数据索引
  • 2D 中的快速碰撞检测
  • 稀疏数据

以碰撞检测为例,对于平面上N个游戏对象,如果需要检测互相之间是否发生碰撞。
如果采用基本算法:每次需进行N(N-1)次比较,时间复杂度是O(n^2)。
四叉树是其中一种优化时间复杂度的算法,时间复杂度是O(nlog n)。
考虑下我们的使用场景,并不是每两个物体都需要进行碰撞检测,比如每一帧进行节点检测,但是两帧直接一个在屏幕右上方的物体和一个在屏幕左上方的物体之间按照移动速度明显是不会发生碰撞的,所以我们不需要对这两个物体进行碰撞检测。那么,我们可以把所有节点构建成一棵用于碰撞检测的树,将可能发生碰撞和不可能发生碰撞的节点区分开。

screen.png

两种方式比较:

search.png

如检测以下几个点的碰撞,普通碰撞:

四叉树就是每个父节点都具有四个子节点的树状数据结构。由于要区分屏幕上的物体,我们要将屏幕划分为四个区域,所以四叉树的四个节点正合适表示这四个区域。
 核心代码是当某一个区域内节点数目超出最大数限制的时候,对该区域分割成更小4个区域,四个区域我们记为 NorthEast区域 + NorthWest区域 + SouthEast区域 + SouthWest左下区域。 如下图,1,2,3区域新插入点后不超过每个单位区域最大数限制,4超过,则进行再次划分。

quardTree.png

   insert (point) {
        // 先判断点是否在区域内
        if (!this.boundary.contains(point)) {
            return 
        }

        // 超出容量限制时,分成更小的四个区域
        if (this.points.length < this.capacity) {
            this.points.push(point)
            return true
        } else {
            if (!this.divided) {
                this.subdivide()
                this.divided = true
            }
            if (this.northest.insert(point)) {
                return true
            }
            
            if (this.northwest.insert(point)) {
                return true
            }

            if (this.southest.insert(point)) {
                return true
            }

            if (this.southwest.insert(point)) {
                return true
            }
        }
    }
}

其中分割区域代码:

    subdivide () {
        let x = this.boundary.x
        let y = this.boundary.y
        let w = this.boundary.w
        let h = this.boundary.h

        let ne = new Rectangle(x + w / 2, y - h / 2, w / 2, h / 2)
        this.northest = new QuardTree(ne, this.capacity)
        let nw = new Rectangle(x - w / 2, y - h / 2, w / 2, h / 2)
        this.northwest = new QuardTree(ne, this.capacity)
        let se = new Rectangle(x + w / 2, y + h / 2, w / 2, h / 2)
        this.southest = new QuardTree(se, this.capacity)
        let sw = new Rectangle(x - w / 2, y + h / 2, w / 2, h / 2)
        this.southwest = new QuardTree(sw, 4 )
    }

依次添加节点,得到四叉树。
对四叉树的展示我们用 p5.js来做,自顶向下展示树。

show () {
        stroke(255)
        strokeWeight(1)
        noFill()
        
        rect(this.boundary.x, this.boundary.y, this.boundary.w * 2, this.boundary.h * 2)
        rectMode(CENTER)
        if (this.divided) {
            this.northest.show()
            this.northwest.show()
            this.southest.show()
            this.southwest.show()
        }
        for (let p of this.points) {
            strokeWeight(4)
            point(p.x, p.y)
        }
    }

绘制结果

image.png

完整代码

代码地址

参考

wiki

比较好的轮子

quadtree

未完...

评论

暂无评论