How to approach 2D side-scrolling platformer collisions easily

Articles & tutorials
#1

Hello everybody!

After I started making my 2D side-scrolling platformer, I realized that even though there are many tutorials around, none of the ones I’ve found go into detail about the collision detection for the player and the monsters. Now, this isn’t a tutorial as such; more of an overview of what to consider, and warnings about which paths not to take.

After trying 2 other methods over the past 2 weeks, and not ending up with a result I could live with, I compiled a list of steps I would take in pursuing a new method of doing things. I’ve finished my own implementation using this method, and it is working very nicely. The two first methods actually worked fine, but had a few kinks I had no way of fixing, and the code got very frustrating to look at after a while. I also had too many little “fixes”, and I wanted something simpler and with less tweaking needed. Something solid.

The key is to have a good overview of what you need to do, and to keep in mind that you want to be able to smoothly transition from player-collisions to monster-collisions, reusing as much as you can. Also, it is a VERY good idea to not just make a lot of points and start detecting tiles on all of them at once. Start slowly, one point at a time. It’ll save you much bug-fixing later.

Take a look at what I’ve ended up with. A few tweaks, and it’ll be flawless.

First, a little overview of approaches you can take, depending on what kind of movement you want. A great reference, is this large overview of the Sonic engines (thanks, UpRightPath, for the link! Their site seems to have broken down, but the text and pictures are still there).

Sonic uses 2 vectors pointing down, 2 for each side, and 2 points at the top.

http://img607.imageshack.us/img607/7578/soniccollisions.png

He also has a point at the bottom in the exact middle. Can’t remember what it is used for, and I can’t go to that site right now. His position is actually in the exact middle of him, and all points are relative to this point.

Sonic engines have many different kinds of tiles. Some of them only collide with some of his collision-points, so if you hit them just right, you can pass through them. Some only work when he’s in a specific state, like the ball and so on. I’m trying to make the point, that your system can be as elaborate as you want it to be. Just make sure you’re set on what you want to do before doing it.

My approach is a bit different. I’ve uploaded a version with debugging-information shown.

There are many points around my player, and even though these don’t change visually depending on the state of my player, you’ll get an idea of how it works. As a side-note, you can see I’ve used a bounding collision rectangle for my monsters, and if a projectile is within such a rectangle, it checks if it’s hitting any of the internal collision rectangles, and administers damage according to the damage ratio for that rectangle. Fun with collisions :smiley:

Anyway, as you can see, my approach is nothing like Sonics. I have 1 point for the feet, 1 for the head, and 3 points in either side. This was because I made the decision that I didn’t want to be able to “stand in the air”, like you can in Sonic because of his 2 vectors at the bottom. Depending on whether I’m jumping, falling or simply strolling about, each point has different functions, and they’re even shifted around a bit.
As an example, because I wanted sloping tiles and also wanted sloping tiles that are upside down, I use a slopeOffset calculated in the constructor of each sloping tile as an offset to these points, so they don’t collide with the slopes. The same technique is used for the 2 points at the top in special cases.

The point at the feet is the actual player position, and it is also the only point colliding with the ground beneath the player, so this is where all the sloping is happening. This is far more difficult to manage than having 2 points, so I probably won’t take that path again. Having 2 points gives you some leeway for handling slopes, falling, and the horror of doing pixel-based collision detection when using floating points, like doubles. I had a lot of trouble making this work, not to mention making it look smooth.

Well, enough talk, let’s get down to business. I’m not promising you vector magic! As I wrote earlier, this is more of an approach to the problem. I only used doubles and ints for my collisions, and it was more than enough for me. Vectors are great when you want to have more physics implemented, though. Sonic has at least three speed-vectors! GroundSpeed, horizontal speed and vertical speed. Use whatever you want.

I would like to start by talking a bit about pitfalls you might, well, fall into :stuck_out_tongue:
First of all, you’ll end up with the easiest calculations, if you do NOT factor in the movementSpeed when detecting your collisions, and then move the player afterwards. Just move the player first, check for collisions, and act accordingly. For smoothness, use a saved position from before he moved, to move him back precisely where you want him, when you detect a collision. I tried the approach of moving him back by movementSpeed*deltaTime, but it resulted in jittery movement when he collided with things.

Also, don’t bruteforce-fix issues. If you’re having problems with weird movement, do the required System.out.println or use the debug-environment in your IDE. If you have a problem with a collision for a specific set of events, there’s more than likely a way to fix it which is not something like “if this this this this this this and this, then do not collide”. Find out why the problem is happening, and then fix it. Any time you brutefore-fix anything, you might end up breaking your collisions in several other cases.

