Previous Tutorial
Next Tutorial
Posted on: 02-11-2012

Gravity Platformer Tutorial #5 : Collision Detection part 1

Welcome to the first part of the fifth tutorial in this series, in which we prepare our code for collision detection.

Before we prepare anything at all we have to look at what we want to achieve with our collision detection, so lets make a small list:
  • First we want the player to collide with walls
  • We probably want slopes at some point in the game, so we have to take them in consideration
  • Obviously we want gravity in multiple ways, but lets just get a "normal" gravity in first
  • And as we are collecting things, we want other objects in the game as well and they also have to be affected by gravity.
That sort off covers it for now.
  1. The first thing that we want to do is add some properties to our map.
    If you used the map file from the earlier tutorial, the only layer we currently have is named "Tilelaag 1" (which is dutch for "Tile Layer 1" by the way). We are going to name it "CollisionLayer" and will be reading our collision data from this layer.
  2. Next up you want all the transparant tiles to be same transparant tile, namely the first one. It's the main reason why the first tile is a transparant one.
  3. We will also add a property to this tile, so we right click on it in the tileset in the bottom right. Then we go to Tile Properties and add a new one with the name "tileType" and the value "air".

All the other tiles we currently have won't have a tileProperty.
The reasoning behind this is, the most often used tile will be a full block tile, so any tiles without a specific tileProperty will be a "solid" tile by default.

I recommend you download the updated map file here: download

