AI and Gaming
=============

Steering
========

Think of a gang, patrolling at the front gate of a castle, protecting an area on a bridge.

Looking inside each members of the gang game (http://www.red3d.com/cwr/boids/applet/), we may see
SteeringForce +=
    wander()            * wanderAmount        * wanderProirity +
    obstacleAvoidance() * avoidAmount         * avoidPriority +
    aligness()          * alignAmount         * alignPriority +
    cohesion()          * cohesionAmount      * cohesionPriority +
    seperation()        * seperationAmount    * seperationPriority +
    alignment()         * alignAmount         * alignPriority +
    wallAvoidance()     * wallAvoidanceAmount * wallAvoidPriority  +
    chasePrey()         * chaseAmount         * chasePriority +
    avoidPrey()         * avoidAmount         * avoidPriority
What is going on here? A round robin between two models:

  * A actor model: I think I want to steer here

  * A physics model (walls, gravity, air or mud resistance): oh no you don't; E.g. flow fields (http://www.red3d.com/cwr/steer/FlowFollow.html)

steer
  |
  |
  v
 Player ---> thrust
How to control a whole host of behaviors:.

Pattern Movements (Wandering)
-----------------------------

When in doubt, pattern movement. At any "X", going in direction "Y", pick any neighbor at random, favoring those nearer your current compass bearing:
pattern[0]={1111111111
            1111111111
            1111111111
            1111111111
            1111111111
            1111111111
            1111111111}

pattern[1]={1...1..111
            .1.1..1...1
            1.1.......1
            .1..111.1.1
            1..1...1.1.
            1.1........
            11.........}

pattern[2]=
Pick patterns at random. Note: pattern[0] means random walk.

Bread crumbs
------------

Actor X drops bread crumbs. Actor Y steers towards (or away) zones of higher bread crumb results.

Bread crumbing have some nice computational properties; e.g. very fast to compute.

Flocking
--------

Kind of pattern movements, for groups.

Look around to a distance of "D" for an plus/minus "X" degrees from your current compass bearing:

  * Increase "X" to make more of the flock spread wide, flock more together;

  * Decrease "X" to turn the "flock" into a single file of actors, playing follow the leader.

With that knowledge, work out how much to operate, align, cohere...

Separation: steer to avoid crowding local flock mates (give this one the highest priority)

Alignment: steer towards the average heading of local flock mates

Cohesion: Cohesion: steer to move toward the average position of local flock mates,

( maybe weighted by your compass bearing; e.g....
741
973
741
)

(See also Lennard-Jones functions (http://en.wikipedia.org/wiki/Lennard-Jones_potential) for combining the above into one equation.)

Leader Following
----------------

Do a weighted sum of the neighborhood, giving a "leader" more weight than the rest of the flock.

Now the problem of programming the flock reduces to just the problem of programming the leader (http://www.red3d.com/cwr/steer/LeaderFollow.html).

Note: the leader can be selected dynamically:

  * E.g. you want to herd the flock through a gate;

  * The "leader" is the flock member closest to the gate;

  * So, if the leader falls, you can automatically pick another another leader

Predation
---------

Predict where the food will be, steer towards there.

Prey avoidance
--------------

Predict where the prey will be, steer away from there.

Or, with knowledge of the terrain, find a predator's blind spot (behind a rock) and go steer to there.

Obstacle avoidance
------------------

Extend "feelers".

If they fall within "r" of some obstacle, then insert a steering force "b" (http://www.red3d.com/cwr/steer/Obstacle.html) to deflect the actor

Path finding and way points
---------------------------

Given a terrain map of regions (rooms, valleys with passes between them, oceans connected by straights),

  * Reduce the navigation problem to paths between way points.

To compute way points:

  * Place points in every room/region of the terrain map

  * Jiggle them so they they are in line of sight of the most number of other points (minimum of one)

  * Pre-computer and cache nearest adjacent nodes

  * Store the adjacency matrix M1[u,v] means path from u to v
     M1=    A B C D E F G
          A . 1 . . . . .
          B . . 1 . . . .
          C . . . 1 1 . .
          D . . . . . . .
          E . . . . . 1 .
          F . . . . . . 1
          G . . . . . . .

  * Complete the matrix. If paths bi-directional, then If M2[u,v] = M1[u,v] or M1[v,u]
     M2=    A B C D E F G
          A . 1 . . . . .
          B 1 . 1 . . . .
          C . 1 . 1 1 . .
          D . . 1 . . . .
          E . . 1 . . 1 .
          F . . . . 1 . 1
          G . . . . . 1 .

  * Note that:

       * M stores all paths of length one.

       * squared(M)  stores all paths of length two.

       * squred(squared(M)) stores all paths of length three.

       * M* (transitive closure) stores all paths of all lengths (see any algorithms book)

       * Loop detection: transitive closure for N vertices O(N3). Loop if "u" is in its own transitive closure.

If you want some geography, add distance measure instead of just "1"
D1=    A B C D E F G
     A . 4 . . . . .
     B . . 2 . . . .
     C . . . 9 7 . .
     D . . . . . . .
     E . . . . . 8 .
     F . . . . . . 3
     G . . . . . . .
These numbers can reflect difficulty in traversing some region (e.g. mud, quicksand, steep slopes)

Navigation in two steps: go straight to the nearest way point, then path follow from weigh point to weigh point.

  * "u := extract_min(Q)" searches for the vertex u in the vertex set Q that has the least dist[u] value.

  * (And as a side-effect, "u"" is removed from "Q")

  * "length(u, v) = D[u,v]

  * Built a shortest path tree between all way points

 1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph:           // Initializations
 3          dist[v] := infinity               // Unknown distance function from source to v
 4          previous[v] := undefined
 5      dist[source] := 0                     // Distance from source to source
 6      Q := copy(Graph)                      // All nodes in the graph are unoptimized - thus are in Q
 7      while Q is not empty:                 // The main loop
 8          u := extract_min(Q)               // Remove and return best vertex from nodes in two given nodes
                                              // we would use a path finding algorithm on the new graph, such as depth-first search.
 9          for each neighbor v of u:         // where v has not yet been removed from Q.
10              alt = dist[u] + length(u, v)
11              if alt < dist[v]              // Relax (u,v)
12                  dist[v] := alt
13                  previous[v] := u
14      return previous[
Note: "previous[]" can be pre-computed and cached (fast runtimes).

When wondering a path, remember to stagger a little and steer more at corners (http://www.red3d.com/cwr/steer/PathFollow.html).

And for crowds to walk paths, add obstacle avoidance (http://www.red3d.com/cwr/steer/CrowdPath.html).

Influence Maps
==============

Recall our geography maps:
D1=    A B C D E F G
     A . 4 . . . . .
     B . . 2 . . . .
     C . . . 9 7 . .
     D . . . . . . .
     E . . . . . 8 .
     F . . . . . . 3
     G . . . . . . .R
Remember that these numbers can reflect difficulty in traversing some region (e.g. mud, quicksand, steep slopes)

An influence map is a second "geography" map that changes at runtime. E.g. suppose you keep dying every time you walk from G to A:
Inf=    A B C D E F G
     A . . . . . . .
     B . . . . . . .
     C . . . . . . .
     D . . . . . . .
     E . . . . . . .
     F . . . . . . .
     G 10 . . . . . .
So now we can do A* to minimize g(x)+h(x) where "h=D+Inf"

Impact of potential fields (potentialFields.pdf) (a.k.a. infleunce maps) on a game.