Collisions

2D Collision Detection and Handling with Java

A wait(&see) approach — December 26, 2008

1

The Problem

Collision detection and handling is a feature every single video game must implement to one degree or another. It allows for basic interaction between the player and his/her environment. It can also be a tricky thing to get right, as you can see in the picture below.

Figure 1: Another innocent victim of bad collision detection. [3]

To figure out how we will implement a robust collision detection and handling scheme for our game, let us use the example of Miloshe (aka GuidoMan), who when we last saw him was about to become very closely acquainted with the north side of Matterhorn. In fact, lets say that this was the frame right before the collision.

Figure 2: Miloshe and Matterhorn [2] at t minus 1.

1

As you may have noticed both Miloshe and Matterhorn have some pretty complicated geometry. To simplify things we will consider the interaction between their bounding rectangles only. So moving time forward by 1 frame we get something like the following situation, in which one of the bounding rectangles is overlapping with or even completely inside of the other.

Figure 3: Collision!

At this point we have the following information to detect and deal with the collision: 1. The absolute location of both bounding rectangles. 2. The relative velocity of one of the rectangles with respect to the other. As is implied by the example, we will assume that one of the objects is stationary and that our relative velocity is in fact absolute.

2

Detection

Fortunately by using Java half of our work is already done for us! That is, since version 1.4 Java provides a built-in way to check whether a shape is intersecting with a line or rectangle, via the intersects() method. [1] trueOrFalse = aShape.intersects(aRectangle); To make this work for us, we need to express the two bounding rectangles as Java Rectangles. One convenient solution would be to define a getBounds() method for a class that is extended by every interactive screen object. public class ScreenObj { // Parent of Milosh and Matterhorn int x,y,width,height; ... public Rectangle getBounds() { 2

return new Rectangle(x,y,width,height); } } This makes detecting a collision brutally simple: if (miloshe.getBounds().intersects(matterhorn.getBounds())) { // Smack! }

3

Handling

Okay so now we know Miloshe just ate it. The question becomes what should we do now that we know? Clearly the picture in Figure 3 is an unrealistic place to leave him. Even his ultra sharp haircut would probably not be able cut through that much granite. Our first step in handling the collision will be to extract Miloshe from the mountain by backtracking along his trajectory coming in. A simple solution would be to subtract his velocity from his current position, effectively going back an entire frame. This is not a good solution because it will leave a variable gap between the two objects. If the velocity is large the gap will also be large and noticeable. The ideal approach would be to backtrack to the point where the bounding rectangles are no longer intersecting and no further.

Figure 4: Two locations to backtrack.

In implementing the good backtracking algorithm we can consider x and y independently. This is good because as Figure 5 shows there is plenty going on even in one dimension!

3

Figure 5: Backtracking along the y axis.

Looking at Figure 5 we can derive Java code to implement our one-dimensional backtracking algorithm. Note the need for two separate behaviors based on the direction of the moving object. Also note the 1 pixel buffer, the reasoning behind which will be discussed shortly. public void backtrackY(ScreenObj a, ScreenObj b) { if (a.vy > 0) { int distY = a.y + a.height - b.y + 1; a.y -= distY; } else { int distY = b.y + b.height - a.y + 1; a.y += distY; } } So seems like we got this backtracking thing all figured out, right? Well, not quite. If we create a similar method for the x axis and apply both methods to the problem of extracting Miloshe from the mountain, the result would look something like Figure 6.

4

Figure 6: Too much of a good thing.

The trick is that distY cannot be greater than the magnitude of vy. If it is, just backtrack by vy. The code below is fixed to do just the right amount of backtracking. 1 public void backtrackY(ScreenObj a, ScreenObj b) { if (a.vy > 0) { int distY = a.y + a.height - b.y + 1; a.y -= distY > a.vy ? a.vy : distY; } else { int distY = b.y + b.height - a.y + 1; a.y += distY > -a.vy ? -a.vy : distY; } } So now Miloshe is free, but still has another problem. Like a dart stuck to a dartboard, so is Miloshe stuck to the surface of Matterhorn. The reason is that throughout the backtracking process his velocity has remained unchanged. Consequently when the next frame rolls around he will simply try to smash his way through again, and again, and again... you get the idea. And each time the backtrack algorithm will extract him and place him exactly back where he started from. A good way to burn off those extra CPU cycles but not much more. We avoid this situation by considering that while Miloshe can make no more progress in the forward x direction, he has velocity and is completely unimpeded in the forward y direction. Generally, once backtracking is complete we should try moving first along one then the other axis. 1 Something else I initially got wrong was to do the subtraction backwards, that is b.y (a.y + a.height) instead of a.y + a.height - b.y which is correct. In Java’s coordinate system a.y is smaller than b.y.

5

Given our assumption that collisions occur only between bounding rectangles, one of these moves absolutely must succeed. The direction in which the move doesn’t succeed has its velocity set to zero, preventing further attempts at collision and mimicking the real life effect of smacking into a wall. public boolean tryMoveAlongY(ScreenObj a, ScreenObj b) { a.y += a.vy; if (a.getBounds().intersects(b.getBounds())) { a.y -= a.vy; return false; } a.vx = 0; // It’s x not y! return true; } Now we see the point of leaving a 1 pixel buffer between the two objects, namely that the objects can now slide cleanly past each other after backtracking.

Figure 7: A successful collision.

To wrap things up notice that we currently have two distinct parts to our collision handling scheme: a backtracking step and a partial forward motion step. Let’s consolidate them in a single method, part of class Miloshe, that is called whenever a collision is detected to occur between him and another object. public class Miloshe extends ScreenObj { ... public void collide(ScreenObj o) { if (o instanceof Matterhorn) { backtrackX(this, o); backtrackY(this, o); if (tryMoveAlongX(this, o)) return;

6

if (tryMoveAlongY(this, o)) return; // If we get down here, // it means something went wrong System.out.println("Wups!"); } } } The job of checking for collisions between any two screen objects is the responsibility to the driver class, which would have to make this check once every frame. In conclusion, we have created a collision detection and handling system that while simplistic works well for collisions occuring between two objects. It does not account for all the possible variables that might be in a video game *cough* gravity, hitting multiple objects in one colission *endcough* but can be a good place to start. Merry christmas, and happy coding!

References [1] Sun Microsystems. Shape (java platform se 6). http://java.sun.com/javase/6/docs/api/java/awt/Shape.html. [2] Vance Roy. Golden matterhorn. http://www.untourscafe.com/photo/photo/listTagged?tag=matterhorn. [3] Unknown. No-clipping motivational poster. http://imagechan.com/images/de99a5ee7b623848e85e8482437d76cf.jpg.

7