A* Pathfinding

BaseCustomTileData.cs

using System;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;
using UnityEngine.Tilemaps;

[CreateAssetMenu(fileName = "BaseCustomTileData", menuName = "Custom Tile Rules/New Custom Tile Rule")]
public class BaseCustomTileData : RuleTile<BaseCustomTileData.Neighbor>, ICloneable, IComparable<BaseCustomTileData>
{
    #region Pathfinder
    /// <summary>
    /// Cost from start
    /// </summary>
    [SerializeField]
    public int G;

    /// <summary>
    /// Cost to the end
    /// </summary>
    [SerializeField]
    public int H;

    /// <summary>
    /// Total cost G + H
    /// </summary>
    [SerializeField]
    public int F => G + H;

    /// <summary>
    /// Parent node
    /// </summary>
    [SerializeField]
    public BaseCustomTileData Parent;
    #endregion

    #region Position
    /// <summary>
    /// Current tile position
    [SerializeField]
    public Vector3Int Position;

    /// <summary>
    /// Neighbours for this tile
    /// </summary>
    private HashSet<Vector3Int> _neighbourDirections;

    public List<BaseCustomTileData> InTilemapNeighbours;
    #endregion

    #region Misc
    /// <summary>
    /// Walkable tile
    /// </summary>
    [SerializeField]
    public bool CanWalk;

    /// <summary>
    /// Player tile
    /// </summary>
    [SerializeField]
    public bool IsPlayer;
    #endregion

    #region Visuals
    /// <summary>
    /// Sprite to render for this TileData
    /// </summary>
    [SerializeField]
    public Sprite Sprite;
    #endregion

    public override void GetTileData(Vector3Int position, ITilemap tilemap, ref TileData tileData)
    {
        base.GetTileData(position, tilemap, ref tileData);
        Position = position;
        tileData.sprite = Sprite;
        SetDirections();
    }

    public override void RefreshTile(Vector3Int position, ITilemap tilemap)
    {
        base.RefreshTile(position, tilemap);
    }

    public override bool StartUp(Vector3Int position, ITilemap tilemap, GameObject instantiatedGameObject)
    {
        return base.StartUp(position, tilemap, instantiatedGameObject);
    }

    public class Neighbor : RuleTile.TilingRule.Neighbor
    {
        public const int Null = 3;
        public const int NotNull = 4;
    }

    public override bool RuleMatch(int neighbor, TileBase tile)
    {
        switch (neighbor)
        {
            case Neighbor.Null: return tile == null;
            case Neighbor.NotNull: return tile != null;
        }
        return base.RuleMatch(neighbor, tile);
    }

    public BaseCustomTileData()
    {

    }

    public BaseCustomTileData(BaseCustomTileData toClone)
    {
        if (toClone == null) return;
        G = toClone.G;
        H = toClone.H;
        Parent = toClone?.Parent;
        Position = toClone.Position;
        CanWalk = toClone.CanWalk;
        IsPlayer = toClone.IsPlayer;
        Sprite = toClone?.Sprite;
        _neighbourDirections = toClone?._neighbourDirections;
        InTilemapNeighbours = toClone?.InTilemapNeighbours;
    }

    public object Clone()
    {
        var newObject = ScriptableObject.CreateInstance<BaseCustomTileData>();
        return newObject.Clone(this);
    }

    public object Clone(BaseCustomTileData toClone)
    {
        G = toClone.G;
        H = toClone.H;
        Parent = toClone?.Parent;
        Position = toClone.Position;
        CanWalk = toClone.CanWalk;
        IsPlayer = toClone.IsPlayer;
        Sprite = toClone?.Sprite;
        _neighbourDirections = toClone?._neighbourDirections;
        InTilemapNeighbours = toClone?.InTilemapNeighbours;
        return this;
    }

    public void SetDirections()
    {
        _neighbourDirections = new HashSet<Vector3Int>
        {
            Position + Vector3Int.up,
            Position + Vector3Int.right,
            Position + Vector3Int.down,
            Position + Vector3Int.left
        };
        InTilemapNeighbours = new List<BaseCustomTileData>();
    }

