Making a perfect map (not tile-based)

Newbie & Debugging Questions
#1

I would like to make a map system as in the GameMaker and the latest code is here. I’ve searched a lot in google and all of them resulted in tutorials about tile-maps. As tile maps do not fit for every type of game and GameMaker uses tiles for a different purpose, I want to make a “Sprite Based” map.

The major problem I had experienced was collision detection being slow for large maps. So I wrote a QuadTree class here and the collision detection is fine upto 50000 objects in the map without PixelPerfect collision detection and 30000 objects with PixelPerferct collisions enabled.

Now I need to implement the method “isObjectCollisionFree(float x, float y, boolean solid, GObject obj)”. The existing implementation is becoming slow in Platformer games and I need suggestions on improvement.

The current Implementation:


/**
 * Checks if a specific position is collision free in the map.
 * 
 * @param x The x-position of the object
 * @param y The y-position of the object
 * @param solid Whether to check only for solid object
 * @param object The object ( used for width and height )
 * @return True if no-collision and false if it collides.
 */
public static boolean isObjectCollisionFree(float x, float y, boolean solid, GObject object){
    boolean bool = true;
    Rectangle bounds = new Rectangle(Math.round(x), Math.round(y), object.getWidth(), object.getHeight());
    ArrayList<GObject> collidables = quad.retrieve(bounds);
    for (int i=0; i<collidables.size(); i++){
        GObject obj = collidables.get(i);
        if (obj.isSolid()==solid && obj != object){
            if (obj.isAlive()){
                if (bounds.intersects(obj.getBounds())){
                    bool = false;
                    if (Global.USE_PIXELPERFECT_COLLISION){
                        bool = !GUtil.isPixelPerfectCollision(x, y, object.getAnimation().getBufferedImage(), obj.getX(), obj.getY(), obj.getAnimation().getBufferedImage());
                    }
                    break;
                }
            }
        }
    }
    return bool;
}

Thanks.

#2

I don’t see any immediate optimization potentials (other than some micro-optimization if the many if-statements).

Why is it slow in first place? The quadtree should give you very few objects around the current object, so the loop would only loop a few times and it should be very fast.

How many objects in average do you get from the quad.retrieve(bounds) call?

#3

It’s giving me 10 to 20 objects. I think the reason may be in the platformer implementation. Here’s the code.


public void update(long elapsedTime){
    MapView.follow(this);
    onground = !Map.isObjectCollisionFree(getX(), getY()+4, true, this);
    if (onground){
        setVelocityY(0);
    }
    if (!onground && !jumping){
    // Gravity
        setVelocityY(4);
    }
    // Jumping
    if (isPressed(VK_SPACE)){
        if (onground && !jumping){
            jumping = true;
        }
    }
    if (jumping){
        setVelocityY(-4);
        jump_time += elapsedTime;
        if (jump_time>=500){
            jump_time = 0;
            jumping = false;
        }
    }
    // Horizontal movement
    setVelocityX(0);
    if (isPressed(VK_LEFT)){
        setVelocityX(-4);
    } else if (isPressed(VK_RIGHT)){
        setVelocityX(4);
    }
}

It works fast again when I remove jumping. Also I posted the same question on stack exchange. They said BlockMaps and what are they?