Now that we got the map updated, we want to load the extra information we have in some kind of model that would be easy accessible for our collision detection.

  1. First up, lets create a new package called "game.level.tile". This package will contain our different types of tiles.
  2. In this package we will create the following classes: "Tile", "SolidTile" and "AirTile".
    The blueprints for these classes will look like this:

    1. public class Tile {
    2.  
    3. protected int x;
    4. protected int y;
    5.  
    6. public Tile(int x, int y) {
    7. this.x = x;
    8. this.y = y;
    9. }
    10.  
    11. public int getX(){
    12. return x;
    13. }
    14.  
    15. public int getY(){
    16. return y;
    17. }
    18.  
    19. }

    1. public class AirTile extends Tile {
    2.  
    3. public AirTile(int x, int y) {
    4. super(x, y);
    5. }
    6.  
    7. }

    1. public class SolidTile extends Tile {
    2.  
    3. public SolidTile(int x, int y) {
    4. super(x, y);
    5. }
    6.  
    7. }

    Both AirTile and SolidTile are not so different yet, but it is important to not get sidetracked and focus on our goal: loading up the new information into our model.

  3. And to do to just that, we will use the good old 2-dimensional array:

    1. private Tile[][] tiles;

    We will add this to our Level class.

  4. We will also add an additional method to level called "loadTileMap()" which will perform the loading and creation of tiles.

    1. private void loadTileMap(){
    2. //create an array to hold all the tiles in the map
    3. tiles = new Tile[map.getWidth()][map.getHeight()];
    4.  
    5. int layerIndex = map.getLayerIndex("CollisionLayer");
    6.  
    7. if(layerIndex == -1){
    8. //TODO we can clean this up later with an exception if we want, but because we make the maps ourselfs this will suffice for now
    9. System.err.println("Map does not have the layer \"CollisionLayer\"");
    10. System.exit(0);
    11. }
    12.  
    13. //loop through the whole map
    14. for(int x = 0; x < map.getWidth(); x++){
    15. for(int y = 0; y < map.getHeight(); y++){
    16.  
    17. //get the tile
    18. int tileID = map.getTileId(x, y, layerIndex);
    19.  
    20. Tile tile = null;
    21.  
    22. //and check what kind of tile it is (
    23. switch(map.getTileProperty(tileID, "tileType", "solid")){
    24. case "air":
    25. tile = new AirTile(x,y);
    26. break;
    27. default:
    28. tile = new SolidTile(x,y);
    29. break;
    30. }
    31. tiles[x][y] = tile;
    32. }
    33. }
    34. }

    In summary, this method does the following:

    • Loop through every tile in the layer "CollisionLayer"
    • Check what kind of tile it is, defaulting to a "solid" tile
    • And then create the right Tile object and put it in the correct spot in the array

  5. Last thing we have to do here is make sure we call the method when we create level object and our Level class will end up looking like this:

    1. public class Level {
    2.  
    3. private TiledMap map;
    4.  
    5. //a list of all characters present somewhere on this map
    6. private ArrayList<Character> characters;
    7.  
    8. private Tile[][] tiles;
    9.  
    10. public Level(String level) throws SlickException{
    11. map = new TiledMap("data/levels/" + level + ".tmx","data/img");
    12. characters = new ArrayList<Character>();
    13.  
    14. loadTileMap();
    15. }
    16.  
    17. private void loadTileMap(){
    18. //create an array to hold all the tiles in the map
    19. tiles = new Tile[map.getWidth()][map.getHeight()];
    20.  
    21. int layerIndex = map.getLayerIndex("CollisionLayer");
    22.  
    23. if(layerIndex == -1){
    24. //TODO we can clean this up later with an exception if we want, but because we make the maps ourselfs this will suffice for now
    25. System.err.println("Map does not have the layer \"CollisionLayer\"");
    26. System.exit(0);
    27. }
    28.  
    29. //loop through the whole map
    30. for(int x = 0; x < map.getWidth(); x++){
    31. for(int y = 0; y < map.getHeight(); y++){
    32.  
    33. //get the tile
    34. int tileID = map.getTileId(x, y, layerIndex);
    35.  
    36. Tile tile = null;
    37.  
    38. //and check what kind of tile it is (
    39. switch(map.getTileProperty(tileID, "tileType", "solid")){
    40. case "air":
    41. tile = new AirTile(x,y);
    42. break;
    43. default:
    44. tile = new SolidTile(x,y);
    45. break;
    46. }
    47. tiles[x][y] = tile;
    48. }
    49. }
    50. }
    51.  
    52. public void addCharacter(Character c){
    53. characters.add(c);
    54. }
    55.  
    56. public ArrayList<Character> getCharacters(){
    57. return characters;
    58. }
    59.  
    60. public Tile[][] getTiles(){
    61. return tiles;
    62. }
    63.  
    64. public void render(){
    65. //render the map first
    66. map.render(0, 0, 0, 0, 32, 18);
    67.  
    68. //and then render the characters on top of the map
    69. for(Character c : characters){
    70. c.render();
    71. }
    72. }
    73.  
    74. }

    Note that I also added a getter for both our characters and our tiles, these will be useful later on.

  6. Remember that our SolidTile and AirTile looked similar? Now is the time to fix that up by adding some bounding shapes to our different tiles.

  7. So first up we will add a protected attribute to our Tile class called boundingShape that is a BoundingShape:

    1. protected BoundingShape boundingShape;

    We will also set the boundingShape to null in the constructor and add a getter method to provide access towards it.

  8. You will see some errors because we don't have any kind of BoundingShape class yet, lets just ignore them for now and think about what kind of shapes we are going to need.

    For our air tiles we don't really need any shape do we? So in the AirTile class we won't change anything and just leave the shape at null.

    For the solid tiles we will need bounding rectangles however. So lets reflect that in our constructor:

    1. boundingShape = new AABoundingRect(x*32,y*32,32,32);

    The arguments are the position in pixels (x,y) and a width and height both in pixels as well.

Ok, lets see what we have done so far. We have a map that has information on what tiles are collidable and now we have also loaded this into a model but not yet defined our BoundingShape and AABoundingRect classes. So lets do so!

  1. Again, we create a new package (I know, I know, lots of packages) called "game.physics" in which we will have our classes that do physics stuff.

  2. The first class we create here will be an abstract class (meaning we can't create an object of this class) called "BoundingShape" that will look like the following:

    1. public abstract class BoundingShape {
    2.  
    3. public boolean checkCollision(BoundingShape bv){
    4. if(bv instanceof AABoundingRect)
    5. return checkCollision((AABoundingRect) bv);
    6. return false;
    7. }
    8.  
    9. public abstract boolean checkCollision(AABoundingRect box);
    10.  
    11. public abstract void updatePosition(float newX, float newY);
    12.  
    13. public abstract void movePosition(float x, float y);
    14.  
    15. public abstract ArrayList<Tile> getTilesOccupying(Tile[][] tiles);
    16.  
    17. public abstract ArrayList<Tile> getGroundTiles(Tile[][] tiles);
    18.  
    19. }

    You might think, what are all these methods for? Well let me explain them:

    • The checkCollision method is used to see what kind of shape we are dealing with and call the right method to deal with the collision, there are different ways of dealing with this, but I found this the most simple one. We don't want to overcomplicate things, after all we only have one type of shape for now.

    • The next one, is the method that will be used to check the collision between any shape that we have implemented and an AABoundingRect, there will be one such method for each shape we add.

    • The next method does exactly what is says, it updates the position of the shape to the new x and y (for a rectangle this is the top left corner and for a circle this might be the center).

    • movePosition in turn only moves it, so if we say movePosition(5,0) the x of the shape will be moved by 5, this will be really useful for checking close collisions

    • The last two methods are illustrated in the picture below.

  3. And now, the implementation of the AABoundingRect.

    You might have been wondering, what is this "AA" stand for?
    It stands for Axis Aligned, which comes down to, this rectangle does not rotate other than in multiples of 90. This makes it a lot easier for our collision detection and we don't need anything else right now.

    1. So lets start with the easy stuff first, the attributes, constructor and the updatePosition and movePosition:

      1. public class AABoundingRect extends BoundingShape {
      2.  
      3. public float x;
      4. public float y;
      5. public float width;
      6. public float height;
      7.  
      8. public AABoundingRect(float x, float y, float width, float height) {
      9. this.x = x;
      10. this.y = y;
      11. this.width = width;
      12. this.height = height;
      13. }
      14.  
      15. public void updatePosition(float newX, float newY) {
      16. this.x = newX;
      17. this.y = newY;
      18. }
      19.  
      20. public void movePosition(float x, float y) {
      21. this.x += x;
      22. this.y += y;
      23. }
      24. }

      I think this speaks for itself.

    2. The next part however does not, we will now implement the rectangle to rectangle collision detection:

      1. public boolean checkCollision(AABoundingRect rect) {
      2. return !(rect.x > this.x+width || rect.x+rect.width < this.x || rect.y > this.y+height || rect.y+rect.height < this.y);
      3. }

      Yes, that is all there is to it.
      But as you might be wondering how it actually works:

      Consider the following image:

      Lets say our we call our yellowish rectangle "player" and the numbered orange ones "rect1" through "rect4".

      Lets check our collision with our player and rect1. We can see that there is no collision, but how could we describe it?

      Well, we could say that the bottom edge of rect1 is higher than the top edge of the player. If this particular phenomenon occurs, there is simply no collision possible. And we can define it for the other rectangles as well.

      Lets take a look at rect2, the same thing happens here, but this time with the right edge of rect2 and the left edge of the player.

      If we also take a look at rectangles 3 and 4 we can see it checks out for every side, so if any of these 4 happens there is no collision possible. But what if all fail? Well that only happens when we have an actual collision!

      That brings us to the following:

      If any of the four conditions we set before are true, then we return false (the ! at the front of the whole statement flips it around). But if all the statements are false, this will flip towards true because we have a collision.

      If this is hard to follow, I recommend you look around on the internet for other ways because this is just one of the many ways 2D rectangle collision/intersection can be calculated, but it is one of the more efficient ones.

    3. Only two methods left, we will get there eventually!

      1. public ArrayList<Tile> getTilesOccupying(Tile[][] tiles) {
      2. ArrayList<Tile> occupiedTiles = new ArrayList<Tile>();
      3.  
      4. //we go from the left of the rect towards to right of the rect, making sure we round upwards to a multiple of 32 or we might miss a few tiles
      5. for(int i = (int) x; i <= x+width+(32-width%32); i+=32){
      6. for(int j = (int) y; j <= y+height+(32-height%32); j+=32){
      7. occupiedTiles.add(tiles[i/32][j/32]);
      8. }
      9. }
      10. return occupiedTiles;
      11. }

      This is the first method where we make use of our model that we created for our tiles.
      There is a few things key here, the first is that we know that our tiles are 32 pixels wide and high, so we can find the right index in the array by dividing our x and y by 32. Integers will automatically round down so we get the right tile.

      Another one here is that we have to take into account that our character might not be exactly 32 by 32 (we will see later that our character is a bit smaller).

      If for example our character would be 27 pixels wide and is positioned at 15 x. This will mean that half our character will be standing in one tile and the other half will be standing in another tile. The problem that will arise is that it will first get the left tile, then add 32 and will see that 15+32 is bigger than 15+27 and the for loop will not trigger for the right tile, rounding up that 27 (or the width of the rectangle to be exact) to a multiple of 32 will remedy that problem.

    4. Alright, one to go!

      1. public ArrayList<Tile> getGroundTiles(Tile[][] tiles) {
      2. ArrayList<Tile> tilesUnderneath = new ArrayList<Tile>();
      3. int j = (int) (y+height+1);
      4.  
      5. for(int i = (int) x; i <= x+width+(32-width%32); i+=32){
      6. tilesUnderneath.add(tiles[i/32][j/32]);
      7. }
      8.  
      9. return tilesUnderneath;
      10. }

      This method is almost the same, the only different is that we only get one horizontal layer of tiles, namely the tiles that are directly below our character.

    Closing Notes

    Because this all might be quite overwhelming, I've decided to split this tutorial in two parts, in the next part we will put what we made in this tutorial to use and also add jumping and basic gravity to our game.

    I really hope that everything is clear, it was quite a challenge to keep things simple, so if anything is unclear, please leave a comment and I will attempt to clarify.
Categories: Game Development, Java, Tutorial

Comments

Nekotripp said: (05-11-2012)
Thanks again for making these tutorials. This one was a little tough at first, but I think I got it now.
Frums said: (05-11-2012)
I'm glad you liked it, I'll promise that the next one will be a bit easier :)
mikey said: (06-12-2012)
Great tutorial! Collision detection is still a bit confusing to me however. Could you clarify this statement?

"If we also take a look at rectangles 3 and 4 we can see it checks out for every side, so if any of these 4 happens there is no collision possible. But what if all fail? Well that only happens when we have an actual collision!"

"it (checks out for every side" refers to the player correct?

"if any of these 4 happens there is no collision" I figured it'd be the opposite. If 1 of these 4 happens (one of the rectangles' edges touches player), then a collision happens.

"But what if all fail, that only happens when we have an actual collision" Why must all fail for a collision? I figured if you at one failed then you're hitting something! :P

Dumb it down a little for me? :)

mikey said: (06-12-2012)
if at least one failed*
Frums said: (06-12-2012)
On this first part you are correct, it refers to the player.

On the second part, take out 2 pieces of paper.

Now lay them down side by side, mark the one of the left with an X and the one on the right with an O.

If we check the 4 conditions if we have X on the left side:
The right side of the X is left of left side of the O.

And however you move that piece around, when you have the right side of the X left of the left side of the O, there is no collision possible.

The other 3 conditions are the same, but for the top, bottom and right side of the X.

But now try to move around your X so that it collides with the O and you will see in whatever way you put it, all 4 conditions will fail :)



What is the name of the website? (to counter the spam)