动态格子算法

技术分享 4年前 (2022-09-14) 0 999+

关注

概述

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

思路

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

示例

示例代码使用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;                 }             }         }     } }