[MUD-Dev] a article on ai -- ANTS -- (fwd)

[J C Lawrence]

------- Forwarded Message

From: "Derold" <bro1 at cyberhighway.net>
To: <gameprogrammer at gameprogrammer.com>
Subject: a article on ai -- ANTS --
Date: Tue, 18 Apr 2000 02:30:17 -0600

Path Finding Via 'Ant Races'  (a floodfill algorithm)

Assume you have a large board with varied terrain, perhaps some
impassable terrain.  Moves are strictly defined as moving one
square on the board; moving that one square may take a longer or
shorter time.  How can you find the best way to get from one=20
place to another?

Introduction:

Visualize trying to find your way across the board.  You release
a flood of ants at the start, and the first ant that reaches your=20
destination has found the best path. =20

How do you find the actual path?

Each time an ant steps on a new square it labels that square with
the time it took to get to that square.  (Ants are not allowed to=20
go where other ants have stepped.) When one ant reaches the
destination, you can find your way back to the start by always
moving into the square with the least time label.

To find the path from the start to the end, simply have your mass
of ants begin at the end and try to get to the start.

Implementation for simple terrain (strictly passable/blocked):

Consider a list of ants.  Each turn, each ant moves to its
destination square and marks it with the current time, spawns
a number of new ants for each free square (that are unmarked and=20
passable) and removes itself from the list.

Implementation for variable terrain:

Consider a list of ants.  Every time tick, you go through the list=20
and decrement the time remaining for each ant to reach its destination
square. Ants that finally reach a new square (time left=3D0) shall mark=20
that square with the current time and produce a number of new=20
ants.  One ant is produced for each unmarked and passable square=20
that the old ant can get to from its current position.  Each new ant=20
is added to the list along with the time to its destination (the cost=20
of the path to the square), and the old ant is removed.  In this=20
manner, each square is always marked with the least time taken=20
to be reached.  Once the 'start' is finally reached by some ant,=20
one can quickly follow the path back to the 'end' by always moving=20
to the adjacent square with the least time.

Problems:

Suppose two ants are heading for the same square?

Ants can check if their destination square is already taken, and
quietly die (sans offspring) if it is.   On the other hand, given
the assumption that the cost to get into this square is the same
from any direction, then as soon as an ant arrives at a square, it
can mark all the adjacent free squares, since no other ant could
possibly do any better.  That way, no two ants will never be heading
for the same square.  This saves a few cycles, too.

Optimizations:

Should we be keeping a big list of ants and checking them all every=20
turn to 'move' them all (get them one tick closer to their=20
destinations) and to see if any have arrived? That seems=20
rather wasteful, especially if some ants are going to take a long
time, hundreds of ticks maybe, getting from one square to the=20
adjacent one.  We can do quite a bit better with a modified data
structure, actually.

Consider not one list of ants, but a queue of lists of ants.
Each list in the queue has the nice characteristic that every ant
in that list will arrive at its destination at the same time, i.e.
in list #1 in the queue, each ant will arrive in one time tick, in
list #2 are all the ants that will arrive wherever they are going
in two ticks, and so on.   So list #0 is always the ants that
have just arrived, that need to spawn children, mark squares,
etc.

To let one time tick pass, just move from the current list in=20
the queue position to the next list in the queue.

In this case, an index into an array of lists can keep track of
the queue position.  After dealing with the current list, bump
up the index and deal with the next list.  The index will wrap
around from the end back to the beginning.

How can we make sure that each list contains the ants arriving at
the appropriate time?  When producing a new ant that is heading
for a square which will take 't' ticks to get to, put that ant
in the list at position current array-index plus t [mod size of the=20
queue].

So you need never check or update times; the position in the
queue keeps track of times for you.  The only timekeeping that
must be done is knowing the current tick number to label just-
reached squares with.  Furthermore, you can make your list
manipulation very simple, since you need never add or remove
an ant except at the beginning of the list.

Another minor optimization:  Give your board an 'impassable'
border, so that you need never check about going outside array
bounds.

How good is this algorithm?

I don't think you can do better without changing the form of
the problem.  For each square, one ant is put onto a list, taken
off a list, and the neighbors of that square are checked.  It
is O(n) on size of the board;  approximately number of squares
times number of neighbors for each square.  Perhaps some other
algorithm could do better for graphs in which each vertex had
a large number of edges, since each edge is being checked twice.

On a 486/80 with a purely C++ implementation, the time to find
the best path for a 100x100 board, going from NW corner to SE
corner, was ~60 milliseconds.  The time was spent doing about
60,000 operations -- looking at each square four times, and
creating and removing 10,000 ants.  I suspect an implementation
in assembler could do it in about 1/4 the clock time, making
it practical for a realtime wargame.

Note that we're finding the best path from _every square_ to the
destination square, if we run the ant race until there are no
new ants being formed.  So, multiple units in a wargame with the=20
same destination would incur no additional overhead.

Possibilities for doing better by changing the problem may be
compressing the board somehow, so that a large group of squares
is considered as one square.  I'd like to see somebody do a quad-tree
implementation.  Even so, running the ant races on the quad-tree
graph would be a good way to find the actual paths.


- -- Richard Wesson

taken from this site
http://www.gameai.com/
by:
Derold Clifford

------- End of Forwarded Message



_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
http://www.kanga.nu/lists/listinfo/mud-dev