Slide 1Path Following at Constant SpeedPathfindingPathfinding RepresentationsAll Pairs Shortest Path (APSP)All Pairs Shortest Path (APSP)All Pairs Shortest Path (APSP)All Pairs Shortest Path (APSP)All Pairs Shortest Path (APSP)All Pairs Shortest Path (APSP)All Pairs Shortest Path (APSP)Floyd ExampleFloyd ExampleFloyd ExampleFloyd ExampleFloyd ExampleFloyd ExampleFloyd ExampleFloyd ExampleFloyd ExampleFloyd ExampleFloyd ExampleFloyd ExampleFloyd’s CodeA* pathfindingOverview of A* algorithmRunning ExampleOpen and Closed ListsWhere to go next…Computing the costComputing H using Manhattan methodContinuing the searchExampleExample continuedSome issuesMore issuesSound in gamesFinding/Making SoundsFinding/Making Sounds (cont’d)Finding/Making Sounds (cont’d)Playing Sounds in XNASimple Sound APIXNA Simple Sound APIXNA Song APIXNA Sound Effect APIDemo of Song and Sound Effect APIComputer Science – Game DesignUC Santa CruzCMPS 20: Game Design Experience2D MovementPathfindingComputer Science – Game DesignUC Santa CruzPath Following at Constant Speed•In previous lecture showed path following–Used Lerp and CatmullRom interpolation methods built into Vector2 class–These methods take an amount•A number between 0 and 1 indicating the percentage distance between the start and end points (a “weight”)•Problem–A given amount can result in different perceived speeds, depending on the length of the line•Solution–Given a desired speed in terms of units per clock tick–Compute per-tick change in amount as follows–Per-tick-amount = unit-speed / Vector2.Distance(start, end)•That is, determine the percentage of the total distance between the points covered by one unit-speedComputer Science – Game DesignUC Santa CruzPathfinding•In many games, computer controlled opponents need to move from one place to another in the game world–If the start and end points are known in advance, and never change, •Can simply define a fixed path•Computed before the game begins•Use path following techniques from previous lecture•Most platformers do this–If the start and end points vary, and are not known in advance (or may vary due to changes in game state), •Have to compute the path to follow while the game is running•Need to use a pathfinding algorithmVideo of pathfinding problemsPathfinding Article: http://www.ai-blog.net/archives/000152.htmlComputer Science – Game DesignUC Santa CruzPathfinding Representations•Waypoints•Navigation MeshesComputer Science – Game DesignUC Santa CruzAll Pairs Shortest Path (APSP)•Assume a labeled directed graph–Nodes are pathnodes in your map–Labels are the distances between connecting nodes (or other specific cost information)•G=(V, E) in which each arc v → w has a non-negative cost C[v,w].•Find, for each ordered pair (v,w) the smallest length of any path from v to w.Computer Science – Game DesignUC Santa CruzAll Pairs Shortest Path (APSP)Floyd’s Algorithm•Assume the vertices in V are numbered 1,...,n.•Use an n X n matrix in which to compute the lengths of the shortest paths.Computer Science – Game DesignUC Santa CruzAll Pairs Shortest Path (APSP)Floyd’s Algorithm•Set A[i,j] = C[i,j] for all i not equal to j. •If there is no arc from i to j, then assume C[i,j] = ∞.•Each diagonal element is set to 0.Computer Science – Game DesignUC Santa CruzAll Pairs Shortest Path (APSP)Floyd’s Algorithm•Make n iterations over the matrix•On the kth iteration, A[i,j] will have for its value the smallest length of any path from i to j that doesn’t pass through a vertex numbered higher than k.Computer Science – Game DesignUC Santa CruzAll Pairs Shortest Path (APSP)Floyd’s Algorithm•On the kth iteration, use the following formula to compute A Ak-1[i,j]•A[i,j] = min{ Ak-1[i,k] + Ak-1[k,j]Computer Science – Game DesignUC Santa CruzAll Pairs Shortest Path (APSP)Floyd’s Algorithm•On the kth iteration, use the following formula to compute A Ak-1[i,j]•A[i,j] = min{ Ak-1[i,k] + Ak-1[k,j] The cost of going from i to j without going through k or any higher nodeComputer Science – Game DesignUC Santa CruzAll Pairs Shortest Path (APSP)Floyd’s Algorithm•On the kth iteration, use the following formula to compute A Ak-1[i,j]•A[i,j] = min{ Ak-1[i,k] + Ak-1[k,j] The cost of going from i to k, then k to j, without going through any nodehigher than k.Computer Science – Game DesignUC Santa CruzFloyd Example1 23528321 2 31 0 8 52 3 0 ∞3 ∞ 2 0A0[i,j]Computer Science – Game DesignUC Santa CruzFloyd Example1 23528321 2 31 0 8 52 3 0 83 ∞ 2 0A1[i,j]Computer Science – Game DesignUC Santa CruzFloyd Example1 23528321 2 31 0 8 52 3 0 83 ∞ 2 0A1[i,j]Computer Science – Game DesignUC Santa CruzFloyd Example1 23528321 2 31 0 8 52 3 0 83 ∞ 2 0A1[i,j]Computer Science – Game DesignUC Santa CruzFloyd Example1 23528321 2 31 0 8 52 3 0 83 ∞ 2 0A1[i,j]Computer Science – Game DesignUC Santa CruzFloyd Example1 23528321 2 31 0 8 52 3 0 83 5 2 0A2[i,j]Computer Science – Game DesignUC Santa CruzFloyd Example1 23528321 2 31 0 8 52 3 0 83 5 2 0A2[i,j]Computer Science – Game DesignUC Santa CruzFloyd Example1 23528321 2 31 0 8 52 3 0 83 5 2 0A2[i,j]Computer Science – Game DesignUC Santa CruzFloyd Example1 23528321 2 31 0 8 52 3 0 83 5 2 0A2[i,j]Computer Science – Game DesignUC Santa CruzFloyd Example1 23528321 2 31 0 7 52 3 0 83 5 2 0A3[i,j]Computer Science – Game DesignUC Santa CruzFloyd Example1 23528321 2 31 0 7 52 3 0 83 5 2 0A3[i,j]Computer Science – Game DesignUC Santa CruzFloyd Example1 23528321 2 31 0 7 52 3 0 83 5 2 0A3[i,j]Computer Science – Game DesignUC Santa CruzMarch 21, 2006CSC481Design and Development of Computer GamesFloyd’s CodeAho, Hopcroft and Ullman, Data Structures and Algorithms, Addison Wesley, pages 208-213.Including code for keeping track of the actual paths!Computer Science – Game DesignUC Santa CruzA* pathfinding•A* algorithm is widely used as the conceptual core for pathfinding in computer games–Most commercial games use variants of the algorithm tailored to the specific game–Original paper:•A Formal Basis for the Heuristic Determination of Minimum Cost Paths•Hart, P.E.; Nilsson, N.J.; Raphael, B.•IEEE Trans. Systems Science and Cybernetics, 4(2), July 1968, pp. 100-107•A* is a graph search algorithm–There is a large research literature on graph search algorithms, and computer game