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

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.

• I suggest you use an existing collision engine as creating a new one will not teach you the techniques you need to assemble code from existing pieces which is what most people often do when they work on a project so they could focus on the unique elements in their game that makes the gameplay and art shine. – wolfdawn Aug 18 '14 at 15:45
• @Zehelvion: Initially I thought about using Box2d but as all the blocks are destroyable it would be a huge amount of additional objects created just for the physics. – Solom Aug 18 '14 at 16:46
• You may want to reconsider it as it has advantages (learning-wise and result-wise) but I don't know if it will work well if you have a lot of boxes. There might be other existing tested code that does the same thing. It is nearly always best to use existing code. – wolfdawn Aug 18 '14 at 17:31

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.

• Well, currently the whole map is a 2D-array (or made of one) but for the neighboring blocks of the player I used a HashMap. – Solom Aug 18 '14 at 16:44
• But what kind of hash map, what exactly are the keys and values? – wolfdawn Aug 18 '14 at 17:28
• it says so in my question but I had to edit because the editor didn't render the angle brackets. I save the coordinates as key (in Form of a Vector2) and the Block itself as value. – Solom Aug 18 '14 at 18:09
• It sounds reasonable. Are you experiencing issues with this? I am not sure what you mean by putting more and more blocks in the hash map so I think that although it is generally a bad idea, you may want to add a small section of code specific to this question. I don't fully follow why you need to populate and then repopulate the hash frequently. Perhaps you should consider a grid (2d-array) of hashes, so you only need to check the hashes that are on squares near the player. – wolfdawn Aug 18 '14 at 18:35
• Well, I populate the HashMap with a neighborhood of the player (50 blocks up, down, left and right). As the player moves this neighborhood changes of course, so that's why I have to, at some point, drop the HashMap and start over, because if it has hundreds of thousands of entries I guess it will become a bit of a performance bottleneck down the line. Currently I can't imagine how to do that with a grid (I'm not a native speaker!) but I think I get what you mean. – Solom Aug 18 '14 at 19:06

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.

You should definitively use a quadtree as Hjorthenify suggest.

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) {