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

using Uber.HabboHotel.GameClients;
using Uber.HabboHotel.Rooms;

namespace Uber.HabboHotel.Pathfinding
{
    class Pathfinder
    {
        Coord[] Movements;
        CompleteSquare[,] Squares;

        Room Room;
        RoomModel Model;
        RoomUser User;

        int mapSizeX;
        int mapSizeY;

        public Pathfinder(Room Room, RoomUser User)
        {
            this.Room = Room;
            this.Model = Room.Model;
            this.User = User;

            if (Room == null || Model == null || User == null)
            {
                return;
            }

            InitMovements(true);

            mapSizeX = Model.MapSizeX;
            mapSizeY = Model.MapSizeY;

            Squares = new CompleteSquare[mapSizeX, mapSizeY];

            for (int x = 0; x < mapSizeX; x++)
            {
                for (int y = 0; y < mapSizeY; y++)
                {
                    Squares[x, y] = new CompleteSquare(x, y);
                }
            }
        }

        public List<Coord> FindPath()
        {
            // Locate the user, and set the distance to zero
            int UserX = User.X;
            int UserY = User.Y;

            Squares[User.X, User.Y].DistanceSteps = 0;

            // Find all possible moves
            while (true)
            {
                Boolean MadeProgress = false;

                for (int x = 0; x < mapSizeX; x++)
                {
                    for (int y = 0; y < mapSizeY; y++)
                    {
                        int passHere = Squares[x, y].DistanceSteps;

                        foreach (Coord movePoint in Movements)
                        {
                            int newX = x + movePoint.x;
                            int newY = y + movePoint.y;

                            if (ValidCoordinates(newX, newY) &&
                                IsSquareOpen(newX, newY, true))
                            {
                                int newPass = passHere + 1;

                                if (Squares[newX, newY].DistanceSteps > newPass)
                                {
                                    Squares[newX, newY].DistanceSteps = newPass;
                                    MadeProgress = true;
                                }
                            }
                        }
                    }
                }

                if (!MadeProgress)
                {
                    break;
                }
            }

            // Locate the goal
            int goalX = User.GoalX;
            int goalY = User.GoalY;

            if (goalX == -1 || goalY == -1)
            {
                return null;
            }

            // Now trace the shortest possible route to our goal
            List<Coord> Path = new List<Coord>();

            Path.Add(new Coord(User.GoalX, User.GoalY));

            while (Path.Count < mapSizeX * mapSizeY)
            {
                Coord lowestPoint = new Coord();
                int lowest = 100;

                foreach (Coord movePoint in Movements)
                {
                    int newX = goalX + movePoint.x;
                    int newY = goalY + movePoint.y;

                    if (ValidCoordinates(newX, newY) &&
                        IsSquareOpen(newX, newY, true))
                    {
                        int count = Squares[newX, newY].DistanceSteps;

                        if (count < lowest)
                        {
                            lowest = count;

                            lowestPoint.x = newX;
                            lowestPoint.y = newY;
                        }
                    }
                }

                if (lowest != 100)
                {
                    Squares[lowestPoint.x, lowestPoint.y].IsPath = true;
                    goalX = lowestPoint.x;
                    goalY = lowestPoint.y;

                    Path.Add(lowestPoint);
                }
                else
                {
                    break;
                }

                if (goalX == UserX && goalY == UserY)
                {
                    break;
                }
            }

            return Path;
        }

        private Boolean IsSquareOpen(int x, int y, Boolean CheckHeight)
        {
            if (Room.ValidTile(x, y) && User.AllowOverride)
            {
                return true;
            }

            if (User.X == x && User.Y == y)
            {
                return true;
            }

            bool isLastStep = false;

            if (User.GoalX == x && User.GoalY == y)
            {
                isLastStep = true;
            }

            if (!Room.CanWalk(x, y, 0, isLastStep))
            {
                return false;
            }

            return true;
        }

        private Boolean ValidCoordinates(int x, int y)
        {
            if (x < 0 || y < 0 || x > mapSizeX || y > mapSizeY)
            {
                return false;
            }

            return true;
        }

        public void InitMovements(bool Diag)
        {
            if (!Diag)
            {
                Movements = new Coord[]
                {
                    new Coord(0, -1),
                    new Coord(1, 0),
                    new Coord(0, 1),
                    new Coord(-1, 0)
                };
            }
            else
            {
                Movements = new Coord[]
                {
                    new Coord(0, 1),
                    new Coord(0, -1),
                    new Coord(1, 0),
                    new Coord(1, 1),
                    new Coord(1, -1),
                    new Coord(-1, 0),
                    new Coord(-1, 1),
                    new Coord(-1, -1)
                };
            }
        }
    }

    class CompleteSquare
    {
        public int x = 0;
        public int y = 0;

        int _distanceSteps = 100;

        public int DistanceSteps
        {
            get { return _distanceSteps; }
            set { _distanceSteps = value; }
        }

        bool _isPath = false;

        public bool IsPath
        {
            get { return _isPath; }
            set { _isPath = value; }
        }

        public CompleteSquare(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
    }
}