Object-to-World Collisions

Object collisions with the world should generally be as accurate as possible. You don't want the player or another object to move through a wall or to jitter when moving along a wall. In , you implemented object-to-world collisions by moving just one coordinate at a time (first x, then y), which worked great for a simple tile-based world in which the objects don't move more than the length of one tile for each frame. In the 3D world, you don't have tiles, but you usually have the 3D world described in a structure that can help with collision detection, such as BSP trees. You'll use the 2D BSP tree from the previous chapter to implement collision with floors, ceilings, and walls.

Bounding Boxes for Testing Against Floors

In the 2D game in , you used the bounding rectangles of the sprites for collision detections. In 3D, besides bounding spheres, circles, or cylinders, bounding boxes are another popular type of collision-detection mechanism. Two types of bounding boxes exist: freeform and axis-aligned. Freeform bounding boxes can be turned and rotated any way, while axis-aligned boxes are aligned with the x-, y-, and z-axis. In this chapter, we used cylinders for object-to-object collision and axis-aligned bounding boxes for object-to-world collisions. The first thing to discuss are floors and ceilings. In a world where floors can be of variable height, you'll want objects to stand on the highest floor under its bounding box, as in Screenshot. Likewise, you don't want objects to move to areas if the ceiling is too low for the object. Also, you might want objects to be able to cross small steps without stopping. In this figure, the player can make the small step up to the platform.

Screenshot Bounding box collision with a floor: The player's bounding box is partially on the stair, so the height of the stair is used as the player's "floor."

Java graphics 11fig09.gif


In Screenshot, the highest floor within the object's bounds is used to determine how high the object stands. When testing an object against the floor and ceilings of the environment, you can check each corner of the box for an intersection with the floor or ceiling. This involves four floor checks, one for each corner of the bounding box. One thing to note about bounding boxes is that they can also be used for object-to-object collisions. You can even have bounding box trees, like sphere trees.

Finding the BSP Leaf for a Specific Location

With a 2D BSP tree, floor information is stored in the leaves of the tree. You can find the leaf for a specific location pretty easily, similarly to how you traversed the tree in the last chapter. This is shown in Listing 11.3.

Listing 11.3 getLeaf() Method of BSPTree.java
/**
 Gets the leaf the x,z coordinates are in.
*/
public Leaf getLeaf(float x, float z) {
 return getLeaf(root, x, z);
}
protected Leaf getLeaf(Node node, float x, float z) {
 if (node == null || node instanceof Leaf) {
 return (Leaf)node;
 }
 int side = node.partition.getSideThin(x, z);
 if (side == BSPLine.BACK) {
 return getLeaf(node.back, x, z);
 }
 else {
 return getLeaf(node.front, x, z);
 }
}


Of course, this just finds the leaf for one location, while an object's bounding box can potentially span multiple leaves. So, you check the leaf of each corner of the bounding box.

Implementing Floor and Ceiling Height Testing

Testing each corner of the bounding boxes for the floor and ceiling height is summed up in some methods in the CollisionDetection class, shown here in Listing 11.4.

Listing 11.4 Checking the Floor and Ceiling (CollisionDetection.java)
/**
 Bounding game object corners used to test for
 intersection with the BSP tree. Corners are in either
 clockwise or counter-clockwise order.
*/
private static final Point2D.Float[] CORNERS = {
 new Point2D.Float(-1, -1), new Point2D.Float(-1, 1),
 new Point2D.Float(1, 1), new Point2D.Float(1, -1),
};
...
 getFloorAndCeiling(object);
 checkFloorAndCeiling(object, elapsedTime);
...
/**
 Gets the floor and ceiling values for the specified
 GameObject. Calls object.setFloorHeight() and
 object.setCeilHeight() to set the floor and ceiling
 values.
*/
public void getFloorAndCeiling(GameObject object) {
 float x = object.getX();
 float z = object.getZ();
 float r = object.getBounds().getRadius() - 1;
 float floorHeight = Float.MIN_VALUE;
 float ceilHeight = Float.MAX_VALUE;
 BSPTree.Leaf leaf = bspTree.getLeaf(x, z);
 if (leaf != null) {
 floorHeight = leaf.floorHeight;
 ceilHeight = leaf.ceilHeight;
 }
 // check surrounding four points
 for (int i=0; i<CORNERS.length; i++) {
 float xOffset = r * CORNERS[i].x;
 float zOffset = r * CORNERS[i].y;
 leaf = bspTree.getLeaf(x + xOffset, z + zOffset);
 if (leaf != null) {
 floorHeight = Math.max(floorHeight,
 leaf.floorHeight);
 ceilHeight = Math.min(ceilHeight,
 leaf.ceilHeight);
 }
 }
 object.setFloorHeight(floorHeight);
 object.setCeilHeight(ceilHeight);
}
/**
 Checks for object collisions with the floor and ceiling.
 Uses object.getFloorHeight() and object.getCeilHeight()
 for the floor and ceiling values.
*/
protected void checkFloorAndCeiling(GameObject object,
 long elapsedTime)
{
 boolean collision = false;
 float floorHeight = object.getFloorHeight();
 float ceilHeight = object.getCeilHeight();
 float bottomHeight = object.getBounds().getBottomHeight();
 float topHeight = object.getBounds().getTopHeight();
 if (!object.isFlying()) {
 object.getLocation().y = floorHeight - bottomHeight;
 }
 // check if below floor
 if (object.getY() + bottomHeight < floorHeight) {
 object.notifyFloorCollision();
 object.getTransform().getVelocity().y = 0;
 object.getLocation().y = floorHeight - bottomHeight;
 }
 // check if hitting ceiling
 else if (object.getY() + topHeight > ceilHeight) {
 object.notifyCeilingCollision();
 object.getTransform().getVelocity().y = 0;
 object.getLocation().y = ceilHeight - topHeight;
 }
}


The getFloorAndCeiling() method gets the floor and ceiling height for an object by checking the leaves at the object's four corners. Keep in mind that an object could be in multiple BSP tree leaves simultaneously. Setting the object's y location occurs in the checkFloorAndCeiling() method. If the object is not flying, the y value is the floor height. Otherwise, it checks to see if the object hits the floor or ceiling. If so, the object's notifyFloorCollision() or notifyCeilingCollision() method is called. Just as with notifyObjectCollision(), these methods do nothing by default, and subclasses of GameObject can override these methods. The way the floor and ceiling collisions are implemented is primitive at this point; the player just instantly pops to higher or lower floors. Later in this chapter, you'll implement gravity and the capability to scoot smoothly up stairs to make the collision handling seem more realistic.

Bounding Boxes for Testing Against Walls

With floors and ceilings, you were testing only for collisions after an object has already moved and only to determine how high the floor is underneath the player. However, walls are thin lines, so if you test for a wall collision only after an object has moved, it's possible you could miss walls that the object has already passed right through. To accurately determine whether an object hits any walls, you need to test the entire path the object travels during the update from one frame to the next. For a 2D BSP tree, because an object's path from one frame to the next is a line segment, you can test this line segment for an intersection with any lines that represent walls. (It's the same concept for a 3D BSP tree, except that the path is tested for an intersection with a plane that represents the walls.) Of course, the objects are solid shapes, not points. So, if you're using bounding boxes for collision testing, you must test all four corners of the bounding box with the walls in a scene, as in Screenshot. In this figure, four paths (for each corner) are tested for an intersection, and three of them intersect a wall.

Screenshot Checking the bounding box corners with an intersection with a wall. Each line segment is checked against the BSP tree for a collision.

Java graphics 11fig10.gif


When more than one intersection is found, as in Screenshot, the shortest path from the start location to the intersection is the one to use for the collision, as shown in Screenshot. Here, the upper-left corner of the object is the first to collide with the wall (it is the shortest path to a line intersection), so it is used to determine the collision location.

Screenshot The closest intersection from each corner of the bounding box is chosen as the collision location.

Java graphics 11fig11.gif


Now you need a fast way to determine whether a path intersects with any polygons in the 3D world. In this case, you'll find the first line segment intersection of a BSP tree.

Intersection of a Line Segment with a BSP Tree

Consider a path from (x1,y1) to (x2,y2). The goal is to find the first intersection of this path with a polygon in the BSP tree, if any. The first intersection is the one closest to (x1,y1). Here is the algorithm for this, starting with the root node of the BSP tree:

  1. Check the path against the node's partition. If the path is either in front of or in back of the node's partition, check the front or back nodes, respectively.

  2. Otherwise, if the path spans the node's partition, bisect the path into two paths along the partition. One path represents the first part of the path, and the other path represents the second part of the path.

    1. Check the first part of the path for an intersection (see Step 1).
    2. If no intersection is found, check the polygons in this node for an intersection.
    3. If no intersection is found, check the second part of the path for an intersection (see Step 1).
    4. If an intersection is found, return the point of intersection. Otherwise, return null.

This algorithm basically says to look at every partition that the path spans, from the first (closest) partition to the last (farthest) partition, and return the first point of intersection, if any. Note that just because a path spans a partition doesn't necessarily mean that an intersection occurred. For an intersection, you need to meet three conditions:

  • For a 2D BSP tree, the line segment representing the polygon spans the path.
  • The polygon isn't a short polygon that the object can step over, and isn't a polygon too high or too low to be in the object's way.
  • The path travels from the front of the polygon to the back of the polygon.

The algorithm for finding the intersection (and the conditions for an intersection) is implemented here in Listing 11.5.

Listing 11.5 Intersection with a Line Segment with the BSP Tree (CollisionDetection.java)
private BSPTree bspTree;
private BSPLine path = new BSPLine();
private Point2D.Float intersection = new Point2D.Float();
...
/**
 Gets the first intersection, if any, of the path (x1,z1)->
 (x2,z2) with the walls of the BSP tree. Returns the
 first BSPPolygon intersection, or null if no intersection
 occurred.
*/
public BSPPolygon getFirstWallIntersection(float x1, float z1,
 float x2, float z2, float yBottom, float yTop)
{
 return getFirstWallIntersection(bspTree.getRoot(),
 x1, z1, x2, z2, yBottom, yTop);
}
/**
 Gets the first intersection, if any, of the path (x1,z1)->
 (x2,z2) with the walls of the BSP tree, starting with
 the specified node. Returns the first BSPPolyon
 intersection, or null if no intersection occurred.
*/
protected BSPPolygon getFirstWallIntersection(
 BSPTree.Node node, float x1, float z1, float x2, float z2,
 float yBottom, float yTop)
{
 if (node == null || node instanceof BSPTree.Leaf) {
 return null;
 }
 int start = node.partition.getSideThick(x1, z1);
 int end = node.partition.getSideThick(x2, z2);
 float intersectionX;
 float intersectionZ;
 if (end == BSPLine.COLLINEAR) {
 end = start;
 }
 if (start == BSPLine.COLLINEAR) {
 intersectionX = x1;
 intersectionZ = z1;
 }
 else if (start != end) {
 path.setLine(x1, z1, x2, z2);
 node.partition.getIntersectionPoint(path,intersection);
 intersectionX = intersection.x;
 intersectionZ = intersection.y;
 }
 else {
 intersectionX = x2;
 intersectionZ = z2;
 }
 if (start == BSPLine.COLLINEAR && start == end) {
 return null;
 }
 // check first part of line
 if (start != BSPLine.COLLINEAR) {
 BSPPolygon wall = getFirstWallIntersection(
 (start == BSPLine.FRONT)?node.front:node.back,
 x1, z1, intersectionX, intersectionZ,
 yBottom, yTop);
 if (wall != null) {
 return wall;
 }
 }
 // test this boundary
 if (start != end || start == BSPLine.COLLINEAR) {
 BSPPolygon wall = getWallCollision(node.polygons,
 x1, z1, x2, z2, yBottom, yTop);
 if (wall != null) {
 intersection.setLocation(intersectionX,
 intersectionZ);
 return wall;
 }
 }
 // check second part of line
 if (start != end) {
 BSPPolygon wall = getFirstWallIntersection(
 (end == BSPLine.FRONT)?node.front:node.back,
 intersectionX, intersectionZ, x2, z2,
 yBottom, yTop);
 if (wall != null) {
 return wall;
 }
 }
 // not found
 return null;
}
/**
 Checks if the specified path collides with any of
 the collinear list of polygons. The path crosses the line
 represented by the polygons, but the polygons may not
 necessarily cross the path.
*/
protected BSPPolygon getWallCollision(List polygons,
 float x1, float z1, float x2, float z2,
 float yBottom, float yTop)
{
 path.setLine(x1, z1, x2, z2);
 for (int i=0; i<polygons.size(); i++) {
 BSPPolygon poly = (BSPPolygon)polygons.get(i);
 BSPLine wall = poly.getLine();
 // check if not wall
 if (wall == null) {
 continue;
 }
 // check if not vertically in the wall (y axis)
 if (wall.top <= yBottom || wall.bottom > yTop) {
 continue;
 }
 // check if moving to back of wall
 if (wall.getSideThin(x2, z2) != BSPLine.BACK) {
 continue;
 }
 // check if path crosses wall
 int side1 = path.getSideThin(wall.x1, wall.y1);
 int side2 = path.getSideThin(wall.x2, wall.y2);
 if (side1 != side2) {
 return poly;
 }
 }
 return null;
}


In this code, getFirstWallIntersection() follows the algorithm mentioned before, and the getWallCollision() method checks for the conditions of an intersection between a path and a polygon. As a sidenote, with a 3D BSP tree, you would also use something like this to determine the height of the floor under an object. Just use this algorithm to find the highest polygon underneath the player by checking for the first intersection with a line segment shot straight down from the object. You've almost got everything to implement a bounding box collision with a BSP tree, but first there's one issue to look into that could cause problems.

The Corner Issue

Alas, all is not well with bounding box collisions! When you're checking each corner of a bounding box with a collision with the world, you run into conditions in which part of the world will collide with the bounding box but not with the corners of the bounding box, as in Screenshot.

Screenshot An object collision with a corner can be a slight problem.

Java graphics 11fig12.gif


In this figure, the object collides with a sharp corner that doesn't touch any of the object's bounding box corners. One way to get around this problem is to treat each edge of the bounding box as a line segment, to test for intersections with the BSP tree. If any of the edges intersect with a polygon in the BSP tree, the object is reverted to its original location. You'll implement this method in the code in this chapter. Alternatively, instead of reverting to its original location, the object could just move back a little bit at a time and test again until no collision is detected. Another solution is to ensure that levels are designed so that this issue never arises. However, this puts a restriction on level design that can make things difficult for the level designer because it's very tempting to make corners, as in the example.

Implementing Object-to-World Collision Detection

That's it for the basic object-to-world collision detection using a BSP tree. The remainder of the code is here in Listing 11.6.

Listing 11.6 Checking Walls (CollisionDetection.java)
// check walls if x or z position changed if (object.getX() != oldLocation.x ||
 object.getZ() != oldLocation.z)
{
 checkWalls(object, oldLocation, elapsedTime);
}
...
/**
 Checks for a game object collision with the walls of the
 BSP tree. Returns the first wall collided with, or null if
 there was no collision.
*/
public BSPPolygon checkWalls(GameObject object,
 Vector3D oldLocation, long elapsedTime)
{
 Vector3D v = object.getTransform().getVelocity();
 PolygonGroupBounds bounds = object.getBounds();
 float x = object.getX();
 float y = object.getY();
 float z = object.getZ();
 float r = bounds.getRadius();
 float stepSize = 0;
 if (!object.isFlying()) {
 stepSize = BSPPolygon.PASSABLE_WALL_THRESHOLD;
 }
 float bottom = object.getY() + bounds.getBottomHeight() +
 stepSize;
 float top = object.getY() + bounds.getTopHeight();
 // pick closest intersection of 4 corners
 BSPPolygon closestWall = null;
 float closestDistSq = Float.MAX_VALUE;
 for (int i=0; i<CORNERS.length; i++) {
 float xOffset = r * CORNERS[i].x;
 float zOffset = r * CORNERS[i].y;
 BSPPolygon wall = getFirstWallIntersection(
 oldLocation.x+xOffset, oldLocation.z+zOffset,
 x+xOffset, z+zOffset, bottom, top);
 if (wall != null) {
 float x2 = intersection.x-xOffset;
 float z2 = intersection.y-zOffset;
 float dx = (x2-oldLocation.x);
 float dz = (z2-oldLocation.z);
 float distSq = dx*dx + dz*dz;
 // pick the wall with the closest distance, or
 // if the distances are equal, pick the current
 // wall if the offset has the same sign as the
 // velocity.
 if (distSq < closestDistSq ||
 (distSq == closestDistSq &&
 MoreMath.sign(xOffset) == MoreMath.sign(v.x) &&
 MoreMath.sign(zOffset) == MoreMath.sign(v.z)))
 {
 closestWall = wall;
 closestDistSq = distSq;
 object.getLocation().setTo(x2, y, z2);
 }
 }
 }
 if (closestWall != null) {
 object.notifyWallCollision();
 }
 // make sure the object bounds is empty
 // (avoid colliding with sharp corners)
 x = object.getX();
 z = object.getZ();
 r-=1;
 for (int i=0; i<CORNERS.length; i++) {
 int next = i+1;
 if (next == CORNERS.length) {
 next = 0;
 }
 // use (r-1) so this doesn't interfere with normal
 // collisions
 float xOffset1 = r * CORNERS[i].x;
 float zOffset1 = r * CORNERS[i].y;
 float xOffset2 = r * CORNERS[next].x;
 float zOffset2 = r * CORNERS[next].y;
 BSPPolygon wall = getFirstWallIntersection(
 x+xOffset1, z+zOffset1, x+xOffset2, z+zOffset2,
 bottom, top);
 if (wall != null) {
 object.notifyWallCollision();
 object.getLocation().setTo(
 oldLocation.x, object.getY(), oldLocation.z);
 return wall;
 }
 }
 return closestWall;
}


First, this code tests four paths, one for each corner of the bounding box for an intersection. If more than one intersection is found, the closest one is chosen. If two intersections are found an equal distance away, the intersection is chosen that is closest to the direction of the object's velocity. This helps when you actually implement sliding against the wall later in this chapter. If an intersection is found, the object's location is set to the collision location, right up next to the wall. After those tests, the code tests to ensure that the object bounding box is empty (no corners, as in Screenshot). If so, the object is reverted to its original location. That's it—basic collision detection is implemented! Now let's try it out.

Screenshot


   
Comments