Send the link below via email or IMCopy
Present to your audienceStart 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
AI: Pathfinding + Level Design Lecture
Transcript of AI: Pathfinding + Level Design Lecture
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?