Step 1 - Prepping
It is a good idea to have a map-layout ready. Make sure you know what kinds of tiles you want. Do you want slopes? (they’re hard to deal with) Do you want traversable tiles you can jump through and land on, and if you hit Down while on them, you fall through? Is there water? Are there moving tiles?

Spend at least some time thinking about it before you throw yourself at it. Play your favourite platformers, and get a sense of which powers are at work.

Here’s my initial setup for a map-structure:
Tile = abstract class, which all tiles extend. Has an int type to identify tileType, or you can do it with the instanceOf-method.
FullColTile = a tile which is fully collidable. Has a boolean transition set to false
TransitionTile = a FullColTile, with transition set to true. Will help us enter sloping tiles properly
SlopedTile = a tile which the player only collides with, if the point being checked is above or below the slope, depending on whether the tile is sloping at the top or bottom
TraversableTile = a tile which only the player’s feet will collide with; if holding Down, the feet will ignore their collisions for these tiles

For reference and reading of the source, my tileTypes are:
FullColTile = 0
SlopedTile = 1
TraversableTile = 2

My SlopedTiles have a point in each side, indicating how high the slope is on either side.
Then, to get the Y-position I need to put the player at, I can use simple line-math to find y according to player X position.
In a tile-system with only 40x40px tiles, I can do this to find out which Y the player is at in the current tile: posY%40
That divides the player’s Y-position, and returns the remainder to me.

The player has a collision-rectangle surrounding him, neatly fitted. I use this as a reference when making points, but you can also just use derivatives of the player position. Below I have explained it as using the player position, but in my source the points will be made using my collision rectangle. It is basically the same thing, and the collision-code will work either way.

EDIT: What you really want is…
when you’re trying to move, you want to move as much of the intended movement you can execute, before stopping your character. This involves the following steps:

  1. Check if you’d collide using the intended movement
  2. If you do collide, change your intended movement to 1 pixel less
  3. Repeat 1 and 2 until you don’t collide or your intended movement has become 0
  4. If your movement has not reached 0, move the character the remaining intended movement. Otherwise, ignore the movement.

If you’re using sloping tiles, do the movement horizontally first, and then the vertical movement. Correct for slopes at your head and feet. You’ll want to do a follow-up check to see if any points collide afterwards. An example could be, that you’re moving up a slope, and your head hits a tile sloping on the bottom. Your slope-corrections might end up cancelling each other out (unless you’ve taken it into account during your corrections), and you’ll end up being inside a tile. If this happens, you want to move the player back horizontally, and then check top and bottom collisions again, and correct them.

As you can see, while this approach is the most “clean” and accurate, it requires a good deal of collision-detecting on each point to work. My approach below only checks each point once, and does a rollback of the character movement if it collides, plus a few extra corrections (refer to my horrible code). While I’ve been able to make it work with next to no jitter (even while jumping furiously between 2 slopes), it is not the prettiest approach, but it is very CPU-friendly :slight_smile:

After writing this, I’ve decided to implement the solution described above for my player, and use the approach below for my monsters. Though the approach below seems to work just fine, even through my extensive testing, I don’t want to risk players getting infuriated or irritated about collisions that might screw up in certain situations, so I want them to be perfect. I don’t really need my monsters to have ultra-perfect collision detection, though. If they collide with something, they just turn around instantly anyway, so I might as well save the CPU-cycles.

I just wanted to make it perfectly clear, that the method described below, is an EASY and thoroughly tested solution to collisions, thought up because I didn’t want my collision-detection to eat up my CPU, even if I do put 800 monsters on-screen. It is not the best solution, but in the least, this document can be an inspiration to people doing their first collision-detection, and save them a bunch of time trying out many different methods, like I did.
End of EDIT

Step 2 - Where am I?
Have the player walking in the top pixel of the FullColTiles. This is more of a state of thinking, than an actual action. You should be aware that this is the easiest way to go about it, instead of trying to make sure the player position is always above a tile. Trust me, I’ve tried!

Before we go any further, there are a number of variables we want to set.
Just before you start your collision-detection, make 2 int’s called roundPosX and roundPosY, by using Math.round() on your X and Y positions, and use these for your calculations instead of the actual position. Using floating-point variables for this kind of collision-detection gets tiresome, and is hard to make smooth.

