快捷導(dǎo)航

JS實(shí)現(xiàn)的四叉樹(shù)算法詳解

更新時(shí)間：2018年12月21日 10:00:38 作者：huansky

這篇文章主要介紹了JS實(shí)現(xiàn)的四叉樹(shù)算法,簡(jiǎn)單分析了四叉樹(shù)的相關(guān)概念、原理、實(shí)現(xiàn)方法及操作注意事項(xiàng),需要的朋友可以參考下

本文實(shí)例講述了JS實(shí)現(xiàn)的四叉樹(shù)算法。分享給大家供大家參考，具體如下：

最近在看canvas動(dòng)畫(huà)方面教程，里面提到了采用四叉樹(shù)檢測(cè)碰撞。之前也看到過(guò)四叉樹(shù)這個(gè)名詞，但是一直不是很懂。于是就又找了一些四叉樹(shù)方面的資料看了看，做個(gè)筆記，就算日后忘了，也可以回來(lái)看看。

QuadTree四叉樹(shù)顧名思義就是樹(shù)狀的數(shù)據(jù)結(jié)構(gòu)，其每個(gè)節(jié)點(diǎn)有四個(gè)孩子節(jié)點(diǎn)，可將二維平面遞歸分割子區(qū)域。QuadTree常用于空間數(shù)據(jù)庫(kù)索引，3D的椎體可見(jiàn)區(qū)域裁剪，甚至圖片分析處理，我們今天介紹的是QuadTree最常被游戲領(lǐng)域使用到的碰撞檢測(cè)。采用QuadTree算法將大大減少需要測(cè)試碰撞的次數(shù)，從而提高游戲刷新性能，

四叉樹(shù)很簡(jiǎn)單，就是把一塊2d的區(qū)域，等分成4份,如下圖: 我們把4塊區(qū)域從右上象限開(kāi)始編號(hào)，逆時(shí)針。

四叉樹(shù)起始于單節(jié)點(diǎn)。對(duì)象會(huì)被添加到四叉樹(shù)的單節(jié)點(diǎn)上。

當(dāng)更多的對(duì)象被添加到四叉樹(shù)里時(shí)，它們最終會(huì)被分為四個(gè)子節(jié)點(diǎn)。（我是這么理解的：下面的圖片不是分為四個(gè)區(qū)域嗎，每個(gè)區(qū)域就是一個(gè)孩子或子節(jié)點(diǎn)）然后每個(gè)物體根據(jù)他在2D空間的位置而被放入這些子節(jié)點(diǎn)中的一個(gè)里。任何不能正好在一個(gè)節(jié)點(diǎn)區(qū)域內(nèi)的物體會(huì)被放在父節(jié)點(diǎn)。（這點(diǎn)我不是很理解，就這幅圖來(lái)說(shuō)，那根節(jié)點(diǎn)的子節(jié)點(diǎn)豈不是有五個(gè)節(jié)點(diǎn)了。）

如果有更多的對(duì)象被添加進(jìn)來(lái)，那么每個(gè)子節(jié)點(diǎn)要繼續(xù)劃分（成四個(gè)節(jié)點(diǎn)）。

正如你看到的，每個(gè)節(jié)點(diǎn)僅包括幾個(gè)物體。這樣我們就可以明白前面所說(shuō)的規(guī)則，例如，左上角節(jié)點(diǎn)里的物體是不可能和右下角節(jié)點(diǎn)里的物體碰撞的。所以我們也就沒(méi)必要運(yùn)行消耗很多資源的碰撞檢測(cè)算法來(lái)檢驗(yàn)他們之間是否會(huì)發(fā)生碰撞。

下面我們對(duì)四叉樹(shù)進(jìn)行實(shí)現(xiàn)：

主要代碼：（代碼是從整個(gè)四叉樹(shù)類里面拷貝出來(lái)的，所以帶有this，大家不要無(wú)視就好，末尾附有完整的代碼）

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是每個(gè)節(jié)點(diǎn)能容納的最多對(duì)象超過(guò) 則分割4個(gè)節(jié)點(diǎn), 我們并不是事先就分好格子，而是在插入對(duì)象的時(shí)候才進(jìn)行劃分。

