Jump to content
  • Advertisement
Sign in to follow this  

effective Entity/Tilemap collisiondetection

This topic is 2586 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts


I am currently working on a 2d sidescroller in C++ and SDL.

Im using a tilemap made up by a vector of tiles.
The tiles have a hitbox, an ID and a type and that's pretty much it.

The different entity-classes there have internal collisiondetection, like;
void Entity::move(std::vector<Tile> tileset)
for (int i = 0; i < tileset.size(); i++)
if (Collision::check(box, tileset.get_box())); //Collsion being a static class
// Do something funny

This works fine but I noticed at one point when I expanded the size of my map that it drastically decreased the speed of the game (gamespeed being FPS-regulated)
I'm pretty sure this has to do with an ineffective way of passing the tiles around.

I have done a few things to fix this;
1. I only draw the sprites and tiles colliding with the camera.
2. I only add the tiles that are of type other then none to the vector (this takes away about 80-90% of the tiles)

And this worked out fine as the game runs as it should again.

My concern is that I only tried this with 4 enteties at a time, leading me to belive that I would notice a decrease in performance again once I hit a larger numbers of enteties.

Anyone got a tip as how I could make the collisiondetection between enteties and map more effective?
How I could work around the passing of the tilelist.

The only solution I have arrived at is having the collison occour outside the entities but that would make programming the effects of the collision much harder.

I want the enteties to move even if they are off screen so all enteties that exsist within the active level must be able to do collisiondetection at all times.

Thanks in advance. / AS

Share this post

Link to post
Share on other sites
It seems that you are checking an object against ALL the tiles. (is this what I'm seeing?)
that's not the way you do it. if you had 100 x 100 (that would mean 10000 tiles, you would have to check against all of them)
you have to calculate which tile is affected by the object position.
For example, my tiles are 32 pixels wide, and my character is at position 120;
I will have to check for collision at 120 pixels ( and 120 pixels + width of the character) against the tiles in that position.

tileset[(int)(object_position_x / tile_size_x)] will give you the tile number, then check if it's passable or not.

checking something against all tiles is a waste of resources.

Share this post

Link to post
Share on other sites
A basic approach would be to divide the map into a grid of sectors.

Simple explaination:
Every update, every entity checks which sector it belongs to and registers itself to that and the adjacent sectors(depending on its width)
Player checks which sector it belongs to, does collision check on all entities in its sector and adjacent sectors.

Try searching for "Quad tree collision 2d"

Share this post

Link to post
HI stromchin, thanks for your reply.

Your solution makes sence to me.
In order to apply such a system or a similar one I will have to change my tile and tilemap classes.
Would have been nice to not have to do any major changes to my code, but I can see why it's necesary, passing around this much (useless) information is not an option.

Thanks for the help!

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!