Pathfinding
Time
3 hrs
Difficulty
Module 2
Prerequisites
Computer Physics
Components
Components
Departments
Career & Technology Studies
Authors
Sandra Kuipers
Groupings
Individual
Pairs
Pairs
Minimum Year Group
None
Blurb
Pathfinding
Outline
Learner Outcomes Students will:


Competency Focus

Interdisciplinary Connections

Reflection What was successful? What needs changing? Alternative Assessments and Lesson Ideas? What other Differentiation Ideas/Plans could be used?


Credits Any CC attribution, thanks, credit, etc.

This page requires you to be logged in to access it. Please login and try again.
5 mins
What is Pathfinding?
Getting Started
 In games, we often want to move a character from point A to point B.
 However, we usually don't want this character to move through walls and doors.
 Pathfinding is a set of algorithms computers use to navigate around obstacles.
10 mins
2D Pathfinding
 2D pathfinding often works by defining a grid of points, and marking each point as either passable or not passable.
 With this grid, it's possible to use an algorithm to find a path from A to B.
 2D pathfinding often uses an algorithm called A* (a star).
 Check out the A* Pathfinding introduction.
 The algorithm gets a bit complex, be sure to read down until you get to the first Demo section.
 You don't need to memorize the math here, just get a sense of the overall approach.
 Once you've read down to the first Demo, be sure to check it out:
 In this example, the green line is able to move around the black cubes.
 The blue area is where the algorithm has searched for a path.
 It uses a type of optimization called a heuristic to skip directions that lead farther away from the target.
 This means it doesn't have to search the whole map to find a path, which makes the algorithm pretty fast.
10 mins
Pathfinding Example
Explorable
 Check out this interactive 2D pathfinding example.
 You can move the red and green squares, and draw walls.
 When you click "Start Search" it will highlight the route the pathfinding algorithm uses.
 Play with the example, and watch the path the algorithm uses.
 Why do you think it takes the path that it does?
 Based on the A* reading, can you observe the Manhattan Distance, Diagonal Distance, and Euclidean Distance in action?
5 mins
3D Pathfinding
 3D pathfinding works similar to 2D, except instead of a grid, it uses a 3D mesh.
 Pathfinding calculations can be expensive: they take a lot of CPU/GPU cycles.
 To simplify the math, many games use a simplified version of the scene called a navigation mesh.
 The navigation mesh is often an invisible mesh that uses much simpler geometry than the game itself.
 The algorithm is very similar, yet instead of a 2D grid, it uses something called a Node Graph.
30 mins
Navmesh in Unity
 As you've seen, there's a lot of algorithms involved in pathfinding.
 Programming a navigation mesh manually can be very complex.
 Luckily unity comes with a builtin NavMesh system.
 Check out the NavMesh tutorial for an example of how to create a navigation mesh.
 You can download the example files to test them out in Unity.
 You can also check out the Building a Navmesh docs for more info.
120 mins
Your Obstacle Course
Evidence
 Can you create an obstacle course that players can navigate around?
 Using NavMesh and a player controller, create a scene that requires pathfinding to traverse.
 This is a freeform project, you don't need to follow the tutorial.
 Consider what kinds of obstacles to add: static ones, or moving ones?
 Can you add a script to move your player, by either mouseclick or keypress?
 Can you add an escape hatch for your player to reach?
 As a bonus, could you add enemies to the map that slowly chase the player?
 Once you've programmed and tested your obstacle course, upload the project to Drive and share a link to the project folder as evidence of your learning in this unit.
Links
 Building a Navmesh
 heuristic
 Pathfinding
 Node Graph
 download the example files
 interactive 2D pathfinding example
 Diagonal Distance
 Euclidean Distance
 Manhattan Distance
 A* Pathfinding introduction
 Demo
 NavMesh tutorial
Images
Embeds
There are no records to display.
There are no records to display.