Jump to content
  • Advertisement
Sign in to follow this  
CyJackX

How to efficiently update a Median-QuadTree for N-planets that update per frame?

This topic is 3157 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm currently creating a game in Java that is an infinite plane in space. Several hundred bodies may be around the limit, but at the moment, I'm not sure about the maximum capacity, and I know that pre-mature optimization is the root of all evil, but I have implemented a QuadTree structure to handle collisions versus the N(N+1)/2 shindig. I experimented with Spatial hashing, BSP, Kd-Trees, and ended up adapting a Quadtree system that uses medians. Instead of dividing into four even squares, each division happens using the median x and y coordinates of the bodies that have been recorded thus far (it only measures until it has to divide). I feel that this eliminates imbalanced quadtrees because, in general, the field's bodies will be equally divided each time. I have not seen this implementation described elsewhere, so I might be making a mistake? Now, this is all fine and dandy except that it rebuilds the tree each frame, because the bodies all move each frame. I've read various articles that describe adding an "Add" function to the quadtree root, which will filter down through the Quadtree and assign the appropriate cells a body. (Some bodies will occupy multiple cells, given sizes.) The idea of a "remove" function is there also, where each body stores a list of the cells it occupies. Adding and removing will both feature dynamic regenerating of the quadtree, but is more efficient in that they only rebuild the parts they affect, hopefully. But one thing I've heard described is an "update" function for the quadtree, where the location of a body is updated in regards to the tree. I can't figure out an efficient way to implement this, besides removing it from the tree and then adding it back in. Because one body may occupy multiple cells, it is not enough to check if it is still within the cells it occupied before; it may have crossed some borders. Although, now that I think about it, perhaps I could have some check for whether a body is fully encapsulated by a cell? Any suggestions?

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by CyJackX

I feel that this eliminates imbalanced quadtrees because, in general, the field's bodies will be equally divided each time.

Last time I was messing around with quad trees my experimental observation was that balanced trees resulted in poorer run-time performance. I cannot prove it empirically, but in my case the query phase took twice as long with balanced QT, construction time was same. I seem to remember that balanced trees are preferred for GPU-based algorithms.

There is also a transformation where single child or non-full nodes are recursively collapsed into a parent to prevent long recursive searches. In my experience it saved some 5-10% at query time, but is gotten for free during construction.

Quote:
Now, this is all fine and dandy except that it rebuilds the tree each frame, because the bodies all move each frame.

I've found this to be the simplest way. In Java, garbage collection becomes annoying so a pool of nodes might help.

Quote:
But one thing I've heard described is an "update" function for the quadtree, where the location of a body is updated in regards to the tree.

If all or most objects are expected to move, then this doesn't really make much sense. Rebalancing the tree either way is non-trivial compared to 20 line full build version, and if all objects move, then overhead doesn't make it worth it.

Quote:
Because one body may occupy multiple cells, it is not enough to check if it is still within the cells it occupied before; it may have crossed some borders.

There's a QT version which doesn't split among cells. During construction, check if object is split across multiple cells. If yes, store it in current cells, otherwise, recurse further.

This also means that a lot of very large objects could end up at higher level nodes, but unless the geometry is somehow degenerate, this shouldn't typically be a problem. This approach is quite simple to implement due to single parent rule.

Share this post


Link to post
Share on other sites
Here is a somewhat working QuadTree Class I've got right now;

It has a bug where stacked objects might break it; I've plugged in a rudimentary "breaking" check.

The update function right now is only useful by doing nothing if it checks that the body occupies only one cell and is still entirely within that one cell.

Each GravitationalBody has a list of CellsOccupying. The remove function is also somewhat of a nightmare; For every cell that G occupies, it removes itself from that cell's list of residents, then each cell must check whether it and its siblings contain enough members to merge back into one cell.



import java.util.Arrays;
import java.util.HashSet;

/**
*
* @author Andy
*/

