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

public class Test
{
    public class Node
    {
        public readonly int x, y;
        public int Hcost, Gcost;
        bool Blockade;
        public Node Parent;
        public int FCost
        {
            get
            {
                return Hcost + Gcost;
            }
        }

        public bool isBlockade()
        {
            return Blockade;
        }

        public void SetToBlockade()
        {
            Blockade = true;
        }

        public bool IsEqualTo(Node node)
        {
            return this.x == node.x && this.y == node.y;
        }

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

    static List<Node> allNodes = new List<Node>();
    static List<Node> openList = new List<Node>(), closedList = new List<Node>(), blockadesList = new List<Node>();
    static Node current, StartNode, EndNode;
    static int Width = 20, Height = 10;

    public static void Main()
    {
        //create nodes
        for (int y = 1; y <= Height; y++)
        {
            for(int x = 1; x <= Width; x++)
            {
                Node n = new Node(x, y);
                allNodes.Add(n);
                if (x == 1 && y == 1) StartNode = n;
                else if (x == Width && y == Height) EndNode = n;
            }
        }
        openList.Add(StartNode);
        while(openList.Count > 0)
        {
            current = openList[0];
            for (int y = current.y + 1; y >= current.y - 1; y--)
            {
                for (int x = current.x - 1; x <= current.x + 1; x++)
                {
                    if (!(x == current.x && y == current.y) && y > 0 && y <= Height && x > 0 && x <= Width)
                    {
                        Node searchedNode = allNodes.Find(item => item.x == x && item.y == y);
                        if (!openList.Contains(searchedNode) && !closedList.Contains(searchedNode) && !searchedNode.isBlockade())
                        {
                            //set parent
                            searchedNode.Parent = current;
                            if (searchedNode.IsEqualTo(EndNode))
                            {
                                Console.WriteLine("i found way");
                                break;
                            }
                            //calc Gcost
                            if (y == current.y + 1 && x == current.x - 1 ||
                                y == current.y + 1 && x == current.x + 1 ||
                                y == current.y - 1 && x == current.x - 1 ||
                                y == current.y + 1 && x == current.x + 1) searchedNode.Gcost = current.Gcost + 14;
                            else searchedNode.Gcost = current.Gcost + 10;
                            //calc Hcost
                            if (y >= current.y)
                            {
                                if (x >= current.x)
                                {
                                    searchedNode.Hcost = (y - current.y) + (x - current.x);
                                }
                                else
                                {
                                    searchedNode.Hcost = (y - current.y) + (current.x - x);
                                }
                            }
                            else
                            {
                                if (x >= current.x)
                                {
                                    searchedNode.Hcost = (current.y - y) + (x - current.x);
                                }
                                else
                                {
                                    searchedNode.Hcost = (current.y - y) + (current.x - x);
                                }
                            }

                            openList.Add(searchedNode);
                        }
                    }
                    else Console.WriteLine("this node doesnt exist!");
                }
            }
            closedList.Add(current);
            openList.Remove(current);
            openList = openList.OrderBy(f => f.FCost).ToList(); //sort list by Fcost

            //check that some nodes didnt have the same Fcost
            for (int i = 0; i < openList.Count; i++)
            {
                for (int y = 0; y < openList.Count; y++)
                {
                    if (!openList[i].IsEqualTo(openList[y]) && openList[i].FCost == openList[y].FCost)
                    {
                        if (openList[i].Hcost <= current.Hcost) openList[0] = openList[i];
                        else openList[0] = openList[y];
                    }
                }
            }
        }
        //create path
        Node NextNode;
        List<Node> Path = new List<Node>();
        NextNode = current;
        while(NextNode.Parent != null)
        {
            Path.Add(NextNode);
            NextNode = NextNode.Parent;
        }
        for (int y = Height; y >= 1; y--)
        {
            for (int x = 1; x <= Width; x++)
            {
                Node DrawedNode = new Node(x, y);
                if (x == StartNode.x && y == StartNode.y) Console.Write("A");
                else if (x == EndNode.x && y == EndNode.y) Console.Write("B");
                else if (Path.Contains(DrawedNode)) Console.Write("O");
                else if (blockadesList.Contains(DrawedNode)) Console.Write("X");
                else Console.Write(".");
            }
            Console.WriteLine();
        }
        Console.Write(openList.Count);
        Console.Read();
    }
}