Pathfinding

Course: CS380

Instructor: Steve Rabin

Type: Solo project

Language: C++

Overview

This subject introduces me to a wide range of concepts and practical algorithms that are commonly used to solve game AI problems. Case studies from real games are used to illustrate the concepts. It have a chance to work with and implement core game AI algorithms. Topics include the game AI programmer mindset, AI architecture (state machines, behavior trees, rule-based systems, goal-based systems, utility, trigger systems, smart terrain, scripting, message passing, and debugging AI), movement, pathfinding, emergent behavior, agent awareness, agent cooperation, terrain analysis, planning, and learning/adaptation

A Star (A*)

Completeness

Heuristic Search

Admissible heuristic = Optimal path

  • Rubber banding and Smoothing post processing to improve the path the agent will follow.

  • Variable weight for the cost of each node.

  • Multiple heuristic computation functions: Euclidean, Octile, Chebyshev and Manhattan.

  • Ability to divide the algorithm computation among multiple frames(visible in the videos).

Recap of Search Algorithms

Guarantee a path is found if it exists (completeness)

     •  Breadth-First, Depth-First, Dijkstra, A* and all variants

Guarantee an optimal path

     • Dijkstra, A* and all variants (if admissible heuristic)

Heuristic search algorithms (smart, head toward goal)

     • Greedy Best-First, A* and all variants

Search

A* Algorithm (Pseudo Code)

Push Start Node onto the Open List

While (Open List is not empty) {

      Pop cheapest node off Open List (parent node)

      If node is the Goal Node, then path found (RETURN “found”)

      For (all neighboring child nodes) {

           Compute its cost, f(x) = g(x) + h(x)

           If child node isn’t on Open or Closed list, put it on Open List.

           If child node is on Open or Closed List, AND this new one is cheaper,

                 then take the old expensive one off both lists and put this new cheaper one on                      the Open List.

}

Place parent node on the Closed List (we’re done with it)

If taken too much time this frame (or in single step mode),

      abort search for now and resume next frame (RETURN “working”)

}

Open List empty, thus no path possible (RETURN “fail”)

Grid Heuristic Calculations

Manhattan distance

xDiff + yDiif = 9+3 = 12

Chebyshev distance

max(xDiff, yDiff) = max(9,3) = 9

Euclidean distance

sqrt(xDiff2 + yDiff2 ) = sqrt(92 + 32 ) = 9.48

Octile distance

min(xDiff, yDiff) * sqrt(2) + max(xDiff, yDiff) – min(xDiff, yDiff) min(9, 3) * 1.41 + max(9, 3) – min(9, 3) = 10.24

© 2020 By Wonjae Jung