2D A* Pathfinding - Timme Kingma

Challenge

Apply my Algorithms & Data Structures coursework to a visual project, with obstacle handling as the main challenge.

My contribution

I implemented the pathfinding algorithm in C# and built its 2D grid visualization in Unity.

Approach

Use Manhattan distance to guide the search, track open and closed nodes, and reconstruct the route through parent references.

Outcome

A working visualization and browser demo, completed in about a week at roughly two hours a day, that deepened my understanding of pathfinding.

Live Demo

The pathfinding runs directly in your browser via Unity WebGL.

Runs in your browser · about 9 MB download

How A* Works

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.

Code Examples

A* Core Loop (C#)

using NUnit.Framework.Internal;
using System;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;

public static class PathFinder
{
    public static List<Vertex> FindPath(Vertex start, Vertex target)
    {
        List<Vertex> openList = new();
        List<Vertex> test = new();
        HashSet<Vertex> 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<Vertex> RetracePath(Vertex start, Vertex end)
    {
        List<Vertex> path = new();
        Vertex current = end;

        while (current != start)
        {
            path.Add(current);
            current = current.Parent;

            if (current == null)
                return null;
        }

        path.Reverse();
        return path;
    }
}

Vertex Data Structure (C#)

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<Vertex> myEdges { get; set; } = new();

    public Vertex (HashSet<Vertex> myEdges, string name,int x,int y)
    {
        this.myEdges = myEdges;
        Name = name;
        this.X = x;
        this.Y = y;
    }
}