public class QuadCell {

private static QuadCell root = new QuadCell();
double x = 0, y = 0, width = 0, height = 0;
public static java.util.Set<QuadCell> interestingCells = new HashSet<QuadCell>(); //Allows for only one instance of QuadCell?
private static int bucketMax = 30;
private HashSet<GravitationalBody> residents = new HashSet<GravitationalBody>(0);
private QuadCell[] children = null;
private QuadCell parent = null;
private boolean hasChildren = false;
private static int breaker = 0;

private QuadCell() {
}

private QuadCell(double x, double y, double width, double height) {
this.x = x;
this.y = y;
this.width = width;
this.height = height;

}

/*
* Adds a body to the quadtree, starting at the root.
*/

public final static void addToRoot(GravitationalBody g) {

/*
* If a body lies outside of the root bounds, expand the root bounds and re-add all the residents in.
*/

if ((Math.abs(g.x - root.x - root.width / 2) > g.safeRadius + root.width / 2)
|| (Math.abs(g.y - root.y - root.height / 2) > g.safeRadius + root.height / 2)) {

//Expands the Root's bounds 10x over to fit the objects.
double tmp = 10 * Math.abs(g.x + g.safeRadius - root.x - root.width / 2);
root.x -= tmp;
root.width += 2 * tmp;
tmp = 10 * Math.abs(g.y + g.safeRadius - root.y - root.height / 2);
root.y -= tmp;
root.height += 2 * tmp;

interestingCells.clear();
//Remember all the residents.
HashSet<GravitationalBody> c = root.listOfResidents();
root.residents.clear();
root.hasChildren = false;
root.children = null;
root.parent = null;
for (GravitationalBody gb : c) {
gb.cellsOccupying.clear();

addToRoot(gb);
}


}
root.addBody(g);


}

private final void addBody(GravitationalBody g) {

//This "breaker" breaks if addbody is called too many times without completing.
if(breaker++ > 10){
System.out.println("broke");
return;
}

//If the body fits within the bounds of a cell;
if ((Math.abs(g.x - x - width / 2) <= g.safeRadius + width / 2)
&& (Math.abs(g.y - y - height / 2) <= g.safeRadius + height / 2)) {


if (hasChildren) {//Add it to its children if it has them.
children[0].addBody(g);
children[1].addBody(g);
children[2].addBody(g);
children[3].addBody(g);
} else { //Otherwise, add it to itself.
residents.add(g);
g.cellsOccupying.add(this);

if (residents.size() > bucketMax) { // If it exceeds the bucketmax...
initializeChildrenAreas();
for (GravitationalBody gb : residents) { //Add each of the bodies back into the root.
gb.cellsOccupying.remove(this);
addBody(gb);
}
residents.clear();
interestingCells.remove(this);
} else {

if (residents.size() > 1) {
interestingCells.add(this);
}
}
}
}
breaker = 0;
}

public final static void updateBody(GravitationalBody g) {

//If the cells that G occupies is only 1...
if (g.cellsOccupying.size() == 1) {
QuadCell c = g.cellsOccupying.get(0);
//Then if G is fully within the bounds of that one cell's box, finish updating.
if ((Math.abs(g.x - c.x - c.width / 2) < c.width / 2 - g.safeRadius) && (Math.abs(g.y - c.y - c.height / 2) < c.height / 2 - g.safeRadius)) {
return;
}
}

//Otherwise, remove G and add it back in. Kind of awful overhead, for now.
removeBody(g);
addToRoot(g);
}
/*
* Removes a Body from the Tree.
*/

public final static void removeBody(GravitationalBody g) {
//For every Cell that this body is occupying...
for (QuadCell c : g.cellsOccupying.toArray(new QuadCell[g.cellsOccupying.size()])) {
//Remove this body from that Cell's List of Residents.
c.residents.remove(g);
if (c.parent != null) {


//If the parent of that cell's children is now under the BucketMax...
if (c.parent.sumAllResidents() <= bucketMax) {
//Treat the Parent as childless, so that when the child's residents are added back, they do not immediately
//fall through back to the children.
c.parent.hasChildren = false;


//Then erase all children. For all its children...

if (c.parent.children != null) {
for (QuadCell children : c.parent.children) {
//...make each child's residents forget the children.
for (GravitationalBody gb : children.residents) {
gb.cellsOccupying.remove(children);
//Then give each child's residents to the parent.
c.parent.addBody(gb);
}
interestingCells.remove(children);
}
}

//Erase parent's children.
c.parent.children = null;
}
}
//If c has less than 2 bodies, remove it from the interesting List.
if (c.residents.size() < 2) {
interestingCells.remove(c);
}

}
//Erase the List containing the cells G occupies.
g.cellsOccupying.clear();

}

public GravitationalBody[] getResidents() {
return residents.toArray(new GravitationalBody[residents.size()]);
}

public final void initializeChildrenAreas() {
int r = residents.size();
GravitationalBody[] g = residents.toArray(new GravitationalBody[r]);
double[] dx = new double[r];
double[] dy = new double[r];
int median = r / 2;
for (int u = r - 1; u >= 0; u--) {
dx = g.x - x;
dy = g.y - y;
}
Arrays.sort(dx);
Arrays.sort(dy);
double dxm, dym;
if (r % 2 == 1) {
dxm = dx[median];
dym = dy[median];
} else {
dxm = (dx[median - 1] + dx[median]) / 2;
dym = (dy[median - 1] + dy[median]) / 2;
}


children = new QuadCell[4];
children[0] = new QuadCell(x, y, dxm, dym);
children[1] = new QuadCell(x + dxm, y, width - dxm, dym);
children[2] = new QuadCell(x, y + dym, dxm, height - dym);
children[3] = new QuadCell(x + dxm, y + dym, width - dxm, height - dym);
children[0].parent = this;
children[1].parent = this;
children[2].parent = this;
children[3].parent = this;
hasChildren = true;
}

//The sum of all the residents within a cell.
private final int sumAllResidents() {
if (!hasChildren) {
return residents.size();
}
return children[0].sumAllResidents()
+ children[1].sumAllResidents()
+ children[2].sumAllResidents()
+ children[3].sumAllResidents();


}

private final HashSet<GravitationalBody> listOfResidents() {
HashSet<GravitationalBody> returnList = new HashSet<GravitationalBody>();
if (!hasChildren) {
returnList.addAll(residents);

} else {

returnList.addAll(children[0].listOfResidents());
returnList.addAll(children[1].listOfResidents());
returnList.addAll(children[2].listOfResidents());
returnList.addAll(children[3].listOfResidents());
}
return returnList;
}
}





Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!