Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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());
    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??


share|improve this question
Hello, instead of saying "I need to implement [method name] because it's slow" tell us what you have problems with. It's confusing, because a sentence before you stated that your quad tree detection is fine with 30000 objects (i.e. is very fast, not slow). You should also remember that on this site we solve repeatable problems, and fixing bugs or low-level implementation issues is rarely considered repeatable. – Markus von Broady Nov 13 '12 at 11:43
The main problem is that when calling this method, the game would freeze and some times lags in seconds. – Sri Harsha Chilakapati Nov 13 '12 at 11:46
I fear this is a typical case of not asking the right questions.. once you figure out what the right question is, the answer is most likely obvious. – Jari Komppa Nov 13 '12 at 11:51
If your collision detection method is so fast it works on tens of thousands of objects, just use it, save all collided objects in an Array and in isObjectCollisionFree check if the object is in the Array. But I'm afraid your collision detection isn't so fast as You think and that's where the problem lies. – Markus von Broady Nov 13 '12 at 12:05
And here is a way of using resized bitmaps as a quadTree:… – Markus von Broady Nov 13 '12 at 12:13

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

share|improve this answer
How could I use BlockMaps for this purpose? The quad-tree is working fine. The main problem is in the collision free method. Perhaps I should move the object to the position, check collisions and restore it. – Sri Harsha Chilakapati Nov 13 '12 at 12:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.