[ECS架構系列]-與四叉樹的一次結合（2）

前言

大家好，我IT俠又雙叒叕來了，上一篇文章說了下ECS架構在H5下是如何使用的。本篇文章就來聊聊主角-四叉樹。

還是在開頭說一下：

不了解四叉樹的可以自行查閱一下相關資料。因為篇幅問題，IT俠會下方簡單的介紹下。
因為demo是基于ECS架構，是以如果不了解ECS架構的話，可以看看我的ECS架構系列文章，擷取我已經開源的ECS架構。或者掃文末的二維碼聯系我，給我“加個雞腿”支援一下！19.9 交個朋友。

正文

最終效果

先給大家看看demo運作起來的效果，看看四叉樹在對象很多的情況下的威力

每一個"田字"矩形是一個4叉樹節點，友善調試的使用
高亮黃色的就是需要檢查是否與主角發生碰撞的塊
高亮紫色的就是目前和主角發生碰撞的塊

[ECS架構系列]-與四叉樹的一次結合（2）

生成了超級多塊後四叉樹的表現

[ECS架構系列]-與四叉樹的一次結合（2）

最後是關閉了調試線後的效果

[ECS架構系列]-與四叉樹的一次結合（2）

四叉樹

四叉樹（quad-tree）是一種資料結構，是一種每個節點最多有四個子樹的資料結構。四叉樹常應用于二維空間資料的分析與分類。是以把四叉樹應用在二維的有效率之碰撞偵測上是非常适合的。

代碼實作

源碼裡的方法我就不一一列舉出來了，因為四叉樹的實作不是本文的重點，隻介紹下四叉樹構造函數，還有包含哪些方法，以及方法的簡單解釋。github上開源很多四叉樹的實作，如果想深入了解可以自行查閱學習。

constructor(bounds: IBounds, maxObjects?: number, maxLevels?: number, level?: number,location?:number,parent?:QuadTree) {
        // 樹節點的邊界（包圍盒）
        this.bounds = bounds; 
        // 節點上最多存放物體的數量，為了測試預設設定為3，具體設定開發者可以自行決定
        this.maxObjects = maxObjects || 3; 
        // 4叉樹的最大層級
        this.maxLevels = maxLevels || 4; 
        // 目前節點在樹中的層級
        this.level = level || 0;
        // 目前節點上所有對象
        this.objs = []; 
        //4個象限(節點)，如果該節點上的對象超過設定的最大值後就進行分裂
        this.nodes = []; 
        //标記一下目前節點是那個象限
        this.location = location;
        // 目前節點的父節點，友善後續删除子樹
        this.parent = parent || null;
    }

四叉樹類有以下成員方法組成：

getIndex 傳回目前對象在哪些象限上
insert 将一個對象加入到目前節點上
clear 清空樹上所有節點和節點上的對象
recovery 如果一個子節點上沒有任何對象，那麼進行一次初始化
split分裂子樹節點，生成4個葉子節點（象限）
retrieve 擷取樹上可能與指定對象發生碰撞的對象
getBounds 擷取所有節點的包圍盒，友善調試
toJSON 轉成json格式，友善調試輸出樹資訊

ECS中使用四叉樹

當有Canvas元件的實體産生時候，捕獲該實體，建立一個四叉樹,根節點包圍盒就用canvas節點的位置和寬高。然後将四叉樹對象儲存到ecs對象上友善其他系統通路。

_canvas.on("Canvas", function (e) {
            //擷取Canvas元件上的canvas屬性
            //該屬性 儲存的就是canvas對象
            let canvas = e.Canvas.canvas;
            // 建立一個四叉樹
            toy.qt = new toy.QuadTree(
                {
                    x: canvas.width / 2,
                    y: canvas.height / 2,
                    width: canvas.width,
                    height: canvas.height
                });
        });

接下來寫一個系統"關心一下"帶有 “Mob”,“Appearance”,“Props” 這3個元件的實體的産生。因為有這3個元件的實體我們認定是一個怪物,怪物會和主角發生碰撞，是以需要放進四叉樹中等待提取。

