Pathfinding.cs

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

public class Pathfinding
{
    private const int MOVE_STRAIGHT_COST = 5;
    private const int MOVE_DIAGONAL_COST = 7;

    private static Pathfinding _instance;
    public static Pathfinding Instance => _instance;

    private Grid grid;

    private List<Tile> openList;
    private List<Tile> closedList;

    public Pathfinding(Grid grid)
    {
        _instance = this;
        this.grid = grid;
    }

    public List<Tile> FindPath(int startX, int startY, int endX, int endY, int movementPoints)
    {
        Tile startTile = grid.GetGridObject(startX, startY);
        Tile endTile = grid.GetGridObject(endX, endY);

        openList = new List<Tile> { startTile };
        closedList = new List<Tile>();

        for (int x = 0; x < grid.GridSizeX; x++)
        {
            for (int y = 0; y < grid.GridSizeY; y++)
            {
                Tile tile = grid.GetGridObject(x, y);
                tile.gCost = int.MaxValue;
                tile.cameFromTile = null;
            }
        }

        startTile.gCost = 0;
        startTile.hCost = CalculateDistanceCost(startTile, endTile);

        while (openList.Count > 0)
        {
            Tile currentTile = GetLowestFCostNode(openList);
            if (currentTile == endTile)
            {
                // reached end
                return CalculatePath(endTile);
            }

            openList.Remove(currentTile);
            closedList.Add(currentTile);

            foreach (Tile neighbour in GetNeighbourList(currentTile))
            {
                if (closedList.Contains(neighbour))
                    continue;

                if (!neighbour.IsWalkable())
                {
                    closedList.Add(neighbour);
                    continue;
                }

                int tentativeGCost = currentTile.gCost + CalculateDistanceCost(currentTile, neighbour);
                //Debug.Log(tentativeGCost);

                if (tentativeGCost >= movementPoints)
                    return CalculatePath(currentTile);

                if (tentativeGCost < neighbour.gCost)
                {
                    neighbour.cameFromTile = currentTile;
                    neighbour.gCost = tentativeGCost;
                    neighbour.hCost = CalculateDistanceCost(neighbour, endTile);

                    if (!openList.Contains(neighbour))
                        openList.Add(neighbour);
                }
            }
        }

        return null;
    }

    private List<Tile> GetNeighbourList(Tile tile)
    {
        List<Tile> neighbours = new List<Tile>();

        if (tile.X - 1 >= 0)
        {
            // left
            neighbours.Add(GetNode(tile.X - 1, tile.Y));

            // left down
            if (tile.Y - 1 >= 0)
                neighbours.Add(GetNode(tile.X - 1, tile.Y - 1));

            // left up
            if (tile.Y + 1 < grid.GridSizeY)
                neighbours.Add(GetNode(tile.X - 1, tile.Y + 1));
        }

        if (tile.X+1 < grid.GridSizeX)
        {
            // right
            neighbours.Add(GetNode(tile.X + 1, tile.Y));

            // right down
            if (tile.Y - 1 >= 0)
                neighbours.Add(GetNode(tile.X + 1, tile.Y - 1));

            // right up
            if (tile.Y + 1 < grid.GridSizeY)
                neighbours.Add(GetNode(tile.X + 1, tile.Y + 1));
        }

        // down
        if (tile.Y - 1 >= 0)
            neighbours.Add(GetNode(tile.X, tile.Y - 1));

        // up
        if (tile.Y + 1 > grid.GridSizeY)
            neighbours.Add(GetNode(tile.X, tile.Y + 1));

        return neighbours;
    }

    private Tile GetNode(int x, int y)
    {
        return grid.GetGridObject(x, y);
    }

    private List<Tile> CalculatePath(Tile endTile)
    {
        List<Tile> path = new List<Tile>();
        path.Add(endTile);

        Tile current = endTile;
        while (current.cameFromTile != null)
        {
            path.Add(current.cameFromTile);
            current = current.cameFromTile;
        }

        path.Reverse();

        return path;
    }

    private Tile GetLowestFCostNode(List<Tile> pathList)
    {
        Tile lowersFCostTile = pathList[0];
        for (int i = 1; i < pathList.Count; i++)
            if (pathList[i].fCost < lowersFCostTile.fCost)
                lowersFCostTile = pathList[i];

        return lowersFCostTile;
    }

    private int CalculateDistanceCost(Tile a, Tile b)
    {
        int xDistance = Mathf.Abs(a.X - b.X);
        int yDistance = Mathf.Abs(a.Y - b.Y);
        int remaining = Mathf.Abs(xDistance - yDistance);

        return MOVE_DIAGONAL_COST * Mathf.Min(xDistance, yDistance) + MOVE_STRAIGHT_COST * remaining;
    }
}