I'm currently implementing my own QuadTree in C++. It runs well with 100 items, but once you start adding more it slows down. remove
, getAll
, and insert
have all been profiled as taking a while. Any advice is appreciated!
class QuadTree {
private:
const static int MAX_OBJECTS = 20;
AABB bounds;
std::vector<QuadTree> children;
std::set<Locatable*> entities;
std::set<Locatable*> allEntities;
// Internal methods
void split() {
children.clear();
double width = (bounds.getWidth() / 2);
double height = (bounds.getHeight() / 2);
double x = bounds.getX();
double y = bounds.getY();
children.push_back(QuadTree(AABB(x + width, y, width, height)));
children.push_back(QuadTree(AABB(x, y, width, height)));
children.push_back(QuadTree(AABB(x, y + height, width, height)));
children.push_back(QuadTree(AABB(x + width, y + height, width, height)));
}
int getIndex(AABB& aabb) {
double vertMid = bounds.getVertMid();
double horzMid = bounds.getHorzMid();
// Fits in top
bool topQuadrant = aabb.getY() + aabb.getHeight() < horzMid;
// Fits in botom
bool bottomQuadrant = aabb.getY() > horzMid;
// Fits in left
if (aabb.getX() + aabb.getWidth() < vertMid) {
if (topQuadrant) {
return 1;
} else if (bottomQuadrant) {
return 2;
}
}
// Fits in right
else if (aabb.getX() > vertMid) {
if (topQuadrant) {
return 0;
} else if (bottomQuadrant) {
return 3;
}
}
return -1;
}
void merge(std::set<Locatable*>& one, std::set<Locatable*> two) {
one.insert(two.begin(), two.end());
}
// End Internal methods
public:
QuadTree(AABB bounds) : bounds(bounds) {
children.reserve(4);
}
// Base
void clear() {
entities.clear();
allEntities.clear();
for (auto it = children.begin(); it != children.end(); it++) {
it->clear();
}
children.clear();
}
void insert(Locatable* object) {
AABB aabb = object->getAABB();
allEntities.insert(object);
if (entities.size() > MAX_OBJECTS) {
if (children.empty()) {
split();
auto it = entities.begin();
while (it != entities.end()) {
int index = getIndex((*it)->getAABB());
if (index != -1) {
children.at(index).insert(*it);
it = entities.erase(it);
}
else {
it++;
}
}
}
int index = getIndex(aabb);
if (index != -1) {
children.at(index).insert(object);
}
else {
entities.insert(object);
}
}
else {
entities.insert(object);
}
}
void remove(Locatable* object, AABB aabb) {
auto it = allEntities.find(object);
if (it == allEntities.end()) {
return;
}
allEntities.erase(it);
it = entities.find(object);
if (it == entities.end()) {
if (!children.empty()) {
int index = getIndex(aabb);
if (index != -1) {
children.at(index).remove(object, aabb);
}
}
}
else {
entities.erase(it);
}
}
QuadTree* getLowestRoot(AABB aabb) {
int index = getIndex(aabb);
if (index == -1 || children.empty()) {
return this;
}
return children.at(index).getLowestRoot(aabb);
}
std::set<Locatable*> getAll() {
std::set<Locatable*> result;
if (children.empty()) {
return entities;
}
result = entities;
for (auto it = children.begin(); it != children.end(); it++) {
merge(result, it->getAll());
}
return result;
}
// End Base
};
getAll
andremove
are still a little on the slow side \$\endgroup\$