2D Tile-based Collision Detection

Question

I've been planning an indie game project for a while now. I'll summarise it for you so I can get right to the question.

It's done entirely using the latest version of XNA through Visual Studio. Hoping to put it on 360 and PC, but am only really looking for a PC-oriented solution at this stage.

It's a 2D side-scrolling shooter (think Metroidvania-style, or even Terraria). It will eventually include an in-game map editor with maps being tile-based (16x16). There will be upwards and downwards scrolling. I'm hoping to implement tile layers in the dev map editor (reason for a dev map editor is it's going to be heavily leaning towards a content-focus, so there will be a lot of maps).

Physical tiles will be very simple with only two major types. Block tiles, which are just a solid tile, and angled tiles, which are tiles with an incline that characters can walk on. I'm strongly considering abandoning angled tiles entirely, but not sure yet.

The character/NPC movement will be simple. Moving side-to-side, jumping, falling, flying (with appropriate items/situations), teleporting. All very static, no dynamic physics necessary. Only basic gravity. When a character steps off the edge of a tile, it falls. When it jumps and a tile is above it, it stops short and falls back down. When it reaches a protruding tile/wall, it can't move further unless it jumps over or flies. All the basic stuff.

Projectiles can be affected by gravity as well, and some situations may arise where a projectile may be manipulated mid-flight, but nothing requiring heavy physics. Some projectiles will move characters as well (think a simple "pushing" mechanic).

So here's the question: I'm at the stage where I'm starting to work on movement and collision-detection but I just can't set myself on a way to go about them. I need ways to determine when character, tiles, and projectiles collide. Given what I've said about the style I'm going for and the tile-based system I'm using, can I get some recommendations+links to some tried and true collision detection methods others have used in similar situations, and maybe an example of a game using a similar approach? What I need more than anything else is inspiration.

And just a quick note, I have several years of experience as a programmer, so I'm not a total newbie :)

Answer 1

I just discovered http://higherorderfun.com/blog/2012/05/20/the-guide-to-implementing-2d-platformers/ and seems a pretty good overview on 2D platformers. I haven't finished reading it, but i think it can help you a lot!

Also i can recommend http://info.sonicretro.org/Sonic_Physics_Guide, which is broad overview on physics techniques used in Sonic.

Answer 2

But the amount of projectiles I'll have on screen at any given time means I'll be looking to implement something like QuadTree to keep things smooth performance-wise.

You might be okay without a quadtree:

1. Collisions between projectiles and static environment tiles can be done directly on the tiles array, without the need for any additional data structure. In other words, you can easily find which tiles an entity (e.g. a projectile) is intersecting directly, with a few calculations based on the bounds of the entity and the tile size. The platformer sample has an example of this problem which I'll transcribe below:

   int leftTile = bounds.Left / TileSize;      // bounds = Rectangle of your entity
   int topTile = bounds.Top / TileSize;
   int rightTile = (int)Math.Ceiling((float)bounds.Right / TileSize) - 1;
   int bottomTile = (int)Math.Ceiling(((float)bounds.Bottom / TileSize)) - 1;
   
   for (int y = topTile; y <= bottomTile; ++y)
   {
       for (int x = leftTile; x <= rightTile; ++x)
       {
           // Entity is touching tile[x, y] so check and handle collision
       }
   }
   

2. For other dynamic objects such as characters, you could dynamically register/unregister them with the tiles that they're intersecting as they move, so that at any moment and for any tile you can directly know if any objects are there (here's an example, article about spatial hashing). If you implement that, then you can just do the same as step one to find which tiles the projectiles are interesecting, then check your grid to see if any objects are there, and if there are, iterate over them linearly.

   This data structure can be as simple as:

   var grid = new List<Entity>[width, height];
   

   Or:

   var grid = new Dictionary<int, List<Entity>>();
   

   In which case you'd convert [x,y] to a single int key like x+y*width and then store in the dictionary.

Answer 3

If you are thinking about the high level flow of the movement and collision detection, something like this is common:

1. Handle logic and player input
2. Update object positions
3. Detect & handle collisions

When detecting collisions you want to filter out tiles and objects that are too far away to make it more efficient. If your level is defined as a 2d array for example you want to just consider the tiles in a certain range around each object. If your level is made out of tile objects, you might need to use some kind of spacial partitioning to avoid iteration through all of them.

To keep it simple you should probably use axis aligned bounding boxes for the collision shapes. This might help http://www.wildbunny.co.uk/blog/2011/12/14/how-to-make-a-2d-platform-game-part-2-collision-detection/

If you want to handle slopes and more general convex shapes you could use the separating axis theorem: http://rocketmandevelopment.com/2010/05/19/separation-of-axis-theorem-for-collision-detection/, but it might be simpler to make an ad-hoc solution for slopes if you only have a small number of slope types.