-
Notifications
You must be signed in to change notification settings - Fork 0
/
QuadTreeGO.cs
172 lines (155 loc) · 4.36 KB
/
QuadTreeGO.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class QuadTreeGO
{
protected int maxObjectCount;
private readonly List<GameObject> storedObjects;
protected Rect bounds;
private readonly QuadTreeGO[] cells;
//max size is the amount of objects in a list
//bounds is the Rect of you map or the object in which you place the game objects
public QuadTreeGO(int maxSize, Rect newBounds){
bounds = newBounds;
maxObjectCount = maxSize;
cells = new QuadTreeGO[4];
storedObjects = new List<GameObject>(maxSize);
}
protected QuadTreeGO()
{ }
public void Insert(GameObject objectToInsert)
{
if(cells[0] != null)
{
int iCell = GetInsertCell(Get2DPosition(objectToInsert));
if(iCell >= 0)
{
cells[iCell].Insert(objectToInsert);
}
else
{
Debug.Log("gameObject is out of the insert rect" + Get2DPosition(objectToInsert) + objectToInsert);
}
return;
}
storedObjects.Add(objectToInsert);
//Objects exceed the maximum count
if(storedObjects.Count > maxObjectCount)
{
//Split the quad into 4 sections
if(cells[0] == null)
{
float subWidth = (bounds.width / 2f);
float subHeight = (bounds.height / 2f);
//NorthEast
cells[0] = new QuadTreeGO(maxObjectCount,new Rect(bounds.x + subWidth, bounds.y, subWidth, subHeight));
//northWest
cells[1] = new QuadTreeGO(maxObjectCount,new Rect(bounds.x, bounds.y, subWidth, subHeight));
//southWest
cells[2] = new QuadTreeGO(maxObjectCount,new Rect(bounds.x, bounds.y + subHeight, subWidth, subHeight));
//southEast
cells[3] = new QuadTreeGO(maxObjectCount,new Rect(bounds.x + subWidth, bounds.y + subHeight, subWidth, subHeight));
}
//Reallocate this quads objects into its children
for(int i = storedObjects.Count-1; i >= 0; --i)
{
GameObject storedObj = storedObjects[i];
cells[GetInsertCell(Get2DPosition(storedObj))].Insert(storedObj);
storedObjects.RemoveAt(i);
}
}
}
public void Remove(GameObject objectToRemove)
{
if(ContainsLocation(Get2DPosition(objectToRemove)))
{
storedObjects.Remove(objectToRemove);
if(cells[0] != null)
{
for(int i=0; i < 4; i++)
{
cells[i].Remove(objectToRemove);
}
}
}
}
private List<GameObject> RetrieveObjectsInArea(Rect area)
{
if(RectOverlap(bounds,area)){
List<GameObject> returnedObjects = new List<GameObject>();
for(int i=0; i < storedObjects.Count; ++i)
{
if(area.Contains(Get2DPosition(storedObjects[i])))
{
returnedObjects.Add(storedObjects[i]);
}
}
if(cells[0] != null){
for(int i = 0; i < 4; i++)
{
List<GameObject> cellObjects = cells[i].RetrieveObjectsInArea(area);
if(cellObjects != null)
{
returnedObjects.AddRange(cellObjects);
}
}
}
return returnedObjects;
}
return null;
}
public GameObject FindClosestGameObject(Vector2 position, float maxDistance)
{
Rect viewRect = new Rect(position.x - maxDistance/2, position.y - maxDistance/2, maxDistance, maxDistance);
List<GameObject> closestObjects = RetrieveObjectsInArea(viewRect);
if (closestObjects == null || closestObjects.Count <= 0)
{
return null;
}
GameObject closestObject = null;
float closestDist = Mathf.Infinity;
foreach (GameObject obj in closestObjects)
{
float newDist = Vector2.Distance(Get2DPosition(obj), position);
if (newDist < closestDist)
{
closestDist = newDist;
closestObject = obj;
}
}
return closestObject;
}
protected bool ContainsLocation(Vector2 location)
{
return bounds.Contains(location);
}
private int GetInsertCell(Vector2 location)
{
for(int i=0; i < 4; i++){
if(cells[i].ContainsLocation(location))
{
return i;
}
}
return -1;
}
private static bool ValueInRange(float value, float min, float max)
{ return (value >= min) && (value <= max); }
protected static bool RectOverlap(Rect A, Rect B)
{
bool xOverlap = ValueInRange(A.x, B.x, B.x + B.width) ||
ValueInRange(B.x, A.x, A.x + A.width);
bool yOverlap = ValueInRange(A.y, B.y, B.y + B.height) ||
ValueInRange(B.y, A.y, A.y + A.height);
return xOverlap && yOverlap;
}
private static Vector2 Get2DPosition(GameObject obj)
{
Vector3 pos = obj.transform.position;
return V3ToV2(pos);
}
protected static Vector2 V3ToV2(Vector3 vector3)
{
return new Vector2(vector3.x, vector3.z);
}
}