概述
動態格子演算法常用于彈幕游戲的碰撞檢測優化，可減少遍歷開銷，
這是我之前做的小游戲就用到了此演算法，當后期滿屏子彈時，優化效果非常明顯，
思路
- 每個點只與當前所處的格子的點檢測碰撞
- 當大格子內的點>格子內點限制 && 大格子的深度 < 最大深度則大格子分裂出四個小格子，把點放到小格子里，
- 當大格子內的點 <= 格子內點限制 并且存在四個小格子時，洗掉小格子,把點放回大格子，
示例
示例代碼使用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變為正方體檢測
- 當檢測物體太大甚至比格子還大此方法不適用
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/507215.html
標籤：其他