# Let's Check My Collision Detection Algorithm

• 03-22-2011, 01:53 AM
Revenna
Let's Check My Collision Detection Algorithm
Hello everyone. I need a bit of help with a collision detection algorithm I'm working on. It's kind of a complicated mess at the moment. What we have here is a tile-based side scrolling thing. I want my sprite to not pass through tiles, and I have a method that finds a tile that's been collided with and can return it, but I've not had much luck keeping weird things from happening afterward, weird things like sinking through the floor, disappearing into outer space, and speeding through solid blocks...

The way I have it written in the code (attached) the sprite can run and jump in free space, it checks the tiles around the sprite to see if they are empty, if not it returns the tile and determines if the sprite was moving up, down, left or right based on the last and updated positions. The current version has println statements that printout when a collision happened and what direction it happened in. I've tried aligning the sprite with the edge of the tile like this:
Code:

```                private void handleCollision(Tile tile, Point newLoc, Point oldLoc, Point tileLoc) {                 //Moving right                 if(newLoc.x > oldLoc.x){                         System.out.println("RIGHT: " + newLoc.x);                         xCoord = (tileLoc.x - chasie.getWidth()) - (SCREENWIDTH/2);                         xVelocity = 0;                         chasie.setState(State.STANDING_RIGHT);                 }                 //Moving left                 else if(newLoc.x < oldLoc.x){                         System.out.println("LEFT: " + newLoc.y);                         xCoord = (tileLoc.x - tileSize) - (SCREENWIDTH/2);                         xVelocity = 0;                         chasie.setState(State.STANDING_RIGHT);                 }                 //Moving down                 else if(newLoc.y > oldLoc.y){                         System.out.println("DOWN: " + newLoc.y);                         chasie.setY(tileLoc.y - chasie.getHeight());                         chasie.setYVelocity(0);                         chasie.setState(State.STANDING_RIGHT);                 }                 //Moving up                 else if(newLoc.y < oldLoc.y){                         System.out.println("UP: " + newLoc.y);                         chasie.setY(tileLoc.y + tileSize);                         chasie.setYVelocity(0);                         chasie.setState(State.STANDING_RIGHT);                 }         }```
Unfortunately this only works in the UP direction, and even then only when you're not moving left or right. Moving left or right ends up with your sprite getting sucked through the tiles at high speed and landing on top of a tile causes an unpleasant bouncing.

Here's what I was thinking I should do:
• Create bounding rectangles for each side of the sprite
• Create bounding rectangles for each side of the tile
• Move based on which rectangles intersect

Would that work or am I wasting my time?

Code Notes:
The sprite doesn't move in the X axis at all
I'll have to adjust my jump method to work with collision detection
Tile objects are images with some extra information
I know its messy but I haven't had time to tweak it yet
• 03-22-2011, 05:25 AM
Are tiles and sprites both referenced to the upper left corner? If so, your math is wrong.

assuming there is a collision...

if moving to the right,
x = tileLoc.x - sprite.width

if moving left,
x = tileLoc.x+tile.width

if moving up,
y = tileLoc.y + tile.height

if moving down
y = tileLoc.y - sprite.height

As a first cut, I suggest treating the sprite as a rectangle and determining collisions by determining rectangle intersections. If you get that working, then you can worry about using a point-by-point collision test for the outline of the sprite with the tiles. To do that, you will need to define a Shape that traces the outline of the sprite and then use the built-in 'contains' methods in Swing/AWT to do collision testing for you.
• 03-23-2011, 04:20 AM
Revenna
That's pretty much what I already have, with the exception of moving the coordinates 320px to the left to compensate for the position of the sprite (center of a 640px screen). xCoord actually represents how far back in X,Y coordinate space to begin drawing the first tile of the map, it really should be a negative number, but I used a positive number and subtracted it from 0 in the render() method for some reason.

I think one of the problems I'm having is that it doesn't seem to know which end of the thing it's colliding with...

Say you've collided with the tile while moving right and you've been aligned to the left edge of it, if you try to walk away from to tile by going left, it registers a collision going left and you get sucked through the tile and aligned with the right edge.

It's kind of hard to explain what's going on, so here's a runnable JAR using the code from above: http://onyxphoto.net/Test.zip. If any of you guys get a chance to run it, try this: run into the first block, then try to walk left, after you get sucked through the block, try to walk right again. See what I mean? You also can't jump into that pyramid looking thing hanging down from the ceiling at the end without getting sucked up into it, and trying to land on a block results in some rather weird bouncing, and the only reason you're not bouncing off the floor is because its Y coordinates are built into the jump() method.

Controls:
Left: Left Arrow
Right: Right Arrow
Jump: Z
Pause: P
Quit: Esc

Thanks again for your help, guys.
• 03-23-2011, 03:44 PM
To determine which wall you hit, do the following:

- Call {sx1,sy1} the point where the sprite was immediately prior to a collision detection, and {sx2, sy2} the point where the sprite would be if not for collision

- You need to know the points of the four corners of the tile. Starting at the top left corner and gogin clockwise, let's label the points {tx1,ty1} through {tx4,ty4}

Now, find the intersection of the vector [{sx1,sy1},{sx2,sy2}] with each of the vectors of the walls. To do that, use the formula for a line and solve the pair of linear equations:

pseudocode...

Code:

```m1 = (sy2 - sy1)/(sx2 - sx1); m2 = (ty2 - ty1)/(tx2 - tx1);  .....do this for each adjacent pair of tile corners b1 = sy1/(m1*sx1); b2 = ty1/(m2*tx1); now set y equal for the two equations and solve for x.... y = m1*x + b1; y = m2*x + b2; m1*x + b1 = m2*x + b2; x*( m1 - m2 ) = b2 - b1; x = (b2 - b1)/(m1-m2); ...once you have x pluf it back into one fo the line equations to get y. You will have to deal with the cases where the denominators are zero.  The equation of a line where x2 = x1 is simply 'x = x1'.  In that case you already know x at teh point of intersection, so just solve for y in the other equation.  In the case where m1 = m2, treat it as if there is no intersection and skip checks for that wall.```
Ok, now you know the points of intersection. The line of motion for your sprite interesects exactly two of the tile walls. To figure out which two, check the distance between each intersection and one of the two corners of the tile that that particular intersection is related to. If that distance is greater than the distance between the tile corners, then the wall can be ignored.

[recall d = sqrt( (x2-x1)^2 + (y2-y1)^2))]

For the other two points, check the distance between {sx1,sy1} and the interesection point. Whichever is smaller is the wall the sprite hit.