Skip to content

Instantly share code, notes, and snippets.

@ismyhc
Last active July 4, 2022 15:40
Show Gist options
  • Save ismyhc/4747262 to your computer and use it in GitHub Desktop.
Save ismyhc/4747262 to your computer and use it in GitHub Desktop.
Quadtree class Im using for Unity and Futile 2d framework
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
public class QuadTree {
private int MAX_OBJECTS = 1;
private int MAX_LEVELS = 3;
private int level;
private List<SquareOne> objects;
private Rect bounds;
private QuadTree[] nodes;
public QuadTree (int pLevel, Rect pBounds)
{
level = pLevel;
objects = new List<SquareOne>();
bounds = pBounds;
nodes = new QuadTree[4];
//DebugLineDraw.drawRectHitBox(pBounds, Color.cyan);
}
// Clear quadtree
public void Clear()
{
objects.Clear();
for(int i = 0; i < nodes.Length; i++)
{
if(nodes[i] != null)
{
nodes[i].Clear();
nodes[i] = null;
}
}
}
// Split the node into 4 subnodes
private void Split()
{
int subWidth = (int)(bounds.width / 2);
int subHeight = (int)(bounds.height / 2);
int x = (int)bounds.x;
int y = (int)bounds.y;
nodes[0] = new QuadTree(level + 1, new Rect(x + subWidth, y, subWidth, subHeight));
nodes[1] = new QuadTree(level + 1, new Rect(x, y, subWidth, subHeight));
nodes[2] = new QuadTree(level + 1, new Rect(x, y + subHeight, subWidth, subHeight));
nodes[3] = new QuadTree(level + 1, new Rect(x + subWidth, y + subHeight, subWidth, subHeight));
}
private List<int> GetIndexes(Rect pRect)
{
List<int> indexes = new List<int>();
double verticalMidpoint = bounds.x + (bounds.width / 2);
double horizontalMidpoint = bounds.y + (bounds.height / 2);
bool topQuadrant = pRect.y >= horizontalMidpoint;
bool bottomQuadrant = (pRect.y - pRect.height) <= horizontalMidpoint;
bool topAndBottomQuadrant = pRect.y + pRect.height + 1 >= horizontalMidpoint && pRect.y + 1 <= horizontalMidpoint;
if(topAndBottomQuadrant)
{
topQuadrant = false;
bottomQuadrant = false;
}
// Check if object is in left and right quad
if(pRect.x + pRect.width + 1 >= verticalMidpoint && pRect.x -1 <= verticalMidpoint)
{
if(topQuadrant)
{
indexes.Add(2);
indexes.Add(3);
}
else if(bottomQuadrant)
{
indexes.Add(0);
indexes.Add(1);
}
else if(topAndBottomQuadrant)
{
indexes.Add(0);
indexes.Add(1);
indexes.Add(2);
indexes.Add(3);
}
}
// Check if object is in just right quad
else if(pRect.x + 1 >= verticalMidpoint)
{
if(topQuadrant)
{
indexes.Add(3);
}
else if(bottomQuadrant)
{
indexes.Add(0);
}
else if(topAndBottomQuadrant)
{
indexes.Add(3);
indexes.Add(0);
}
}
// Check if object is in just left quad
else if(pRect.x - pRect.width <= verticalMidpoint)
{
if(topQuadrant)
{
indexes.Add(2);
}
else if(bottomQuadrant)
{
indexes.Add(1);
}
else if(topAndBottomQuadrant)
{
indexes.Add(2);
indexes.Add(1);
}
}
else
{
indexes.Add(-1);
}
return indexes;
}
public void Insert(SquareOne sprite)
{
SquareOne fSprite = sprite;
Rect pRect = fSprite.GetTextureRectRelativeToContainer();
if(nodes[0] != null)
{
List<int> indexes = GetIndexes(pRect);
for(int ii = 0; ii < indexes.Count; ii++)
{
int index = indexes[ii];
if(index != -1)
{
nodes[index].Insert(fSprite);
return;
}
}
}
objects.Add(fSprite);
if(objects.Count > MAX_OBJECTS && level < MAX_LEVELS)
{
if(nodes[0] == null)
{
Split();
}
int i = 0;
while(i < objects.Count)
{
SquareOne sqaureOne = objects[i];
Rect oRect = sqaureOne.GetTextureRectRelativeToContainer();
List<int> indexes = GetIndexes(oRect);
for(int ii = 0; ii < indexes.Count; ii++)
{
int index = indexes[ii];
if (index != -1)
{
nodes[index].Insert(sqaureOne);
objects.Remove(sqaureOne);
}
else
{
i++;
}
}
}
}
}
public List<SquareOne> Get(List<SquareOne> fSpriteList, Rect pRect)
{
return Retrieve(fSpriteList, pRect);
}
private List<SquareOne> Retrieve(List<SquareOne> fSpriteList, Rect pRect)
{
List<int> indexes = GetIndexes(pRect);
for(int ii = 0; ii < indexes.Count; ii++)
{
int index = indexes[ii];
if(index != -1 && nodes[0] != null)
{
nodes[index].Retrieve(fSpriteList, pRect);
}
fSpriteList.AddRange(objects);
}
return fSpriteList;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment