Skip to content

gebakx/mv-games

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

14 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

class: center, middle

Artificial Intelligence

Movement &
Pathfinding in Games


Gerard Escudero, 2020


:scale 40%

.center[.small[Source: Birds of a Feather Flock]]


class: left, middle, inverse

Outline

  • .cyan[Introduction]

  • NavMesh

  • Steerings

  • Flocking

  • Graphs

  • Pathfinding

  • References


Movement

.center[:scale 75%]

.blue[It is the lowest AI level.]


Hierarchy of movement behaviors

.center[:scale 65%] .center[.small[Source: .red[(Reynolds, 1999)]]]

Steering

  • Composed by .blue[simple atomic behaviors]

  • They can be .blue[combined] to behave very complex


Kinematic

  • Simplest behaviors (.blue[static])

  • Characters as points (.blue[center of mass])

  • .blue[$2\frac{1}{2}D$]: hybrid 2D & 3D to simplify maths

.cols5050[ .col1[ .blue[Input]

  • $position$ (vector)

  • $orientation$ (float) ]

.col2[ .blue[Output]

  • $velocity$ (vector)

  • $angular$ (float)

]]

$$position = position + velocity$$

$$orientation = orientation + angle$$


Kinematic Seek & Flee

It calculates the direction from the agent to the target.

.cols5050[ .col1[ .blue[Input]:

  • agent(position, orientation)
  • target(position)
  • maxVelocity, maxRotation

.blue[Output]:

  • velocity
  • angle

.blue[Examples]:

.small[Source: .red[(Reynolds, 1999)]] ]]


Kinematic in Unity

.blue[direction]: vector from robber to treasure $$d=(t_x-r_x, 0, t_z-r_z)$$

// Seek
Vector3 direction = target.transform.position - transform.position;
direction.y = 0f;    // (x, z): position in the floor
// Flee
Vector3 direction = transform.position - target.transform.position;

.blue[velocity]: vector direction with magnitude maxVelocity $$\vert d\vert=\sqrt{d_x^2+d_z^2};v=\frac{d}{\vert d\vert}maxVelocity$$

Vector3 movement = direction.normalized * maxVelocity;

.blue[rotation]:

float angle = Mathf.Rad2Deg * Mathf.Atan2(movement.x, movement.z);
Quaternion rotation = Quaternion.AngleAxis(angle, Vector3.up);  // up = y

Update and Time in Unity

.blue[Update]: rotation and position (dt = Time.deltaTime)

transform.rotation = Quaternion.Slerp(transform.rotation, rotation, 
                                      Time.deltaTime * turnSpeed);
transform.position += transform.forward.normalized * maxVelocity * Time.deltaTime;

.blue[Time]: how to reduce frequency in steerings calls

    float freq = 0f;
       
    void Update()
    {
        freq += Time.deltaTime;
        if (freq > 0.5)
        {
            freq -= 0.5f;
            Seek(); 
        }
        // Update commands
    }

Math & Unity Stuff I

.blue[distance]: between points $$d(v,w)=\sqrt{(w_x-v_x)^2+(w_z-v_z)^2}$$

Vector3.Distance(target.transform.position, transform.position)

Needed as .blue[stoping criteria] to avoid wiggle in .blue[seek].

.blue[angle]: between 2 vectors

Mathf.Abs(Vector3.Angle(transform.forward, movement)  // forward = z

dot product: $\langle v,w\rangle=v_x\cdot w_x+v_y\cdot w_y$

$$\theta=\arccos{\frac{\langle v,w\rangle}{\vert v\vert \vert w\vert}}$$


Math & Unity Stuff II

.blue[signed angle]:

Vector3.SignedAngle(v, w, transform.forward)

based on cross product:

$$v\times w=(v_y\cdot w_z-v_z\cdot w_y,v_z\cdot w_x-v_x\cdot v_z,v_x\cdot w_y-v_y\cdot w_x)$$

.cols5050[ .col1[

  • Clockwise: $(v\times w).z<0$

  • Anti-clockwise: $(v\times w).z<0$ ] .col2[ :scale 40%

.small[Source: .red[wikipedia]] ]]


Steerings

  • Kinematic .blue[drawback]: it is not very realistic

  • Steering (Dynamic): by adding acceleration

Seek

.cols5050[ .col1[ .blue[Input]:

  • agent(position, orientation)
  • target(position)
  • maxVelocity, maxRotation
  • acceleration, turnAcceleration

.blue[Output]:


Steering Update

void Update()
{
    if (Vector3.Distance(target.transform.position, transform.position) <
        stopDistance) return;

    Seek();   // calls to this function should be reduced

    turnSpeed += turnAcceleration * Time.deltaTime;
    turnSpeed = Mathf.Min(turnSpeed, maxTurnSpeed);
    movSpeed += acceleration * Time.deltaTime;
    movSpeed = Mathf.Min(movSpeed, maxSpeed);

    transform.rotation = Quaternion.Slerp(transform.rotation, 
                                          rotation, Time.deltaTime * turnSpeed);
    transform.position += transform.forward.normalized * movSpeed *
                          Time.deltaTime;   
}

Steering Seek

void Seek()
{
    Vector3 direction = target.transform.position - transform.position;
    direction.y = 0f;
    movement = direction.normalized * acceleration;
    float angle = Mathf.Rad2Deg * Mathf.Atan2(movement.x, movement.z);
    rotation = Quaternion.AngleAxis(angle, Vector3.up);
}

Arriving

A chasing agent should never reach its goal when seeking.

  • .blue[Stopping distance]

  • .blue[Steering Arrive]

$$speed=\frac{maxSpeed\times distance}{slowRadius}$$

.small[.center[max acceleration should be controlled]]

.blue[Example]:


class: left, middle, inverse

Outline

  • .brown[Introduction]

  • .cyan[NavMesh]

  • Steerings

  • Flocking

  • Graphs

  • Pathfinding

  • References


Recast

.center[:scale 75%]

  • Used by all major engines (state of the art)

  • Also some proprietary engine (Horizon Zero Dawn)


Navigation Mesh

.center[:scale 65%] .center[Recast in Unity (documentation & source)]

.cols5050[ .col1[ .blue[NavMesh]: polygon set representing walkable surfaces

.blue[NavMeshAgent]: navigation component ] .col2[ .blue[OffMeshLink]: navigation shortcuts

.blue[NavMeshObstacle]: dynamic obstacle ]]


NavMesh

.cols5050[ .col1[ .blue[Creating the NavMesh]:

  • Open Window - AI - Navigation

  • Select scene objectes as:

    • Static
    • Walkable or Not Walkable
  • Click Bake tab - Bake button

Bake again as you need

Main properties:

  • Agent Radius & Height

  • Max Slope & Step Height ] .col2[ :scale 75%

:scale 90% ]]


NavMesh Agent I

Inner Workings of the Navigation System:

  1. Find Paths
  2. Follow the Path
  3. Avoid Obstacles
  4. Move the Agent (Steerings)

.center[:scale 90%]


NavMesh Agent II

.blue[Using the NavMesh]:

  • Add the NavMesh Agent component to the agent

  • Code:

    public NavMeshAgent agent;
    public GameObject target;

    void Seek()
    {
        agent.destination = target.transform.position; 
    };

Main property groups:

  • Steering: Speed, Stopping Distance, Auto Braking...

  • Object Avoidance: Radius...

  • Path Finding: Auto Traverse Off Mesh Links...


NavMesh Obstacle

.blue[Creating a dynamic obstable]:

  • Add the NavMesh Obstacle component to the object

  • Add the RigidBody component to the object (being kinematic)

Main property:

  • Carve: creates a hole in the NavMesh

:scale 95% .center[.small[Source & documentation]]


Off-Mesh Link I

.blue[Creating an Off-mesh Link]:

  • Add the Off Mesh Link component to one of the two objects

.center[:scale 90%] .center[.small[Source & documentation]]


Off-Mesh Link II

.blue[Building Off-mesh Links]:

  • Tic the Generate OffMeshLinks at Navigation - Object

.center[:scale 45%] .center[.small[Source & documentation]]

  • Bake again

Main properties:

  • Drop Height & Jump Distance

Navigation Areas and Costs

.blue[Navigation Areas] define how difficult it is to walk across a specific area.

.center[:scale 85%] .center[.small[Source & documentation]]


Navigation System

A* searh algorithm

  • NavMeshAgent.SetDestination: possible not available at next frame

  • NavMeshAgent.pathPending

NavMeshPath

  • Data structure: path as a list of waypoints

  • NavMeshAgent.path: documentation

Advanced NavMesh


class: left, middle, inverse

Outline

  • .brown[Introduction]

  • .brown[NavMesh]

  • .cyan[Steerings]

  • Combination (flocking)

  • Pathfinding

  • References


Wander

.cols5050[ .col1[

.blue[Simple implementation]: .small[

void Wander()
{
    float radius = 2f;
    float offset = 3f;

    Vector3 localTarget = new Vector3(
        Random.Range(-1.0f, 1.0f), 0, 
        Random.Range(-1.0f, 1.0f));
    localTarget.Normalize();
    localTarget *= radius;
    localTarget += new Vector3(0, 0, offset);

    Vector3 worldTarget = 
        transform.TransformPoint(localTarget);
    worldTarget.y = 0f;

    Seek(worldTarget);
}

Example ] ] .col2[ :scale 95% .center[.small[.red[(Millington, 2019)]]]

.blue[Issues]:

  • How often calling wander?
  • What happens in the limit?
  • Remember Auto Brake & Stopping Distance ]]

Pursue & Evade

.blue[Simple implementation]:

Vector3 targetDir = target.transform.position - transform.position;
float lookAhead = targetDir.magnitude / agent.speed;
Seek(target.transform.position + target.transform.forward * lookAhead);

// Flee for evasion

.cols5050[ .col1[ .blue[Examples]:


Hide (Previous C# Stuff)

Example

.blue[Defining Hiding Spots]:

GameObject[] hidingSpots;
...
hidingSpots = GameObject.FindGameObjectsWithTag("hide");

.cols5050[ .col1[ .blue[Anonymous Functions]:

Func<int, int> inc = (a) => a + 1;

inc(4)) 👉 5

.blue[Tuples]:

(int, string) a = (1, "Pep");
(int, string) b = (2, "Anna");

a.CompareTo(b) 👉 -1

] .col2[ .blue[Linq Select] (Queries):

int[] v = { 3, 2, -3, 5 };

v.Min() 👉 -3

v.Select((x) => Math.Abs(x)).Min() 👉 2 ]]


Hide

.blue[Simple implementation]:

    void Hide()
    {
        Func<GameObject, float> distance = 
            (hs) => Vector3.Distance(target.transform.position, 
                                     hs.transform.position);
        GameObject hidingSpot = hidingSpots.Select(
            ho => (distance(ho), ho)
            ).Min().Item2;

        Vector3 dir = hidingSpot.transform.position - target.transform.position;
        Ray backRay = new Ray(hidingSpot.transform.position, -dir.normalized);
        RaycastHit info;
        hidingSpot.GetComponent<Collider>().Raycast(backRay, out info, 50f);   

        Seek(info.point + dir.normalized);     
    }

Follow Path

.blue[Patrol with Waypoints]:

public GameObject[] waypoints;
int patrolWP = 0;
...
if (!agent.pathPending && agent.remainingDistance < 0.5f) Patrol();
...
void Patrol()
{
    patrolWP = (patrolWP + 1) % waypoints.Length;
    Seek(waypoints[patrolWP].transform.position);
}

Smoothing the corners

.blue[Ghost Following]:

  • Follow a ghost agent
    Example
  • Adjust speeds (ghost waiting?)
  • Remember to disable the ghost Mesh Renderer

.cols5050[ .col1[ .blue[Path Following]:

Use .blue[Beizer Curves] to create the path.

Both contain getting closest point to the curve.

] .col2[ :scale 90% ]]


Combining Steering Behaviors

  • Previours steerings serve as building blocks for complex behaviors.

  • Combination can happen in many ways:

    • .blue[Arbitration]: switch steerings as world changes
      Example: wander & pursue

    • .blue[Blending]: sum or weighted sum
      Example: flocking (separation + align + cohesion)
      Problem: .red[components cancelling]

    • .blue[Mixing arbitration and blending]

  • Advanced combinations:

    • .blue[Priority groups]: blending plus priorities
      execute highest priority steerings and ignore the rest

    • .blue[More complex structures]: Cooperative Arbitration

  • Combinations need to be carefully adjusted.


Steering Stuff

  • There are many more movements (see references):
    Example: .blue[Obstacle and Wall Avoidance]

.center[:scale 30%] .center[.small[Source]]

  • Reynolds OpenSteer
    C++ library to help construct steering behaviors for autonomous characters in games and animation

class: left, middle, inverse

Outline

  • .brown[Introduction]

  • .brown[NavMesh]

  • .brown[Steerings]

  • .cyan[Flocking]

  • Graphs

  • Pathfinding

  • References


Flocking

.cols5050[ .col1[ Groupal behavior such of birds or fishes.

.blue[Sum of three simple rules]:

  • Cohesion: neighbour center of mass
  • Match velocity/align: average neighbours heading
  • Separation: avoid crowding neighbours ] .col2[ :scale 90% .small[Source: Birds of a Feather Flock]

Example Video ]]

.center[:scale 25% :scale 25% :scale 25%
source]


Flocking Settings

.blue[Flocking Manager]:

.center[:scale 45%]

allFish = new GameObject[numFish];
for (int i = 0; i < numFish; ++i) {
    Vector3 pos = this.transform.position + ... // random position
    Vector3 randomize = ... // random vector direction
    allFish[i] = (GameObject)Instantiate(fishPrefab, pos, 
                                Quaternion.LookRotation(randomize));
    allFish[i].GetComponent<Flock>().myManager = this;
}

Flocking Rules I

.blue[Cohesion]:

Vector3 cohesion = Vector3.zero;
int num = 0;

foreach (GameObject go in myManager.allFish) {
    if (go != this.gameObject) {
        float distance = Vector3.Distance(go.transform.position, 
                                          transform.position);
        if (distance <= myManager.neighbourDistance) {
            cohesion += go.transform.position;
            num++;
        }
    }
}

if (num > 0)
    cohesion = (cohesion / num - transform.position).normalized * speed;

Flocking Rules II

.blue[Match velocity/align]:

Vector3 align = Vector3.zero;
int num = 0;

foreach (GameObject go in myManager.allFish) {
    if (go != this.gameObject) {
        float distance = Vector3.Distance(go.transform.position, 
                                          transform.position);
        if (distance <= myManager.neighbourDistance) {
            align += go.GetComponent<Flock>().direction;
            num++;
        }
    }
}

if (num > 0) {
    align /= num;
    speed = Mathf.Clamp(align.magnitude, myManager.minSpeed, myManager.maxSpeed);
}

Flocking Rules III

.blue[Separation]:

Vector3 separation = Vector3.zero;

foreach (GameObject go in myManager.allFish) {
    if (go != this.gameObject) {
        float distance = Vector3.Distance(go.transform.position, 
                                          transform.position);
        if (distance <= myManager.neighbourDistance)
            separation -= (transform.position - go.transform.position) / 
                          (distance * distance);
    }
}

More Flocking Stuff

.blue[Combination]:

direction = (cohesion + align + separation).normalized * speed;
  • Three rules + combination should be placed in the same foreach.

.blue[Update]:

transform.rotation = Quaternion.Slerp(transform.rotation,
                                      Quaternion.LookRotation(direction),
                                      myManager.rotationSpeed * Time.deltaTime);
transform.Translate(0.0f, 0.0f, Time.deltaTime * speed);

.blue[Final notes]:

  • Rules should not be calculated every frame.

  • Some random issues enriches the behaviour.

  • Introduction of a lider is a common extension.


class: left, middle, inverse

Outline

  • .brown[Introduction]

  • .brown[NavMesh]

  • .brown[Steerings]

  • .brown[Flocking]

  • .cyan[Graphs]

  • Pathfinding

  • References


Graphs

.cols5050[ .col1[ :scale 80%.red[*]

:scale 60%.red[*] ] .col2[ .blue[Math definition]:

$G=(V,E)$

$V=\textrm{set of vertices}$

$E=\textrm{set of edges}$

.blue[Example]:

$V=${$v_1,v_2,v_3$}

$E=${$(v_1,v_2),(v_1,v_3),(v_2,v_3)$}

]]

  • .blue[Edges] can be .blue[directed] (one way) or .blue[undirected] (two ways).

  • Both vertices and edges can contain information.

.footnote[.red[*] Source]


Representation as graphs

.center[ :scale 40% :scale 40%
.red[source]]

.cols5050[ .col1[ .center[:scale 80%
.red[Source]] ] .col2[ .center[:scale 90%
.red[Source]] ]]


Some Applications in GameAI

.cols5050[ .col1[ .blue[Pathfinding]:

.center[:scale 70%
.red[Source]]

.blue[Decision making]: planners

.center[:scale 80%
.red[Source]] ] .col2[

.blue[Tactics]: influence maps

.center[:scale 90%
.red[Source]] ]]


Shortest Path Problem

.cols5050[ .col1[ Find the minimum (sum of edges costs) path between two vertices.

Main Algorithms:

  • .blue[Dijkstra]: general cases
  • .blue[A*]: requires an heuristic $h$ (estimation cost function) ] .col2[ .center[ :scale 70%
    Source] ]]

.center[ :scale 30% :scale 30%
Source]


Dijkstra

.cols5050[ .col1[ .blue[Pseudocode]: :scale 110% Source

.blue[C# implementation]: view / code ] .col2[ .center[ :scale 90% Source] ]]


A*

.cols5050[ .col1[ .blue[Pseudocode]: :scale 110% Source

.blue[C# implementation]: view / code ] .col2[ .center[ :scale 90% Source] ]]

Dijkstra is A* when $h(x)=0,\forall x$.

class: left, middle, inverse

Outline

  • .brown[Introduction]

  • .brown[NavMesh]

  • .brown[Steerings]

  • .brown[Flocking]

  • .brown[Graphs]

  • .cyan[Pathfinding]

  • References


Pathfinding

Components:

  • .blue[World Representation] as .blue[graphs]

    • Vertices: convex surfaces
      no line segment between two inner points goes outside the surface

    • Edges: connect vertices with cost

  • .blue[A*] algorithm:

    • choosing a .blue[heuristic]
  • .blue[Path Smoothing]

    • algorithm

World Representation

.cols5050[ .col1[ .blue[Tile Graphs]: .small[World splitted in regular tiles (squares, hexagons...)]

:scale 75%
Source

.blue[Points of Visibility]:

:scale 60%
Source

] .col2[ .blue[Dirichlet Domains]: .small[Regions defined (manually) by a set points]

:scale 80%
Source

.blue[Navigation Meshes]: :scale 95% ]]


Heuristics

.blue[Properties]:

  • .red[Underestimating]: heuristic too slow.
    The more accurate the faster A* runs.

  • .red[Overestimating]: heuristic too high.
    A* my not return the best path.

  • .red[Admissible]: if an heuristic $h(n)$ is lower than the true cost for all the nodes, A* is optimal.

.blue[Some common heuristics]:

  • .red[Euclidean distance]
    In presence of lot of walls and corridor (indoor levels) it takes longer to run.

  • .red[Cluster Heuristic]: grouping graph vertices together in clusters.
    Every room becomes a cluster. Automatic or provided by de level designer.


Path Smoothing

.cols5050[ .col1[ .blue[Simple Smoothing]:

:scale 100% ] .col2[ .blue[Bézier curve based smooth path]: .center[ :scale 90% Source] ]]


Hierarchical Pathfinding

.blue[Main idea]:

  • Clustering: group nodes to build a higher level graph

  • Connection costs:
    minimum, maximum or average distances

  • Pathfinding:

    • Apply pathfinding on higher level graph
    • For each cluster in resulting path apply pathfinding

.blue[Example]: .center[ :scale 100% Hierarchical Path-Finding for Navigation Meshes]


Other A* Variations

  • .blue[Open Goal Pathfinding]: many possible goals.
    Example: alarms

  • .blue[Dynamic Pathfinding] (D*): changing evironment (allows backtracking) Example: change the route to avoid detection

  • .blue[Low Memory Algorithms]:

    • IDA*: no lists
    • SMA*: fixed size open list
  • .blue[Pooling Planners]: queue of pathfinders.
    Example: MMORG

  • .blue[Continuous Time Pathfinding]: task changes quickly (JPS+)
    Example: Racing Games


class: left, middle, inverse

Outline

  • .brown[Introduction]

  • .brown[NavMesh]

  • .brown[Steerings]

  • .brown[Flocking]

  • .brown[Graphs]

  • .brown[Pathfinding]

  • .cyan[References]


References

Libraries


Resources

.blue[Examples]:

.blue[Bezier Curves]:

.blue[Image]

About

No description, website, or topics provided.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published