擷取更多筆記和源碼
公衆号:CocosCreator筆記
四叉樹原理本人就不贅述了，很多前輩都有詳細的講解
首先說明下四叉樹并不是一個碰撞引擎，它隻是一種減少碰撞候選者的算法，是以在利用四叉樹得到碰撞候選元素後，還需要去檢測這些候選元素與目标元素是否發生碰撞
2D中是四叉樹，3D中則對應的為八叉樹
項目（微信小遊戲《宇宙少女》）中實測：
同屏極限情況下，可碰撞元素為：
200左右子彈+70左右怪物+若幹buff+玩家
碰撞關系為：
子彈和怪物碰撞
特定怪物和其他怪物碰撞反彈
玩家和怪物碰撞
玩家和buff碰撞
使用cocos的碰撞系統，在H5表現良好，微信小遊戲的Android平台也還可以，但是在ios平台上，FPS隻有20+
使用四叉樹做空間規劃，對子彈做進一步的優化，減少碰撞元素
碰撞檢測使用圓圓碰撞和圓矩碰撞，放棄了pow()和sqrt()方法， 其相對于加減乘除會消耗更多的CPU（之前在QQ群讨論過）
改良後的碰撞檢測在微信小遊戲的Android平台性能良好，IOS平台的FPS也達到了50+
項目中使用每幀重建四叉樹，當然也可以自己維護四叉樹中碰撞元素的位置
1四叉樹概念
四叉樹（quad-tree）是一種資料結構，是一種每個節點最多有四個子樹的資料結構。四叉樹是在二維圖檔中定位像素的唯一适合的算法。因為二維空間（圖經常被描述的方式）中，平面像素可以重複的被分為四部分，樹的深度由圖檔、計算機記憶體和圖形的複雜度決定。四叉樹可以用來在資料庫中放置和定位檔案（稱作記錄或鍵）。這一算法通過不停的把要查找的記錄分成4部分來進行比對查找直到僅剩下一條記錄為止。
2空間規劃
遊戲程式設計模式-空間分區
将對象存儲在根據位置組織的資料結構中來高效地定位它們。 你有一組對象（可能還挺多），将對象存儲在一個根據對象位置來組織的資料結構中，該資料結構可以讓你高效查詢位于或靠近某處的對象。當對象位置改變時，更新并繼續維護該空間資料對象。用更複雜的資料結構（空間）來換取大量查詢時的性能優化（時間）。
部落格園中一篇講解詳細的blog
https://www.cnblogs.com/xin-lover/p/12216053.html
廣告
遊戲程式設計模式
作者：[美]Robert Nystrom（尼斯卓姆）
京東
3
quadtree-js
在GitHub上找到的一個前輩實作的四叉樹：
https://github.com/timohausmann/quadtree-js
并提供了兩個線上示範的demo，其中紅色為四叉樹節點，空白方塊為四叉樹中的元素，灰色方塊為滑鼠的位置，即目标元素，綠色方塊為碰撞候選元素
1.手動添加靜态對象并檢視四叉樹拆分：
https://timohausmann.de/quadtree.js/simple.html
2.在持續運動的對象中檢視四叉樹拆分：
https://timohausmann.de/quadtree.js/dynamic.html
4使用方法
1.引入quadtree.js
①通過代碼引入：
import * as Quadtree from "../R-framework/quadtree.js";
②插件引入：
将quadtree.js檔案導入編輯器的時候選擇為插件
2.建立四叉樹
區域為整個螢幕
let myTree = new Quadtree({ x: -cc.winSize.width / 2, y: -cc.winSize.height / 2, width: cc.winSize.width / 2, height: cc.winSize.height / 2 });
3.插入元素
參數為元素的左下角坐标及其寬高
myTree.insert({ x: 200, y: 150, width: 20, height: 20 });
4.檢索元素
參數為目标元素的左下角坐标及其寬高
傳回值為碰撞候選元素數組
let elements = myTree.retrieve({ x: 150, y: 100, width: 20, height: 20 });
5.碰撞檢測
在得到碰撞候選元素後，需要檢測是否與目标元素發生碰撞，檢測的方法可以用cocos的碰撞元件，也可以根據項目需求定制碰撞檢測
6.清除四叉樹
檢測完畢後，需要清除四叉樹中的元素，以友善下次繼續檢測
myTree.clear();
或者維護四叉樹空間中碰撞元素的位置