調用四叉樹執行個體上的 insert 方法把怪物的包圍盒和怪物實體一起打包到一個對象上儲存進四叉樹上的節點中。

_character.on(["Mob","Appearance","Props"],function(ent){
              //調用四叉樹執行個體上的 insert 方法
               toy.qt.insert({
                   _node:ent,
                   width:ent.Props.props.width,
                   height:ent.Props.props.height,
                   x:ent.Props.props.x,
                   y:ent.Props.props.y
               });
            
        });

現在怪物都被放進了四叉樹上，接着我們需要寫一個使用者輸入系統，監聽玩家控制主角移動等事件。這裡用的是 hammer.js庫來實作。

定義一個使用者輸入系統,該系統關心"LocalControl",“Props”,“Node”,“Character” 元件。有這4個元件的實體就是我們的主角實體。之後分别監聽 panstart(開始觸摸螢幕) ,panmove(移動手指), panend (手擡起) 這3個事件。

let _userInput = toy.system("userInputSystem",101);
            
            _userInput.on(["LocalControl","Props","Character","Node"],function(ent){
                let props = ent.Props.props;

                let canvasEnt = toy.getFirstEnt("Canvas");
                if(!canvasEnt){
                    return;
                }
               
                let mc = new Hammer.Manager(canvasEnt.Canvas.canvas)
                // pan的距離判斷為0 手指不限定
                mc.add(new Hammer.Pan({threshold:0,pointers:0}))
                
                mc.on("panstart",function(ev){
                    props.isTouch = true;
                    let rect = canvasEnt.Canvas.canvas.getBoundingClientRect();

                    props.x = props.lastX = ev.center.x - rect.left;
                    props.y = props.lastY = ev.center.y - rect.top;

                    toy.__output.innerHTML = JSON.stringify(props, null, 4);

                  
                });


                mc.on("panmove", function onPanMove(ev) {
                    toy.comOnce("RecoverColor");
                    props.lastX = props.lastX;
                    props.lastY = props.lastY;

                    props.x = props.lastX + ev.deltaX;
                    props.y = props.lastY + ev.deltaY;
                    
                    ent.Node.node.x =  props.x;
                    ent.Node.node.y =  props.y;

                    props.isTouch = true;
                    toy.__output.innerHTML = JSON.stringify(props, null, 4);           
                    //嘗試擷取帶有"HighLight"元件的實體
                    let e = toy.getFirstEnt("HighLight");
                    // 保證世界上隻有一個實體帶有"HighLight"
                    if(!e){
                        //建立一個帶有"HighLight"元件的實體。
                        //之後湖北關心該元件的系統捕獲
                        toy.com("HighLight")
                    }
                  
                });


                mc.on("panend", function onPanEnd(ev){
                    props.isTouch = false;

                    props.lastX = props.x;
                    props.lastY = props.y;

                    toy.__output.innerHTML = JSON.stringify(props, null, 4);          
                    let e = toy.getFirstEnt("HighLight");
                    //這邊主角停止移動 我就删除了帶有"HighLight"元件的實體.
                    //其實也可以不删除，我這邊删除該實體那麼在主角停止移動的時候負責高亮的系統就不會工作了。
                    e && toy.removeCom(e,"HighLight")
                });

            });

可以看到IT俠在"panmvoe"事件回調中建立了一個"HighLight"元件的實體，目的就是為了告知（world）引擎我需要高亮，如果有關心"HighLight"的系統存在的話，那麼該系統就會工作。那麼接下來就是定義一個關心該元件的系統。

