8.2. PATHFINDING Pathfinding algorithms Execution ExecutionManagement Management SSt rt ar at t eeggy y W W orl orl d d Int Int erf erf ac ac e e MMoov v eem m ee nnt t Animation

Animation Physics Physics PATHFINDING ALGORITHMS Introduction and forms of navigation mesh ... ... Path finding Pathfinding is the process of finding a path from a specified source position to a specified target position. To do this some means of defining the search space is needed alongside an algorithm which will plan a walk from source to target. The most common search space representations are: Grids Waypoint graphs Navigation meshes Aside: The search space represents traversal routes in the game world (usually ignoring small and/or moving objects which can be handled by steering behaviours). Navigation(tile based)

Intuitive representation - works well for many games (e.g. tile-based realtime/turn-based strategy or role playing). Each node represents the centre of a cell, with the edges denoting connections between cells. Each cell can be flagged as passable/impassable and/or given a terrain movement cost (e.g. forest, swamp, etc.). Large objects may occupy one or more cells. Advantages: Fast look-up Navigation (waypoint graph) A waypoint graph defines straight routes between waypoints. Advantages: Nodes can be connected to any number of other waypoint nodes Waypoint graphs can easily represent arbitrary level topologies and are excellent for games with restricted movement, e.g. Pacman Can incorporate auxiliary information, e.g. ladders Note: Typically provide an

Navigation (navigation mesh) Combination of grids and waypoint graphs. Every node of a navigation mesh represents a convex polygon (as opposed to a single position). Advantages: Convex as any two points inside can be connected without crossing an edge of the polygon Navigation mesh can be thought of as a walkable surface Complete representation of the level Navigation (navigation mesh) Advantages (continued): Can be used to tie pathfinding and collision detection together Can easily be used for 2D and 3D games Execution ExecutionManagement Management

SSt rt ar at t eeggy y W W orl orl d d Int Int erf erf ac ac e e MMoov v eem m ee nnt t Animation Animation Physics Physics PATHFINDING ALGORITHMS Forms of pathfinding algorithm

... ... Pathfinding algorithms A path is a list of cells, points, or nodes that an agent must traverse. A pathfinding algorithm finds a path from a start position to a goal position. An algorithm that guarantees to find a path if one exists is a complete algorithm. The pathfinding algorithm can be assessed in terms of: Quality of final path Resource consumption during search (i.e. CPU and Basic algorithms (seek + random obstacle avoidance ) Seek combined with random movement when a direct seek cannot be executed is a simple and sometimes workable method of obstacle avoidance (particularly within environments with

relatively small and sparse obstacles) while( Goal not reached ) { Move straight towards goal if( blocked ) { Move (sidestep) in random direction } } Basic algorithms (seek + obstacle tracing) Another simple approach of obstacle avoidance is to trace around the obstacle (useful for large objects that can be circumnavigated). Tracing continues until a path straight towards the target can be obtained. while( Goal not reached ) { Move directly towards goal if( Obstacle in way ) { Trace around in (counter) clockwise direction until path towards goal.

} } How will the previous algorithms handle the following environments: Basic algorithms (breadcrumb trace) Each time some target objects moves it leaves behind a breadcrumb marker (an invisible marker recording the location of the object). The source object can follow the breadcrumbs to the target. Aside: Breadcrumb traces can be used to provide tracking in games, where opponents can home in on a target once their path is picked Producing a better path In order to provide a better algorithm (and one that actually produces a movement plan) we will consider the following types of algorithm: Breadth-First, Best-First, Dijkstra and A* These algorithms use linked lists of nodes to

represent candidate paths. They all use: An open list A closed list The open list tracks promising nodes. A node is taken from the open list and used to create additional open nodes (which are added to the open list). The initial node taken from the open list is then added to the closed Producing a better path (common structure) Create start point node and push onto open list 1 2 while( open list is not empty ) { Pop node from open list call this currentNode if( currentNode == goalNode ) { Goal found } else { Create successor nodes for cells around currentNode and push them onto open list Put currentNode onto closed list

} } Questions: What node should be popped from open list? Which successor nodes should be created? 3 4 5 6 7 End Start Open list: { (1,3), (2,3), (3,3), (1,4), Open list: { (2,4) } } (3,4), (1,5), (2,5), Closed list: { ) (3,5) } Closed list: { (2,4) ) Producing a better path (Breath Finds

a path from the first search) start to the goal by examining the search space ply-by-ply Which node is popped? Node that been waiting the longest Which successor nodes are added? Every point around the currentNode that is not impassable or already created End Start Breath first search Exhaustive search (systematic, but not clever) Consumes substantial amount of CPU and memory Guarantees to find paths that have

fewest number of nodes in them (not necessarily the shortest distance!) Complete algorithm Producing a better path (Best first search) Uses problem specific Which node is popped? knowledge to speed up the search process, i.e. is a heuristic search Computes the distance of every node to the goal Uses the distance (or heuristic cost) as a priority value to determine the next node that should be brought out of the open list Open node that is closest to the goal Which successor nodes are added? Every point around the currentNode that is not impassable or already created

