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

成都創(chuàng)新互聯(lián)2013年至今，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目網(wǎng)站制作、成都網(wǎng)站設(shè)計(jì)網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元臺(tái)山做網(wǎng)站,已為上家服務(wù),為臺(tái)山各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:18982081108

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

QuadTree四叉樹顧名思義就是樹狀的數(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ù)，從而提高游戲刷新性能，

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

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

當(dāng)更多的對(duì)象被添加到四叉樹里時(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ì)四叉樹進(jìn)行實(shí)現(xiàn)：

主要代碼：（代碼是從整個(gè)四叉樹類里面拷貝出來(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;
}

文章標(biāo)題：JS實(shí)現(xiàn)的四叉樹算法詳解-創(chuàng)新互聯(lián)
標(biāo)題URL：http://weahome.cn/article/cdcgds.html