[Game Programming Galaxy]
                                  [Logo]
                                 [Design]

                             Chase and Evasion

The most simple way to track down a player is to move directly towards him,
the most easy way to avoid him, is to move in the opposite direction. A
very simple algorithm, which can be used if there're no obstacles is shown
in Listing 1. This algorithm is really simple: It just compares two
positions (the position of the monster and the position of the player, for
example), and returns the direction to move. It doesn't care if there's
something in the way, so if there're walls, a monster would constantly bang
its head against them if the player is on the other side.

                                 Listing 1


                             The Monster Patrol

Some quite good Jump'n'Runs let their monsters move from point A to point
B, then to C and so on; the last point connects back to the first. This
isn't much harder than the chase algorithm explained above , the only
difference is, that the monsters are "chasing" the waypoints and not the
player.

In the "update and move" part of your programm, you would check if the
monster has reached the next waypoint, and if so assign the next waypoint
to it. See listing 2 for sample source. I'll come back to this topic later,
discussing Waypoints, Zelda style

                                 Listing 2


                             Obstacle avoidence

The enemies controlled by the above algos are heading either directly
towards the player, or run in the opposite direction. They don't care about
the environment they move in, ignoring walls, trees and alike. The most
easy way to handle this problem would be to store some "surrounding
information" (si) within each object. That means if a monster runs into a
solid object, it could "ask" this object where to move in order to avoid
it.
Depending on the direction from which the hit occured, every surface
returns an other pair of dx/ dy values to the monster. The rules to choose
these values are quite simple:

  1. Let them go where they want: If the heading of the monster is, f.e. ,
     from top left to bottom right, and it hit the left side of the
     obstacle, let it move downwards.
  2. If the obstacle gets hit in the direction of one if the axis, return
     the surrounding information of the other axis.
     If an obstacle has the si ( -1, 1) and gets hit from something moveing
     along the x axis, you would return the y part of the surrounding
     information, in this case the value 1.

The obvious drawback is to have to store another two values for every
object. You could store this information using 4 bits, so this might not be
a great problem.

Here're two articles covering the topic"obstacle avoidence", also:

   * Maze navigation is the topic of a very interesting article, which can
     be found at x2ftp tutorial contest directory. It uses an iterative
     approach which can speed up pathfinding by a certain amount.
   * A whole website covers the topic " Smart Unit Navigation " it's quite
     good, so I consider it suggested reading.

                           Waypoints, Zelda Style

The monsters in Zelda are moving mainly using waypoints (I'm talking about
the simple monsters, not the bosses). At each waypoint they "look around",
and if the player is within the view cone of one of the monsters the aim
directly towards him. This effect can be achieved if you check at each
waypoint, if the player is not behind the monster (and thus can be seen, if
the monster looks around). If a monster runs into an obstacle, it does not
even try to avoid it, but just moves in the same direction over and over.
BTW: Diablo seems to use a similar method, but the monsters in this program
move a bit along the barrier, using a "try and hope" approach to find a way
to the player.

                     Cheating- Tracking down the player

A very efficient way to find the player could be to use "blood hounds",
some aggressive, small creatures which can follow the player's trail (if
they were not small, the game would be very unfair). You could store the
direction the player moved as he stood the last time at a certain position
as an attribute of this position. This would enable the blood hound to
track down the player efficiently (This kind of algo. could be used nicely
for a pacman type of game).

If thouse hounds are faster than the player, they could really be a
nightmare for the player. Imagine they could "call" others, as soon as they
can "see" the player (that means as soon as thouse monsters and the player
are both visible on the screen)... and since they follow the trail of the
player there's no hiding, because an invisibility spell can't fool the
their sense of smell...

      [Image]              [Image]              [Image]

  ------------------------------------------------------------------------
                              | What's New? |
      | Design | Tutorials | Projects | Tools | Genres | Tile based |
                               | Link Page |
  ------------------------------------------------------------------------

                Designed and maintained by Lennart Steinke
                        lennart_steinke@bigfoot.com

                            Hosted by GeoCities
                                                    [Welcome to GeoCities!]