Path finders typically scan a large area to determine a path for the unit to follow. Step taking algorithms typically scan a small area instead to determine a few steps for the unit to take. Step takers can respond better to changes in the map, but this diagram shows one of the problems that can occur:
The unit is initially at the bottom of the map and wants to get to the top. There is nothing in the area it scans (shown in green) to indicate that the unit should not move up, so it continues on its way. Near the top, it detects an obstacle and changes direction. It then finds its way around the "U"-shaped obstacle, following the red path. In contrast, a path-finder would have found a shorter path (blue), never sending the unit into the concave shaped obstacle. How can we avoid these areas in a step taker?
If maps are created by a human, simply avoid making concave obstacles. Alternatively, you could mark each concave area in the map. Then, the unit can treat interiors of concave areas as obstacles (except those that contain the unit's destination).
In this figure, the shaded area is treated as an obstacle because the unit does not want to travel into its interior. The unit can go around instead of going inside and then coming out.
This technique is also useful for computer generated maps, as long as they do not change often as the game runs. You can write an algorithm to find all concave obstacles, and then mark their interiors as possible obstacles.
Instead of marking areas of the map as being obstacles, it should be possible for units to try any path, but then learn to avoid areas that caused them to turn around. This technique may be more useful for maps that change often, as the units can learn to avoid an area, but be willing to try it again occasionally to see if things have changed.
Back: Space | Up: Home | Next: AI Techniques |
Last modified: Sun Nov 18 11:32:17 2001 From Amit's Game Programming Site | Copyright (C) 2000, Amit J. Patel |