Pathfinding in Unity

implementing A* search and graph search algorithms in Unity

Created byWilmer Lin

Last updated 11/2020

English

English [Auto],

What you'll learn

Understand the fundamentals of graph search algorithms
Implement your own basic version of A*

Course content

5 sections • 38 lectures • 4h 33m total length

Welcome1:22
Welcome to Pathfinding in Unity!
Prerequisites and Course How-To4:00
Before you begin this course, please review the prerequisites. This course is intended for Intermediate Unity developers with experience in C# scripting.
Naming Conventions6:00
Here let's review the naming conventions that we use for the included Unity project.

Nodes and Graphs3:18
Let's review the basics of pathfinding. Graphs are a set of interconnected nodes, which are joined by edges. We will apply this data structure to a physical map, allowing us to solve for a path through a maze.
The Node class6:00
Each graph is made of nodes. Let's define a class for our most basic object, the Node.
The MapData class5:29
In this lesson, we define a MapData class, designed to read the level data into the Graph.
The Graph class6:07
We will create a Graph class to manage the various nodes which will comprise our level.
Neighbor Nodes7:26
Our nodes will be connected by proximity. In this lesson, we define a set of compass directions and establish how nodes and their neighbors are connected.
NodeView8:25
Let's use the MVC (Model View Controller) design pattern to create some new components. We will make an interface class called the NodeView specifically designed for displaying a Node onscreen.
GraphView8:54
Let's create another user interface class, the GraphView, for managing all of our NodeViews.
Text Mapdata Part 19:26
In this lesson, we review creating level data as a Text Asset, allowing us to store our map as a simple set of ASCII characters on disk.
Text MapData Part 28:56
In this lesson, we create the MakeMap method in the MapData class, allowing us to read the 1's and 0's from our ASCII Text Asset. Now we have a much easier means of generating our level maps!
Resources4:42
We can use the Resources command to help organize our project folders. Setting up the default Resources folder allows us to look for map data without needing to browse for files explicitly in the Inspector!
Image Mapdata9:59
If using a text editor to create your level map is too cumbersome, let's use our favorite image editor to create a level! Using a one-pixel brush we can save our maze in a super small image file. This is a super interactive way to create new levels!
Update: Script Execution Order7:15
We have a minor bug in our MapData class. Let's examine how Script Execution Order can affect the behavior of our components and apply a simple fix.

Pathfinding Basics5:25
The Pathfinder class10:12
Create and initialize a Pathfinder class in Unity, connect the graph, start and goal nodes, and visualize the search with color-coded frontier, explored, and path nodes.
Search Part 15:32
Use the pathfinder to explore the graph with a frontier queue, turning visited nodes gray and frontier nodes magenta, while initializing isComplete and iterations and using show colors.
Search Part 26:22
Perform a stepwise frontier-based search in Unity by expanding the frontier one node at a time, enqueueing new neighbors, and tracing a breadcrumb trail to visualize explored nodes.
Node Arrows10:12
Show a breadcrumb trail by rendering arrows from each node to the previous one, oriented using vector3 difference and quaternion look rotation.
Path Nodes9:16
Breadth First Search11:59
Explore breadth-first search in Unity by testing on larger mazes, tuning visualization options, and measuring performance with early exit and diagnostic logs.
Dijkstra's Algorithm5:06
Learn how Dijkstra's algorithm enhances pathfinding in Unity as an improved breadth first search that tracks distance from the start, updates the previous node for the shortest route.
Node Distance4:41
Dijkstra's Search11:09
Toggle between breadth-first search and Dijkstra's algorithm to expand frontiers in a Unity pathfinding scene. Track distance traveled to compare path length and routing.
Priority Queue Part 16:59
Learn how to enhance Unity pathfinding with a priority queue by using distance traveled as the priority, sorting frontier nodes by shortest path to reach solutions faster.
Priority Queue Part 212:27
Implement a generic priority queue in Unity using a min binary heap to efficiently manage nodes by priority, with enqueue and dequeue operations that maintain heap order.
Priority Queue Part 311:34
Implement a binary-heap priority queue in Unity to dequeue the top item, reheapify after removal, and expose peak, contains, to-list, and count, while exploring Dykstra and BFS in pathfinding.
Terrain Cost Part 112:52
Terrain Cost Part 214:01
Greedy Best-First Search11:58
A* Search12:35
In this lesson, we tweak our Pathfinder search routine to implement A* search!
Code Comments0:01

Search Routine Updates6:54
A small correction to the graph search. Oops!
Refactored Project0:35
Case Study: Monument Valley Prototype5:42
In this case study, we show you a simple example of how you might use pathfinding in your Unity application.
Here we show a clone of Monument Valley. The click-to-move controller relies on a pathfinder to decide how the player can reach a certain part of the level.
Check out the link in the Resources to the published article.

Requirements

Unity 3D version 2017 or above (personal FREE edition)
Mac or PC
OPTIONAL Photoshop or image-editing program to customize level data

Description

Description

This course is designed for intermediate users of Unity (see the Prerequisites for specific topics you should be familiar with before joining).

Though Unity comes pre-packaged with an excellent pathfinding system, we explore beyond using a black box to calculate paths through your game levels.

Pathfinding and search algorithms are a core component of game development. If you want to level up your skills, enroll today and dive into implementing your own version of A* search!

Through a carefully crafted set of lectures we learn search algorithms, starting with Breadth-First Search, diving in Dijkstra's algorithm and culminating with the industry-standard A* search for pathfinding.

All concepts are presented with easy-to-understand visuals!

Some other bonus features of those course:

learn to use text files or texture maps to drive level data in Unity
learn how to implement a priority queue (binary heap) in C#
learn to structure a small project using the MVC(Model View Controller) design pattern

Who this course is for:

intermediate Unity developers with good working knowledge of C#
anyone who wants to implement graph search algorithms in Unity

Pathfinding in Unity

What you'll learn

Explore related topics

Course content

Introduction3 lectures • 11min

Constructing a Maze12 lectures • 1hr 26min

Pathfinding Algorithms18 lectures • 2hr 42min

Updates3 lectures • 13min

Bonus2 lectures • 1min

Requirements

Description

Who this course is for: