Path Finding with Bredth First Search
by
Wilson Saunders
3-19-03
Intro:
When controlling multiple figures on a screen it is impossible to set the exact paths (in a reasonable amount of time) for each figure to correctly navigate a set of obstacles. There for a bit of artificial intelligence is required. By setting a start and final point there are several phases to computing a path between the two. A strait line is the most obvious solution. However a strait line is occasionally not the correct solution. For example if there is intervening terrain and immovable obstacles setting the path to a strait line produces figures running through solid objects like phantoms which is quite often not the desired effect.

Algorithm:
Obstacle Detection
For the majority of points the strait line algorithm will work. However this is not always the case and so a means is needed to to find when it will and will not work. The least computationally expensive method is to check for the intersection of line segments. Using the end points of two line segments the angle between each line segment and the other points can be calculated. If the angles for one point be greater than 180 and less than 180 for the other then the line segments intersect. Applied to this problem the line segments are a face of an obstacle and the strait line path from start to destination.

Tree Growth:
To find the proper path a number of different paths must be explored. This exploration is done by generating a binary tree. The start point is recorded in the root node. If the Obstacle Detection algorithm finds that the strait line path between start and end is blocked the first child is set to the point to the left of the object where there is a clear line between start and chosen point. The second child receives a point left of the object that satisfies the same condition. Obstacle Detection and Tree Growth is done again using the children as roots.

Best Path:
Once the tree is created it is a simple matter of finding all the points that can reach the user supplied destination and calculating the total distance from that point to the start and end adding the values for each segment along the way. The shortest of these paths is chosen.

Here is a Picture of this path finding in action.
The blue lines represent the chosen path of arround the brown obsticles.



Application:
The most common application for this kind of algorithm is to the RTS (Real Time Strategy) genera of video game. The user does not have time to issue orders to all his or her units individually much less set a path. So an algorithm like this one can be used to give the units a decision making capability.

Just for Fun:
This project was completed when the a tree successfully created and the shortest path found. However to make this look very cool other features were added. Thus was born:

Rebels Vs Imperials


Taking insperation from the many shoot-outs in the Starwars series I created two models representing the Imperial Storm Troopers and the Rebel Alliance Cannon Fodder. Each module consists of 13 segments that can be rotated around the joints. I copied the code from a forward kinematics assignment made earlier in the course to get this to work. Also specific joint rations are saved and loaded from file to get the model to run about. A total of three movement files are loaded. One for running, walking, and falling.

An example of a Rebel Trooper in the middle of his falling motion



In addition to the forward kinematics shot modeling had to be implemented. Each trooper can shoot one blaster bolt at a time. The trooper selects an enemy trooper who is within his line of sight. Line of sight is calculated with the same obstacle detection algorithm used in path finding. Once the trooper has acquired a target he rotates to face it then fires a shot. Since Storm Troopers and Alliance Cannon Fodder are notoriously bad shots I had to add an aim giggle of ten degrees. This way long distance shoot-outs rarely result in a fatality since the aim giggle throws the bolt's angle off that it won't collide. At closer ranges the bolts have a wider angle that hits and are subsequently more lethal.

Here is a movie of storm troopers assaulting a rebel line