Loading presentation...

Present Remotely

Send the link below via email or IM


Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.


AI: Pathfinding + Level Design Lecture

for Intro to Game D & D

Ben Smith

on 26 March 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of AI: Pathfinding + Level Design Lecture

and Level Design AI: Pathfinding The Maze 1. Grab Paper and Pencil and draw a Maze! How did you win? Fun? AI: Pathfinding Basics Knowledge of the world: Algorithm Framework Init start/root node, push on Open. Breadth-First New Maze Make a maze to solve with an algorithm! Best-First! Basics same as breadth, but uses Heuristic for sorting open stack. A* Best-First + Dijkstra 3. Trade mazes with a classmate and solve theirs! 4. Repeat #3! Heuristics? Algorithm? Grids Waypoint-Graphs Nav Meshes skipping Random Trace... Init 2 stacks: "Open" and "Closed" while Open not empty:
1. pop a node ("current") - if goal then END
2. create successors and push onto Open
3. put current node on Closed Always pop oldest node first. Exhaustive, finds optimal path (in terms of steps). Pros: Cons: Expensive, inefficient. if step != distance will not find optimal path. Use graph paper, draw edges on lines, spaces are passable. Make maze small: 6x6 to 10x10 area Place start and end to make an interesting path (some loops, dead ends, not along the perimeter). Create root (at start). While ! at goal and open cells exist: Take (pop) cell closest to goal: Create (push) successor nodes. Sort based on assigned FinalCost. FinalCost = GivenCost +
HeuristicCost * HeuristicWeight GivenCost = Dijkstra given cost (sum of step costs). Dijkstra Make one more maze! Now each node is assigned a GivenCost. GivenCost = shortest distance covered from start to this node/cell. March through your maze, giving each cell a GivenCost value: new cost = previous cost + step distance +1 for lateral steps, +1.4 for diagonal Pop node with lowest GivenCost off
Open at each iteration. Will revisit nodes and compare GivenCosts, deleting higher cost node. Dijkstra Pseudo-code: create rootNode, givenCost = 0, push onto Open while Open is not empty: 1) pop node with lowest givenCost 2) if node is END then exit. 3) for every adjacent cell: a) if impassable then skip b) create successorNode: givenCost = parent's givenCost + cost of going from parent to this c) if adjacent cell has a successorNode already:
keep node with lower cost, delete other. d) push successorNode on open list. (if exit without finding END: goal is unreachable) HeuristicCost = ?? Typically Best-First distance-to-goal measure. HeuristicWeight: controls performance! can include other weights: cover/exposure, terrain difficulty, etc. Pathfinding for your games Navigation helper class builds/stores navigation grid/mesh calculates best path between any 2 points Agents request a path to their target and traverse request new paths as the target moves or other factors change Q: How to build and store the navigation grid/mesh? As an array?
Linked list of nodes? Read in a B&W bitmap? March box colliders through the scene? Optimize with zones and portals? Implement A*! Pathfinding (FIFO stack) For every node popped off of Open: create successor nodes for all passable adjoining cells. Pros? Cons? Problems? Where does it perform best? Where does it perform worst?
Full transcript