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

namespace data.Game
{
    public class Pather : Maze
    {
        //16*16 maps (room list) should be enough for all catacomb levels
        public Pather()
            : base(SizeX,SizeY)
        {
            base.AllowDiagonals = true;
        }
        public Pather(bool allowDiagonals)
            : base(SizeX, SizeY)
        {
            //base.AllowDiagonals = allowDiagonals;
            base.AllowDiagonals = true;
        }

        //fields
        static int left = 0, top = 0, right = 0, bottom = 0; //bounds of the defined rooms inside the big _RoomList array

        //methods
        /// <summary>
        /// used to convert world coordinates to coordinates used in our maze
        /// </summary>
        /// <param name="i"></param>
        /// <param name="ConvertX"></param>
        /// <returns></returns>
        private uint ConvertToRelative(int i, bool ConvertX)
        {
            SetBounds();
            int x = ((i - GameInfo.RoomOffsetX) / 5 - left * 12);
            int y = ((i - GameInfo.RoomOffsetY) / 5 - top * 12);
            if (ConvertX)
                return (uint)x;
            return (uint)y;
        }
        public List<System.Drawing.Point> GoTo(GameObject obj)
        {
            return GoTo(obj.X, obj.Y);
        }
        public List<System.Drawing.Point> GoTo(Warp warp)
        {
            if (warp == null)
                return null;
            return GoTo(warp.X, warp.Y);
        }
        public List<System.Drawing.Point> GoTo(int[] RoomIndex)
        {
            throw new ApplicationException("Method not implemented");
        }
        public List<System.Drawing.Point> GoTo(System.Drawing.Point WorldCoordinates)
        {
            return GoTo(WorldCoordinates.X, WorldCoordinates.Y);
        }
        public List<System.Drawing.Point> GoTo(int WorldX, int WorldY)
        {
            return GoTo(ConvertToRelative(WorldX, true), ConvertToRelative(WorldY, false));
        }
        public List<System.Drawing.Point> GoTo(System.Drawing.Point WorldFrom, System.Drawing.Point WorldTo)
        {
            if (!SetWalkableInfo())
                throw new ApplicationException("Failed to set Walkable info from GoTo()");
            int FromX = (int)ConvertToRelative(WorldFrom.X, true);
            int FromY = (int)ConvertToRelative(WorldFrom.Y, false);
            this[FromX, FromY] = 0;
            
            base.fromx = FromX;
            base.fromy = FromY;
            base.tox = (int)ConvertToRelative(WorldTo.X, true);
            base.toy = (int)ConvertToRelative(WorldTo.Y, false);
            this[base.tox, base.toy] = 0;
            base.FindPath((int)FromX, (int)FromY, base.tox, base.toy);
            return base.PathPoints(left, top);      
        }
        private List<System.Drawing.Point> GoTo(uint RelativeX, uint RelativeY)
        {
            if (!SetWalkableInfo())
                throw new ApplicationException("Failed to set Walkable info from GoTo()") ;
            int FromX = (int)ConvertToRelative(GameInfo.PlayerX, true);
            int FromY = (int)ConvertToRelative(GameInfo.PlayerY, false);
            this[FromX, FromY] = 0;
            this[(int)RelativeX, (int)RelativeY] = 0;
            base.fromx = FromX;
            base.fromy = FromY;
            base.tox = (int)RelativeX;
            base.toy = (int)RelativeY;
            base.FindPath((int)FromX, (int)FromY, (int)RelativeX,(int)RelativeY);
            //Logger.Log(base.ToString((int)FromX, (int)FromY, (int)RelativeX, (int)RelativeY));
            //Logger.Log(base.PathToString((int)FromX, (int)FromY, (int)RelativeX, (int)RelativeY));
            return base.PathPoints(left, top);       
        }
        
        /// <summary>
        /// will set the base[x,y] walk info
        /// </summary>
        /// <returns>false if it fails to set bounds</returns>
        private bool SetWalkableInfo()
        {
            if (!SetBounds())
                return false;
            base.m_iRows = (right - left + 1) * 12;
            base.m_iCols = (bottom - top + 1) * 12;
            base.m_iMaze = new int[base.m_iRows, base.m_iCols];
            for (int x = left; x < right + 1; x++)
            {
                for (int y = top; y < bottom + 1; y++)
                {
                    for (int xroom = 0; xroom < 12; xroom++)
                    {
                        for (int yroom = 0; yroom < 12; yroom++)
                        {
                            //to set values in maze, substract left and top from all values
                            int xMaze = 0, yMaze = 0;
                            //set the x and y index of the maze relative to current rooms/room indexes
                            // (( x - left) * 12) removes the unused rooms to the left and adds previous rooms
                            xMaze = ((x - left) * 12) + xroom;
                            yMaze = ((y - top) * 12) + yroom;
                            
                            if (GameInfo._RoomList[x, y].Walkable != null &&
                                ((xroom == 0 || yroom == 0 || xroom == 11 || yroom == 11)))
                            {
                                //set this to walkable because edges are buggy (need to fix in Walkable array to check for other Prop0 value)
                                base[xMaze, yMaze] = 0;
                                continue;
                            }
                            
                            if (GameInfo._RoomList[x, y].Walkable != null
                                && GameInfo._RoomList[x, y].Walkable[xroom, yroom] == true)
                            {
                                //this is walkable
                                base[xMaze, yMaze] = 0;
                            }
                            else
                            {
                                //this is not walkable
                                base[xMaze, yMaze] = 1;
                            }
                        }
                    }
                }
            }
            return true;
        }

        /// <summary>
        /// set the left, top, bottom and right bounds of the array to determine the size of the maze
        /// (because we dont want to use a 16*12*16*12 array all the time)
        /// </summary>
        /// <returns>true if it finds the bounds, false otherwise</returns>
        private static bool SetBounds()
        {
                for (int x = 0; x < 16; x++)
                {
                    for (int y = 0; y < 16; y++)
                    {
                        if (GameInfo._RoomList[x, y].isDefined)
                        {
                            left = x;
                            goto done1;
                        }
                    }
                }
                return false;
            done1:
                for (int y = 0; y < 16; y++)
                {
                    for (int x = 0; x < 16; x++)
                    {
                        if (GameInfo._RoomList[x, y].isDefined)
                        {
                            top = y;
                            goto done2;
                        }
                    }
                }
                return false;
            done2:
                for (int x = 15; x > -1; x--)
                {
                    for (int y = 15; y > -1; y--)
                    {
                        if (GameInfo._RoomList[x, y].isDefined)
                        {
                            right = x;
                            goto done3;
                        }
                    }
                }
                return false;
            done3:
                for (int y = 15; y > -1; y--)
                {
                    for (int x = 15; x > -1; x--)
                    {
                        if (GameInfo._RoomList[x, y].isDefined)
                        {
                            bottom = y;
                            goto finish;
                        }
                    }
                }
                return false;
            finish:
                return true;
        }
        private static int SizeX
        {
            get
            {
                if (right == 0 || left == 0)
                    SetBounds();
                return right - left ;
            }
        }
        private static int SizeY
        {
            get
            {
                if (bottom == 0 || top == 0)
                    SetBounds();
                return bottom - top ;
            }
        }
    }


   
    /// <summary>
    /// Summary description for MazeSolver.
    /// Class name: MazeSolver
    /// Developed by: Syed Mehroz Alam
    /// Email: smehrozalam@yahoo.com
    /// URL: Programming Home "http://www.geocities.com/smehrozalam/"
    /// 
    /// Constructors:
    /// 	( int[,] ):	takes 2D integer array	
    /// 	( int Rows, int Cols )	initializes the dimensions, indexers may be used 
    /// 							to set individual elements' values
    /// 
    /// Properties:
    /// 	Rows: returns the no. of rows in the current maze
    /// 	Cols: returns the no. of columns in the current maze
    /// 	Maze: returns the current maze as a 2D array
    /// 	PathCharacter: to get/set the value of path tracing character
    /// 	AllowDiagonal: whether diagonal paths are allowed
    /// 
    /// Indexers:
    /// 	[i,j] = used to set/get elements of maze
    /// 
    /// Public Methods (Description is given with respective methods' definitions)
    ///		int[,] FindPath(int iFromY, int iFromX, int iToY, int iToX)
    /// 
    /// Private Methods
    ///		void GetNodeContents(int[,] iMaze, int iNodeNo)
    ///		void ChangeNodeContents(int[,] iMaze, int iNodeNo, int iNewValue)
    ///		int[,] Search(int iBeginningNode, int iEndingNode)
    /// 
    /// </summary>
    public delegate void MazeChangedHandler(int iChanged, int jChanged);
    /// <summary>
    /// base class for Pather
    /// </summary>
    public class Maze
    {
        protected int fromx, fromy, tox, toy;
        public string ToString(int fromx, int fromy, int tox, int toy)
        {
            System.Text.StringBuilder sb = new System.Text.StringBuilder();
            for (int y = 0; y < this.GetMaze.GetUpperBound(1); y++)
            {
                for (int x = 0; x < this.GetMaze.GetUpperBound(0); x++)
                {
                    if (x == fromx && y == fromy)
                    {
                        sb.Append("S");
                    }
                    else if (x == tox && y == toy)
                    {
                        sb.Append("E");
                    }
                    else
                    {
                        sb.Append(this[x, y]);
                    }
                }
                sb.Append(Environment.NewLine);
            }
            return sb.ToString();
        }
        public string PathToString()
        {
            
            int[,] solved = this.iMazeSolved;
            System.Text.StringBuilder sb = new System.Text.StringBuilder();
            for (int y = 0; y < this.GetMaze.GetUpperBound(1); y++)
            {
                for (int x = 0; x < this.GetMaze.GetUpperBound(0); x++)
                {
                    if (solved[x, y] == 100)
                    {
                        if (x == tox && y == toy)
                            sb.Append("E");
                        else if (x == fromx && y == fromy)
                            sb.Append('S');
                        else
                            sb.Append("+");
                    }
                    else
                    {
                        sb.Append(solved[x, y]);
                    }
                    
                }
                sb.Append(Environment.NewLine);
            }
            return sb.ToString();
        }
       

        /// <summary>
        /// Class attributes/members
        /// </summary>
        public int[,] m_iMaze;
        public int m_iRows;
        public int m_iCols;
        int iPath = 100;
        bool diagonal = false;
        public event MazeChangedHandler OnMazeChangedEvent;
        List<System.Drawing.Point> retList = new List<System.Drawing.Point>();
        public List<System.Drawing.Point> PathPoints(int left, int top)
        {
            for (int i =0; i < retList.Count; i++)
            {
                System.Drawing.Point p = retList[i];
                int x = p.X, y = p.Y;
                p.X = 22500 + x * 5  + left * 60;
                p.Y = GameInfo.RoomOffsetY + y * 5  + top * 60;
                retList[i] = p;
            }
            retList.Reverse();
            return retList;
        }

        /// <summary>
        /// Constructor 1: takes a 2D integer array
        /// </summary>
        public Maze(int[,] iMaze)
        {
            m_iMaze = iMaze;
            m_iRows = iMaze.GetLength(0);
            m_iCols = iMaze.GetLength(1);
        }

        /// <summary>
        /// Constructor 2: initializes the dimensions of maze, 
        /// later, indexers may be used to set individual elements' values
        /// </summary>
        public Maze(int iRows, int iCols)
        {
            m_iMaze = new int[iRows, iCols];
            m_iRows = iRows;
            m_iCols = iCols;
        }

        /// <summary>
        /// Properites:
        /// </summary>
        public int Rows
        {
            get { return m_iRows; }
        }

        public int Cols
        {
            get { return m_iCols; }
        }
        public int[,] GetMaze
        {
            get { return m_iMaze; }
        }
        public int PathCharacter
        {
            get { return iPath; }
            set
            {
                if (value == 0)
                    throw new Exception("Invalid path character specified");
                else
                    iPath = value;
            }
        }
        public bool AllowDiagonals
        {
            get { return diagonal; }
            set { diagonal = value; }
        }
        int[,] iMazeSolved;

        /// <summary>
        /// Indexer
        /// </summary>
        public int this[int iRow, int iCol]
        {
            get { return m_iMaze[iRow, iCol]; }
            set
            {
                m_iMaze[iRow, iCol] = value;
                if (this.OnMazeChangedEvent != null)	// trigger event
                    this.OnMazeChangedEvent(iRow, iCol);
            }
        }

        /// <summary>
        /// The function is used to get the contents of a given node in a given maze,
        ///  specified by its node no.
        /// </summary>
        private int GetNodeContents(int[,] iMaze, int iNodeNo)
        {
            int iCols = iMaze.GetLength(1);
            return iMaze[iNodeNo / iCols, iNodeNo - iNodeNo / iCols * iCols];
        }

        /// <summary>
        /// The function is used to change the contents of a given node in a given maze,
        ///  specified by its node no.
        /// </summary>
        private void ChangeNodeContents(int[,] iMaze, int iNodeNo, int iNewValue)
        {
            int iCols = iMaze.GetLength(1);
            iMaze[iNodeNo / iCols, iNodeNo - iNodeNo / iCols * iCols] = iNewValue;
        }

        /// <summary>
        /// This public function finds the shortest path between two points
        /// in the maze and return the solution as an array with the path traced 
        /// by "iPath" (can be changed using property "PathCharacter")
        /// if no path exists, the function returns null
        /// </summary>
        public int[,] FindPath(int iFromY, int iFromX, int iToY, int iToX)
        {
            int iBeginningNode = iFromY * this.Cols + iFromX;
            int iEndingNode = iToY * this.Cols + iToX;
            return (Search(iBeginningNode, iEndingNode));
        }


        /// <summary>
        /// internal function for that finds the shortest path using a technique
        /// similar to breadth-first search.
        /// It assigns a node no. to each node(2D array element) and applies the algorithm
        /// </summary>
        private enum Status
        { Ready, Waiting, Processed }
        private int[,] Search(int iStart, int iStop)
        {
            
            const int empty = 0;

            int iRows = m_iRows;
            int iCols = m_iCols;
            int iMax = iRows * iCols;
            int[] Queue = new int[iMax];
            int[] Origin = new int[iMax];
            int iFront = 0, iRear = 0;

            //check if starting and ending points are valid (open)
            if (GetNodeContents(m_iMaze, iStart) != empty || GetNodeContents(m_iMaze, iStop) != empty)
            {
                return null;
            }

            //create dummy array for storing status
            int[,] iMazeStatus = new int[iRows, iCols];
            //initially all nodes are ready
            for (int i = 0; i < iRows; i++)
                for (int j = 0; j < iCols; j++)
                    iMazeStatus[i, j] = (int)Status.Ready;

            //add starting node to Q
            Queue[iRear] = iStart;
            Origin[iRear] = -1;
            iRear++;
            int iCurrent, iLeft, iRight, iTop, iDown, iRightUp, iRightDown, iLeftUp, iLeftDown;
            while (iFront != iRear)	// while Q not empty	
            {
                if (Queue[iFront] == iStop)		// maze is solved
                    break;

                iCurrent = Queue[iFront];

                iLeft = iCurrent - 1;
                if (iLeft >= 0 && iLeft / iCols == iCurrent / iCols) 	//if left node exists
                    if (GetNodeContents(m_iMaze, iLeft) == empty) 	//if left node is open(a path exists)
                        if (GetNodeContents(iMazeStatus, iLeft) == (int)Status.Ready)	//if left node is ready
                        {
                            Queue[iRear] = iLeft; //add to Q
                            Origin[iRear] = iCurrent;
                            ChangeNodeContents(iMazeStatus, iLeft, (int)Status.Waiting); //change status to waiting
                            iRear++;
                        }

                iRight = iCurrent + 1;
                if (iRight < iMax && iRight / iCols == iCurrent / iCols) 	//if right node exists
                    if (GetNodeContents(m_iMaze, iRight) == empty) 	//if right node is open(a path exists)
                        if (GetNodeContents(iMazeStatus, iRight) == (int)Status.Ready)	//if right node is ready
                        {
                            Queue[iRear] = iRight; //add to Q
                            Origin[iRear] = iCurrent;
                            ChangeNodeContents(iMazeStatus, iRight, (int)Status.Waiting); //change status to waiting
                            iRear++;
                        }

                iTop = iCurrent - iCols;
                if (iTop >= 0) 	//if top node exists
                    if (GetNodeContents(m_iMaze, iTop) == empty) 	//if top node is open(a path exists)
                        if (GetNodeContents(iMazeStatus, iTop) == (int)Status.Ready)	//if top node is ready
                        {
                            Queue[iRear] = iTop; //add to Q
                            Origin[iRear] = iCurrent;
                            ChangeNodeContents(iMazeStatus, iTop, (int)Status.Waiting); //change status to waiting
                            iRear++;
                        }

                iDown = iCurrent + iCols;
                if (iDown < iMax) 	//if bottom node exists
                    if (GetNodeContents(m_iMaze, iDown) == empty) 	//if bottom node is open(a path exists)
                        if (GetNodeContents(iMazeStatus, iDown) == (int)Status.Ready)	//if bottom node is ready
                        {
                            Queue[iRear] = iDown; //add to Q
                            Origin[iRear] = iCurrent;
                            ChangeNodeContents(iMazeStatus, iDown, (int)Status.Waiting); //change status to waiting
                            iRear++;
                        }
                if (diagonal == true)
                {
                    iRightDown = iCurrent + iCols + 1;
                    if (iRightDown < iMax && iRightDown >= 0 && iRightDown / iCols == iCurrent / iCols + 1) 	//if bottom-right node exists
                        if (GetNodeContents(m_iMaze, iRightDown) == empty) 	//if this node is open(a path exists)
                            if (GetNodeContents(iMazeStatus, iRightDown) == (int)Status.Ready)	//if this node is ready
                            {
                                Queue[iRear] = iRightDown; //add to Q
                                Origin[iRear] = iCurrent;
                                ChangeNodeContents(iMazeStatus, iRightDown, (int)Status.Waiting); //change status to waiting
                                iRear++;
                            }

                    iRightUp = iCurrent - iCols + 1;
                    if (iRightUp >= 0 && iRightUp < iMax && iRightUp / iCols == iCurrent / iCols - 1) 	//if upper-right node exists
                        if (GetNodeContents(m_iMaze, iRightUp) == empty) 	//if this node is open(a path exists)
                            if (GetNodeContents(iMazeStatus, iRightUp) == (int)Status.Ready)	//if this node is ready
                            {
                                Queue[iRear] = iRightUp; //add to Q
                                Origin[iRear] = iCurrent;
                                ChangeNodeContents(iMazeStatus, iRightUp, (int)Status.Waiting); //change status to waiting
                                iRear++;
                            }

                    iLeftDown = iCurrent + iCols - 1;
                    if (iLeftDown < iMax && iLeftDown >= 0 && iLeftDown / iCols == iCurrent / iCols + 1) 	//if bottom-left node exists
                        if (GetNodeContents(m_iMaze, iLeftDown) == empty) 	//if this node is open(a path exists)
                            if (GetNodeContents(iMazeStatus, iLeftDown) == (int)Status.Ready)	//if this node is ready
                            {
                                Queue[iRear] = iLeftDown; //add to Q
                                Origin[iRear] = iCurrent;
                                ChangeNodeContents(iMazeStatus, iLeftDown, (int)Status.Waiting); //change status to waiting
                                iRear++;
                            }

                    iLeftUp = iCurrent - iCols - 1;
                    if (iLeftUp >= 0 && iLeftUp < iMax && iLeftUp / iCols == iCurrent / iCols - 1) 	//if upper-left node exists
                        if (GetNodeContents(m_iMaze, iLeftUp) == empty) 	//if this node is open(a path exists)
                            if (GetNodeContents(iMazeStatus, iLeftUp) == (int)Status.Ready)	//if this node is ready
                            {
                                Queue[iRear] = iLeftUp; //add to Q
                                Origin[iRear] = iCurrent;
                                ChangeNodeContents(iMazeStatus, iLeftUp, (int)Status.Waiting); //change status to waiting
                                iRear++;
                            }
                }


                //change status of current node to processed
                ChangeNodeContents(iMazeStatus, iCurrent, (int)Status.Processed);
                iFront++;

            }

            //create an array(maze) for solution
            iMazeSolved = new int[iRows, iCols];
            for (int i = 0; i < iRows; i++)
                for (int j = 0; j < iCols; j++)
                    iMazeSolved[i, j] = m_iMaze[i, j];

            //make a path in the Solved Maze
            iCurrent = iStop;
            ChangeNodeContents(iMazeSolved, iCurrent, iPath);
            for (int i = iFront; i >= 0; i--)
            {
                if (Queue[i] == iCurrent)
                {
                    iCurrent = Origin[i];
                    if (iCurrent == -1)		// maze is solved
                        return (iMazeSolved);
                    ChangeNodeContents(iMazeSolved, iCurrent, iPath);
                    //iMaze[iNodeNo / iCols, iNodeNo - iNodeNo / iCols * iCols] = iNewValue;
                    int x = iCurrent / iCols;
                    int y = iCurrent - iCurrent / iCols * iCols;
                    retList.Add(new System.Drawing.Point(x, y));
                }
            }

            //no path exists
            return null;
        }
    }

}