My game has a quadrant tree for handling collisions (All objects is circles). I made a QuadTree class for my game using GPT, everything was fine, but when I added 5k objects, the game took more than 150ms to process all collisions (very long for my game). The problem was that for each object, the nearest half of the map was returned. I fixed (sort of) freezes, now it returns about 6-10 objects for each, which is good. But now, sometimes when an object appears or moves to some point on the map, it loses its collision, and no object can collide with it from one or more sides. I think it's because the object is at the junction of two nodes. I have no idea how to fix it, what am I doing wrong? Please help me.
Here is the code of the QuadTree class:
public class QuadTree {
private static final int MAX_OBJECTS = 5;
private static final int MAX_LEVELS = 10;
private int level;
private List<GameObject> objects;
private Rectangle bounds;
private QuadTree[] nodes;
public QuadTree(int level, Rectangle bounds) {
this.level = level;
objects = new ArrayList<>();
this.bounds = bounds;
nodes = new QuadTree[4];
}
public void clear() {
objects.clear();
for (int i = 0; i < nodes.length; i++) {
if (nodes[i] != null) {
nodes[i].clear();
nodes[i] = null;
}
}
}
private void split() {
int subWidth = bounds.getWidth() / 2;
int subHeight = bounds.getHeight() / 2;
int x = bounds.getX();
int y = bounds.getY();
nodes[0] = new QuadTree(level + 1, new Rectangle(x + subWidth, y, subWidth, subHeight));
nodes[1] = new QuadTree(level + 1, new Rectangle(x, y, subWidth, subHeight));
nodes[2] = new QuadTree(level + 1, new Rectangle(x, y + subHeight, subWidth, subHeight));
nodes[3] = new QuadTree(level + 1, new Rectangle(x + subWidth, y + subHeight, subWidth, subHeight));
}
private List<Integer> getIndex(GameObject circle) {
List<Integer> index = new ArrayList<>();
double verticalMidpoint = bounds.getX() + (bounds.getWidth() / 2);
double horizontalMidpoint = bounds.getY() + (bounds.getHeight() / 2);
boolean topQuadrant = (circle.getY() + (circle.getRadius() / 2) < horizontalMidpoint);
boolean bottomQuadrant = (circle.getY() + (circle.getRadius() / 2) > horizontalMidpoint);
if (circle.getX() + (circle.getRadius() / 2) < verticalMidpoint) {
if (topQuadrant) {
index.add(1);
} else if (bottomQuadrant) {
index.add(2);
}
} else if (circle.getX() + (circle.getRadius() / 2) > verticalMidpoint) {
if (topQuadrant) {
index.add(0);
} else if (bottomQuadrant) {
index.add(3);
}
}
return index;
}
public void remove(GameObject circle) {
List<Integer> index = getIndex(circle);
if (index.size() > 0 && nodes[0] != null) {
for (int i : index) {
if (nodes[i].bounds.contains(circle))
nodes[i].remove(circle);
}
} else {
objects.remove(circle);
}
if (objects.size() < MAX_OBJECTS && nodes[0] != null) {
for (int i = 0; i < nodes.length; i++) {
if (nodes[i] != null) {
nodes[i].clear();
nodes[i] = null;
}
}
}
}
public void insert(GameObject circle) {
if (nodes[0] != null) {
List<Integer> index = getIndex(circle);
if (index.size() > 0) {
for (int i : index) {
if (nodes[i].bounds.contains(circle))
nodes[i].insert(circle);
}
return;
}
} else {
objects.add(circle);
}
if (objects.size() > MAX_OBJECTS && level < MAX_LEVELS) {
if (nodes[0] == null) {
split();
}
int i = 0;
while (i < objects.size()) {
List<Integer> index = getIndex(objects.get(i));
if (index.size() > 0) {
for (int io : index) {
if (nodes[io].bounds.contains(objects.get(i)))
nodes[io].insert(objects.remove(i));
}
} else {
i++;
}
}
}
}
public List<GameObject> retrieve(List<GameObject> returnObjects, GameObject circle) {
List<Integer> index = getIndex(circle);
if (index.size() > 0 && nodes[0] != null) {
for (int i : index) {
if (nodes[i].bounds.contains(circle))
nodes[i].retrieve(returnObjects, circle);
}
}
returnObjects.addAll(objects);
return returnObjects;
}
}
All nearby objects should have been returned to handle collisions, but because something went wrong when searching for objects at the intersection of the node, this did not happen.