I've created a functional A* implementation in C#/XNA for a game I'm working on. However, I am using rather large paths, and of course, the larger the paths are, the longer it takes to trace them. There is no way to shorten the paths (Thin Maze - Style) and I assume this is a horrid way to implement it. I followed a tutorial, and hope I can get some help in optimizing it.    static public List<Point> FindPath(Point Start, Point End)    {        List<Square> Open = new List<Square>();        List<Square> Closed = new List<Square>();        Open.Add(new Square(Start));        Square currentSquare = Open[0];        Square PS = new Square(new Point(0, 0));        int index = 0;        int Dupes = 0;        while (Open.Count > 0 && currentSquare.Pos != End && index < 1000 && Dupes < 1)        {            if (currentSquare == PS)            {                Dupes++;            }            else            {                Dupes = 0;            }            index++;            Open.Sort(new CompareSquareH());            currentSquare = Open[0];            Closed.Add(currentSquare);            Open.Remove(currentSquare);            for (int x = -1; x <= 1; x++)            {                for (int y = -1; y <= 1; y++)                {                    if (!(x == -1 && y == -1) && !(x == 1 && y == -1) && !(x == 1 && y == 1) && !(x == -1 && y == 1))                    {                        if (x + currentSquare.Pos.X > 0 && x + currentSquare.Pos.X < ED.LoadedMap.Tiles.GetLength(0) && y + currentSquare.Pos.Y > 0 && y + currentSquare.Pos.Y < ED.LoadedMap.Tiles.GetLength(1))                        {                            if (!ED.LoadedMap.Tiles[x + currentSquare.Pos.X, y + currentSquare.Pos.Y].Solid)                            {                                bool pass = true;                                foreach (Square S in Closed)                                {                                    if (S.Pos == new Point(currentSquare.Pos.X + x, currentSquare.Pos.Y + y))                                    {                                        pass = false;                                        break;                                    }                                }                                if (pass)                                {                                    foreach (Square S in Open)                                    {                                        if (S.Pos == new Point(currentSquare.Pos.X + x, currentSquare.Pos.Y + y))                                        {                                            pass = false;                                            break;                                        }                                    }                                    Open.Add(new Square(new Point(currentSquare.Pos.X + x, currentSquare.Pos.Y + y), currentSquare, H(currentSquare.Pos.X + x, End.X, currentSquare.Pos.Y + y, End.Y)));                                }                            }                        }                    }                }            }        }        if (Open.Count > 0 && currentSquare.Pos == End && index < 1000)        {            List<Point> Final = new List<Point>();            while (currentSquare.Parent != null)            {                Final.Add(new Point(currentSquare.Pos.X, currentSquare.Pos.Y));                currentSquare = currentSquare.Parent;            }            Final.Reverse();            return Final;        }        else        {            return new List<Point>();        }    }    static public List<Point> FindPath(Point Start, Point End)    {        List<Square> Open = new List<Square>();        List<Square> Closed = new List<Square>();        Open.Add(new Square(Start));        Square currentSquare = Open[0];        Square PS = new Square(new Point(0, 0));        int index = 0;        int Dupes = 0;        while (Open.Count > 0 && currentSquare.Pos != End && index < 1000 && Dupes < 1)        {            if (currentSquare == PS)            {                Dupes++;            }            else            {                Dupes = 0;            }            index++;            Open.Sort(new CompareSquareH());            currentSquare = Open[0];            Closed.Add(currentSquare);            Open.Remove(currentSquare);            for (int x = -1; x <= 1; x++)            {                for (int y = -1; y <= 1; y++)                {                    if (!(x == -1 && y == -1) && !(x == 1 && y == -1) && !(x == 1 && y == 1) && !(x == -1 && y == 1))                    {                        if (x + currentSquare.Pos.X > 0 && x + currentSquare.Pos.X < ED.LoadedMap.Tiles.GetLength(0) && y + currentSquare.Pos.Y > 0 && y + currentSquare.Pos.Y < ED.LoadedMap.Tiles.GetLength(1))                        {                            if (!ED.LoadedMap.Tiles[x + currentSquare.Pos.X, y + currentSquare.Pos.Y].Solid)                            {                                bool pass = true;                                foreach (Square S in Closed)                                {                                    if (S.Pos == new Point(currentSquare.Pos.X + x, currentSquare.Pos.Y + y))                                    {                                        pass = false;                                        break;                                    }                                }                                if (pass)                                {                                    foreach (Square S in Open)                                    {                                        if (S.Pos == new Point(currentSquare.Pos.X + x, currentSquare.Pos.Y + y))                                        {                                            pass = false;                                            break;                                        }                                    }                                    Open.Add(new Square(new Point(currentSquare.Pos.X + x, currentSquare.Pos.Y + y), currentSquare, H(currentSquare.Pos.X + x, End.X, currentSquare.Pos.Y + y, End.Y)));                                }                            }                        }                    }                }            }        }        if (Open.Count > 0 && currentSquare.Pos == End && index < 1000)        {            List<Point> Final = new List<Point>();            while (currentSquare.Parent != null)            {                Final.Add(new Point(currentSquare.Pos.X, currentSquare.Pos.Y));                currentSquare = currentSquare.Parent;            }            Final.Reverse();            return Final;        }        else        {            return new List<Point>();        }    }    static int H(int X1, int X2, int Y1, int Y2)    {        return Math.Abs(X1 - X2) + Math.Abs(Y1 - Y2) + ED.LoadedMap.Tiles[X1,X2].GetCost();    }}public class Square{    public Square(Point pos, Square parent, int h)    {        Pos = pos;        Parent = parent;        H = h;    }    public Square(Point pos)    {        Pos = pos;    }    public int H;    public Point Pos;    public Square Parent;}public class CompareSquareH : IComparer<Square>{    int IComparer<Square>.Compare(Square x, Square y)    {        if (x.H > y.H)        {            return 1;        }        if (x.H < y.H)        {            return -1;        }        return 0;    }}
A* Implementation results in exponential speed loss
c#;performance;algorithm;pathfinding
The #1 mistake I see in new A* implementations, which is the mistake you've made, is not using a priority queue for the open set, and not using a better data structure than a list (e.g. a tree or hash map) for the closed set. That means operations like:Open.Sort(new CompareSquareH());currentSquare = Open[0];Closed.Add(currentSquare);Open.Remove(currentSquare);Require O(n * lg n) for the sort, O(n) for the add, and O(n) for the removal. Likewise, checks like finding whether a node is in the open or closed set, for which you used:foreach (Square S in Closed)Are obviously O(n), when with other structures like a tree or hashed set they can take O(lg n) or O(1).This adds entire orders of magnitude to the computation time required.The tutorial you have found looks pretty awful (although it does mention this). I recommend instead Amit's A* pages, particularly the section on implementing the open and closed sets.