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 built-in 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 free-form 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 mouse-click or key-press?
- 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.
