Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29AI PathfindingAI PathfindingChristopher ZoncaChristopher Zonca04/10/200804/10/2008OverviewOverviewWhat is AI pathfinding?What is AI pathfinding?Why is it important?Why is it important?Possible solutionsPossible solutionsA* SearchA* SearchApplicationsApplicationsSpeeding it upSpeeding it upConclusionsConclusionsWhat is Pathfinding?What is Pathfinding?Getting from point A to point BGetting from point A to point BWhat is Pathfinding?What is Pathfinding?Must be fast!Must be fast!Must give optimal (or near optimal) Must give optimal (or near optimal) solutionssolutionsWhy is this important?Why is this important?Have you ever played a game with Have you ever played a game with frustrating pathfinding? frustrating pathfinding?Why is this important?Why is this important?Many games need good pathfindingMany games need good pathfindingThis is difficult!This is difficult!Possible SolutionsPossible SolutionsBest-First Search (BFS)Best-First Search (BFS)Greedy algorithmGreedy algorithmUses what's known as a heuristicUses what's known as a heuristicMore on heuristics laterMore on heuristics laterFast, but not optimalFast, but not optimalPossible SolutionsPossible SolutionsDijkstra'sDijkstra'sDynamic programming solutionDynamic programming solutionNot as fast as BFS but finds optimal Not as fast as BFS but finds optimal solutionsolutionUseful when we don’t know where Useful when we don’t know where we’re goingwe’re goingPossible SolutionsPossible SolutionsA* SearchA* SearchCombines the best of BFS and Combines the best of BFS and Dijkstra'sDijkstra'sVery similar to Dijkstra's but uses a Very similar to Dijkstra's but uses a heuristic to guide the searchheuristic to guide the searchVery fast and multi-purpose algorithmVery fast and multi-purpose algorithmMore on heuristicsMore on heuristicsIn this context, it's a guessIn this context, it's a guessReturns the estimated distance Returns the estimated distance between the inputted node and the between the inputted node and the destinationdestinationCommon methods: Common methods: Manhattan Distance Manhattan Distance Euclidean DistanceEuclidean DistanceEuclidean Distance SquaredEuclidean Distance SquaredMore on A*More on A*Generally considered an industry Generally considered an industry standardstandardMany games use A* for pathfindingMany games use A* for pathfindingData Structure of A*Data Structure of A*Create nodes throughout the search spaceCreate nodes throughout the search spaceWe will look at the example of a 2D gridWe will look at the example of a 2D gridCan be adapted to work in 3D environmentsCan be adapted to work in 3D environmentsEach node has three fields:Each node has three fields:A value that we will calculate as we visit the A value that we will calculate as we visit the nodesnodesThe distance to the start nodeThe distance to the start nodeA parent which is used to reconstruct the final A parent which is used to reconstruct the final pathpathCreate a priority queue, initialized to Create a priority queue, initialized to contain the starting nodecontain the starting nodeSorted by the node's f-valueSorted by the node's f-valueAlgorithm of A*Algorithm of A*Remove the first item of the queue Remove the first item of the queue Calculate the f-value for all adjacent nodesCalculate the f-value for all adjacent nodesf(n) = g(n) + h(n)f(n) = g(n) + h(n)g(n) is the shortest distance from that node to g(n) is the shortest distance from that node to the startthe starth(n) is the result of the heuristic explained h(n) is the result of the heuristic explained earlierearlierIf this f-value is less than its current f-value, If this f-value is less than its current f-value, replace it and set its parent to the current nodereplace it and set its parent to the current nodeAdd all unvisited neighboring nodes to the Add all unvisited neighboring nodes to the queuequeueRepeat until the destination node is selectedRepeat until the destination node is selectedDemonstrationDemonstrationQuirks of A*Quirks of A*|h(n) – h*(n)| |h(n) – h*(n)| << log(h*(n)) log(h*(n))If this is true, polynomial time is guaranteedIf this is true, polynomial time is guaranteedIf this is false, exponential time is possibleIf this is false, exponential time is possibleIf h(n) – h*(n) = 0, linear time!If h(n) – h*(n) = 0, linear time!Heuristic is admissible if it is always Heuristic is admissible if it is always smaller than the actual distancesmaller than the actual distanceIf it's too high, A* becomes BFSIf it's too high, A* becomes BFSIf its too low, A* becomes Dijkstra'sIf its too low, A* becomes Dijkstra'sAdapting to game worldAdapting to game worldSome games lend themselves easily Some games lend themselves easily to these kinds of algorithmsto these kinds of algorithmsAdapting to game worldAdapting to game worldMost environments can be adaptedMost environments can be adaptedCreate graph of nodes and apply Create graph of nodes and apply algorithmalgorithmBe sure to account for obstacles if Be sure to account for obstacles if dynamic node creation is useddynamic node creation is used=>SpeedSpeedPathfinding in general is slowPathfinding in general is slowLarge time and space complexitiesLarge time and space complexities=>Possible SolutionsPossible SolutionsMany techniques are usedMany techniques are usedUse a high heuristicUse a high heuristicUseful when we don't need Useful when we don't need exactexactHanswers, just good ones (although Hanswers, just good ones (although this isn't guaranteed)this isn't guaranteed)=>Possible SolutionsPossible SolutionsUse a tie-breaking schemaUse a tie-breaking schemaPrefer points near the destination nodePrefer points near the destination nodeTurns into...Much better!Much better!More SolutionsMore SolutionsAdd a processing queueAdd a processing queueWhen a unit needs a path, use a quick When a unit needs a path, use a quick algorithm (like BFS) to find onealgorithm (like BFS) to find oneAdd it to a low priority processing Add it to a low priority processing queuequeueWhen it's its turn,
View Full Document
Unlocking...