Make 2 doubles to hold the old player X and Y positions before he is moved.

Move the player according to his wishes.

Create 2 variables to hold the X and Y for the tile the player is currently in, according to the new player position.
Bear in mind, using division will always leave you short by 1, so remember to add this manually, like this:
int currentPlayerTileX = (int) Math.round(posX/40)+1;
int currentPlayerTileY = (int) Math.round(posY/40)+1;

Step 3 - Can I go now?
Check horizontal collisions on these points, and move the player back to oldPosX if any collide. It is also nice to have booleans representing the result for each point, so you can do some tweaking after running through them.

BotLeft: (playerPosX-(playerWidth/2), playerPosY-slopingOffset)
BotRight: (playerPosX+(playerWidth/2), playerPosY-slopingOffset)

MidLeft: (playerPosX-(playerWidth/2), playerPosY-(playerHeight/2))
MidRight: (playerPosX+(playerWidth/2), playerPosY-(playerHeight/2))

TopLeft: (playerPosX-(playerWidth/2), playerPosY-playerHeight+slopingOffset)
TopRight: (playerPosX+(playerWidth/2), playerPosY-playerHeight+slopingOffset)

The slopingOffset, is the slopeHeight of X ((playerWidth/2)+2) in the most sloping tile you have. This makes sure, that if a collision is detected on a slopedTile horizontally, stop him, if he’s about to enter a slopingTile. Using the width/2 is to get the maximum amount of pixels a collision point can enter a tile, be fore the player himself enters it, and the +2 is added because my points are all 1px outside the collision rectangle.

NOTE: When jumping or falling, botLeft and botRight omit the slopingOffset. I do this, because I use them to push the player away from a ledge or tile, if either of these points collide with the world and his actual position didn’t reach the tile.

Step 4 - Watch your head!
If the player is walking around, maybe on a slope, and bumps his head on a tile, we want to rollback his X movement, but if he is jumping or falling, we don’t want his forward movement stopped. So, when the player is not jumping or falling, just reset his posX if he hits something with his head. This is the last thing I’m struggling with myself, but I’ve found a solution that’ll have to do for now.

If not jumping or falling:

  • if it is a FullColTile (which also means TransitionTiles; remember to omit them from this), move the player back to oldPosX
  • else if it is a sloped tile, and it is sloping at the top, move the player back to oldPosX
  • if it is a sloped tile, and it is sloping at the bottom and the top of the player is above the slope, move the player back to oldPosX
  • if it is a traversable tile, do nothing

else if jumping:

  • if it is a FullColTile (which also means TransitionTiles; remember to omit them from this), move the player down to oldPosY, and move him to oldPosX
  • if it is a sloped tile, and it is sloping at the top, move the player down to oldPosY, and move him to oldPosX
  • if it is a sloped tile, and it is sloping at the bottom and the top of the player is above the slope, I found that it did not work well for me to reset him to his old positions.
    Slopes are hard to master, so I took a different turn here, and subtracted jumpSpeed*elapsedTime instead. Test the 2 approaches out a bit. It’s fun :smiley:
  • if it is a traversable tile, do nothing
  • Remember to do stopJumping() and startFalling() at any of those.

else if falling (it’s hard to hit your head whilst falling, but better not leave anything up to chance):

  • if it is a FullColTile (which also means TransitionTiles; remember to omit them from this), move the player down to oldPosY, and move him to oldPosX
  • if it is a sloped tile, and it is sloping at the top, move the player down to oldPosY, and move him to oldPosX
  • if it is a sloped tile, and it is sloping at the bottom and the top of the player is above the slope, again I took the same path as described for jumping
  • if it is a traversable tile, do nothing

Step 5 - Let’s see you daaaance!
Check all foot-collisions from the player position point. It is important that this is the last step, because we want to place the player correctly, depending on the collision-detection we’ve already done. See, if we did this first and moved the player to the right spot on a sloped tile, and then messed around with posX afterwards, he would end up being inside or above the slope.
As an extra note, you should check whether your actions here mean that the players head ends up in a tile, and if so, undo your action and reset his X, too. I haven’t done this, and my implementation still suffers a bit from it. I have a workaround for now.

