四叉樹是干什么的？
百度百科
四元樹又稱四叉樹是一種樹狀資料結構，在每一個節點上會有四個子區塊，四元樹常應用于二維空間資料的分析與分類， 它將資料區分成為四個象限，資料范圍可以是方形或矩形或其他任意形狀，
從定義我們可以看出重點資訊：
- 樹狀結構
- 四個區塊
- 分類
- 矩形
圖示講解
講解之前需要先說明一下四叉樹是用來做什么的，明白了原理才好理解它的行為，
使用四叉樹就是使用分類的方法，減少碰撞節點的個數，只取出與給定碰撞體相同區域或者壓在碰撞體所在區域邊上的物件，
- 將游戲螢屏分為四個區域，
- 插入物件
- 插入的物件超過了我們設定的閾值時，劃分
- 插入的物件再次超過了我們設定的閾值時，繼續分，
分析
插入
從上面的圖示我們可以很好理解四叉樹的原理，涉及的都是插入操作，
那么插入操作具體都做了什么呢？
從代碼中我們可以看出：
- 當插入第一個物件的時候只走了2；這個時候沒有子樹，所以不會走1，因為objects（管理的物件）的長度還沒有超過我們設定的閾值MAX_OBJECTS,所以也不會走3，
- 一直插入，當objects中的數量，超過了我們設定的閾值MAX_OBJECT,就會開始劃分，產生子樹，有了nodes，劃分之后將自己管理的節點插入到子樹中，再此之前，都不會走1，因為還沒有產生子樹，
- 劃分之后再次插入新物件，如果物件可以獲得對應的象限，就會走1 不會走2和3，如果沒有獲得對應的象限才會走2，3（沒有獲得的情況可能是你創建的物件在螢屏外，游戲中很多情況是敵人從螢屏外走進螢屏的，具體可參考我做的《星際迷航》或者《星際戰》游戲），
更新物件
我是把四插入作為了物件管理器使用，要不然物件也需要更新，所以有了這一步操作，如果不這樣你需要自己創建物件管理器，一個一個放進去，洗掉，通過四叉樹直接管理省了不少事情，
更新象限資訊，
這是一個遞回操作，更新象限做的事情比較多了，
-
檢查物件是否存活，如果死亡就回收，我這里使用了物件池，所以物件實作了poolAble介面，
-
判斷物件的所占區域是否在四叉樹的區域內
這里需要說明的是一個四叉樹本身的區域是它管理的四個象限這么大，也就是一個四叉樹管理四個象限
不在管理區域的話需要判斷當前this是否為根節點，如果是說明物件已經出屏了，（這個時候可以通過物件實作的isVisible介面來控制是否回收，因為不是所有在螢屏外的都要回收，比如要進入螢屏的敵人，是不可能回收的，所以需要自己用isVisible介面來控制），如果不是就將物件放入根節點，重新劃分， -
在管理區域內，就看看在四叉樹管理的哪個象限里，更新象限資訊，
如果沒有變化什么都不過，如果有變化，先判斷象限是否為-1，為什么會出現-1，也就是不在四個象限的任何一個象限？因為壓線了，此番操作后的結果如下圖，
根據給定矩形獲取物件串列
- 第一個是步長，用于獲取深度，當然深度越長，處理的時間越長，獲取的物件也精細，這個可以根據自己游戲的同屏四叉樹層級而定了，
- 如果通過obj的rect獲得物件所在象限如果獲得了對應的象限，用獲得的象限的四叉樹再獲取，如果壓線的話就需要將碰撞的兩個象限的內容都取出來，
- 回傳四叉樹中沒有分割象限的物件，
怎么用呢？
自然就是把要碰撞的物件傳給retrieve函式獲得需要碰撞的物件串列進行碰撞檢測了，
也就是文章靠頭說的：
使用四叉樹就目的是為了減少碰撞節點的個數，使用的是分類的方法，
至于用什么樣的碰撞檢測函式，不是四叉樹關心的事情，
至于用幾個四叉樹管理物件，也不是四叉樹關心的事情，
結語
想要demo的同學可以去我的微店或者官方creator商城購買《跨引擎游戲框架》原始碼，跟demo是一個專案，買過的同學請加我好友，群已經建好，有更新我會群里直接發包，
原始碼購買入口：
demo展示：
專案截圖：
框架的相關模塊教程可以到《我的專輯》游戲開發進階教程中獲取，
后續還會推出更多與框架有關的教程：如：戰斗框架，教學框架等等，并附帶完整的游戲實作（飛行射擊游戲為例，學會做飛行射擊游戲不是目的，目的是通過這一款游戲，你可以獲得做其他所有型別的游戲的思路），希望可以在不餓死自己的前提下幫助更過的朋友們快速找到開發思路，
長按下方二維碼，關注《微笑游戲》公眾號，獲取更多精彩內容，
歡迎掃碼關注公眾號《微笑游戲》，瀏覽更多內容，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/31107.html
標籤：其他
上一篇：JPS/JPS+ 尋路演算法
下一篇：游戲開發中的多語言處理