AI demonstration

I chose to research obstacle avoidance steering. This technique is basically what it sounds like: it involves steering a moving object such that it will never collide with obstacles. We do this via the use of raycasting. The moving object casts the rays; one straight forward, on angled above, and one angled below. If none of these return a collision, than it’s business as usual. However, if a ray returns a collision, the player moves parallel to the collision point’s normal, away from the obstacle.

Fig 1: The bottom ray has returned a collision. The green line is the normal to the collision point, and the gray line is the parallel the player will travel along.

However, this wasn’t quite enough to achieve the desired effect. When the AI unit isn’t avoiding obstacles, it’s moving towards a goal on a linear path. Therefore, if the AI encountered an obstacle it was because said obstacle was in between the AI and its target. What this lead to was a stuttering effect; one frame, the AI would detect a collision and steer to avoid it. Now the AI wasn’t facing the obstacle anymore, so next frame it would turn to face its target. But since it’s only moved one frame’s worth of distance, it would be right back to facing the obstacle, repeating the process. Since it got that frame of movement in the AI eventually made its way around the obstacle, but it was an ugly process.

            To circumvent this, I implemented a buffer for defaulting to target seeking. Before switching to the target seek steering, the AI would raycast in that direction, with the same spread as a normal cast. If the raycast returned a hit, the AI kept on its avoid steering, but if it returned nothing, the AI switched back to target seek steering. This cast was a little longer than the obstacle detection cast, since otherwise the AI got out of range prematurely and would stutter similar to how it would stutter without the check at all.

Fig 2: The player is avoiding the blue planet.  Although the obstacle detection (red rays) is giving the all clear, the buffer (blue rays) is telling the player that a switch would be premature. Therefore the player will keep avoiding the obstacle until they have fully cleared it.

            Over the course of my research I used 3 main sources. I first looked at an article by Craig W. Reynolds of Sony Computer Entertainment America discussing various AI behaviors (found here http://www.red3d.com/cwr/steer/gdc99/). Of particular interest was his section on obstacle avoidance steering. He discussed the common method of avoiding obstacles based on bounding spheres, as well as the general theory of only caring about objects in the AI’s movement path, and only caring about the closest object at that.

            From there, I found a forum discussion on gamedev.net (http://www.gamedev.net/topic/632735-help-with-obstacle-avoidance-behavior/) that brought up the alternate method of raycasting. The users “slicer4ever” and “IADaveMark” discussed the benefits of bounding spheres vs. raycasting. Although I intended to demonstrate this technique using spherical obstacles regardless of my approach, I decided to use raycasting since it was the more general solution, working for any convex shape. Finally, I found a great starting point for my work using the pseudo-code found in “Artificial Intelligence for Games” by Ian Millington and John Funge.

            This technique has uses for many action-based games, since it solves a very common problem. Many games require AI to successfully navigate around obstacles, and if said obstacles are constantly moving or being dynamically created or destroyed, A* pathfinding becomes wildly impractical. This technique relies on raycasting, an expensive process, meaning that it is unsuited for platforms with constrained processing time, such as mobile.