If not jumping or falling:

  • if it is a FullColTile, do nothing
  • if it is a transition-tile (the tile under a slope), move him up 1px
  • if it is a sloped tile, this is where we need to do something extra, to keep the player from sticking when moving to a sloped tile which doesn’t have the same height as the tile we came from:
    • check 1 pixel below the feet, and using this point, find out the following…
      • is this a sloping tile, which is sloping on top? If so, continue…
      • if this point is below the slope, move him to the correct Y on the slope
      • else startFalling()
        NOTE: Remember, we already took care of tiles sloping upwards, by moving the player 1px up when he enters a TransitionTile,
        so we only consider tiles sloping downwards here.
  • if it is a traversable tile, and the player has enabled traversing (holding Down), start falling
  • if there’s no collision, startFalling()

else if jumping:

  • if it is a FullColTile, move the player to the top pixel in the tile
  • if it is a transition-tile (the tile under a slope), move the player to the top pixel in the tile and then y-1
  • if it is a sloped tile sloping on the top, and he is under the slope, move him to the correct Y on the slope
  • if it is a sloped tile sloping on the bottom, move the player to the top pixel in the tile
  • if it is a traversable tile, do nothing
  • For all those, also remember to do stopJumping()

else if falling:

  • if it is a FullColTile, move the player to the top pixel in the tile
  • if it is a transition-tile (the tile under a slope), move the player to the top pixel in the tile and then y-1
  • if it is a sloped tile sloping at the top, and he is under the slope, move him to the correct Y on the slope
  • if it is a sloped tile sloping on the bottom, move the player to the top pixel in the tile
  • if it is a traversable tile, and the player has NOT enabled traversing (holding Down), move the player to the top pixel in the tile
  • if it is a traversable tile, and the player has enabled traversing (holding Down), do nothing
  • For all those, also remember to do stopFalling()

Step 6 - So, where do you want me?
When you draw the player, you can shift the image every which way you want. If you want him walking further inside the tile or if you want him to be walking on top of the tile and not 1px into it, simply shift the image by an offset like this:
g.drawImage(player.getImage(), player.getPosX()-(player.getWidth()/2), player.getPosY()-player.getHeight()+myOffset, null);

myOffset should be negative if you want him moved upwards, and positive for moving him further into the tile.

Performance
I’ve done some testing, and with this approach 400 monsters on-screen takes about 3ms of my deltaTime. That leaves plenty for music, sounds, key-polling, drawing. I only want about 20 at any one time.

Problems with this approach
As the good UpRightPath mentioned, this approach only works if the entities are around 2 tiles high, assuming your map has singular tiles floating around. Already, if I put a floating slope in the height of the midsection of my player, he will act weirdly if he walks into it and starts jumping furiously. These instances can be taken care of when you check your collision-booleans.
A simple fix might be to, instead of having a middle point in each side, you check every second or third point from top to bottom in either side, and chain this to your midRightCOllided and midLeftCollided booleans. This’ll take a bit more computing-time, but as you can see from the performance-point above, it shouldn’t be an issue.

Remember, this is just an EASY and SIMPLE way of handling these things. It’s not going to get you a Sonic-game, but for simple platformers it’ll work nicely, and it is easy to port to your monsters once you get it working for your player. I did my port in a few minutes. Speaking of Sonic, when moving very fast, or having small tiles, you have to take into account that your player or monsters might move more than 1 tile per update, in which case you have to check every tile between where the player was, and where he’s trying to go, log which tile he collides with first, and move him to the right place. This will take a bunch of extra code, and you might want to consider an approach with vectors instead of points.

Well, that’s about it :slight_smile:

I followed my own instructions here, and ended up with what you can see from the links at the top. I really hope this helps someone. I’ve had so much great help for my games on this forum, and it’s about time I give something back.

Good luck to you all in your code adventures 8)

Ultroman, signing off

Player class
Methods called from Game-class

Edited with new thoughts and good points raised by UpRightPath. Thanks!

#2

This method works fairly well until you try to have entities in your map who are of a much larger size. Once you have an entity that is more than two times the size of tiles, the number of sensors used to check for collisions start to become more and more unmanageable (Especially if you want to completely prevent instances of tunneling) or at least more difficult to select the positions of intelligently and handle the resultant checks of.

Another method is to instead find the tile coordinates of your entity’s edges, then check a sub-section of the tile map defined by those edges and some sort of limit, typically in the form of (leftX, bottomY) to (rightX, bottomY - limit). The tile that you select will be the one that is most important for collisions (IE- The highest one, or whatever.) It also works for jumping (leftX, topY) to (rightX, topY + limit), or for the sides (leftX, bottomY) to (leftX - limit, topY) or (rightX, bottomY) to (rightX + limit, topY). It does take a few more checks (Depending on the size of the entity, it’ll check about double the number of tiles needed to ensure a lack of tunneling with the sensor system).

