2.7 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, 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

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 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.

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" 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.

And for crowds to walk paths, add obstacle avoidance.

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 (a.k.a. infleunce maps) on a game.

This document was generated on March 1, 2011 using texi2html 5.0.