|
 Features
What
if I'm in a Smooth World?
All these
search methods have assumed a playing area composed of square or hexagonal
tiles. What if the game play area is continuous? What if the positions
of both entities and obstacles are stored as floats, and can be as finely
determined as the resolution of the screen? Figure
11A shows a sample layout. For answers to these search conditions,
we can look at the field of robotics and see what sort of approaches are
used for the path-planning of mobile robots. Not surprisingly, many approaches
find some way to reduce the continuous space into a few important discrete
choices for consideration. After this, they typically use A* to search
among them for a desirable path. Ways of quantizing the space include:
Tiles.
A simple approach is to slap a tile grid on top of the space. Tiles
that contain all or part of an obstacle are labeled as blocked; a
fringe of tiles touching the blocked tiles is also labeled as blocked
to allow a buffer of movement without collision. This representation
is also useful for weighted regions problems. See Figure
11B.
Points
of visibility. For obstacle avoidance problems, you can focus
on the critical points, namely those near the vertices of the obstacles
(with enough space away from them to avoid collisions), with points
being considered connected if they are visible from each other (that
is, with no obstacle between them). For any path, the search considers
only the critical points as intermediate steps between start and goal.
See Figure
11C.
Convex
polygons. For obstacle avoidance, the space not occupied by polygonal
obstacles can be broken up into convex polygons; the intermediate
spots in the search can be the centers of the polygons, or spots on
the borders of the polygons. Schemes for decomposing the space include:
C-Cells (each vertex is connected to the nearest visible vertex; these
lines partition the space) and Maximum-Area decomposition (each convex
vertex of an obstacle projects the edges forming the vertex to the
nearest obstacles or walls; between these two segments and the segment
joining to the nearest visible vertex, the shortest is chosen). See
Figure
11D. For weighted regions problems, the space is divided into
polygons of homogeneous traversal cost. The points to aim for when
crossing boundaries are computed using Snell's Law of Refraction.
This approach avoids the irregular paths found by other means.
Quadtrees.
Similar to the convex polygons, the space is divided into squares.
Each square that isn't close to being homogenous is divided into four
smaller squares, recursively. The centers of these squares are used
for searching a path. See Figure
11E.
Generalized
cylinders. The space between adjacent obstacles is considered
a cylinder whose shape changes along its axis. The axis traversing
the space between each adjacent pair of obstacles (including walls)
is computed, and the axes are the paths used in the search.
See Figure
11F.
Potential
fields. An approach that does not quantize the space, nor require
complete calculation beforehand, is to consider that each obstacle
has a repulsive potential field around it, whose strength is inversely
proportional to the distance from it; there is also a uniform attractive
force to the goal. At close regular time intervals, the sum of the
attractive and repulsive vectors is computed, and the entity moves
in that direction. A problem with this approach is that it may fall
into a local minimum; various ways of moving out of such spots have
been devised.
Bryan
Stout has done work in "real" AI for Martin Marietta and in computer games
for MicroProse. He is preparing a book on computer game AI to be published
by Morgan Kaufmann Publishers in 2001. He can be contacted at bstout@mindspring.com.
 
[Back to] Introduction
|
|
|
|
|