#3

Yep, that’s why I labelled it “easily” :slight_smile: Good points, though. Maybe I should incorporate them, so people know the limits of the method.

Also, there are ways to combat such things as smaller tiles. You could incorporate my method here, and instead of having a middle point in the sides, you simply check every second or third point (as many as you need to be sure) between topRightXY and bottomRightXY for collisions. Then do the same for the topLeft/topRight and bottomLeft/bottomRight points. Since you don’t want the entity to be able to go through anything with his midsection, you can use the same approach as I described. As I mentioned, I do extra checks after getting the collided-booleans for each point, and with this method of checking every point, the sides would just replace the boolean for the midRight/midLeft point boolean.
I think I might give that a go one day :slight_smile:

I might add, that when running my “game” with all those monsters having the same collision-detection method, even though it seems elaborate and there is a lot of code to run through, most of it is encapsulated in if-statements, meaning only a fraction of the code is considered at each frame, so it hardly takes any CPU-time as it is. Something like 3ms for a player and about 400 monsters on-screen on my 2.53GHz i3 dual-crap laptop. And as long as you do like I did, and only update and draw monsters within a specific range of the player, you shouldn’t get any slowdown, unless you spawn…let’s see…about 2000 monsters on the screen at the same time. Since it’s a pretty simple deal to do a tile look-up in a 2D-array for a batch of points, you should be able to get a pretty mileage for your cycles.

#4

The link to your game is dead.

#5

That’s weird…well, I’ve updated both links. Quite a lot has happened today :slight_smile:

Also added the “What you REALLY want is…” section, describing the (IMO) optimal collision-detection method, and the differences between it and my approach. I hope this clears up any confusion.

The solution was mainly thought up to avoid doing CPU-intensive collision-detection on many characters, and also provide an easy solution for people having their first attempts at it. If you have any questions, please do post them or PM me. I’ll be updating the document while I’m proceeding with having my own crack at it.

#6

Really nice read. I tend to make the ‘orientation point’ of my entities the bottom-center point in stead of the dead center. I like to orient things from the feet and the floor as it were, that just seems the more natural approach when you deal with entities that walk.

#7

Thank :slight_smile:

That’s what I did. I feel that makes the most sense. I just mentioned that the Sonic-people use a point in the center of the character.

As you can see, these two points (from the article) assume your player position is, as you say, in the bottom middle:
BotLeft: (playerPosX-(playerWidth/2), playerPosY-slopingOffset)
BotRight: (playerPosX+(playerWidth/2), playerPosY-slopingOffset)

#8

Very detailed, looks great!

#9

As you can see, these two points (from the article) assume your player position is, as you say, in the bottom middle:

Excuse me, I’m going to stand in the corner for a few moments. I complete read over that.

In that case: even more awesome article that I completely agree with :slight_smile:

#10

I think your link to the overview of Sonic engines points to something else. There’s no information on game engines.

#11

Well, you’re sort of right. There’s a lot of information on the physics engine, including movement, collisions and tilemaps on that site, but unfortunately I linked to the wrong part of the site. It’s corrected now, and here’s the correct link as well.

#12

Thanks. That’s pretty interesting. I did not know they used height masks in those games. Do you know how many 2D Sonic games this applies to? I can imagine several ways to implement a platform game and I wonder if even the newer games all work this way.

#13

Well, I don’t know about the newer ones, but it is a solid and well-trialled method (is that a word?), so why not? I believe I read somewhere on that site, that this was the method used for all the oldies.

What I found very interesting was the tiling. That they build big tiles out of smaller tiles, which are in turn built by even smaller tiles.

#14

I don’t know, but I imagine that they would have tweaked the formula somewhere along the line. Such a change could change the feel of the game. Plus there are the bugs/artifacts as presented on those wiki pages. Plus changes in hardware (16 bit vs 3D/2.5D capable) could hinder or alternatively obsolete old methods. It could be that there are no other major shortcomings in this method, and in that case it would be nice to know.

One of those alternative platform physics systems that came to mind was a vector based system (vector geometry as opposed to raster/tile geometry.) Something like that might resolve the uneven terrain issue or provide some other benefit I’m unaware and cannot think of as of now.

#15

Found this.

http://higherorderfun.com/blog/2012/05/20/the-guide-to-implementing-2d-platformers/