Astar.cs

/*
 * A* Pathfinding Algorithm
 * Modified from my solution to the "After the Dance Battle" challenge
 *   in the 2011 Facebook Hacker Cup
 * by Andrew Brown
 * Last modified: 1/14/11
 */

using System;
using System.IO;
using System.Collections.Generic;

namespace Astar
{
    class Pathfinding
    {
        public const int UNKNOWN = 99999999;

        // Returns a list of coordinates corresponding to the minimum number of moves
        // required to move from start to end in map.
        public static List<Coordinate> AstarPath(Map map, Coordinate start, Coordinate end)
        {
            List<Coordinate> moves = new List<Coordinate>();
            List<Node> neighbors;

            int moves_needed = AstarPrep(map, start, end);
            if (moves_needed == Pathfinding.UNKNOWN)
            {
                throw new Exception("Seems to be an impossible destination!");
            }

            // Work back from the end, follow the path of lower numbers
            Coordinate curloc = end;
            while (curloc != start)
            {
                moves.Add(curloc);

                neighbors = map.GetSurroundingNodes(curloc);
                foreach (Node n in neighbors)
                {
                    if (n.distance_from_start < map.GetNode(curloc).distance_from_start)
                    {
                        curloc = n;
                    }
                }
            }

            moves.Reverse();
            return moves;
        }

        // A* meat
        // Modifies map; returns the number of moves needed to get from start
        // to end in map.
        private static int AstarPrep(Map map, Coordinate start, Coordinate end)
        {
            List<Node> queue   = new List<Node>();
            List<Node> history = new List<Node>();
            int moves_needed   = UNKNOWN;

            // Start position
            map.GetNode(start.X, start.Y).distance_from_start = 0;
            queue.Add(map.GetNode(start.X, start.Y));

            while (queue.Count > 0)
            {
                // Pop queue
                Node curloc = queue[queue.Count - 1];
                queue.RemoveAt(queue.Count - 1);

                // Add to history
                history.Add(curloc);

                // Neighbors onto queue
                List<Node> neighbors = map.GetSurroundingNodes(curloc);
                foreach (Node n in neighbors)
                {
                    // Neighbor = wall?
                    if (n.value == Map.S_WALL)
                    {
                        history.Add(n);
                        continue;
                    }

                    // Neighbor = end?
                    if (n.value == Map.S_END)
                    {
                        if (curloc.distance_from_start + 1 < moves_needed)
                        {
                            moves_needed = curloc.distance_from_start + 1;
                            n.distance_from_start = curloc.distance_from_start + 1;
                        }
                        history.Add(curloc);
                        continue;
                    }

                    // Update neighbors with min(new, old) distance
                    if (curloc.distance_from_start + 1 < n.distance_from_start)
                    {
                        n.distance_from_start = curloc.distance_from_start + 1;
                    }

                    // Queue if we haven't been there and we aren't queued already
                    if (!history.Contains(n) && !queue.Contains(n))
                    {
                        queue.Add(n);
                    }
                }

                // Next!
            }

            if (moves_needed == UNKNOWN)
            {
                throw new Exception("Impossible path");
            }

            return moves_needed;
        }

    }

    // Map class modeled for Facebook Hacker Cup "After the Dance Battle" puzzle
    class Map
    {
        public const char S_WALL  = 'W';
        public const char S_START = 'S';
        public const char S_END   = 'E';
        public const char S_EMPTY = '.';

        private int height, width;
        private char[,] data;
        private List<Node> nodes;

        private Coordinate start, end;
        private List<Coordinate> walls = new List<Coordinate>();

        public Map(string raw)
        {
            string[] split = raw.Split(' ');

            try
            {
                height = Convert.ToInt32(split[0]);
                width  = Convert.ToInt32(split[1]);
                data   = new char[height, width];
            }
            catch
            {
                throw new Exception("Something is horrendously wrong with the input file");
            }

            for (int y = 0; y < height; y++)
            {
                string row = split[y + 2];
                for (int x = 0; x < width; x++)
                {
                    data[y, x] = row[x];

                    switch (row[x])
                    {
                        case S_START:
                            start = new Coordinate(x, y);
                            break;
                        case S_END:
                            end = new Coordinate(x, y);
                            break;
                        case S_WALL:
                            walls.Add(new Coordinate(x, y));
                            break;
                    }
                }
            }

            InitNodes();

        }

