A* Grid Pathfinding

using UnityEngine;
using System.Collections.Generic;

/// <summary>
/// Grid-based A* pathfinding. Works without Unity NavMesh.
/// Ideal for 2D top-down games and tile-based environments.
/// </summary>
public class AStarPathfinding : MonoBehaviour
{
    public static AStarPathfinding Instance { get; private set; }

    [Header("Grid")]
    [SerializeField] private int gridWidth = 50;
    [SerializeField] private int gridHeight = 50;
    [SerializeField] private float cellSize = 1f;
    [SerializeField] private Vector3 gridOrigin = Vector3.zero;
    [SerializeField] private LayerMask obstacleLayer;

    [Header("Settings")]
    [SerializeField] private bool allowDiagonal = true;
    [SerializeField] private bool showDebug = true;

    private Node[,] grid;

    private class Node
    {
        public int x, y;
        public bool walkable;
        public float weight;
        public float gCost, hCost;
        public Node parent;

        public float fCost => gCost + hCost;
        public Vector3 worldPosition;

        public Node(int x, int y, bool walkable, Vector3 pos, float weight = 1f)
        {
            this.x = x;
            this.y = y;
            this.walkable = walkable;
            this.worldPosition = pos;
            this.weight = weight;
        }
    }

    private void Awake()
    {
        if (Instance == null)
            Instance = this;
        else
        {
            Destroy(gameObject);
            return;
        }

        GenerateGrid();
    }

    /// <summary>
    /// Regenerate the walkability grid (call after terrain changes).
    /// </summary>
    public void GenerateGrid()
    {
        grid = new Node[gridWidth, gridHeight];

        for (int x = 0; x < gridWidth; x++)
        {
            for (int y = 0; y < gridHeight; y++)
            {
                Vector3 worldPos = gridOrigin + new Vector3(
                    x * cellSize + cellSize * 0.5f,
                    0f,
                    y * cellSize + cellSize * 0.5f
                );

                bool walkable = !Physics.CheckBox(
                    worldPos,
                    Vector3.one * cellSize * 0.4f,
                    Quaternion.identity,
                    obstacleLayer
                );

                grid[x, y] = new Node(x, y, walkable, worldPos);
            }
        }
    }

    /// <summary>
    /// Find a path from start to end world positions.
    /// Returns a list of world positions, or null if no path found.
    /// </summary>
    public List<Vector3> FindPath(Vector3 startPos, Vector3 endPos)
    {
        Node startNode = GetNodeFromWorld(startPos);
        Node endNode = GetNodeFromWorld(endPos);

        if (startNode == null || endNode == null || !endNode.walkable)
            return null;

        List<Node> openSet = new List<Node> { startNode };
        HashSet<Node> closedSet = new HashSet<Node>();

        // Reset costs
        for (int x = 0; x < gridWidth; x++)
            for (int y = 0; y < gridHeight; y++)
            {
                grid[x, y].gCost = float.MaxValue;
                grid[x, y].parent = null;
            }

        startNode.gCost = 0;
        startNode.hCost = Heuristic(startNode, endNode);

        while (openSet.Count > 0)
        {
            Node current = GetLowestFCost(openSet);

            if (current == endNode)
                return RetracePath(startNode, endNode);

            openSet.Remove(current);
            closedSet.Add(current);

            foreach (Node neighbor in GetNeighbors(current))
            {
                if (!neighbor.walkable || closedSet.Contains(neighbor))
                    continue;

                float moveCost = current.gCost + Heuristic(current, neighbor) * neighbor.weight;

                if (moveCost < neighbor.gCost)
                {
                    neighbor.gCost = moveCost;
                    neighbor.hCost = Heuristic(neighbor, endNode);
                    neighbor.parent = current;

                    if (!openSet.Contains(neighbor))
                        openSet.Add(neighbor);
                }
            }
        }

        return null; // No path found
    }

    private Node GetLowestFCost(List<Node> nodes)
    {
        Node lowest = nodes[0];
        for (int i = 1; i < nodes.Count; i++)
        {
            if (nodes[i].fCost < lowest.fCost ||
                (nodes[i].fCost == lowest.fCost && nodes[i].hCost < lowest.hCost))
            {
                lowest = nodes[i];
            }
        }
        return lowest;
    }

    private float Heuristic(Node a, Node b)
    {
        int dx = Mathf.Abs(a.x - b.x);
        int dy = Mathf.Abs(a.y - b.y);

        if (allowDiagonal)
            return Mathf.Min(dx, dy) * 1.414f + Mathf.Abs(dx - dy);
        else
            return dx + dy;
    }

    private List<Node> GetNeighbors(Node node)
    {
        List<Node> neighbors = new List<Node>();
        int[] dx = { 0, 1, 0, -1 };
        int[] dy = { 1, 0, -1, 0 };

        for (int i = 0; i < 4; i++)
        {
            int nx = node.x + dx[i];
            int ny = node.y + dy[i];
            if (nx >= 0 && nx < gridWidth && ny >= 0 && ny < gridHeight)
                neighbors.Add(grid[nx, ny]);
        }

        if (allowDiagonal)
        {
            int[] ddx = { 1, 1, -1, -1 };
            int[] ddy = { 1, -1, 1, -1 };
            for (int i = 0; i < 4; i++)
            {
                int nx = node.x + ddx[i];
                int ny = node.y + ddy[i];
                if (nx >= 0 && nx < gridWidth && ny >= 0 && ny < gridHeight)
                    neighbors.Add(grid[nx, ny]);
            }
        }

        return neighbors;
    }

    private List<Vector3> RetracePath(Node start, Node end)
    {
        List<Vector3> path = new List<Vector3>();
        Node current = end;

        while (current != start)
        {
            path.Add(current.worldPosition);
            current = current.parent;
        }

        path.Reverse();
        return path;
    }

    private Node GetNodeFromWorld(Vector3 worldPos)
    {
        Vector3 local = worldPos - gridOrigin;
        int x = Mathf.FloorToInt(local.x / cellSize);
        int y = Mathf.FloorToInt(local.z / cellSize);

        if (x < 0 || x >= gridWidth || y < 0 || y >= gridHeight)
            return null;

        return grid[x, y];
    }

#if UNITY_EDITOR
    private void OnDrawGizmos()
    {
        if (!showDebug || grid == null) return;

        for (int x = 0; x < gridWidth; x++)
        {
            for (int y = 0; y < gridHeight; y++)
            {
                Gizmos.color = grid[x, y].walkable
                    ? new Color(0f, 1f, 0f, 0.1f)
                    : new Color(1f, 0f, 0f, 0.3f);
                Gizmos.DrawCube(grid[x, y].worldPosition, Vector3.one * cellSize * 0.9f);
            }
        }
    }
#endif
}