using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace mmoRLserver
{
    public static class Pathfinding //A* pathfinding implementation
    {
        public class Node : IComparable<Node>
        {
            public Node discoverer = null;
            public int x = 0;
            public int y = 0;
            public int destX = 0;
            public int destY = 0;
            public int travelCost = 99999;
            public int heuristic = 99999;

            public Node(Node orig, int x, int y, int destX, int destY, int cost)
            {
                this.discoverer = orig;
                this.x = x;
                this.y = y;
                this.destX = destX;
                this.destY = destY;
                this.travelCost = cost;
                this.heuristic = Math.Abs(destX - this.x) + Math.Abs(destY - this.y);
            }

            public int CompareTo(Node node)
            {
                int toReturn = (this.travelCost + this.heuristic) - (node.travelCost + node.heuristic);
                return toReturn;
            }
        }

        public struct Route
        {
            public List<int> relativeX;
            public List<int> relativeY;
            public List<int> absoluteX;
            public List<int> absoluteY;
            public int travelCost;
            public bool exists;

            public Route(bool exists)
            {
                this.exists = exists;
                this.travelCost = 0;
                this.relativeX = new List<int>();
                this.relativeY = new List<int>();
                this.absoluteX = new List<int>();
                this.absoluteY = new List<int>();
            }

            public Route(Node finalNode)
            {
                this.exists = true;
                this.travelCost = finalNode.travelCost;
                this.relativeX = new List<int>();
                this.relativeY = new List<int>();
                this.absoluteX = new List<int>();
                this.absoluteY = new List<int>();

                //Put the fastest route in a list
                List<Node> fastestRoute = new List<Node>();
                Node currentNode = finalNode;
                while (currentNode.discoverer != null)
                {
                    fastestRoute.Add(currentNode);
                    currentNode = currentNode.discoverer;
                }
                fastestRoute.Add(currentNode);

                //Then reverse iterate the list (skip the origina tile) and turn it into a Route
                bool first = true;
                int currentX = 0;
                int currentY = 0;
                for (int i = fastestRoute.Count - 1; i > -1; i--)
                {
                    int thisX = fastestRoute[i].x;
                    int thisY = fastestRoute[i].y;

                    if (first)
                    {
                        first = false;
                    }
                    else
                    {
                        absoluteX.Add(thisX);
                        absoluteY.Add(thisY);
                        relativeX.Add(thisX - currentX);
                        relativeY.Add(thisY - currentY);
                    }

                    currentX = thisX;
                    currentY = thisY;
                }
            }
        }

        public static bool collisionCheck(Map map, int x, int y, int[] xObstacles = null, int[] yObstacles = null, int[] xExceptions = null, int[] yExceptions = null)
        {
            bool canPass = true;
            if (map.tiles[x, y].solid) canPass = false;
            else if (map.objects[x, y].solid) canPass = false;
            else if (xObstacles != null && yObstacles != null)
            {
                int max = xObstacles.Length;
                if (yObstacles.Length < max) max = yObstacles.Length;
                for (int i = 0; i < max; i++)
                {
                    if (x == xObstacles[i] && y == yObstacles[i])
                    {
                        if (!(xExceptions.Contains(x) && yExceptions.Contains(y)))
                        {
                            canPass = false;
                        }
                    }
                }
            }
            if (canPass) //Then try to block the way with monsters!
            {
                for (int i = 0; i < map.monsters.Count; i++)
                {
                    if (canPass) //Don't bother if already invalid
                    {
                        if (xExceptions != null && yExceptions != null)
                        {
                            if (!(xExceptions.Contains(x) && yExceptions.Contains(y)))
                            {
                                if (map.monsters[i].x == x && map.monsters[i].y == y) canPass = false;
                            }
                        }
                    }
                }
            }

            return (!canPass); //True if collision, false if not
        }

        public static Route GetFastestRoute(Map map, int startX, int startY, int destX, int destY, bool ignoreObstacles = true,
            int limit = 99999, int[] xObstacles = null, int[] yObstacles = null, bool destException = false)
        {
            Route toReturn = new Route(false);

            List<Node> openNodes = new List<Node>();
            List<Node> closedNodes = new List<Node>();

            openNodes.Add(new Node(null, startX, startY, destX, destY, 0));

            int lowestTravelCost = 0;
            while (!toReturn.exists && lowestTravelCost <= limit && openNodes.Count > 0)
            {
                openNodes.Sort();

                //Victory check
                if (openNodes[0].x == destX && openNodes[0].y == destY)
                {
                    toReturn = new Route(openNodes[0]);
                }
                else //Calculate shit
                {
                    closedNodes.Add(openNodes[0]);
                    for (int iy = -1; iy < 2; iy++)
                    {
                        for (int ix = -1; ix < 2; ix++)
                        {
                            if (Math.Abs(ix) + Math.Abs(iy) != 2) //No diagonals
                            {
                                int targetX = openNodes[0].x + ix;
                                int targetY = openNodes[0].y + iy;

                                //Check if target tile is in bounds
                                if (targetX > -1 && targetX < Map.MAP_WIDTH && targetY > -1 && targetY < Map.MAP_HEIGHT)
                                {
                                    //Check if it's possible to move over target tile
                                    bool canPass = true;

                                    int[] xExceptions = new int[] { };
                                    int[] yExceptions = new int[] { };

                                    if (destException)
                                    {
                                        xExceptions = new int[] { destX };
                                        yExceptions = new int[] { destY };
                                    }

                                    if (!ignoreObstacles) canPass = (!collisionCheck(map, targetX, targetY, xObstacles, yObstacles,
                                        xExceptions, yExceptions));

                                    if (canPass)
                                    {
                                        //Check if the target is still within the limit
                                        if (openNodes[0].travelCost + 1 <= limit)
                                        {
                                            //Check if already in list
                                            bool newNode = true;
                                            for (int i = 0; i < closedNodes.Count; i++) if (closedNodes[i].x == targetX && closedNodes[i].y == targetY) newNode = false;
                                            for (int i = 0; i < openNodes.Count; i++) if (openNodes[i].x == targetX && openNodes[i].y == targetY) newNode = false;

                                            if (newNode)
                                            {
                                                openNodes.Add(new Node(openNodes[0], targetX, targetY, openNodes[0].destX, openNodes[0].destY, openNodes[0].travelCost + 1));
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                    openNodes.RemoveAt(0);
                }
            }

            return toReturn;
        }
    }
}