Sign in to follow this  
AlanSmithee

effective Entity/Tilemap collisiondetection

Recommended Posts

AlanSmithee    2102
Hello.

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;
[code]void Entity::move(std::vector<Tile> tileset)
{
for (int i = 0; i < tileset.size(); i++)
{
if (Collision::check(box, tileset[i].get_box())); //Collsion being a static class
{
// Do something funny
}
}
}[/code]


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
stromchin    102
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
Atomical    99
Hidden
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
AlanSmithee    2102
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
Sirisian    2263
[url="http://www.gamedev.net/topic/602654-collision-detection-with-a-tilemap-raping-the-walls/page__view__findpost__p__4815243"]Could look at this post also.[/url]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this