Making a perfect map (not tile-based)

Question

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;
}

Also some tutorials on sprite-based maps are needed. But on google search, I get tile based maps.

My question is how can I make a more efficient map system? I don't want using tile-maps as they aren't fit for every game.

And since the solid objects won't move, should I consider them as tiles??

Thanks.

Answer 1

For collision detection doom used a technique called a blockmap instead of a quadtree, to find objects that needed to be tested for collisions.