Producing a better path (Best first Which node is popped? search) Open node that is closest to the goal using Euclidean distance Which successor nodes are added? Every point around the currentNode that is not impassable or already created Uses fewer resources than Breadth-First Tends to find good paths Complete algorithm End Start Producing a better path (Best first search) Not guaranteed to find most optimal path differen t

Producing a better path (Dijkstra Disregards distance to goal search) Keeps track of the cost of every path i.e. computes accumulated cost paid to reach a node from the start Uses the cost (called the given cost) as a priority value to determine the next node that should be brought out of the open list Which node is popped? Open node that is attached to path with lowest cost Which successor nodes are added? Every point around the currentNode that is not impassable or already created. differen t Producing a better path (Dijkstra

search) Which node is popped? Open node that is attached to path with lowest cost Which successor nodes are added? Every point around the currentNode that is not impassable or already created. Exhaustive search At least as resource intensive as BreadthFirst Always finds the most optimal path Complete algorithm 3 3 3 3 4 5

2 2 2 3 4 5 6 1 1 4 5 6End End 1 Start 1

1 1 2 2 2 1 5 6 5 2 3 4 5 Producing a better path (A* Which node is popped? Algorithm) Combination of best-first Open node that is attached and Dijkstra searches.

Uses both heuristic cost and given cost to order the open list Start End Given cost = measured cost to reach node Heuristic cost = estimate of cost to end node to path with lowest cost Which successor nodes are added? Every point around the currentNode that is not impassable or already created. If needed, update path/cost to a node if lower cost path found Path Cost = Given Cost + (Heuristic Cost * Heuristic Weight) Producing a better path (A* Which node is popped? Algorithm) 7

Open node that is attached to path with lowest cost Which successor nodes are added? Every point around the currentNode that is not impassable or already created. If needed, update path/cost to a node if lower cost path found Path Cost = Given Cost + (Heuristic Cost * Heuristic Weight) 8 7 6 7 6 7 5 5 Start 7

6 5 7 6 6 6 7 6 6 7 6 6 6 End 7 5 6

7 On average, uses fewer resources than Dijkstra and Breadth-First Admissible heuristic (i.e. never overestimated true cost) guarantees it will find the most optimal path while( open list is not empty ) Lowest Lowest cost cost based based on on { known known added added with with heuristic heuristic Pop node with lowest cost andcost assign to currentNode cost if( currentNode == endNode ) { Goal found; Break } The The navigation navigation graph graph will will be be queried

else { queried to to return return possible possible linkage linkage for( every node connected to currentNode ) { Create successorNode (cost = givenCost(startNodesuccessorNode) + heuristicCost (successorNodeendNode, parent = currentNode ) A* Algorithm Create startNode and push onto open list (cost = heuristicCost(startNodeendNode) The The parent parent node node isis stored stored to to permit permit backtracking backtracking if( successorNode has been visited before ) if( successorNode has a lower cost than the current stored node) { Replace the old node with successorNode (a better path was found) } else { Ignore this successorNode ) } Both Both the the open open and

and closed closed lists lists else will Add will need need to to be be searched searched to to Add the the unvisited unvisited node node to to the the open open list list check Push the successorNode onto the open list check for for already already visited visited nodes nodes } Push the currentNode onto the closed list }

Backtrack from currentNode through parent nodes and invert to return path A* - Different types of heuristic Underestimating Heuristics A heuristic that underestimates the distance will result in a larger search space (i.e. longer execution time). A heuristic that always underestimates (or gets it right) is guaranteed to return the best possible path. Overestimating Heuristics A heuristic that overestimates the distance will tend to produce paths with fewer nodes (i.e. moving towards the goal faster, but potentially missing the best route, Euclidean Distance (i.e. distance as the crow flies) is a common heuristic that is guaranteed to never overestimate. In outdoor settings, Euclidean distance can offer a very good heuristic. In indoor settings, with lots of walls and doors, it can

drastically underestimate the distance resulting in a much larger search Hierarchical pathfinding Hierarchical pathfinding plans a route in much the same way a person would, i.e. a high-level route is planned, and then refined as needed. Hierarchical pathfinding offers a very effective means of path finding, i.e. a high-level route can be initially planned with more detailed planning deferred until needed (i.e. improved computational loading, It can be difficult to implement as the cost of each sub-journey must be, typically, heuristically estimated (i.e. issues of over- and underestimating arise). A* - Adding terrain cost

The quickest path may not be the physically shortest path unless all terrain is equally easy to traverse. A game with different types of terrain might provide movement costs that depend on the type of terrain and capabilities of the moving object. The extension to the basic A* algorithm is straightforward (although it can add some extra complexity into the heuristic cost prediction). Summary Today we explored: Path-finding graph representations. Range of path- finding approaches from simple random walks to A* planning To do: ion

t s e u Q e t le p Com Clinic o your t le b a c li p p a If athp e r lo p x e , e

gam s. m h it r o lg a g in find r u o y s d r a w o t Word als. o g t in o p

a h lp a