using UnityEngine;
using System.Collections;
using System.Collections.Generic;
public class Grid
{
    public static Grid Instance;
    public NodeElement[,] nodes;
    public int width, height;
    public Grid(int _width = 0, int _height = 0)
    {
        Instance = this;
        width = _width;
        height = _height;
        nodes = new NodeElement[width, height];
        for (int x = 0; x < width; x++)
        {
            for (int y = 0; y < height; y++)
            {
                nodes[x, y] = new NodeElement(x, y, 0, true);
            }
        }
    }
    public bool WithinBounds(int x, int y)
    {
        return x >= 0 && x < width && y >= 0 && y < height;
    }
    public bool WithinBounds(NodeElement p)
    {
        return WithinBounds(p.x, p.y);
    }
    public static NodeElement GetNodeAt(int x, int y)
    {
        if (Instance.WithinBounds(x, y))
        {
            return Instance.nodes[x, y];
        }
        return null;
    }
    public static bool IsWalkableAt(int x, int y)
    {
        NodeElement temp = GetNodeAt(x, y);
        if (temp != null)
        {
            return temp.passable;
        }
        return false;
    }
    public List<NodeElement> openList;
    NodeElement _start, _goal;
    public static List<NodeElement> Path(NodeElement start, NodeElement goal)
    {
        Instance._start = start;
        Instance._goal = goal;
        List<NodeElement> _path = new List<NodeElement>();
        NodeElement tNode;
        // set the `g` and `f` value of the start node to be 0
        start.costSofar = 0;
        start.heuristicStartToEndLen = 0;

        // push the start node into the open list
        _path.Add(start);
        start.isOpened = true;

        // while the open list is not empty
        while (_path.Count > 0)
        {
            // pop the position of node which has the minimum `f` value.
            _path.Sort();
            tNode = _path[_path.Count - 1];
            _path.RemoveAt(_path.Count - 1);
            //tNode.isClosed = true;

            if (tNode == goal)
            {
                return NodeElement.Backtrace(tNode); // rebuilding path
            }

            identifySuccessors(tNode);
        }

        return _path;
    }
    public static float Euclidean(int iDx, int iDy)
    {
        float tFdx = (float)iDx;
        float tFdy = (float)iDy;
        return (float)Mathf.Sqrt(tFdx * tFdx + tFdy * tFdy);
    }
    private static void identifySuccessors(NodeElement iNode)
    {
        List<NodeElement> tOpenList = Instance.openList;
        int tEndX = Instance._goal.x;
        int tEndY = Instance._goal.y;
        NodeElement tNeighbor;
        NodeElement tJumpNode;

        List<NodeElement> tNeighbors = findNeighbors(iNode);
        for (int i = 0; i < tNeighbors.Count; i++)
        {
            tNeighbor = tNeighbors[i];
            tJumpNode = jump(tNeighbor.x, tNeighbor.y, iNode.x, iNode.y);
            if (tJumpNode != null)
            {
                tJumpNode = GetNodeAt(tJumpNode.x, tJumpNode.y);
                // include distance, as parent may not be immediately adjacent:
                float tCurNodeToJumpNodeLen = Euclidean(Mathf.Abs(tJumpNode.x - iNode.x), Mathf.Abs(tJumpNode.y - iNode.y));
                float tStartToJumpNodeLen = (float)iNode.costSofar + tCurNodeToJumpNodeLen; // next `startToCurNodeLen` value

                if (!tJumpNode.isOpened || tStartToJumpNodeLen < tJumpNode.startToCurNodeLen)
                {
                    tJumpNode.startToCurNodeLen = tStartToJumpNodeLen;
                    tJumpNode.heuristicStartToEndLen = tJumpNode.startToCurNodeLen + tJumpNode.heuristicCurNodeToEndLen;
                    tJumpNode.cameFrom = iNode;

                    if (!tJumpNode.isOpened)
                    {
                        tOpenList.Add(tJumpNode);
                        tJumpNode.isOpened = true;
                    }
                }
            }
        }
    }
    private static List<NodeElement> findNeighbors(NodeElement iNode)
    {
        NodeElement tParent = iNode.cameFrom;
        int tX = iNode.x;
        int tY = iNode.y;
        int tPx, tPy, tDx, tDy;
        List<NodeElement> tNeighborNodes = new List<NodeElement>();
        NodeElement tNeighborNode;

        // directed pruning: can ignore most neighbors, unless forced.
        if (tParent != null)
        {
            tPx = tParent.x;
            tPy = tParent.y;
            // get the normalized direction of travel
            tDx = (tX - tPx) / Mathf.Max(Mathf.Abs(tX - tPx), 1);
            tDy = (tY - tPy) / Mathf.Max(Mathf.Abs(tY - tPy), 1);

            {
                // search diagonally
                if (tDx != 0 && tDy != 0)
                {
                    if (IsWalkableAt(tX, tY + tDy))
                    {
                        tNeighborNodes.Add(GetNodeAt(tX, tY + tDy));
                    }
                    if (IsWalkableAt(tX + tDx, tY))
                    {
                        tNeighborNodes.Add(GetNodeAt(tX + tDx, tY));
                    }

                    if (IsWalkableAt(tX + tDx, tY + tDy))
                    {
                        if (IsWalkableAt(tX, tY + tDy) && IsWalkableAt(tX + tDx, tY))
                            tNeighborNodes.Add(GetNodeAt(tX + tDx, tY + tDy));
                    }

                    if (IsWalkableAt(tX - tDx, tY + tDy))
                    {
                        if (IsWalkableAt(tX, tY + tDy) && IsWalkableAt(tX - tDx, tY))
                            tNeighborNodes.Add(GetNodeAt(tX - tDx, tY + tDy));
                    }

                    if (IsWalkableAt(tX + tDx, tY - tDy))
                    {
                        if (IsWalkableAt(tX, tY - tDy) && IsWalkableAt(tX + tDx, tY))
                            tNeighborNodes.Add(GetNodeAt(tX + tDx, tY - tDy));
                    }


                }
                // search horizontally/vertically
                else
                {
                    if (tDx == 0)
                    {
                        if (IsWalkableAt(tX, tY + tDy))
                        {
                            tNeighborNodes.Add(GetNodeAt(tX, tY + tDy));

                            if (IsWalkableAt(tX + 1, tY + tDy) && IsWalkableAt(tX + 1, tY))
                            {
                                tNeighborNodes.Add(GetNodeAt(tX + 1, tY + tDy));
                            }
                            if (IsWalkableAt(tX - 1, tY + tDy) && IsWalkableAt(tX - 1, tY))
                            {
                                tNeighborNodes.Add(GetNodeAt(tX - 1, tY + tDy));
                            }
                        }
                        if (IsWalkableAt(tX + 1, tY))
                            tNeighborNodes.Add(GetNodeAt(tX + 1, tY));
                        if (IsWalkableAt(tX - 1, tY))
                            tNeighborNodes.Add(GetNodeAt(tX - 1, tY));
                    }
                    else
                    {
                        if (IsWalkableAt(tX + tDx, tY))
                        {

                            tNeighborNodes.Add(GetNodeAt(tX + tDx, tY));

                            if (IsWalkableAt(tX + tDx, tY + 1) && IsWalkableAt(tX, tY + 1))
                            {
                                tNeighborNodes.Add(GetNodeAt(tX + tDx, tY + 1));
                            }
                            if (IsWalkableAt(tX + tDx, tY - 1) && IsWalkableAt(tX, tY - 1))
                            {
                                tNeighborNodes.Add(GetNodeAt(tX + tDx, tY - 1));
                            }
                        }
                        if (IsWalkableAt(tX, tY + 1))
                            tNeighborNodes.Add(GetNodeAt(tX, tY + 1));
                        if (IsWalkableAt(tX, tY - 1))
                            tNeighborNodes.Add(GetNodeAt(tX, tY - 1));
                    }
                }
            }

        }
        // return all neighbors
        else
        {
            tNeighborNodes = GetNeighbors(iNode);
            for (int i = 0; i < tNeighborNodes.Count; i++)
            {
                tNeighborNode = tNeighborNodes[i];
                tNeighborNodes.Add(GetNodeAt(tNeighborNode.x, tNeighborNode.y));
            }
        }

        return tNeighborNodes;
    }
    public static List<NodeElement> GetNeighbors(NodeElement iNode)
    {
        int tX = iNode.x;
        int tY = iNode.y;
        List<NodeElement> neighbors = new List<NodeElement>();
        bool tS0 = false, tD0 = false,
            tS1 = false, tD1 = false,
            tS2 = false, tD2 = false,
            tS3 = false, tD3 = false;
        int x = tX, y = tY - 1;
        if (IsWalkableAt(tX, tY))
        {
            neighbors.Add(GetNodeAt(x, y));
            tS0 = true;
        }
        x = tX + 1; y = tY;
        if (IsWalkableAt(x, y))
        {
            neighbors.Add(GetNodeAt(x, y));
            tS1 = true;
        }
        x = tX; y = tY + 1;
        if (IsWalkableAt(x, y))
        {
            neighbors.Add(GetNodeAt(x, y));
            tS2 = true;
        }
        x = tX - 1; y = tY;
        if (IsWalkableAt(x, y))
        {
            neighbors.Add(GetNodeAt(x, y));
            tS3 = true;
        }

        tD0 = tS3 && tS0;
        tD1 = tS0 && tS1;
        tD2 = tS1 && tS2;
        tD3 = tS2 && tS3;


        x = tX - 1; y = tY - 1;
        if (tD0 && IsWalkableAt(x, y))
        {
            neighbors.Add(GetNodeAt(x, y));
        }
        x = tX + 1; y = tY - 1;
        if (tD1 && IsWalkableAt(x, y))
        {
            neighbors.Add(GetNodeAt(x, y));
        }
        x = tX + 1; y = tY + 1;
        if (tD2 && IsWalkableAt(x, y))
        {
            neighbors.Add(GetNodeAt(x, y));
        }
        x = tX - 1; y = tY + 1;
        if (tD3 && IsWalkableAt(x, y))
        {
            neighbors.Add(GetNodeAt(x, y));
        }
        return neighbors;
    }
    private static NodeElement jump(int iX, int iY, int iPx, int iPy)
    {
        if (!IsWalkableAt(iX, iY))
        {
            return null;
        }
        else if (GetNodeAt(iX, iY) == Instance._goal)
        {
            return Instance._goal;
        }

        int tDx = iX - iPx;
        int tDy = iY - iPy;
        NodeElement jx = null;
        NodeElement jy = null;
        {
            // check for forced neighbors
            // along the diagonal
            if (tDx != 0 && tDy != 0)
            {
                if ((IsWalkableAt(iX + tDx, iY + tDy) && IsWalkableAt(iX, iY + tDy) && !IsWalkableAt(iX + tDx, iY)) ||
                    (IsWalkableAt(iX + tDx, iY + tDy) && IsWalkableAt(iX + tDx, iY) && !IsWalkableAt(iX, iY + tDy)))
                {
                    return GetNodeAt(iX, iY);
                }
            }
            // horizontally/vertically
            else
            {
                if (tDx != 0)
                {
                    // moving along x
                    if ((IsWalkableAt(iX, iY + 1) && !IsWalkableAt(iX - tDx, iY + 1)) ||
                        (IsWalkableAt(iX, iY - 1) && !IsWalkableAt(iX - tDx, iY - 1)))
                    {
                        return GetNodeAt(iX, iY);
                    }
                }
                else
                {
                    if ((IsWalkableAt(iX + 1, iY) && !IsWalkableAt(iX + 1, iY - tDy)) ||
                        (IsWalkableAt(iX - 1, iY) && !IsWalkableAt(iX - 1, iY - tDy)))
                    {
                        return GetNodeAt(iX, iY);
                    }
                }
            }


            // when moving diagonally, must check for vertical/horizontal jump points
            if (tDx != 0 && tDy != 0)
            {
                jx = jump(iX + tDx, iY, iX, iY);
                jy = jump(iX, iY + tDy, iX, iY);
                if (jx != null || jy != null)
                {
                    return GetNodeAt(iX, iY);
                }
            }

            // moving diagonally, must make sure both of the vertical/horizontal
            // neighbors is open to allow the path
            if (IsWalkableAt(iX + tDx, iY) && IsWalkableAt(iX, iY + tDy))
            {
                return jump(iX + tDx, iY + tDy, iX, iY);
            }
            else
            {
                return null;
            }
        }

    }

}