Back to General and Gameplay Programming

Simple 2D collision detection for a platform game (easiest solution possible using tile engine)

Tom Kingston · 2015-12-18T14:05:25

Hello there forum dwellers!! So I recently started thinking that there don't seem to be many tutorials out there which teach tile collision in a simple manner. The ones that do seem to skip out on one of the most important aspects: handling corners/edges. So I've been working on a platform game for quite some time now, and it uses a tile collision system which seems to do the job, but it also seems to have a few problems of its own. I'd just like to be able to have a tile engine which detects where something is in relation to a tile, then adjusts its position accordingly. Currently, the tile system I have in place seems to work fine, but every now and again, some objects seem to slip through cracks in the tile, and I honestly can't figure out why. I've had this problem for a couple of years now, and it's always just gone on the backburner, because whenever I try and fix it, it just infuriates me! I have a few theories about what could possibly be causing it, but I'd really appreciate some insight from some more experienced programmers than myself! Here's the general gist of how it works (in order): 1.) Game receives player input 2.) All game objects on screen update accordingly 3.) All game objects check for collisions with tiles 4.) All game objects re-position It's also worth mentioning that the tiles are given properties as the level is loaded in. So if there's a strip of horizontal tiles, for example, only the tops and bottoms will check for collision, since nothing can fall inside of them and check for left/right collisions. Tiles surrounded by tiles are actually negated, since nothing can touch them, and perform no collision checks at all. An example of this is shown in this screenshot, where only the edges that use detection have a shadowed highlight around them: As we see here, the strip of tiles under the player only check where collisions can happen. The strips to the left and right have no top/bottom collision checks. As far is this goes, the collision works the majority of the time. However, sometimes things can fall through, such as bullets, shown here: http://giphy.com/gifs/xTka01Lb9WeBuchFrq Bullets and players inherit from the same class, so they use the same collision method. Here, we see the player's collision is handled fine until he hits a booster pad, which pushes him out of the map, even though his velocity is capped: http://giphy.com/gifs/l0OWjxILsfxsbzLa0 The interesting thing about both of these is that the bullets and player only seem to be passing through the cracks in the tiles. I've noticed that most of the bullets fall through the tiles when either (bullet.x == tile.x) or ((bullet.x + bullet.width) == (tile.x + tile.width)), with the odd ones also falling through the middle tiles. So I guess there's no x penetration to take into account there. Also, the player passes through the wall when the base of him is touching the top of the tile ((player.y + player.height) == tile.y) or also when the top of him touches the underneath of a tile (player.y == (tile.y + tile.height)). This could just be coincidence, but it's an observation I've made. Below is the code which every game entity uses to check against collidable tiles. If anyone could offer some insight, or even a more graceful solution, I would really appreciate it! public void BoxCollision(CollisionTile currentTile) { GameSpace.collisionsWithHashing++; Vector2 penetration; Vector2 detection; detection.X = (currentTile.Rectangle.Left + currentTile.Rectangle.Width / 2) - (collisionRectangle.Left + collisionRectangle.Width / 2); detection.Y = (currentTile.Rectangle.Top + currentTile.Rectangle.Height / 2) - (collisionRectangle.Top + collisionRectangle.Height / 2); if (Math.Abs(detection.X) > (collisionRectangle.Width / 2) + (currentTile.Rectangle.Width / 2) || Math.Abs(detection.Y) > (collisionRectangle.Height / 2) + (currentTile.Rectangle.Height / 2)) { } else { //Collision has occured. penetration.X = (collisionRectangle.Width / 2) + (currentTile.Rectangle.Width / 2) - Math.Abs(detection.X); penetration.Y = (collisionRectangle.Height / 2) + (currentTile.Rectangle.Height / 2) - Math.Abs(detection.Y); if (penetration.Y < penetration.X) { //Touching top or bottom of platform if (detection.Y < 0 && currentTile.bottomCollidable) { //Hitting underneath of platform collidingWithBottom = true; if (velocity.Y < 0) { if (elasticity > 0) { velocity.Y *= -elasticity; } else { velocity.Y = 0; } position.Y = currentTile.Rectangle.Bottom; } } else if (detection.Y > 0 && currentTile.topCollidable) { //Hitting top of platform (walking and gravity bound) collidingWithTop = true; if (velocity.Y > 0) { if (elasticity > 0) { velocity.Y *= -elasticity; } else { velocity.Y = 0; } position.Y = currentTile.Rectangle.Top - collisionRectangle.Height; } } } else if (penetration.X < penetration.Y) { //Touching right or left of platform if (detection.X < 0 && currentTile.rightCollidable) { //Hitting right side of platform collidingWithRight = true; if (velocity.X <= 0) { if (elasticity > 0) { velocity.X *= -elasticity; } else { velocity.X = 0; } position.X = currentTile.Rectangle.Right; } } else if (detection.X > 0 && currentTile.leftCollidable) { //Hitting left side of platform collidingWithLeft = true; if (velocity.X >= 0) { if (elasticity > 0) { velocity.X *= -elasticity; } else { velocity.X = 0; } position.X = currentTile.Rectangle.X - collisionRectangle.Width; } } } } }

