Minimizing amount of comparisons for collisions?

Question

In my 'Terraria' based game I am having lag issues. The cause of the lag is as follows:

• Every update loop through all the tiles in the world:
• If the rectangle that was passed as an arg intersects with the current tiles rectangle return true. If not go to the next tile.
• If the rectangle that was passed as an arg doesn't intersect with any of the tiles rectangles then return false.

My solution is to only check collisions for the tiles that are on the screen. At the moment my code renders all of the tiles regardless of the position. I know that this is a very lag-filled approach and I have no idea at all what the maths is to only get the tiles the player can see. If it helps the world is stored in a hash map that is initialised like this:

public Map<Integer, Tile> world = new HashMap<Integer, Tile>();
// numeric id = key , tile = value

I have tried looping through the tiles in 2 ways:

public boolean checkCollision(Rectangle argRect)
{
    for(int i = 0; i < world.size(); i++){
        Tile tile = world.get(i);
        Rectangle tileRect = new Rectangle(tile.rect);

        if(tileRect.intersects(argRect)){
            return true;}       
    }   
    return false;   
}

And:

public boolean checkCollision(Rectangle argRect)
{
    for (Entry<Integer, Tile> entry : world.entrySet()) {
          Object key = entry.getKey();
          Tile tile =  world.get(key);
          Rectangle tileRect = new Rectangle(tile.rect);
          if(tileRect.intersects(argRect)){return true;}
    }
    return false;   
}

Could I pass the players position to this method and have it only loop through tiles in the area? Would this approach have to loop through the tiles to see which ones are in the area?

Answer 1

There are a couple things you can do.

First, don't update every tile every tick of the game. Games like Terraria do periodic updates on only parts of the world at any time. Sub-divide your tile grid into chunk. Update one chunk each tick. You don't need to do it any more. You might even need to do it less. Things like growing grass and such are literally just a random check each time a tile is updated. You can control the rate of growth by altering how often ticks are done and how rare the random chance is.

For collision, you can limit it even further than what's on screen. In fact, for enemies near the edge of the screen, using only tiles on screen may be incorrect.

Instead, check the tiles that your rectangle could possibly be colliding with. You have a grid world. This is super easy. Take the upper left position of your rectangle, determine which tile that's in. Take the bottom right and do the same. Now you have the exact rectangle worth of tiles you can possibly be colliding with. This is probablyl (hopefully) what you do for drawing. Check against those. You could even with a little extra work determine which new tiles you could be colliding with (say, if you move right, and you can only move so fast each update, at most you have to check the right edge's worth of tiles), though there's probably no reason to do that.

Note that breaking your world into chunks can have further performance advantages. Generally, there will be one-four chunks visible at any given time. If you lay out the whole world in rows, each tile in each row is entire world's width away in memory. This can cause some (very slight) overhead. Keeping things in chunks means that a whole rectangle of tiles (left to right, top to bottom) are relatively close together in memory. If you process tiles in whole chunks at a time, this means your code runs slightly faster because more of the interesting data will be in cache at any given time.

Don't use a hashmap for your world. A hashmap is cheaper than many data structures, but your world (or a chunk in the world) is a 2D grid. Just use an array, which is always the absolute cheapest data structure when it is an option (and will be orders of magnitude more efficient than a hashmap in this case, I'd bet). I don't recall if Java supports 2D arrays automatically, but if not, just remember that array[y][x] is the same thing as array[y * width + x] and carry on.

Also avoid using full objects for your tiles. A simple integer will do if you are clever, do the world update trick I mentioned, and maybe a little bit packing. Objects are heavy-weight heap-allocated things in Java and a big grid of tiles will be inefficient as full objects. Likewise, avoid using operator new anywhere you don't strictly need it. Consider passing in rectangles to collision as simpler values (either explicit, x, y, w, h or using existing vectors and rectangles from your entities). new is not the cheapest operation, increases pressure on the garbage collecto