This project highlights an implementation of the A* pathfinding algorithm using Manhattan distance as a heuristic. The algorithm is implemented in C# within the Unity game engine, allowing for real-time pathfinding in a 2D grid-based environment. A* efficiently finds the shortest path between two points while navigating around obstacles, making it ideal for game development and AI applications.
My reason for creating this project was to apply the knowledge from my recent Algorithms & Data Structures class. I wanted to see how the A* algorithm works in practice and create a visual representation of it in Unity. This project allowed me to deepen my understanding of pathfinding algorithms and their applications in game development.
The project took about a week to complete, with around two hours of work each day. The most challenging part was creating an efficient way to account for obstacles in the grid while ensuring the algorithm did not take an inefficient path.
The pathfinding runs directly in your browser via Unity WebGL.
A* (A-star) is a graph traversal and pathfinding algorithm that finds the shortest path between a start and a target node. It combines the benefits of Dijkstra's algorithm (guaranteed shortest path) and Greedy Best-First Search (speed) by using a heuristic function. For each node, A* calculates F = G + H, where G is the actual cost from the start node, and H is the estimated (heuristic) cost to the target, I used the Manhattan distance. The algorithm always explores the node with the lowest F score next, ensuring an optimal and efficient path.
A* maintains two lists: the open list (nodes to be evaluated) and the closed list (nodes already evaluated). At each step, the node with the lowest F score is taken from the open list. Its neighbors are checked, skipping obstacles and already-visited nodes. For each valid neighbor, G, H, and the parent node are updated if a cheaper path is found. Once the target is reached, the path is reconstructed by following each node's Parent reference back to the start. If the open list empties without reaching the target, no path exists.
using NUnit.Framework.Internal;
using System;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;
public static class PathFinder
{
public static List FindPath(Vertex start, Vertex target)
{
List openList = new();
List test = new();
HashSet closedList = new();
start.G = 0;
openList.Add(start);
while (openList.Count > 0)
{
Vertex current = openList.OrderBy(v => v.F).ThenBy(v => v.H).First();
if (current == target)
return RetracePath(start, target);
openList.Remove(current);
closedList.Add(current);
foreach (var neighbor in current.myEdges)
{
if (neighbor.isObject || closedList.Contains(neighbor))
continue;
int newCost = current.G + 1;
if (newCost < neighbor.G || !openList.Contains(neighbor))
{
neighbor.G = newCost;
neighbor.H = Mathf.Abs(target.X - neighbor.X) + Mathf.Abs(target.Y - neighbor.Y);
neighbor.Parent = current;
test.Add(current);
if (!openList.Contains(neighbor))
openList.Add(neighbor);
}
}
}
return null;
}
private static List RetracePath(Vertex start, Vertex end)
{
List path = new();
Vertex current = end;
while (current != start)
{
path.Add(current);
current = current.Parent;
if (current == null)
return null;
}
path.Reverse();
return path;
}
}
using System;
using System.Collections.Generic;
using UnityEngine;
[Serializable]
public class Vertex: MonoBehaviour
{
public bool isObject;
public int X;
public int Y;
public int G;
public int H;
public Vertex Parent;
public double F { get { return G + H; } private set { F = value; } }
public string Name;
public HashSet myEdges { get; set; } = new();
public Vertex (HashSet myEdges, string name,int x,int y)
{
this.myEdges = myEdges;
Name = name;
this.X = x;
this.Y = y;
}
}