   Posted on: 03-11-2012

## Gravity Platformer Tutorial #5 : Collision Detection part 2

In the last part we created a model that holds our tiles and we've also defined the axis aligned bounding shape.

Lets start using it!

1. We start off by introducing another class. This class is called "LevelObject" and will be located in the "game.level" package.

The LevelObject class is going to be the superclass of all the dynamic objects in our game, including characters, enemies and all other objects that we will introduce.

We still start off by defining its attributes:

`    protected float x;    protected float y;    protected BoundingShape boundingShape;     protected float    x_velocity = 0;    protected float    y_velocity = 0;    protected float    maximumFallSpeed = 1;     protected boolean  onGround = true;`

It is more common to call the x and y velocities the horizontal and vertical velocity, but as we will have 4 different gravities it would only be confusing.

The full class will look like this:

`public abstract class LevelObject {     protected float x;    protected float y;    protected BoundingShape boundingShape;     protected float    x_velocity = 0;    protected float    y_velocity = 0;    protected float    maximumFallSpeed = 1;     protected boolean  onGround = true;     public LevelObject(float x, float y){        this.x = x;        this.y = y;         //default bounding shape is a 32 by 32 box        boundingShape = new AABoundingRect(x,y,32,32);    }     public void applyGravity(float gravity){      //if we aren't already moving at maximum speed        if(y_velocity < maximumFallSpeed){            //accelerate            y_velocity += gravity;            if(y_velocity > maximumFallSpeed){                //and if we exceed maximum speed, set it to maximum speed                y_velocity = maximumFallSpeed;            }        }    }     public float getYVelocity() {        return y_velocity;    }     public void setYVelocity(float f){        y_velocity = f;    }     public float getXVelocity(){        return x_velocity;    }     public void setXVelocity(float f){        x_velocity = f;    }     public float getX(){        return x;    }     public float getY(){        return y;    }     public void setX(float f){        x = f;        updateBoundingShape();    }     public void setY(float f){        y = f;        updateBoundingShape();    }     public void updateBoundingShape(){        boundingShape.updatePosition(x,y);    }     public boolean isOnGround(){        return onGround;    }     public void setOnGround(boolean b){        onGround = b;    }     public BoundingShape getBoundingShape(){        return boundingShape;    } }`

There are 2 things I'd like to clarify, the first begin the updateBoundingShape().

The updateBoundingShape() is a method that we could override if our bounding box is not situated at the same position as the object itself. This will be useful for our player as you will see later.

The second thing is the applyGravity, this is a method that tries to apply a gravitational force to our object, it makes sure we don't fall faster than our maximum falling speed.

2. Because we will be working with velocities now, our character movement needs an overhaul as well, we can't just update the x anymore.

`public abstract class Character extends LevelObject {     protected HashMap<Facing,Image>     sprites;     protected HashMap<Facing,Animation> movingAnimations;    protected Facing                    facing;    protected boolean                   moving = false;    protected float                     accelerationSpeed = 1;    protected float                     decelerationSpeed = 1;    protected float                     maximumSpeed = 1;     public Character(float x, float y) throws SlickException{        super(x,y);        //in case we forget to set the image, we don't want the game to crash, but it still has to be obvious that something was forgotten        setSprite(new Image("data/img/placeholder_sprite.png"));         //default direction will be right        facing = Facing.RIGHT;    }     protected void setMovingAnimation(Image[] images, int frameDuration){        movingAnimations = new HashMap<Facing,Animation>();         //we can just put the right facing in with the default images        movingAnimations.put(Facing.RIGHT, new Animation(images,frameDuration));         Animation facingLeftAnimation = new Animation();        for(Image i : images){            facingLeftAnimation.addFrame(i.getFlippedCopy(true, false), frameDuration);        }        movingAnimations.put(Facing.LEFT, facingLeftAnimation);     }     protected void setSprite(Image i){        sprites = new HashMap<Facing,Image>();        sprites.put(Facing.RIGHT, i);        sprites.put(Facing.LEFT , i.getFlippedCopy(true, false));    }     public boolean isMoving(){        return moving;    }     public void setMoving(boolean b){        moving = b;    }     //move towards x_velocity = 0    public void decelerate(int delta) {        if(x_velocity > 0){            x_velocity -= decelerationSpeed * delta;            if(x_velocity < 0)                x_velocity = 0;        }else if(x_velocity < 0){            x_velocity += decelerationSpeed * delta;            if(x_velocity > 0)                x_velocity = 0;        }    }     public void jump(){        if(onGround)            y_velocity = -0.4f;    }     public void moveLeft(int delta){        //if we aren't already moving at maximum speed        if(x_velocity > -maximumSpeed){            //accelerate            x_velocity -= accelerationSpeed*delta;            if(x_velocity < -maximumSpeed){                //and if we exceed maximum speed, set it to maximum speed                x_velocity = -maximumSpeed;            }        }        moving = true;        facing = Facing.LEFT;    }     public void moveRight(int delta){        if(x_velocity < maximumSpeed){            x_velocity += accelerationSpeed*delta;            if(x_velocity > maximumSpeed){                x_velocity = maximumSpeed;            }        }        moving = true;        facing = Facing.RIGHT;    }     public void render(){         //draw a moving animation if we have one and we moved within the last 150 miliseconds        if(movingAnimations != null && moving){            movingAnimations.get(facing).draw(x-2,y-2);                        }else{                        sprites.get(facing).draw(x-2, y-2);                  }    } }`

As you can see, there are quite a lot of changes here. Lets walk through them.

• One of the most important changes is that the moveLeft and moveRight now use the x_velocity instead of directly updating our characters position. We will have a special class later that will handle the movement of all objects in the level and that will use collision detection to check if we can move.
• Another change in the moveLeft and moveRight methods is that we set a moving attribute. I thought about this a lot and decided to remove the lastTimeMoved because it would be to inaccurate for the deceleration of our character.
• Which brings us to the acceleration and deceleration speeds, this is something that makes our characters able to move a bit smoother. After all, are you instantly at full speed when you start running?
• The decelerate method handles the deceleration of the character, an important thing here is to check which way we are going (we can have a positive x velocity, which moves us right but also a negative one that moves us left).
• And last but not least, the jump method that sets a y_velocity if we are on the ground

3. Now the last changes are to the Player class:

`public class Player extends Character {     public Player(float x, float y) throws SlickException{        super(x,y);        setSprite(new Image("data/img/characters/player/player.png"));         setMovingAnimation(new Image[]{new Image("data/img/characters/player/player_1.png"),new Image("data/img/characters/player/player_2.png"),                                       new Image("data/img/characters/player/player_3.png"),new Image("data/img/characters/player/player_4.png")}                                       ,125);        boundingShape = new AABoundingRect(x+3, y, 26, 32);         accelerationSpeed = 0.001f;        maximumSpeed = 0.15f;        maximumFallSpeed = 0.3f;        decelerationSpeed = 0.001f;    }     public void updateBoundingShape(){        boundingShape.updatePosition(x+3,y);    } }`

Here is where the updateBoundingShape method comes in handy. Our character is not exactly 32 pixels wide, so we want our bounding rectangle to be a bit thinner. This also means that our bounding shape will not be at the same location as our player, it has to be moved 3 pixels to the right to be in the correct spot.

Something that you might think is that the acceleration speed and the deceleration speed are really low. They are not that low if you keep the delta in mind, which will multiply all those values by at least 16 (at 60 frames per second).

4. The last thing we do is update our MouseAndKeyBoardPlayerController class to tell our player that he isn't moving whenever we don't have a movement key down and add a key for jumping:

`    private void handleKeyboardInput(Input i, int delta){        //we can both use the WASD or arrow keys to move around, obviously we can't move both left and right simultaneously        if(i.isKeyDown(Input.KEY_A) || i.isKeyDown(Input.KEY_LEFT)){            player.moveLeft(delta);        }else if(i.isKeyDown(Input.KEY_D) || i.isKeyDown(Input.KEY_RIGHT)){            player.moveRight(delta);        }else{            //we dont move if we don't press left or right, this will have the effect that our player decelerates            player.setMoving(false);        }         if(i.isKeyDown(Input.KEY_SPACE)){            player.jump();        }    }`

If you run the game now, you will notice that we "broke" the movement. But technically it isn't broken, our characters get the right movement. Its just that we don't move them yet according to their speeds.

1. So lets fix this problem by introducing a Physics class to our game, this class will go into "game.physics" (who would've guessed?)

`public class Physics {     private final float gravity = 0.0015f;     public void handlePhysics(Level level, int delta){     } }`

The handlePhysics will handle all the physics within a level, and of course we don't have to forget about the delta!

I've also already defined a gravity here, we will make use of this later.

2. Before we implement the physics, lets actually add it to our LevelState. This will mean we add an attribute, create a Physics object in the constructor.

Last thing we have to do here is call the "handlePhysics" method in the update:

`    public void update(GameContainer container, StateBasedGame sbg, int delta) throws SlickException {        //every update we have to handle the input from the player        playerController.handleInput(container.getInput(), delta);        physics.handlePhysics(level, delta);    }`
3. Now we are going to create a few helpful methods in our Physics class, the first being "checkCollision(LevelObject obj, Tile[][] mapTiles)". This method will get all the tiles occupied by the object, and check collisions with them.

`    private boolean checkCollision(LevelObject obj, Tile[][] mapTiles){        //get only the tiles that matter        ArrayList<Tile> tiles = obj.getBoundingShape().getTilesOccupying(mapTiles);        for(Tile t : tiles){            //if this tile has a bounding shape            if(t.getBoundingShape() != null){                if(t.getBoundingShape().checkCollision(obj.getBoundingShape())){                    return true;                }            }        }        return false;    }`

And here we see our hard work from the first part paying back.

4. The next method is going to be "isOnGround(LevelObject obj, Tile[][] mapTiles)". This method will be a bit more complex than the previous one.

`    private boolean isOnGroud(LevelObject obj, Tile[][] mapTiles){        //we get the tiles that are directly "underneath" the characters, also known as the ground tiles        ArrayList<Tile> tiles = obj.getBoundingShape().getGroundTiles(mapTiles);         //we lower the the bounding object a bit so we can check if we are actually a bit above the ground        obj.getBoundingShape().movePosition(0, 1);         for(Tile t : tiles){            //not every tile has a bounding shape (air tiles for example)            if(t.getBoundingShape() != null){                //if the ground and the lowered object collide, then we are on the ground                if(t.getBoundingShape().checkCollision(obj.getBoundingShape())){                    //don't forget to move the object back up even if we are on the ground!                    obj.getBoundingShape().movePosition(0, -1);                    return true;                }            }        }         //and obviously we have to move the object back up if we don't hit the ground        obj.getBoundingShape().movePosition(0, -1);         return false;    }`

What we do in this method, is make use of our getGroundTiles method from the first part of the tutorial and then check if we are directly above them.

The way we check that is, is to move the bounding shape of the object down 1 pixel. Then we check if we have a collision. This is a simple way of checking if there is something below our object.

5. Now comes the tough part, the actual movement of our objects in the level.

The first thing we do is define two addiotional methods, "handleCharacters(Level level, int delta) and "handleGameObject(LevelObject obj,Level level, int delta).

Lets take a look at the first method:

`    private void handleCharacters(Level level, int delta){        for(Character c : level.getCharacters()){             //and now decelerate the character if he is not moving anymore            if(!c.isMoving()){                c.decelerate(delta);            }             handleGameObject(c,level,delta);        }    }`

The main reason why we have this method is because our characters have the ability to accelerate, and therefore have to decelerate if they are no longer attempting to accelerate.

We also have to update our handlePhysics method to make use of our newly created method

`     public void handlePhysics(Level level, int delta){        handleCharacters(level,delta);    }`
6. As for now, we have to implement our handleGameObject method. But before we do lets just write down what it should be doing.

1. Determine if our character is on the ground
2. If we are not on the ground or if we are about to make a jump (meaning we have a y_velocity) we have to apply gravity
3. Now we have to calculate how much we are moving, make using of the delta.
4. And when we have calculated this, we will move our character alternating x and y and stopping when we hit something

This last step is easier said than done, so lets see how it works.

Lets say our character would want to move 50 pixels to the right in one frame (this could happen when we have a lower framerate). If we would just move our character and then check for collisions, he could end up walking through 32 pixel wide walls. So what we can do to remedy this is that we move him for 50 pixels, but only 1 pixel at a time. That way we will encounter any obstacles along the way and can stop right in front of them.

Another thing we have to keep in mind is that we also have vertical movement, so we want to calculate the slope of the movement (y_movement divided by x_movement equals the slope). We also have to make sure that both the x_step and the y_step are a maximum of 1 pixel.

This first illustration is the movement of an object by using the slope of 1 pixel right and 2 pixels up, which comes down to 0.5 pixels right and 1 pixel up (we only wanted 1 pixel to be our maximum step). This second illustration is how we can calculate the slope (basic linear algebra) 7. So now that we know what we have to implement, here we go:

`    private void handleGameObject(LevelObject obj, Level level, int delta){         //first update the onGround of the object        obj.setOnGround(isOnGroud(obj,level.getTiles()));         //now apply gravitational force if we are not on the ground or when we are about to jump        if(!obj.isOnGround() || obj.getYVelocity() < 0)            obj.applyGravity(gravity*delta);        else            obj.setYVelocity(0);         //calculate how much we actually have to move        float x_movement = obj.getXVelocity()*delta;        float y_movement   = obj.getYVelocity()*delta;         //we have to calculate the step we have to take        float step_y = 0;        float step_x = 0;         if(x_movement != 0){            step_y = Math.abs(y_movement)/Math.abs(x_movement);            if(y_movement < 0)                step_y = -step_y;             if(x_movement > 0)                step_x = 1;            else                step_x = -1;             if((step_y > 1 || step_y < -1) && step_y != 0){                step_x = Math.abs(step_x)/Math.abs(step_y);                if(x_movement < 0)                    step_x = -step_x;                if(y_movement < 0)                    step_y = -1;                else                    step_y = 1;            }        }else if(y_movement != 0){            //if we only have vertical movement, we can just use a step of 1            if(y_movement > 0)                step_y = 1;            else                step_y = -1;        }         //and then do little steps until we are done moving        while(x_movement != 0 || y_movement != 0){             //we first move in the x direction            if(x_movement != 0){                //when we do a step, we have to update the amount we have to move after this                if((x_movement > 0 && x_movement < step_x) || (x_movement > step_x  && x_movement < 0)){                    step_x = x_movement;                    x_movement = 0;                }else                    x_movement -= step_x;                 //then we move the object one step                obj.setX(obj.getX()+step_x);                 //if we collide with any of the bounding shapes of the tiles we have to revert to our original position                if(checkCollision(obj,level.getTiles())){                    //undo our step, and set the velocity and amount we still have to move to 0, because we can't move in that direction                    obj.setX(obj.getX()-step_x);                    obj.setXVelocity(0);                    x_movement = 0;                }             }            //same thing for the vertical, or y movement            if(y_movement != 0){                if((y_movement > 0 && y_movement < step_y) || (y_movement > step_y  && y_movement < 0)){                    step_y = y_movement;                    y_movement = 0;                }else                    y_movement -= step_y;                 obj.setY(obj.getY()+step_y);                 if(checkCollision(obj,level.getTiles())){                    obj.setY(obj.getY()-step_y);                    obj.setYVelocity(0);                    y_movement = 0;                    break;                }            }        }    }`

The calculation of the x_step and y_step were a bit more complicated then I illustrated, this is because we can have both positive and negative movement and both have to be capped to a maximum of 1 (either positive or negative).

And there we go, we now have collision detection, basic gravity and jumping in our game!

### Closing Notes

Again I hope I was clear in my explanation, so if you have any questions, don't hesitate and ask away.

One thing you could try to understand this a bit better is to grab a piece of paper with a grid on it, then draw some kind of object on the grid (being your obstacle). Then grab a small piece of paper and try to move it around the way we do in the code, it might clear things up.
Categories: Game Development, Java, Tutorial

jL said: (06-11-2012)
Thanks for the tuts! Took a minute, but I got this one. Keep 'em comin'!
QuantumScience said: (09-11-2012)
I've read a bunch of stuff about collision detection but this one made me understood everything. Thank you!
mikey said: (02-12-2012)
my character is stuck running in place as noted in step 4 after following this as precisely as i could. compiles and runs fine however. what are some common errors?
Frums said: (02-12-2012)
This is because we broke that on purpose, we want to have the controls manipulate the velocity of the player, and then have our physics object do the actual moving of the objects in our world (including our player).

If you implement the physics object as well you will see that it works again :)
Kyle Herrid said: (14-12-2013)
I have been avidly following these tutorials, but both a friend and I have encountered the following problem in this chapter:

After (what should be) completing this and the previous chapters, I get a strange error that appears to stem from calling physics.handlePhysics(level, delta) in the update function of game.state.LevelState.

the console spits out the following message:
"INFO:Slick Build #237
INFO:LWJGL Version: 2.9.0
INFO:OriginalDisplayMode: 1600 x 900 x 32 @60Hz
INFO:TargetDisplayMode: 1280 x 720 x 0 @0Hz
INFO:Starting display 1280x720
INFO:Use Java PNG Loader = true
INFO:Controllers not available
ERROR:null
java.lang.NullPointerException
at state.LevelState.update(LevelState.java:47)
at org.newdawn.slick.state.StateBasedGame.update(StateBasedGame.java:266)
at org.newdawn.slick.GameContainer.updateAndRender(GameContainer.java:663)
at org.newdawn.slick.AppGameContainer.gameLoop(AppGameContainer.java:411)
at org.newdawn.slick.AppGameContainer.start(AppGameContainer.java:321)
at main.Game.main(Game.java:28)
Sat Dec 14 20:21:32 PST 2013 ERROR:Game.update() failure - check the game code.
org.newdawn.slick.SlickException: Game.update() failure - check the game code.
at org.newdawn.slick.GameContainer.updateAndRender(GameContainer.java:669)
at org.newdawn.slick.AppGameContainer.gameLoop(AppGameContainer.java:411)
at org.newdawn.slick.AppGameContainer.start(AppGameContainer.java:321)
at main.Game.main(Game.java:28)"

Even after completely replacing every file in the physics package with the files in the following tutorial, it does not get any better.

Any help?
Brian said: (25-02-2014)
I'm running into the same error as Kyle.

P.S. Im lovin' the tutorials.
Brian said: (26-02-2014)
Got it! I forgot to call the constructor for Physics when I added the attribute to the LevelState class.