This project highlights an implemtation 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. The A* algorithm 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 inplement my knowlage of my resently gaven class Algorithms & Data structures. I wanted to see how the A* algorithm works in practice and to 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, eatch day spend about 2 hours on it. The most challenging part was creating an effiecent way to also take into account the objects in the grid, and to make sure the algorithm dosnt take an ineffiecent 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;
}
}