General and Gameplay Programming Programming

Started by zuhane December 01, 2015 11:51 PM

28 comments, last by zuhane 8 years, 4 months ago

Plus Pingya

107

December 03, 2015 05:45 AM

What I usually do is:


const float stepValue = 0.5f;

for (float i=0.0f, step=absf(velocity.x)/stepValue; i<step; i+= stepValue) {
    bool collisionNotOcccured = someLogicToCheckCollision();
    if (collisionNotOccured)
       position.x += stepValue;
    ...
}

This way, no matter how distance the object need to be moving in a single frame, it will always being blocked by the collision. In the other words, the object's position is being checked every stepValue (0.5f). Your problem is, when your object is moving a long distance in a single frame, or fast (bullet). The object's position may skips some tile collision checking. Imagine that you are having tileWidth 32.0f, but your bullet is moving 40.0f per frame, it will obviously skip the collision checking for that specific tile that supposes to blocked the bullet.

zuhane

320

Author

December 03, 2015 08:50 PM

Right, so I've been doing some serious research into this subject and I've come across this:

http://answers.unity3d.com/questions/176953/thin-objects-can-fall-through-the-ground.html

I'd imagine that this seems to be occurring due to the size of the bullets. The mac shoots bullets that are 3x3 pixels in size, so it seems that

due to the slightly randomized Y velocity each bullet is given as it is created, some of them just clip through the floor. I've found that if I preference

the Y penetration over X penetration in my code, it takes preference of collision with corners. In other words, the lines:


penetration.X = (collisionRectangle.Width / 2) + (currentTile.Rectangle.Width / 2) - Math.Abs(detection.X);
penetration.Y = (collisionRectangle.Height / 2) + (currentTile.Rectangle.Height / 2) - Math.Abs(detection.Y);

can have a slight change here:


penetration.Y = (collisionRectangle.Height / 2) + (currentTile.Rectangle.Height / 2) - Math.Abs(detection.Y) - 5;

causing the Y penetration to take slight preference over the X penetration. This means that when the player rolls up a wall, he no longer has a weird clipping

issue with corners, and automatically pulls himself onto ledges if there's a 5-pixel gap involved, shown here:

http://giphy.com/gifs/d2YX8ZlN2gD37x9S

This also creates a larger margin to check for collisions with the top or bottom of a tile, meaning that with this in play, bullets no longer fall through the floor or

fly up through the ceiling. However, clipping is now more likely to occur with left and right collisions:

http://giphy.com/gifs/d2Z9hH2IrRE9Y4qQ

Now, this is interesting, as the exact inverse can also apply. If I change the other line of code to:


penetration.X = (collisionRectangle.Width / 2) + (currentTile.Rectangle.Width / 2) - Math.Abs(detection.X) - 5;

Then the X penetration now has a bias over the Y penetration, meaning that if an object is at the corner of a block, it preferences moving to the left or right (whichever is nearest) and drags from the top or bottom, shown here:

http://giphy.com/gifs/26tPe8JwTgOFeZQbK

Also, with this in place, bullets now never clip through the right or left parts of a wall, but fall through the ground/ceiling much more often:

http://giphy.com/gifs/26tPs3a88YPcP9bvG

=====================================

I'd also just like to mention something else. I'm almost certain that using contact lists won't actually help fix the problem at all. This is because the right/left checkers

of the wall ONLY affect the object's x-axis, and the top and bottom ONLY affect the y-axis, so touching multiple tiles at once should not cause any sort of conflict of interest.

I think the problem seems to be the bullet-through-paper issue that was mentioned earlier. I've tested a few things, and I've noticed that bigger objects are allowed to move

faster without clipping through walls, and smaller objects are not allowed to move as quickly, since they have more chance of completely skipping through a tile and never

performing a collision check in the first place.

My friends and I are currently trying to crack this problem, and we'd like to try a method which prevents bullet-through-paper issues. Bearing in mind that we're really not

professionals by any standard, could you guys possibly recommend some kind of tutorial or simple solution to this problem? I looked at your code, pluspingya, but I don't really understand what it does.

I was thinking of possibly storing the previous positions of all objects in a buffer, then checking to see if there's a tile in-between the current iteration and past iteration on every update, but would this be CPU-intensive? Is there a more graceful solution? Look forward to your replies!

http://giant.gfycat.com/AccomplishedCluelessIbisbill.gif

Khatharr

8,814

December 03, 2015 08:55 PM

If it is the bullet through paper problem then you could try not using paper, but the best solution is continuous detection. Are you using any kind of broad-phase test?

void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

zuhane

320

Author

December 03, 2015 09:15 PM

I'm not using broad-phase as far as I'm aware. It seems that even large objects can clip through if they're moving fast enough though. Is it

speculative contacts that fixes this problem? I've tried googling it, but the results seem way too daunting and beyond my level of programming.

http://giant.gfycat.com/AccomplishedCluelessIbisbill.gif

Khatharr

8,814

December 03, 2015 09:35 PM

A broad phase test is a cheap collision test or method of organization that discards obvious misses before running more expensive tests. You expressed concern about performance costs related to continuous detection (the storing the previous position thing). Incidentally, rather than having some external buffer somewhere, you could just hold the previous position in the object itself. If your stages are very large at all then you'll probably want some kind of broad phase in any case.

Fortunately in 2D tile-based games you can implement broad phase tests quite easily.

http://www.wildbunny.co.uk/blog/2011/12/14/how-to-make-a-2d-platform-game-part-2-collision-detection/

You just create a rect that encloses the entity at its previous and current positions, then you only have to test against tiles that intersect that rect.

void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

BeerNutts

4,410

December 03, 2015 09:56 PM

My 1st thought for your problem was that it was the bullet through paper, but you had said:

I'd just like to point out that the velocity isn't causing the problem. I've done some reading around the subject on how objects moving
at a high velocity can pass through the tiles without ever getting to perform a check, but this is happening with objects moving at a

capped velocity, so it's not an issue to do with speed. I'll add this in later though!

So, I assumed you had already looked at the issue, and thus I didn't bring it up as a possibility. The wildbunny link from Khatharr is a good one. Of course, if I were writing a platformer, I'd be using a 2d physics library (chipmunk-physics, box2d, etc.) and not trying to handle all the physics myself, but it's can be fun writing the physics code yourself.

Good luck!

My Gamedev Journal: 2D Game Making, the Easy Way

---(Old Blog, still has good info): 2dGameMaking
-----
"No one ever posts on that message board; it's too crowded." - Yoga Berra (sorta)

zuhane

320

Author

December 04, 2015 05:29 PM

Is it a good idea to mix broad-phase with spatial hashing? I already implemented spatial hashing as I wanted to have large

levels available. Could I, in theory, check through a spatial hasher, then reduce checks even further with a broad-phase collision test?

would broad-phase essentially replace my current loops which check each spatial hash table?

I'm tempted to do this if you think it can solve the clipping issues that I'm having.

And to BeerNutts: I have actually put in velocity caps, but I'd imagine that certain objects are just so small that a velocity cap still doesn't account

for the sheer tiny size of the object, so I wasn't too clear about that! I didn't think it was velocity-related, but since bigger objects can move faster

without clipping, I'm beginning to think it is. I might as well add this in if it allows me to have fast-moving objects all over the screen.

I considered using a library before, but many people have said that they're very difficult to come to terms with, and would probably be extremely overkill

for a game that barely uses any physics :)

http://giant.gfycat.com/AccomplishedCluelessIbisbill.gif

Khatharr

8,814

December 04, 2015 08:22 PM

A spatial hash is effective as a broad phase.

http://www.gamedev.net/page/resources/_/technical/game-programming/spatial-hashing-r2697

This doesn't solve your clipping problem though. This is to manage collision performance, since you expressed concerns about that.

void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

BeerNutts

4,410

December 04, 2015 09:59 PM

I considered using a library before, but many people have said that they're very difficult to come to terms with, and would probably be extremely overkill
for a game that barely uses any physics

Well, I'd disagree with them, but that doesn't mean I'm right :) IMO, any game that uses movements and collisions and any kind of collision responses should use a physics library as it makes moving, collision detection, and collision response VERY SIMPLE. there is some learning curve, but IMO it's worth it.

Anyway, I know it's probably too late in your game for this, but, maybe for future reference, take a quick look at my old blog in my signature (start form old posts), it details making a top-down 2d game using a 2d physics library (chipmunk-physics).

Good luck, and have fun.

My Gamedev Journal: 2D Game Making, the Easy Way

---(Old Blog, still has good info): 2dGameMaking
-----
"No one ever posts on that message board; it's too crowded." - Yoga Berra (sorta)

zuhane

320

Author

December 04, 2015 10:31 PM

Ah yes, I'll definitely consider implementing some kind of library. I do, however, just want to know if there's any solution

regarding bullet-through-paper problems. I believe I'll try something similar to broad-phase by storing a buffer of previous positions

of objects and seeing if anything intersects the current positions with the previous buffer positions. I'll post if I find any new developments,

as people reading this may gain something from it!

http://giant.gfycat.com/AccomplishedCluelessIbisbill.gif

Simple 2D collision detection for a platform game (easiest solution possible using tile engine)

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Simple 2D collision detection for a platform game (easiest solution possible using tile engine)

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines