这篇文章主要介绍了JS实现的四叉树算法,简单分析了四叉树的相关概念、原理、实现方法及操作注意事项,需要的朋友可以参考下

本文实例讲述了JS实现的四叉树算法。分享给大家供大家参考,具体如下:

最近在看canvas动画方面教程,里面提到了采用四叉树检测碰撞。之前也看到过四叉树这个名词,但是一直不是很懂。于是就又找了一些四叉树方面的资料看了看,做个笔记,就算日后忘了,也可以回来看看。

QuadTree四叉树顾名思义就是树状的数据结构,其每个节点有四个孩子节点,可将二维平面递归分割子区域。QuadTree常用于空间数据库索引,3D的椎体可见区域裁剪,甚至图片分析处理,我们今天介绍的是QuadTree最常被游戏领域使用到的碰撞检测。采用QuadTree算法将大大需要测试碰撞的次数,从而提高游戏刷新性能,

四叉树很简单,就是把一块2d的区域,等分成4份,如下图:  我们把4块区域从右上象限开始编号, 逆时针。

四叉树起始于单节点。对象会被添加到四叉树的单节点上。

当更多的对象被添加到四叉树里时,它们最终会被分为四个子节点。(我是这么理解的:下面的图片不是分为四个区域吗,每个区域就是一个孩子或子节点)然后每个物体根据他在2D空间的位置而被放入这些子节点中的一个里。任何不能正好在一个节点区域内的物体会被放在父节点。(这点我不是很理解,就这幅图来说,那根节点的子节点岂不是有五个节点了。)

如果有更多的对象被添加进来,那么每个子节点要继续划分(成四个节点)。

正如你看到的,每个节点仅包括几个物体。这样我们就可以明白前面所说的规则,例如,左上角节点里的物体是不可能和右下角节点里的物体碰撞的。所以我们也就没必要运行消耗很多资源的碰撞检测算法来检验他们之间是否会发生碰撞。

下面我们对四叉树进行实现:

主要代码:(代码是从整个四叉树类里面拷贝出来的,所以带有this,大家不要无视就好,末尾附有完整的代码)

function QuadTree(boundBox, lvl) {
  var maxObjects = 10;
  this.bounds = boundBox || {
    x: 0,
    y: 0,
    width: 0,
    height: 0
  };
  var objects = [];
  this.nodes = [];
  var level = lvl || 0;
  var maxLevels = 5;
}

maxObjects是每个节点能容纳的最多对象超过 则分割4个节点, 我们并不是事先就分好格子, 而是在插入对象的时候才进行划分。

maxLevels是 四叉树的最大层数 超过 则不再划分 从根节点开始 最多6 层。

level: 当前层数

objects: 当前节点内的待检测的对象。

bounds:当前节点所表示的2d区域的范围

nodes: 4个子节点队列。

四叉树每个节点的面积可以为任意形状。然后,我们会使用五个四叉树里会用到的方法,分别为:clear,split,getIndex,insert和retrieve。

function clear() {
    objects = [];
    for (var i = 0; i < this.nodes.length; i++) {
      this.nodes[i].clear();
    }
    this.nodes = [];
  };

Clear函数,是通过循环来清除四叉树所有节点的所有对象。

function split() {
    // Bitwise or [html5rocks]
    var subWidth = (this.bounds.width / 2) | 0;
    var subHeight = (this.bounds.height / 2) | 0;
    this.nodes[0] = new QuadTree({
      x: this.bounds.x + subWidth,
      y: this.bounds.y,
      width: subWidth,
      height: subHeight
    }, level+1);
    this.nodes[1] = new QuadTree({
      x: this.bounds.x,
      y: this.bounds.y,
      width: subWidth,
      height: subHeight
    }, level+1);
    this.nodes[2] = new QuadTree({
      x: this.bounds.x,
      y: this.bounds.y + subHeight,
      width: subWidth,
      height: subHeight
    }, level+1);
    this.nodes[3] = new QuadTree({
      x: this.bounds.x + subWidth,
      y: this.bounds.y + subHeight,
      width: subWidth,
      height: subHeight
    }, level+1);
}

Split 方法,就是用来将节点分成相等的四份面积,并用新的边界来初始化四个新的子节点。

function getIndex(obj) {
    var index = -1;
    var verticalMidpoint = this.bounds.x + this.bounds.width / 2;
    var horizontalMidpoint = this.bounds.y + this.bounds.height / 2;
    // Object can fit completely within the top quadrant
    var topQuadrant = (obj.y < horizontalMidpoint && obj.y + obj.height < horizontalMidpoint);
    // Object can fit completely within the bottom quandrant
    var bottomQuadrant = (obj.y > horizontalMidpoint);
    // Object can fit completely within the left quadrants
    if (obj.x < verticalMidpoint &&
        obj.x + obj.width < verticalMidpoint) {
      if (topQuadrant) {
        index = 1;
      }
      else if (bottomQuadrant) {
        index = 2;
      }
    }
    // Object can fix completely within the right quandrants
    else if (obj.x > verticalMidpoint) {
      if (topQuadrant) {
        index = 0;
      }
      else if (bottomQuadrant) {
        index = 3;
      }
    }
    return index;
};

getIndex 方法是个四叉树的辅助方法,在四叉树里,他决定了一个节点的归属,通过检查节点属于哪个象限。(最上面第一幅图不是逆时针在一个面积里划分了四块面积,上面标示了他们的序号,这个方法就是算在一个父节点里他的子节点的序号)

比如当前区域是Rectange(0, 0, 600, 600) 待检测矩形是Rectangel(0, 0, 30, 30) 那么他就在左上象限 index = 1 如果是Rectange(400, 400, 30, 30) 那么他就在右下象限 index = 3

function insert(obj) {
    if (typeof obj === "undefined") {
      return;
    }
    if (obj instanceof Array) {
      for (var i = 0, len = obj.length; i < len; i++) {
        this.insert(obj[i]);
      }
      return;
    }
    if (this.nodes.length) {
      var index = this.getIndex(obj);
      // Only add the object to a subnode if it can fit completely
      // within one
      if (index != -1) {
        this.nodes[index].insert(obj);
        return;
      }
    }
    objects.push(obj);
    // Prevent infinite splitting
    if (objects.length > maxObjects && level < maxLevels) {
      if (this.nodes[0] == null) {
        this.split();
      }
      var i = 0;
      while (i < objects.length) {
        var index = this.getIndex(objects[i]);
        if (index != -1) {
          this.nodes[index].insert((objects.splice(i,1))[0]);
        }
        else {
          i++;
        }
      }
    }
};

每次插入一个对象 我们都先看看当前节点有没有子节点 如果有 我们就插入子节点。 一直检测到他没有子节点为止 我们就把对象插入到这个节点, 如果这个节点的对象数量 > 10个 并且当前节点的层数 < MAX_LEVELS 我们就把节点继续划分4个子节点。 然后把当前对象循环 删除 并插入子节点。如果对象在中心线上,getIndex会返回-1, 所以这些对象会入到父节点上面。

一旦对象添加上后,要看看这个节点会不会,可以通过检查对象被加入节点后有没有超过一个节点最大容纳对象的数量。起源于节点可以插入任何对象,这个对象只要符合子节点都可以被加入。否则就加入到父节点。

function retrieve(returnedObjects, obj) {
    if (typeof obj === "undefined") {
      console.log("UNDEFINED OBJECT");
      return;
    }
    var index = this.getIndex(obj);
    if (index != -1 && this.nodes.length) {
      this.nodes[index].findObjects(returnedObjects, obj);
    }
    for (var i = 0, len = objects.length; i < len; i++) {
      returnedObjects.push(objects[i]);
    }
    return returnedObjects;
};

最后一个四叉树的方法就是 retrieve 方法,他返回了与指定节点可能发生碰撞的所有节点(就是不停寻找与所给节点在同样象限的节点)。这个方法成倍的碰撞检测数量。

四叉树的代码就到这里为止了。

完整的代码如下:

完整的代码中retrieve就是findObjects。

/**
 * QuadTree object.
 *
 * The quadrant indexes are numbered as below:
 *   |
 * 1 | 0
 * ----+----
 * 2 | 3
 *   |
 */