maxLevels是四叉樹(shù)的最大層數(shù) 超過(guò) 則不再劃分從根節(jié)點(diǎn)開(kāi)始最多6 層。

level：當(dāng)前層數(shù)

objects: 當(dāng)前節(jié)點(diǎn)內(nèi)的待檢測(cè)的對(duì)象。

bounds：當(dāng)前節(jié)點(diǎn)所表示的2d區(qū)域的范圍

nodes: 4個(gè)子節(jié)點(diǎn)隊(duì)列。

四叉樹(shù)每個(gè)節(jié)點(diǎn)的面積可以為任意形狀。然后，我們會(huì)使用五個(gè)四叉樹(shù)里會(huì)用到的方法，分別為：clear,split,getIndex,insert和retrieve。

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

Clear函數(shù)，是通過(guò)循環(huán)來(lái)清除四叉樹(shù)所有節(jié)點(diǎn)的所有對(duì)象。

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 方法，就是用來(lái)將節(jié)點(diǎn)分成相等的四份面積，并用新的邊界來(lái)初始化四個(gè)新的子節(jié)點(diǎn)。

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 方法是個(gè)四叉樹(shù)的輔助方法，在四叉樹(shù)里，他決定了一個(gè)節(jié)點(diǎn)的歸屬，通過(guò)檢查節(jié)點(diǎn)屬于哪個(gè)象限。（最上面第一幅圖不是逆時(shí)針在一個(gè)面積里劃分了四塊面積，上面標(biāo)示了他們的序號(hào)，這個(gè)方法就是算在一個(gè)父節(jié)點(diǎn)里他的子節(jié)點(diǎn)的序號(hào)）

比如當(dāng)前區(qū)域是Rectange(0, 0, 600, 600) 待檢測(cè)矩形是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++;
        }
      }
    }
};

每次插入一個(gè)對(duì)象我們都先看看當(dāng)前節(jié)點(diǎn)有沒(méi)有子節(jié)點(diǎn) 如果有我們就插入子節(jié)點(diǎn)。一直檢測(cè)到他沒(méi)有子節(jié)點(diǎn)為止我們就把對(duì)象插入到這個(gè)節(jié)點(diǎn)，如果這個(gè)節(jié)點(diǎn)的對(duì)象數(shù)量 > 10個(gè) 并且當(dāng)前節(jié)點(diǎn)的層數(shù) < MAX_LEVELS 我們就把節(jié)點(diǎn)繼續(xù)劃分4個(gè)子節(jié)點(diǎn)。然后把當(dāng)前對(duì)象循環(huán) 刪除并插入子節(jié)點(diǎn)。如果對(duì)象在中心線上，getIndex會(huì)返回-1，所以這些對(duì)象會(huì)被插入到父節(jié)點(diǎn)上面。

一旦對(duì)象添加上后，要看看這個(gè)節(jié)點(diǎn)會(huì)不會(huì)分裂，可以通過(guò)檢查對(duì)象被加入節(jié)點(diǎn)后有沒(méi)有超過(guò)一個(gè)節(jié)點(diǎn)最大容納對(duì)象的數(shù)量。分裂起源于節(jié)點(diǎn)可以插入任何對(duì)象，這個(gè)對(duì)象只要符合子節(jié)點(diǎn)都可以被加入。否則就加入到父節(jié)點(diǎn)。

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;
};

最后一個(gè)四叉樹(shù)的方法就是 retrieve 方法，他返回了與指定節(jié)點(diǎn)可能發(fā)生碰撞的所有節(jié)點(diǎn)（就是不停尋找與所給節(jié)點(diǎn)在同樣象限的節(jié)點(diǎn)）。這個(gè)方法成倍的減少碰撞檢測(cè)數(shù)量。

四叉樹(shù)的代碼就到這里為止了。

完整的代碼如下：

完整的代碼中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

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)組操作技巧總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》

希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: