BSP motion planning
From CGAFaq
BSP trees are useful for building an "exact cell decomposition". A cell is any region which is used as a node in a planning graph. An exact cell decomposition is one in which every cell is entirely occupied, or entirely empty. The alternative is an "approximate cell decomposition", in which cells may also be partially occupied. A regular grid on a complex scene is an example of an "approximate cell decomposition".
Example
Consider a game which uses randomly oriented blocks for obstacles in an enclosed arena. For purposes of path planning, we are interested in the decomposition of the ground plane. We can get this by building a BSP tree containing all of the blocks, and pass a polygon which represents the ground into the tree. The splitting routine should be modified to maintain connectivity information when splitting polygons. Using a technique similar to boolean modelling, we can reduce the tree to contain only those polygons which are the regions of the ground plane not contained inside any obstacles.
Now, a planning graph can be built, using some point inside of each polygon, and connecting to a point inside of each of its neighbors. Note that the selection of the point location has implications for the length of resulting paths. Planning begins by identifying the cell which contains the start point, and the cell which contains the end point. Then a standard A* style search can be used on the planning graph to find the set of polygons that must be crossed to get to the end point from the start point.
Implementation Notes
A simple optimization can help yield a straight path where on is important. When planning through a given region, keep track of where you are coming from and where you are going to. By treating the edges of the region as portals, and allowing your entry and exit points to slide along the portals, you can insure a minimum length path through each node.
Initial content for this page from the BSP tree FAQ, included with permission of its maintainer, Bretton Wade.