function QuadTree(boundBox, lvl) {
  var maxObjects = 10;
  this.bounds = boundBox || {
    x: 0,
    y: 0,
    width: 0,
    height: 0
  };
  var objects = [];
  this.nodes = [];
  var level = lvl || 0;
  var maxLevels = 5;
  /*
   * Clears the quadTree and all nodes of objects
   */
  this.clear = function() {
    objects = [];
    for (var i = 0; i < this.nodes.length; i++) {
      this.nodes[i].clear();
    }
    this.nodes = [];
  };
  /*
   * Get all objects in the quadTree
   */
  this.getAllObjects = function(returnedObjects) {
    for (var i = 0; i < this.nodes.length; i++) {
      this.nodes[i].getAllObjects(returnedObjects);
    }
    for (var i = 0, len = objects.length; i < len; i++) {
      returnedObjects.push(objects[i]);
    }
    return returnedObjects;
  };
  /*
   * Return all objects that the object could collide with
   */
  this.findObjects = function(returnedObjects, obj) {
    if (typeof obj === "undefined") {
      console.log("UNDEFINED OBJECT");
      return;
    }
    var index = this.getIndex(obj);
    if (index != -1 && this.nodes.length) {
      this.nodes[index].findObjects(returnedObjects, obj);
    }
    for (var i = 0, len = objects.length; i < len; i++) {
      returnedObjects.push(objects[i]);
    }
    return returnedObjects;
  };
  /*
   * Insert the object into the quadTree. If the tree
   * excedes the capacity, it will split and add all
   * objects to their corresponding nodes.
   */
  this.insert = function(obj) {
    if (typeof obj === "undefined") {
      return;
    }
    if (obj instanceof Array) {
      for (var i = 0, len = obj.length; i < len; i++) {
        this.insert(obj[i]);
      }
      return;
    }
    if (this.nodes.length) {
      var index = this.getIndex(obj);
      // Only add the object to a subnode if it can fit completely
      // within one
      if (index != -1) {
        this.nodes[index].insert(obj);
        return;
      }
    }
    objects.push(obj);
    // Prevent infinite splitting
    if (objects.length > maxObjects && level < maxLevels) {
      if (this.nodes[0] == null) {
        this.split();
      }
      var i = 0;
      while (i < objects.length) {
        var index = this.getIndex(objects[i]);
        if (index != -1) {
          this.nodes[index].insert((objects.splice(i,1))[0]);
        }
        else {
          i++;
        }
      }
    }
  };
  /*
   * Determine which node the object belongs to. -1 means
   * object cannot completely fit within a node and is part
   * of the current node
   */
  this.getIndex = function(obj) {
    var index = -1;
    var verticalMidpoint = this.bounds.x + this.bounds.width / 2;
    var horizontalMidpoint = this.bounds.y + this.bounds.height / 2;
    // Object can fit completely within the top quadrant
    var topQuadrant = (obj.y < horizontalMidpoint && obj.y + obj.height < horizontalMidpoint);
    // Object can fit completely within the bottom quandrant
    var bottomQuadrant = (obj.y > horizontalMidpoint);
    // Object can fit completely within the left quadrants
    if (obj.x < verticalMidpoint &&
        obj.x + obj.width < verticalMidpoint) {
      if (topQuadrant) {
        index = 1;
      }
      else if (bottomQuadrant) {
        index = 2;
      }
    }
    // Object can fix completely within the right quandrants
    else if (obj.x > verticalMidpoint) {
      if (topQuadrant) {
        index = 0;
      }
      else if (bottomQuadrant) {
        index = 3;
      }
    }
    return index;
  };
  /*
   * Splits the node into 4 subnodes
   */
  this.split = function() {
    // Bitwise or [html5rocks]
    var subWidth = (this.bounds.width / 2) | 0;
    var subHeight = (this.bounds.height / 2) | 0;
    this.nodes[0] = new QuadTree({
      x: this.bounds.x + subWidth,
      y: this.bounds.y,
      width: subWidth,
      height: subHeight
    }, level+1);
    this.nodes[1] = new QuadTree({
      x: this.bounds.x,
      y: this.bounds.y,
      width: subWidth,
      height: subHeight
    }, level+1);
    this.nodes[2] = new QuadTree({
      x: this.bounds.x,
      y: this.bounds.y + subHeight,
      width: subWidth,
      height: subHeight
    }, level+1);
    this.nodes[3] = new QuadTree({
      x: this.bounds.x + subWidth,
      y: this.bounds.y + subHeight,
      width: subWidth,
      height: subHeight
    }, level+1);
  };
}

参考文章:

Quick Tip: Use Quadtrees to Detect Likely Collisions in 2D Space

更多关于JavaScript相关内容感兴趣的读者可查看本站专题:《JavaScript数算用法总结》、《JavaScript数据结构与算法总结》、《JavaScript数组操作总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与总结》、《JavaScript查找算法总结》及《JavaScript错误与调试总结》

希望本文所述对大家JavaScript程序设计有所帮助。

最新资讯
TCL科技:前三季度净利润20.25亿元,同比下降21.42%

TCL科技:前三季度净利

TCL科技发布三季报,前三季度净利润20.25亿元,同比下降21
iPhone 12除了性价比和 5G,它还剩下什么?

iPhone 12除了性价比

相信很多人都已经收到不久前订购的iPhone12,有些应该也
中兴通讯:第三季度实现净利润8.55亿元,同比下降67.83%

中兴通讯:第三季度实现

中兴通讯公告,第三季度实现净利润8.55亿元,同比下降67.8
中兴通讯:拟以发行股份方式购买中兴微电子18.8219%股权

中兴通讯:拟以发行股份

中兴通讯发布公告称,拟以发行股份方式购买恒健欣芯、汇
携程升级会员权益体系 年轻用户占比超7成

携程升级会员权益体系

携程近期宣布再次升级会员权益体系,全新的黑钻会员正式
余承东:今年压力很大睡眠不足 正想尽办法让业务继续

余承东:今年压力很大睡

华为将于10月30日举行Mate40系列国内发布会,今日华为终
最新文章
详解Vue的ref特性的使用

详解Vue的ref特性的使

这篇文章主要介绍了详解Vue的ref特性的使用,文中通过
vue学习笔记之slot插槽基本用法实例分析

vue学习笔记之slot插

这篇文章主要介绍了vue学习笔记之slot插槽基本用法,结
vue跳转方式(打开新页面)及传参操作示例

vue跳转方式(打开新页

这篇文章主要介绍了vue跳转方式(打开新页面)及传参操作,
vue学习笔记之过滤器的基本使用方法实例分析

vue学习笔记之过滤器

这篇文章主要介绍了vue学习笔记之过滤器的基本使用方
js获取本日、本周、本月的时间代码

js获取本日、本周、本

本篇文章给大家分享的内容是利用js如何获取本日、本周
node crawler如何添加promise支持

node crawler如何添加

这篇文章主要介绍了node crawler如何添加promise支持,