-
Notifications
You must be signed in to change notification settings - Fork 0
/
quadtree.cpp
121 lines (101 loc) · 3.42 KB
/
quadtree.cpp
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
#include <iostream>
#include <SDL2/SDL.h>
#include "quadtree.hpp"
#include "defs.hpp"
#include "game.hpp"
QuadTree::QuadTree(short x, short y, short w, short h, short d) {
xpos = x;
ypos = y;
height = h;
width = w;
depth = d;
north_west = nullptr;
north_east = nullptr;
south_west = nullptr;
south_east = nullptr;
//std::cout << "QuadTree initialized" << std::endl;
}
bool QuadTree::insert(Entity* entity) {
//Out of bounds, not part of this quadtree
if (entity->xpos + entity->width < xpos || entity->xpos > xpos + width || entity->ypos + entity->height < ypos || entity->ypos > ypos + height) {
//std::cout << entity->tag << " was out of bounds." << std::endl;
return false;
}
//Check for capacity and if there are no subdivisions in this quadtree
if (depth == MAX_DEPTH || (entities.size() < MAX_OBJECTS && north_west == nullptr)) {
//std::cout << entity->tag << " has been inserted at depth: " << depth << std::endl;
entities.insert(entity);
return true;
}
if (entities.size() > 0) {
entities.clear();
}
if (north_west == nullptr) subdivide();
north_west->insert(entity);
north_east->insert(entity);
south_west->insert(entity);
south_east->insert(entity);
return true;
}
void QuadTree::subdivide() {
north_west = new QuadTree(xpos, ypos, width / 2, height / 2, depth + 1);
north_east = new QuadTree(xpos + width / 2, ypos, width / 2, height / 2, depth + 1);
south_west = new QuadTree(xpos, ypos + height / 2, width / 2, height / 2, depth + 1);
south_east = new QuadTree(xpos + width / 2, ypos + height / 2, width / 2, height / 2, depth + 1);
}
void QuadTree::clean() {
for (auto it = entities.begin(); it != entities.end();) {
if ((*it)->mark_remove) {
it = entities.erase(it);
continue;
}
Entity* e = *it;
int relative_xpos = Game::camera->xpos + e->xpos;
int relative_ypos = Game::camera->ypos + e->ypos;
if (e->xpos + e->width < xpos || e->xpos > xpos + width || e->ypos + e->height < ypos || e->ypos > ypos + height) {
it = entities.erase(it);
} else {
++it;
}
}
}
void QuadTree::construct(std::unordered_set<Entity*> collideable_entities) {
for (Entity* entity : collideable_entities) {
if (entity != nullptr && !entity->mark_remove) {
insert(entity);
}
}
}
void QuadTree::combine() {
if (north_west == nullptr) {
return;
}
north_west->combine();
north_east->combine();
south_west->combine();
south_east->combine();
// if it's a leaf node
if (north_west->north_west == nullptr) {
// all empty
if (north_west->entities.size() == 0 && north_east->entities.size() == 0 && south_west->entities.size() == 0 && south_east->entities.size() == 0) {
delete north_west;
delete north_east;
delete south_east;
delete south_west;
north_west = nullptr;
north_east = nullptr;
south_west = nullptr;
south_east = nullptr;
}
}
}
void QuadTree::getLeaves (std::vector<QuadTree*>& v) {
if (north_west == nullptr) {
v.push_back(this);
} else {
north_west->getLeaves(v);
north_east->getLeaves(v);
south_west->getLeaves(v);
south_east->getLeaves(v);
}
}