Using the A* Algorithm with a BSP Tree

Let's consider a typical floor plan for a 3D world like you used in previous chapters. In this world, what could your nodes be? First, the nodes could be placed by hand. All you would have to do is make sure the edges between neighbor nodes have a clear path (no obstacles in the way) and that there are enough nodes to cover the entire map. However, this can be a bit tedious. Who wants to sit around defining where path-finding nodes are on a map? So let's try to come up with an automatic solution for node placement.

Portals

You can take advantage of the fact that your "rooms" in the floor plan are convex. This means a bot traveling from one entryway of the room to another will never hit any walls, as long as the two entryways aren't collinear. If two entryways are collinear (they exist on the same line in space) and a wall was between them (think doorways in a dorm hall), then a bot could collide with the wall between them. So, extra care may be needed to define room boundaries so that collinear entryways in the same room don't occur. Entryways between convex rooms are often called portals. Portals are generally an invisible polygon (or, in a 2D world, an invisible line) that separates two convex areas. See Screenshot for an example: The dotted lines represent the portals.

Screenshot Dotted lines represent the portals between convex areas.

Java graphics 12fig07.gif


Portals can also be used as a rendering technique. With portal rendering, you start by drawing all the polygons in the room that the camera is in. If any portals are in the view, the room on the other side of the portal is drawn, and then so on until the view is filled. Using portals as nodes means you can easily create a graph for traveling room to room, as in Screenshot.

Screenshot The portals can be the nodes in a graph representing the map.

Java graphics 12fig08.gif


The only issue is that the start and goal locations are within a room, not on a portal. However, because rooms are convex, a bot can move in a straight line from any location in a room to one of the room's portals without running into any walls. So, when you are doing an A* search, you can make temporary nodes that represent the start and the goal. These node's neighbors are all the portals of the room they are in. Note that using portals as nodes takes only the world into account—obstacles based on game objects aren't considered. So, if you have a door or other game object in the way, you'll need some extra code to move around those objects or at least consider them in the search.

Implementing Portals

In a BSP tree, portals can be stored in the leaves of the tree because the leaves represent convex areas. This way, you can easily get all the portals for a room. Here you just add a list of portals to the BSP tree leaf you created in :

public static class Leaf extends Node {
 public float floorHeight;
 public float ceilHeight;
 public Rectangle bounds;
 public List portals;
}


Finding the portals is easy. Because a leaf in a 2D tree represents an area, just check each edge of that area to see if there's a "solid wall" on it. If there is not, you have a portal. The same is true for a 3D BSP tree, except that every face of the leaf volume is checked. When you have a portal, you need to know what leaf is on either side of it. You can find out by doing a simple tree traversal, shown in Listing 12.3 with the getFrontLeaf() and getBackLeaf() methods of BSPTree.

Listing 12.3 getLeaf() Methods of BSPTree.java
/**
 Gets the Leaf in front of the specified partition.
*/
public Leaf getFrontLeaf(BSPLine partition) {
 return getLeaf(root, partition, BSPLine.FRONT);
}
/**
 Gets the Leaf in back of the specified partition.
*/
public Leaf getBackLeaf(BSPLine partition) {
 return getLeaf(root, partition, BSPLine.BACK);
}
protected Leaf getLeaf(Node node, BSPLine partition, int side)
{
 if (node == null || node instanceof Leaf) {
 return (Leaf)node;
 }
 int segSide = node.partition.getSide(partition);
 if (segSide == BSPLine.COLLINEAR) {
 segSide = side;
 }
 if (segSide == BSPLine.FRONT) {
 return getLeaf(node.front, partition, side);
 }
 else if (segSide == BSPLine.BACK) {
 return getLeaf(node.back, partition, side);
 }
 else { // BSPLine.SPANNING
 // shouldn't happen
 return null;
 }
}


These methods assume the partition doesn't span any other partitions because the partition is the edge of a leaf. The correct Leaf object is returned depending on whether you want the leaf in front of or in back of the partition. Finally, you'll make a Portal class, as shown in Listing 12.4. This class is a subclass of AStarNode.

Listing 12.4 Portal.java
package com.brackeen.javagamebook.bsp2D;
import java.util.*;
import com.brackeen.javagamebook.math3D.Vector3D;
import com.brackeen.javagamebook.path.AStarNode;
/**
 A Portal represents a passable divider between two
 leaves in a BSP tree (think: entryway between rooms).
 The Portal class is also an AStarNode, so AI creatures
 can use the A* algorithm to find paths throughout the
 BSP tree.
*/
public class Portal extends AStarNode {
 private BSPLine divider;
 private BSPTree.Leaf front;
 private BSPTree.Leaf back;
 private ArrayList neighbors;
 private Vector3D midPoint;
 /**
 Create a new Portal with the specified divider and front/
 back leaves.
 */
 public Portal(BSPLine divider, BSPTree.Leaf front,
 BSPTree.Leaf back)
 {
 this.divider = divider;
 this.front = front;
 this.back = back;
 midPoint = new Vector3D(
 (divider.x1 + divider.x2) / 2,
 Math.max(front.floorHeight, back.floorHeight),
 (divider.y1 + divider.y2) / 2);
 }
 public float getCost(AStarNode node) {
 return getEstimatedCost(node);
 }
 public float getEstimatedCost(AStarNode node) {
 if (node instanceof Portal) {
 Portal other = (Portal)node;
 float dx = midPoint.x - other.midPoint.x;
 float dz = midPoint.z - other.midPoint.z;
 return (float)Math.sqrt(dx * dx + dz * dz);
 }
 else {
 return node.getEstimatedCost(this);
 }
 }
 public List getNeighbors() {
 if (neighbors == null) {
 neighbors = new ArrayList();
 if (front != null) {
 neighbors.addAll(front.portals);
 }
 if (back != null) {
 neighbors.addAll(back.portals);
 }
 // remove all references to this node
 while (neighbors.remove(this));
 }
 return neighbors;
 }
}


The neighbors of a portal are the portals in the front and back leaves. The getNeighbors() method fills the neighbors in a list. The getEstimatedCost() estimates the cost between portals as the distance between the midpoints of each portal. Note that for two adjacent nodes, getEstimatedCost() is the same as the actual cost. Finally, you just need one more type of AStarNode that is a location anywhere within a convex area defined by the leaf. These nodes are generally just temporary because they are used only for the start and goal nodes of a specific path search.

Listing 12.5 LeafNode Inner Class of AStarSearchWithBSP
/**
 The LeafNode class is an AStarNode that represents a
 location in a leaf of a BSP tree. Used for the start
 and goal nodes of a search.
*/
public class LeafNode extends AStarNode {
 BSPTree.Leaf leaf;
 Vector3D location;
 public LeafNode(BSPTree.Leaf leaf, Vector3D location) {
 this.leaf = leaf;
 this.location = location;
 }
 public float getCost(AStarNode node) {
 return getEstimatedCost(node);
 }
 public float getEstimatedCost(AStarNode node) {
 float otherX;
 float otherZ;
 if (node instanceof Portal) {
 Portal other = (Portal)node;
 otherX = other.getMidPoint().x;
 otherZ = other.getMidPoint().z;
 }
 else {
 LeafNode other = (LeafNode)node;
 otherX = other.location.x;
 otherZ = other.location.z;
 }
 float dx = location.x - otherX;
 float dz = location.z - otherZ;
 return (float)Math.sqrt(dx * dx + dz * dz);
 }
 public List getNeighbors() {
 return leaf.portals;
 }
}


The LeafNode class is fairly straightforward. The neighbors of a LeafNode are all the portals of the BSP tree leaf the node is in. The estimated cost is calculated as the distance between the node location and a portal's midpoint. Now you have all the little pieces you need to perform an A* search on a BSP tree. Next, you'll put all the little pieces together in a wrapper that implements a generic path-finding interface.



   
Comments