Finding the Closest Intersection Point
The process of checking for intersections with obstacles is quite compli
cated, so let’s take this step by step.
A) The vehicle should only consider those obstacles within range of its
detection box. Initially, the obstacle avoidance algorithm iterates
through all the obstacles in the game world and tags those that are
within this range for further consideration.
B) The algorithm then transforms all the tagged obstacles into the vehi
cle’s local space (for an explanation of local space, see Chapter 1).
This makes life much easier as after transformation any objects with a
negative local x-coordinate can be dismissed.
C) The algorithm now has to check to see if any obstacles overlap the
detection box. Local coordinates are useful here as all you need to do
is expand the bounding radius of an obstacle by half the width of the
detection box (the vehicle’s bounding radius) and then check to see if
its local y value is smaller than this value. If it isn’t, then it won’t
intersect the detection box and can subsequently be discarded from
Figure 3.7 should help clear up these first three steps for you. The letters on
the obstacles in the diagram correspond to the descriptions.
D) At this point there are only those obstacles remaining that intersect the
detection box. It’s now necessary to find the intersection point closest
to the vehicle. Once more, local space comes to the rescue. Step C
expanded an object’s bounding radius. Using this, a simple line/circle
intersection test can be used to find where the expanded circle inter
sects the x-axis. There will be two intersection points, as shown in
Figure 3.8. (We don’t have to worry about the case where there is one
100 | Chapter 3
The Steering Behaviors
Figure 3.7. Steps A, B, and C