What datastructure would you use for a collision-detection in a tilemap?

Question

Currently I save those blocks in my map that could be colliding with the player in a HashMap (Vector2, Block). So the Vector2 represents the coordinates of the blog.

Whenever the player moves I then iterate over all these Blocks (that are in a specific range around the player) and check if a collision happened.

This was my first rough idea on how to implement the collision-detection. Currently if the player moves I put more and more blocks in the HashMap until a specific "upper bound", then I clear it and start over.

I was fully aware that it was not the brightest solution for the problem, but as said, it was a rough first implementation (I'm still learning a lot about game-design and the data-structure).

What data-structure would you use to save the Blocks? I thought about a Queue or even a Stack, but I'm not sure, hence I ask.

Answer 1

You should consider using a plain 2d-array or alternatively an array of rooms, where each room is a 2d-array or a grid.

A grid would looks something like this:

The player is the yellow dot and the blocks are the green ones. if the player is the light gray square, you only need to check for blocks that around that square area. This saves you the time of repopulating the hash supposedly if I understand you correctly.

You can check if the player is hitting something at (x = 770, y = 505) by dividing these values by a block's size and then checking the corresponding spot in the 2d array.

For instance if a block's size is 50 x 50 you do 770 / 50 = 15 and 505/50 = 10 so you check the array at array[15][10].

If the blocks are very sparse you could consider using a hash where the keys are the positions the blocks would have in the 2d-array.

Do not use a quad-tree unless you are absolutely sure you need it. It is definitely not required for nearly any 2d pc game nowadays.

If you memory demands are so intense that you need to consider loading and clearing data from memory like you suggest, divide the level into a grid and keep only 4 relevant squares of the grid in the memory at a time.

If your blocks are not even, simply create a grid (represented by a 2d array) and add the blocs to each square of the grid they overlap with in advance. Then check the relevant grid squares for elements the player might be colliding with.

Answer 2

For your collision I would merge adjacent colliding tiles together into one big collision box instead of iterating over every single tile and checking their individual collision.

Also I think that a quadtree would work much better than your current approach with a HashMap as it splits your gameworld up in sections and make it easy to delete a section of objects which are far from the player.

Answer 3

You should definitively use a quadtree as Hjorthenify suggest.

see: handling collision detection with a quadtree

At each frame you may reconstruct your quadtree and then for each collideable entity you retrieve the entities contained (or intersected) in the same area (NE, NW, SE, SW).

For exemple :

public void checkCollision(Entity e, ArrayList<Entity> entities) {

    QuadTree<Entity> tree = new QuadTree<Entity>(entities);

    ArrayList<Entity> sameAreaEntities = tree.retrieves(e);

    for (Entity collideable : sameAreaEntities) {
        if (collide(e, collideable)) {

            // do something

        }
    }
}