I am making a 2D game just to see what i can do. And right now im at the part where i have to do object collision and i choose to use a quad tree. the problem at hand is inserting an object into multiple subnodes.So the problem i have run into is when i insert an object into the tree, the tree is supposed to put the object into the lowest leaf node possible. but for some reason that i have yet to discover at least one object remains in each parent node when it is not supposed to.
So my question is could you guys help identify and provide possible solutions to the problem above. if you guys deam the problem unsolvable could you please provide an alternate way of going about it.
My code:
package net.evergone.engine;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;
import org.lwjgl.util.vector.Vector2f;
import org.newdawn.slick.Color;
import net.evergone.EverGone;
import net.evergone.game.BasicRectangle;
public class QuadtreeNode
{
private int MAX_OBJECTS = 2;
private int MAX_LEVELS = 6;
private int level = 0;
private boolean children = false;
private static boolean temp = false;
private BasicRectangle boundBox;
private ArrayList<BasicRectangle> objects;
private QuadtreeNode[] nodes;
/**
*
* Default constructor for QuadtreeNode
*/
public QuadtreeNode(int level, BasicRectangle boundBox)
{
this.level = level;
this.boundBox = boundBox;
objects = new ArrayList<BasicRectangle>();
nodes = new QuadtreeNode[4];
}
/**
*
* Splits the parent node into 4 leef nodes
*/
public void split()
{
float parentX = boundBox.getPosition().getX();
float parentY = boundBox.getPosition().getY();
nodes[0] = new QuadtreeNode(level+1, new BasicRectangle(new Vector2f(parentX+boundBox.getWidth()/2, parentY), boundBox.getWidth()/2, boundBox.getHeight()/2));
nodes[1] = new QuadtreeNode(level+1, new BasicRectangle(new Vector2f(parentX, parentY), boundBox.getWidth()/2, boundBox.getHeight()/2));
nodes[2] = new QuadtreeNode(level+1, new BasicRectangle(new Vector2f(parentX, parentY+boundBox.getHeight()/2), boundBox.getWidth()/2, boundBox.getHeight()/2));
nodes[3] = new QuadtreeNode(level+1, new BasicRectangle(new Vector2f(parentX+boundBox.getWidth()/2, parentY+boundBox.getHeight()/2), boundBox.getWidth()/2, boundBox.getHeight()/2));
children = true;
}
public int[] getIndex(BasicRectangle r)//TODO use intersection methods
{
int[] indexs = new int[4];
int e = 0;
float verticalMidpoint = boundBox.getPosition().getX() + (boundBox.getWidth() / 2);
float horizontalMidpoint = boundBox.getPosition().getY() + (boundBox.getHeight() / 2);
//BasicRectangle can completely fit within the top quadrants
boolean topQuadrant = (r.getPosition().getY() <= horizontalMidpoint);
//BasicRectangle can completely fit within the bottom quadrants
boolean bottomQuadrant = (r.getPosition().getY()+r.getHeight() >= horizontalMidpoint);
//BasicRectangle can completely fit within the left quadrants
boolean leftquadrant = (r.getPosition().getX() <= verticalMidpoint);
//BasicRectangle can completely fit within the right quadrants
boolean rightQuadrant = (r.getPosition().getX()+r.getWidth() >= verticalMidpoint);
if(topQuadrant && rightQuadrant)
{
indexs[e] = 0;
e++;
}
if(topQuadrant && leftquadrant)
{
indexs[e] = 1;
e++;
}
if(bottomQuadrant && leftquadrant)
{
indexs[e] = 2;
e++;
}
if(bottomQuadrant && rightQuadrant)
{
indexs[e] = 3;
}
for(int i =1;i<indexs.length;i++)
if(indexs[i] == 0)
indexs[i]=-1;
return indexs;
}
public void insert(BasicRectangle r)//TODO
{
if(children)
{
int[] indexs = getIndex(r);
for(int e : indexs)
if(e != -1)
nodes[e].insert(r);
return;
}
objects.add(r);
if(objects.size()>MAX_OBJECTS && level < MAX_LEVELS)
{
if(!children)
split();
int i = 0;
while(i<objects.size())
{
int[] indexs = getIndex(objects.get(i));
for(int e : indexs)
if(e != -1)
nodes[e].insert(objects.get(i));
objects.remove(i);
i++;
}
}
objects.trimToSize();
}
/**
* Return all objects that could collide with the given object
*/
public void retrieve(List<BasicRectangle> returnObjects, BasicRectangle r)
{
if(children)
{
int[] indexs = getIndex(r);
for(int e : indexs)
if(e != -1)
nodes[e].retrieve(returnObjects, r);
return;
}
for(BasicRectangle e : objects)
if(!returnObjects.contains(e))
returnObjects.addAll(objects);
/*if(!temp)
retrieveHelper(returnObjects);
temp = true;*/
while(returnObjects.contains(r))
returnObjects.remove(r);
}
public void retrieveHelper(List<BasicRectangle> returnObjects)
{
if(children)
for(QuadtreeNode e : nodes)
e.retrieveHelper(returnObjects);
returnObjects.addAll(objects);
}
/**
*
* clears the node
*/
public void clear()
{
objects.clear();
if(children)
for(QuadtreeNode e : nodes)
if(e != null)
{
e.clear();
e = null;
}
children = false;
temp = false;
}
public BasicRectangle getBoundBox()
{
return boundBox;
}
/**
*
* Strictly debug only (draw method with be Quadtree.java)
*/
public void draw()
{
if(children)
for(QuadtreeNode e : nodes)
e.draw();
else
boundBox.drawOutLine();
}
public void debugIndex(BasicRectangle r)
{
int[] indexs = getIndex(r);
System.out.println(Arrays.toString(indexs));
System.out.println("Parent node: "+objects.size());
for(BasicRectangle e : objects)
e.setColor(Color.yellow);
for(int e : indexs)
if(e != -1)
System.out.println("node "+e+": "+nodes[e].objects.size());
}
public QuadtreeNode[] getNodes()
{
return nodes;
}
}
In the insert method instead of removing the object (objects.remove(i);) set the object at i to null (objects.set(i, null);).