// 改系統是一個update方法 每一幀都會執行
      _sketch.onUpdate("HighLight",function(dt,es){
            //如果沒有所關心的實體那麼直接傳回
            if(!es[0]){
                return;
            }
             //拿到轉化為json的四叉樹資料
            let data = toy.qt.toJSON()
            // 拿到主角實體
            let selfEnt = toy.getFirstEnt("LocalControl")
            
            if(!selfEnt){
                return;
            }
            //擷取所有怪物實體
            let foods = toy.getAllEnt(["Mob","Health"])  
            
            // 擷取可能與主角發生碰撞的怪物
            let hlFood = toy.qt.retrieve(selfEnt.Node.node);

            if( !hlFood[0]){
                return;
            }
            
            hlFood.forEach((food)=>{

                //檢查碰撞 
                if(food._node.OldColor){
                   return;
                }
                //判斷2個物體是否将相交
                let isIntersects = toy.intersects(selfEnt.Node.node,food._node.Node.node);
                
                //在自己身上挂一個元件來儲存自己原來的顔色，友善後面還原
                toy.com("OldColor",{color:toy.deepClone(food._node.Props.props.color)},food._node);   
                
                if(false === isIntersects){
                 
                    food._node.Props.props.color = {r:219,g:100,b:0}
                }else{
                    food._node.Props.props.color = {r:106,g:9,b:125}                  
                    //告訴關心帶有"Collisioned"元件實體的系統 來處理碰撞
                    toy.comOnce("Collisioned",{character:selfEnt,target: food._node});
                }
            });
        });

碰撞邏輯就不屬于demo功能了。開發者可以自行處理

let _collision = toy.system("CollisionSystem",100);

        _collision.on("Collisioned",function(ent){
            let character = ent.Collisioned.character;
            let target = ent.Collisioned.target;
            //todo 寫自定義的碰撞需求
        });

最後就是怪物消失，我們需要更新一下樹節點狀态。寫一個死亡系統關心帶有"Mob",“Dead” 元件的實體，這些實體被定義為了已經死亡的實體。

let _dead = toy.system("DeadSystem",100);
        _dead.on(["Mob","Dead"],function(ent){
            // 從實體的Tree元件上擷取儲存在樹節點上的引用
            let treeNodes = ent.Tree.node;

            if(!treeNodes[0]){
                return;
            }
          
           //檢查是否該實體所在的子節點是空閑的
          //如果空閑則從四叉樹上删除該子節點
            treeNodes.forEach((node)=>{
                node.remove(ent);
            });
            // 從world中删除該實體
            toy.destroy(ent);

        });

結束語

現在有了建立四叉樹，将對象加入樹，檢查是否和與主角發生碰撞，還有删除樹上空閑的子節點。等功能，相信大家已經大概了解 ECS架構是如何與四叉樹結合來做碰撞檢測的了。

如果需要源碼的可以微信和我聯系哈。支援一下交個朋友。

謝謝看到最後（ps: 點贊支援一下呗）

上篇回顧

[ECS架構系列]-與四叉樹的一次結合（1）

ECS系列文章

[ECS系列] 架構中必不可少的工具類

[ECS系列] World的設計思路

[ECS系列] 實體，元件，系統的設計思路

[ECS系列] 歡迎來到ECS的世界

公衆号

我是IT俠來了，下面是我的公衆号，專注于分享IT圈内各種技術幹貨，内容涉及後端技術，前端技術等等，希望大家喜歡。再次感謝關注。

[ECS架構系列]-與四叉樹的一次結合（2）

有什麼問題可以加本人微信，一起交流。

[ECS架構系列]-與四叉樹的一次結合（2）

[ECS架構系列]-與四叉樹的一次結合（2）

前言

正文

最終效果

四叉樹

代碼實作

ECS中使用四叉樹

結束語

上篇回顧

ECS系列文章

更多精彩

公衆号

繼續閱讀

主流浏覽器四大綜合性能測試

JavaScript自學筆記【4】函數的聲明與調用目錄二、函數的聲明三、函數的調用

請求逾時VUE axios重新再次請求

nodejs微信開發---授權登入+擷取使用者資訊微信網頁授權

debian9更新4.9.0核心到4.19.2核心過程

Javascript建構Bingo卡片遊戲

JavaScript的那些坑之事件代理事件代理事件階段

javascript的for (var i in data)慎用javascript中的for (var i in data)謹慎用

tab滑鼠經過菜單切換

vue （vue2.0）使用總結(從大體結構總結)

vue搭建過程及出現問題

/\B(?=(?:\d{3})+$)/g 一條令人費解的正規表達式

适用于JavaScript的ECMAScript 2020規範向前發展

JS生成uuid的四種方法

layui多任務上傳添加進度條