        public static List<Map> FromFile(string filename)
        {
            StreamReader fin  = new StreamReader(filename);
            List<Map>    maps = new List<Map>();

            int cases = Convert.ToInt32(fin.ReadLine());
            for (int c = 0; c < cases; c++)
            {
                fin.ReadLine(); // Clear the \n between each map
                string[] line   = fin.ReadLine().Split(' ');
                int      height = Convert.ToInt32(line[0]);
                int      width  = Convert.ToInt32(line[1]);

                string raw = String.Format("{0} {1}", height, width);
                for (int i = 0; i < height; i++)
                {
                    raw = String.Format("{0} {1}", raw, fin.ReadLine());
                }

                maps.Add(new Map(raw));
            }

            fin.Close();
            return maps;
        }

        void InitNodes()
        {
            nodes = new List<Node>();
            for (int y = 0; y < height; y++)
            {
                for (int x = 0; x < width; x++)
                {
                    nodes.Add(new Node(this, x, y));
                }
            }

        }

        public void PrintDebugDistances()
        {
            for (int i = 0; i < nodes.Count; i++)
            {
                string symbol = nodes[i].distance_from_start.ToString();

                // Empty (0) nodes
                if (nodes[i].distance_from_start == Pathfinding.UNKNOWN)
                {
                    symbol = S_EMPTY.ToString();
                }

                // Special nodes
                switch (nodes[i].value)
                {
                    case S_WALL:
                    case S_END:
                        symbol = nodes[i].value.ToString();
                        break;
                }

                Console.Write("{0,2} {1}",
                    symbol, ((i + 1) % width == 0 ? "\n" : ""));

            }
        }

        public List<Node> GetSurroundingNodes(Coordinate loc)
        {
            List<Node> surrounding = new List<Node>();

            int base_index = loc.Y * width + loc.X;

            // Up
            if (loc.Y > 0)
            {
                surrounding.Add(GetNode(loc.X, loc.Y - 1));
            }

            // Right
            if (loc.X + 1 < width)             {
                 surrounding.Add(GetNode(loc.X + 1, loc.Y));
            }

             // Left
             if (loc.X > 0)
            {
                surrounding.Add(GetNode(loc.X - 1, loc.Y));
            }

            // Down
            if (loc.Y + 1 < height)
            {
                surrounding.Add(GetNode(loc.X, loc.Y + 1));
            }

            return surrounding;
        }

        public Node GetNode(int x, int y)
        {
            return nodes[y * width + x];
        }

        public Node GetNode(Coordinate c)
        {
            return GetNode(c.X, c.Y);
        }

        #region Accessors/Mutators
        public Coordinate Start
        {
            get { return start; }
            set { start = value; }
        }

        public Coordinate End
        {
            get { return end; }
            set { end = value; }
        }

        public List<Coordinate> Walls
        {
            get { return walls; }
        }

        public List<Node> Nodes
        {
            get { return nodes; }
        }

        public char[,] Data
        {
            get { return data; }
        }
        #endregion
    }

    class Coordinate
    {
        private int x, y;

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

        public int X { get { return x; } set { x = value; } }
        public int Y { get { return y; } set { y = value; } }

        public override string ToString()
        {
            return String.Format("({0}, {1})", x, y);
        }

        public static bool operator ==(Coordinate a, Coordinate b)
        {
            return (a.X == b.X && a.Y == b.Y);
        }

        public static bool operator !=(Coordinate a, Coordinate b)
        {
            return !(a == b);
        }

        public override bool Equals(object obj)
        {
            return base.Equals(obj);
        }

        public override int GetHashCode()
        {
            return base.GetHashCode();
        }
    }

    class Node : Coordinate
    {
        public char value;
        public int distance_from_start;

        public Node(Map m, int x, int y)
            : base(x, y)
        {
            distance_from_start = Pathfinding.UNKNOWN;
            value = m.Data[y, x];
        }

        public Node(Map m, Coordinate c) : this(m, c.X, c.Y) { }
    }

}