    public void CalculateInTilemapNeighbours(HashSet<BaseCustomTileData> _board)
    {
        foreach (var position in _neighbourDirections)
        {
            BaseCustomTileData tileData = _board
                .Where(t => t.Position == position && t.CanWalk && !t.IsPlayer)
                .FirstOrDefault();
            if (tileData != null)
            {
                InTilemapNeighbours.Add(tileData);
            }
        }
    }

    public int CompareTo(BaseCustomTileData comparable)
    {        
        if(F > comparable.F) return 1;
        if (F < comparable.F) return -1;
        return 0;
    }
}

MinHeap.cs

using System;

public class MinHeap<T> where T : class, IComparable<T>
{
    /// <summary>
    /// Current values
    /// </summary>
    private T[] values;

    /// <summary>
    /// Current size
    /// </summary>
    private int size = 0;

    public MinHeap(int maxSize)
    {
        //initialize for given capacity
        Array.Resize<T>(ref values, maxSize + 1);
    }

    /// <summary>
    /// Add a new element
    /// Resize if necessary
    /// </summary>
    /// <param name="value">Value to add</param>
    public void Add(T value)
    {
        if (size == values.Length - 1)
            Array.Resize<T>(ref values, values.Length + 1); //adjust array if necessary
        values[size++] = value;
        AdjustHeap(size);
    }

    /// <summary>
    /// Get the first element
    /// </summary>
    /// <returns>Can return null if size is 0</returns>
    public T Next() //pop
    {
        if (size <= 0) return null; //:>
        //store to return
        T current = values[0];
        //swap
        values[0] = values[size - 1];
        //del
        values[size - 1] = null;
        size--;
        if (size == 0) return current;
        NormalizeAt(0);
        return current;
    }

    private void NormalizeAt(int i)
    {
        var swappable = i;        
        var left = GetLeft(i);
        if (left < size && values[left].CompareTo(values[i]) < 0)
        {
            swappable = left;
        }

        var right = GetRight(i);
        if (right < size && values[right].CompareTo(values[swappable]) < 0)
        {
            swappable = right;
        }

        if (swappable != i)
        {
            Swap(i, swappable);
            NormalizeAt(swappable);
        }
    }

    private void AdjustHeap(int i)
    {
        if (size <= 1) return;
        var parent = ParentIndex(i);
        if (parent >= 0 && values[i - 1].CompareTo(values[parent]) < 0)
        {
            Swap(i - 1, parent);
            AdjustHeap(parent);
        }
    }

    private void Swap(int i, int j)
    {
        T temp = values[i];
        values[i] = values[j];
        values[j] = temp;
    }

    private int ParentIndex(int i)
    {
        if (i <= 0) return int.MinValue;
        return (i - 1) / 2;
    }

    private int GetRight(int i)
    {
        if (i > size) return int.MaxValue;
        return 2 * i + 2;
    }

    private int GetLeft(int i)
    {
        if (i > size) return int.MaxValue;
        return 2 * i + 1;
    }

    public T Last()
    {
        return values[^1];
    }

    public int Count()
    {
        return size;
    }

    //:<
    public bool Contains(T item)
    {
        foreach (var v in values)
        {
            if (v == item) return true;
        }

        return false;
    }
}

PathFinder.cs

using System.Collections.Generic;
using System.Linq;
using UnityEngine;

/// <summary>
/// A* Pathfinding
/// </summary>
public class PathFinder
{
    /// <summary>
    /// Find a path for a given start and end positions
    /// </summary>
    /// <param name="start">Start position</param>
    /// <param name="end">End position</param>
    /// <returns>Path or empty</returns>
    public HashSet<Vector3Int> BuildPath(BaseCustomTileData start, BaseCustomTileData end)
    {
        var minHeap = new MinHeap<BaseCustomTileData>(100);
        minHeap.Add(start);
        var closed = new HashSet<BaseCustomTileData>();

        do
        {
            //get lowest F score
            var current = minHeap.Next();
            closed.Add(current);

            //path found
            if (current == end)
            {
                return ReducePath(start, current);
            }

            foreach (var neighbour in current.InTilemapNeighbours)
            {
                if (neighbour.IsPlayer) continue;
                if (neighbour.IsEnemy) continue;
                if (!neighbour.CanWalk) continue;
                if (closed.Contains(neighbour)) continue;
                if (minHeap.Contains(neighbour)) continue;

                var newCost = current.G + GetDistance(current, neighbour);
                if (neighbour.G > 0 && newCost > neighbour.G) continue;

                neighbour.G = newCost;
                neighbour.H = GetDistance(neighbour, end);
                neighbour.Parent = current;
                minHeap.Add(neighbour);
            }
        } while (minHeap.Count() > 0);

        return new HashSet<Vector3Int>();
    }

