I've been staring at this code trying to troubleshoot this for the past 3 days, but I seem to have gone Code Blind. I KNOW the issue is stupidly simple, but I just can't crack the problem.

I'm using a bastardized quadtree to store the terrain for a map. Each node is either full of children, or stores an instance of a tile (position data is saved in the tile). tile stores its AABB (x,y,w,h), and block type (1 = ground, 0 = air/nothing). Later it will store objects and entities as well. Inserting (right now) does NOT cause merging - that is a separate function call.

The darn thing renders properly if drawn to a Pixmap. Which drives me absolutely crazy.

Expected Output (image generated to PixMap from data) :

Expected output from a properly merged quadtree

Output WITHOUT merging (tile width/heigh is 8 pixels), totally as expected :

Perfectly normal representation of the above quadtree, without merging of same blocks (all data 8x8 pixel squares)

Output WITH merging (bizzare.) : The same exact quadtree in all other images, except the squares are not aligned at all.

UPDATE : I set up a small test, with a 32x32 area, same 8pix base tile size. First image is a 4x4 quadtree grid at 8px size. Second image is 2x2 quadtree at 16px, Third image is 1x1 at 32px size. The red and blue marker is drawn from the physical world camera, is 16x16, drawn at -8,-8 (so the center is at 0,0. The brown is a ground texture - drawn into the phys world camera. For ALL of these images, the quadtree origin is at 0,0. WHAT IS MOVING THE ORIGIN FURTHER AND FURTHER APART?! NOTHING IN MY CODE IS DOING THIS!!?!

4x4 grid of 8 pixel tiles, NOT ALIGNED TO CAMERA 0,0! 2x2 grid of 16 pixel tiles, FURTHER MISALIGNED FROM LAST IMAGE! 1x1 grid of 32 pixel tile. STILL FURTHER MISALIGNED!!

Code which I am fairly sure is the problem (from the tile class) PPM is a constant defined elsewhere (Pixels Per Meter), set to 8. This is all rendered through LibGDX :

    public void setPhys(World w) {
    if(this.block != 0) {
        this.bdef = new BodyDef();
        NovaLog.debug("bdef.position.set(" + (this.aabb.x / PPM) + ", " + (this.aabb.y / PPM) + ");");
        bdef.position.set(this.aabb.x / PPM,this.aabb.y / PPM);
        bdef.type = BodyType.StaticBody;
        this.body = w.createBody(bdef);

        PolygonShape shape = new PolygonShape();
        NovaLog.debug("shape.setAsBox("+((this.aabb.width / PPM)/2) + ", " +  ((this.aabb.height / PPM)/2) +");");
        shape.setAsBox((this.aabb.width / PPM)/2, (this.aabb.height / PPM)/2);
        this.fdef = new FixtureDef();
        this.fdef.shape = shape;
        this.fixture = this.body.createFixture(fdef);

And the merge code from the quadnode class (might be problems here, I don't even know any more).

protected boolean merge() {

    //Leaves are already merged!
    if(this.isLeaf()) {return true;}

    boolean canMerge = true;
    //If we have child nodes, try to merge them.
    if(c[0] != null) {if(!c[0].merge()) {NovaLog.debug("NW couldn't merge."); canMerge = false;}}
    if(c[1] != null) {if(!c[1].merge()) {NovaLog.debug("NE couldn't merge."); canMerge = false;}}
    if(c[3] != null) {if(!c[3].merge()) {NovaLog.debug("SW couldn't merge."); canMerge = false;}}
    if(c[2] != null) {if(!c[2].merge()) {NovaLog.debug("SE couldn't merge."); canMerge = false;}}

    //If nodes aren't leaf nodes, and we couldn't merge them, return false.
    if(canMerge == false) {NovaLog.debug("Couldn't merge children."); return false; }

    // we should be able to try to merge this node.
    if(c[0].data.equalTo(c[1].data) && c[3].data.equalTo(c[2].data) && c[0].data.equalTo(c[3].data)){
        //Data is identical, WE CAN MERGE.
        this.data.block = c[0].data.block;
        this.c[0] = null;
        this.c[1] = null;
        this.c[3] = null;
        this.c[2] = null;
        NovaLog.debug("Merge success -> " + this.toString());
        return true;
    } else {
        // Data is NOT identical, we cannot merge!
        NovaLog.debug("Data not identical - ");
        for(int x = 0; x < 4;x++) {NovaLog.debug("" + c[x].data.block);}return false;

I really doubt there's an issue here, but just in case...

protected boolean subdivide() {
    NovaLog.info("SUBDIVIDING : " + this.data.aabb.toString());
    //we cannot split this node if it has items or entities in it.
    if(!this.data.items.isEmpty() || this.data.entity != null) {
        NovaLog.error("cannot subdivide! ERROR!");
        return false;

    float w = (float) (data.aabb.width / 2d);

    if(c[0] == null) {

        AABB aabbNW = new AABB(new Vector2(data.aabb.x,data.aabb.y), w, w);
        c[0] = new QuadNode(aabbNW, this);
        NovaLog.debug("NW = " + aabbNW.toString());

    if(c[1] == null) {
        Vector2 xyNE = new Vector2(data.aabb.x + w, data.aabb.y);
        AABB aabbNE = new AABB(xyNE, w, w);
        c[1] = new QuadNode(aabbNE, this);
        NovaLog.debug("NE = " + aabbNE.toString());

    if(c[2] == null) {
        Vector2 xySW = new Vector2(data.aabb.x, data.aabb.y + w);
        AABB aabbSW = new AABB(xySW, w, w);
        c[2] = new QuadNode(aabbSW, this);
        NovaLog.debug("SW = " + aabbSW.toString());

    if(c[3] == null) {
        Vector2 xySE = new Vector2(data.aabb.x + w, data.aabb.y + w);
        AABB aabbSE = new AABB(xySE, w, w);
        c[3] = new QuadNode(aabbSE, this);
        NovaLog.debug("SE = " + aabbSE.toString());

    return true;

At this point, I'm a Westworld Host looking at something that could do harm to his psyche - "It doesn't look like anything to me." Please help - the bruise on my forehead from banging my head against the wall is growing larger.

  • 1
    \$\begingroup\$ It looks like the boxes are being drawn with the wrong origin, with the size of the origin offset proportional to the width of the box. So, I'd look for any code that thinks it's dealing with the corner of the box, but is actually working with the center, or vice versa. \$\endgroup\$
    – DMGregory
    Jun 15 '19 at 22:58
  • \$\begingroup\$ shape.setAsBox requires the halfwidth and halfheight of the box. Only spot that requires a center, rather than a corner position. It's not the scaling either - removing it completely makes it huge, but equally odd looking. Note the non-merged displays totally as expected - this is just the quadtree filled with 8x8 boxes. \$\endgroup\$
    – Mr Wisski
    Jun 15 '19 at 23:06

Apparently, whatever local origin is set in the default Shape.setAsBox() IS WRONG, or at least wrong for the use I'm using it as.

There is a longer version of setAsBox that allows you to set the Center of the shape...and putting in the simple halfwidth of the node, in each part of the vector leads to...properly aligned boxes. Why this is required, when you set position in the body def, i have absolutely no idea.

Corrected line :

shape.setAsBox((float)((this.aabb.width / PPM)/2.0f), (float) ((this.aabb.height / PPM)/2.0f), new Vector2((float)(this.aabb.width/2.0f)/PPM,(float)(this.aabb.width/2.0f)/PPM), 0.0f );

Results : A picture of a QuadTree, properly converted into Box2D Static boxes.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .