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

namespace PushBox
{
    public class ObjectPoint
    {
        public int X;
        public int Y;
        public ObjectPoint()
        {
            X = 0;
            Y = 0;
        }
        public ObjectPoint(int x, int y)
        {
            X = x;
            Y = y;
        }
    }
    public class Node
    {
        private double g = 0;//父點到當前點的耗費
        private double h = 0;//當前點到終點的耗費
        private int x = 0;  //坐標
        private int y = 0;
        public double F //總耗費
        {
            get
            {
                return g + h;
            }
        }
        public double G
        {
            get
            {
                return g;
            }
            set
            {
                g = value;
            }
        }
        public double H
        {
            get
            {
                return h;
            }
            set
            {
                h = value;
            }
        }
        public int X
        {
            get
            {
                return x;
            }
            set
            {
                x = value;
            }
        }
        public int Y
        {
            get
            {
                return y;
            }
            set
            {
                y = value;
            }
        }
        private bool canMove = true;
        public bool CanMove
        {
            get
            {
                return canMove;
            }
            set
            {
                canMove = value;
            }
        }
        protected Node parentNode = null;
        public Node ParentNode
        {
            get
            {
                return parentNode;
            }
            set
            {
                parentNode = value;
            }
        }
    }
    public class Finder
    {
        private System.Collections.ArrayList openLine = new System.Collections.ArrayList();
        private System.Collections.ArrayList closeLine = new System.Collections.ArrayList();
        private Node[] fn;
        private ObjectPoint startOP = null;
        private ObjectPoint endOP = null;
        public Finder(Node[] afn)
        {
            fn = afn;
        }
        //設置所有節點的H值；
        private void SetH()
        {
            for (int i = 0; i < fn.Length; i++)
            {
                fn[i].H = Math.Abs(endOP.X - fn[i].X) + Math.Abs(endOP.Y - fn[i].Y);
            }
        }
        public Node GetNode(int ax, int ay)
        {
            for (int i = 0; i < fn.Length; i++)
            {
                if ((fn[i].X == ax) && (fn[i].Y == ay))
                {
                    return fn[i];
                }
            }
            return null;
        }
        public bool CanFind()
        {
            Node bn = GetNode(this.endOP.X, endOP.Y);
            if (bn == null) return false;
            for (int i = 0; i < openLine.Count; i++)
            {
                if (bn == openLine[i]) return true;
            }
            return false;
        }
        protected bool IsInOpenLine(Node afn)
        {
            for (int i = 0; i < this.openLine.Count; i++)
            {
                if (afn == openLine[i]) return true;
            }

            return false;
        }
        protected bool IsInCloseLine(Node afn)
        {
            for (int i = 0; i < this.closeLine.Count; i++)
            {
                if (afn == closeLine[i]) return true;
            }
            return false;
        }
        protected void AddToOpenLine(Node afn)
        {
            if (!afn.CanMove) return;  //如果不能移動的就不加了。
            for (int i = 0; i < this.openLine.Count; i++)
            {
                if (afn == openLine[i]) return;
            }
            for (int i = 0; i < this.closeLine.Count; i++)
            {
                if (afn == closeLine[i]) return;
            }
            //排序
            for (int i = 0; i < this.openLine.Count; i++)
            {
                if (afn.F <= ((Node)openLine[i]).F)
                {
                    openLine.Insert(i, afn);
                    return;
                }
            }
            openLine.Add(afn);
        }
        protected void AddToCloseLine(Node afn)
        {
            for (int i = 0; i < this.closeLine.Count; i++)
            {
                if (afn == closeLine[i]) return;
            }
            closeLine.Add(afn);
        }
        //找出并設置相領的節點.
        protected void FindNearNode(Node afn)
        {
            int mx, my;
            mx = afn.X;
            my = afn.Y;
            FindNearNodeXY(afn, mx - 1, my);
            FindNearNodeXY(afn, mx + 1, my);
            FindNearNodeXY(afn, mx, my - 1);
            FindNearNodeXY(afn, mx, my + 1);
            this.openLine.Remove(afn);
            this.AddToCloseLine(afn);
        }
        protected void FindNearNodeXY(Node afn, int ax, int ay)
        {
            Node newNode = null;
            newNode = GetNode(ax, ay);
            if (newNode != null)
            {
                if (!newNode.CanMove)
                {
                    AddToCloseLine(newNode);
                    return;
                }
                if ((!IsInOpenLine(newNode)) && (!IsInCloseLine(newNode)))
                {
                    newNode.ParentNode = afn;
                    newNode.G = afn.G + 10;
                    AddToOpenLine(newNode);
                }
                else
                {
                    if ((!IsInCloseLine(newNode)) && (newNode.F > afn.F + 10))
                    {
                        newNode.ParentNode = afn;
                        newNode.G = afn.G;
                    }
                }
            }
        }
        public string Find(ObjectPoint aStartOP, ObjectPoint aEndOP)
        {
            this.startOP = new ObjectPoint(aStartOP.X, aStartOP.Y);
            this.endOP = new ObjectPoint(aEndOP.X, aEndOP.Y);

            Node SP = GetNode(startOP.X, startOP.Y);

            SP.G = 0;

            this.SetH();
            AddToOpenLine(GetNode(startOP.X, startOP.Y));
            while ((!CanFind()) && openLine.Count > 0)
            {
                this.FindNearNode((Node)(openLine[0]));
            }
            //找出了以后
            Node EP = GetNode(endOP.X, endOP.Y);
            string str = "";
            if (EP.ParentNode == null) return "false";
            while (EP.ParentNode != SP)
            {
                str = (EP.ParentNode.Y * 15 + EP.ParentNode.X).ToString() + "F" + str;
                EP = EP.ParentNode;
            }
            str += (endOP.Y * 15 + endOP.X).ToString() + "F";
            return str;
        }
    }
}