Last active
July 4, 2022 15:40
-
-
Save ismyhc/4747262 to your computer and use it in GitHub Desktop.
Quadtree class Im using for Unity and Futile 2d framework
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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