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