概述

動態格子演演算法常用於彈幕遊戲的碰撞檢測優化，可減少遍歷開銷。
這是我之前做的小遊戲就用到了此演演算法，當後期滿屏子彈時，優化效果非常明顯。

思路

• 每個點只與當前所處的格子的點檢測碰撞
• 當大格子內的點>格子內點限制 && 大格子的深度 < 最大深度則大格子分裂出四個小格子，把點放到小格子裡。
• 當大格子內的點 <= 格子內點限制 並且存在四個小格子時，刪除小格子,把點放回大格子。

範例

範例程式碼使用C#語言，視覺化工具使用Unity

GridNode

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class GridRect
{
    public GridRect(float in_x,float in_y,float in_w, float in_h)
    {
        x = in_x;
        y = in_y;
        w = in_w;
        h = in_h;
    }
    public float x;
    public float y;
    public float w;
    public float h;
}

public class GridNode
{
    List<GridNode> children;
    public GridRect rect;
	//最大深度
    const int max_deep = 3;
	//每個格子最大有多少個待檢測物體
    const int max_cnt = 4;
    int deep;
    int cnt;

    List<GameObject> points = new List<GameObject>();
    public GameObject grid;
	
	// 新增一個點
    public void Add(GameObject go)
    {
        ++cnt;
        points.Add(go);
        if(children == null)
        {
			// 到達葉子格子，待檢測物體儲存當前格子 point.grid = this
            if (deep <= max_deep && cnt > max_cnt)
            {
                Grow();
            }
        }
        else //若是孩子存在，判斷點在哪個子格子裡，把點放進子格子
        {
            foreach (var item in children)
            {
                if(item.Evaluate(go))
                {
                    item.Add(go);
                    break;
                }
            }
        }
    }
	
	//移除點
    public void Remove(GameObject go)
    {
        --cnt;
        points.Remove(go);
        if (children != null)
        {
            foreach (var item in children)
            {
                if (item.Evaluate(go))
                {
                    item.Remove(go);
                    break;
                }
            }

            if (cnt <= max_cnt)
            {
                Shrink();
            }
        }
        else
        {
            
        }
    }
	
	// 樹生長，生成四個子格子，在把點放在子格子裡
    public void Grow()
    {
        children = new List<GridNode>();
        var rects = new List<GridRect>();
        var half_w = rect.w / 2;
        var half_h = rect.h / 2;
		// 計運算元格子的區域
        rects.Add(new GridRect(rect.x, rect.y, half_w, half_h));
        rects.Add(new GridRect(rect.x + half_w, rect.y, half_w, half_h));
        rects.Add(new GridRect(rect.x, rect.y + half_h, half_w, half_h));
        rects.Add(new GridRect(rect.x + half_w, rect.y + half_h, half_w, half_h));

        for (int i = 0; i < 4; i++)
        {
            var child = new GridNode();
            var r = rects[i];
            child.Init(r.x, r.y, r.w, r.h, deep + 1);
            foreach (var item in points)
            {
                if(child.Evaluate(item))
                {
                    child.Add(item);
                    break;
                }
            }
            children.Add(child);
        }
    }
	
	// 收緊，刪除子格子
    public void Shrink()
    {
        foreach (var item in children)
        {
            item.Clear();
        }
        children = null;
    }
	
	// 判斷點是否在此格子區域內
    public bool Evaluate(GameObject go)
    {
        var pos = go.transform.position;
        var ret = pos.x >= rect.x && pos.x < (rect.x + rect.w) &&
            pos.y >= rect.y && pos.y < (rect.y + rect.h);
        return ret;
    }
	
	// 初始化
    public void Init(float x, float y, float w, float h, int in_deep)
    {
        rect = new GridRect(x, y, w, h);
        deep = in_deep;
        grid = GameObject.Instantiate(GridState.Inst.grid_prefab);
        grid.transform.SetParent(GridState.Inst.grid_parent);
        var tr = grid.GetComponent<RectTransform>();
        tr.position = new Vector3(x, y, 0);
        tr.sizeDelta = new Vector2(w, h);
    }
	
    public void Clear()
    {
        if(grid != null)
        {
            GameObject.Destroy(grid);
        }
    }
}

• 組織結構可以視為4叉樹
• 視情況合理調整最大深度max_deep
• 註釋葉子節點處，待檢測物體儲存當前格子

GridState

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class GridState : MonoBehaviour
{
    // Start is called before the first frame update
    static public GridState Inst;

    public GameObject grid_prefab;
    public GameObject point_prefab;

    public Transform grid_parent;
    public Transform point_parent;

    GridNode root;
    Queue<GameObject> point_que = new Queue<GameObject>();
    bool is_create_mode;
    private void Awake()
    {
        Inst = this;
    }

    void Start()
    {
        is_create_mode = true;
        root = new GridNode();
        root.Init(0, 0, 1334, 750, 0);
    }

    float cnt;
    float max = 0.1f;
    private void FixedUpdate()
    {
        var t = Time.fixedDeltaTime;
        cnt += t;
        if (cnt > max)
        {
            cnt -= max;
            if (is_create_mode)
            {
                var go = GameObject.Instantiate(point_prefab, point_parent);
                go.transform.position = new Vector3(Random.Range(0, 1334), Random.Range(0, 750), 0);
                root.Add(go);
                point_que.Enqueue(go);
                if (point_que.Count > 50)
                {
                    is_create_mode = false;
                }
            }
            else
            {
                var go = point_que.Dequeue();
                root.Remove(go);
                GameObject.Destroy(go);
                if (point_que.Count == 0)
                {
                    is_create_mode = true;
                }
            }
        }
    }
}

• 儲存維護動態格子4叉樹的根節點
• 動態格子演演算法測試，執行結果如思路上的圖所示

備註

• 3D空間也適用，需Evaluate變為正方體檢測
• 當檢測物體太大甚至比格子還大此方法不適用