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, rulebased systems, goalbased 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)
• BreadthFirst, DepthFirst, 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 BestFirst, 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