动态格子算法 - 张宏港

动态格子算法常用于弹幕游戏的碰撞检测优化，可减少遍历开销。
这是我之前做的小游戏就用到了此算法，当后期满屏子弹时，优化效果非常明显。

• 每个点只与当前所处的格子的点检测碰撞
• 当大格子内的点>格子内点限制 && 大格子的深度 < 最大深度则大格子分裂出四个小格子，把点放到小格子里。
• 当大格子内的点 <= 格子内点限制 并且存在四个小格子时，删除小格子,把点放回大格子。

示例代码使用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变为正方体检测
• 当检测物体太大甚至比格子还大此方法不适用