本文實例講述了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程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