    /// <summary>
    /// Find a path for a given start and end positions
    /// </summary>
    /// <param name="start">Start position</param>
    /// <param name="end">End position</param>
    /// <returns>Path or empty</returns>
    public HashSet<Vector3Int> BuildPath(BaseCustomTileData start, BaseCustomTileData end, HashSet<Vector3> inRange)
    {
        var minHeap = new MinHeap<BaseCustomTileData>(100);
        minHeap.Add(start);
        var closed = new HashSet<BaseCustomTileData>();

        do
        {
            //get lowest F score
            var current = minHeap.Next();
            closed.Add(current);

            //path found
            if (current == end)
            {
                return ReducePath(start, current);
            }

            foreach (var neighbour in current.InTilemapNeighbours)
            {
                if (neighbour.IsPlayer) continue;
                if (neighbour.IsEnemy) continue;
                if (!neighbour.CanWalk) continue;
                if (!inRange.Contains(neighbour.Position)) continue;
                if (closed.Contains(neighbour)) continue;
                if (minHeap.Contains(neighbour)) continue;

                var newCost = current.G + GetDistance(current, neighbour);
                if (neighbour.G > 0 && newCost > neighbour.G) continue;

                neighbour.G = newCost;
                neighbour.H = GetDistance(neighbour, end);
                neighbour.Parent = current;
                minHeap.Add(neighbour);

            }
        } while (minHeap.Count() > 0);

        return new HashSet<Vector3Int>();
    }

    /// <summary>
    /// Build a path to paint
    /// </summary>
    /// <param name="start"></param>
    /// <param name="end"></param>
    /// <returns></returns>
    private HashSet<Vector3Int> ReducePath(BaseCustomTileData start, BaseCustomTileData end)
    {
        var path = new HashSet<Vector3Int>();
        var current = end;
        while (current != start)
        {
            path.Add(current.Position);
            current = current.Parent;
        }

        path.Reverse();
        return path;
    }

    /// <summary>
    /// Calculate manhattan
    /// </summary>
    /// <param name="nodeA"></param>
    /// <param name="nodeB"></param>
    /// <returns></returns>
    public static int GetDistance(BaseCustomTileData nodeA, BaseCustomTileData nodeB)
    {
        return Mathf.Abs(nodeA.Position.x - nodeB.Position.x) + Mathf.Abs(nodeA.Position.y - nodeB.Position.y);
    }

    ///// <summary>
    ///// Find a path for a given start and end positions
    ///// </summary>
    ///// <param name="start">Start position</param>
    ///// <param name="end">End position</param>
    ///// <returns>Path or empty</returns>
    //public HashSet<Vector3Int> BuildPathSlower(BaseCustomTileData start, BaseCustomTileData end)
    //{
    //    var open = new List<BaseCustomTileData>
    //    {
    //        start
    //    };

    //    var closed = new HashSet<BaseCustomTileData>();

    //    while (open.Count() > 0)
    //    {
    //        //get lowest F score            
    //        var current = open.OrderBy(t => t.F).First();
    //        //open.Remove(current);
    //        closed.Add(current);

    //        //path found
    //        if (current == end)
    //        {
    //            return ReducePath(start, current);
    //        }

    //        foreach (var neighbour in current.InTilemapNeighbours)
    //        {
    //            if (neighbour.IsPlayer) continue;
    //            if (!neighbour.CanWalk) continue;
    //            if (closed.Contains(neighbour)) continue;

    //            neighbour.G = GetDistance(start, neighbour);
    //            neighbour.H = GetDistance(end, neighbour);
    //            neighbour.Parent = current;
    //            if (!open.Contains(neighbour))
    //            {
    //                open.Add(neighbour);
    //            }
    //        }
    //    }

    //    return new HashSet<Vector3Int>();
    //}
}