Path finding - again

Question

Nearly time to hand this project in, and I want it to be as close to perfect as possible. So, any issue (no matter how small) - let me know. If you have any ideas that would improve the efficiency or readability of my code (e.g. delegates), let me know.

I am already aware that I should use camelCase for variables and PascalCase for methods. I will do that at completion of the code.

AStar class:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;

namespace prjT02L08_Predator_Prey
{
    public class AStar //Variant on Dijkstra's Algorithm - faster
    {
        public static Node[,] Grid; //Using the data type created below to make a grid, a 2 dimensional array of nodes (squares)

    public static List<Node> FindPath(Point start, Point end) //Finds the fastest route from the start to end
    {

        //Checks that we aren't trying to make a path from one place to the same place
        if (start.X == end.X && start.Y == end.Y)
        {
            return null;
        }

        //Resets all the parent variables to clear the paths created last time
        for (int x = 0; x <= Grid.GetUpperBound(0); x++)
        {
            for (int y = 0; y <= Grid.GetUpperBound(1); y++)
            {
                Grid[x, y].Parent = null;
            }
        }

        List<Node> OpenList = new List<Node>(); //Nodes to be considered, ones that may be on the path
        //The above OpenList would be better as an OrderedList, however, I wanted to implement my own sort
        //An even better solution, and more "complex", would be to implement a Red-Black Tree
        //I can get this to work, but am unsure about how to add a delete() method


        //List<Node> ClosedList = new List<Node>();
        //This is replaced by the dictionary below - Faster sorting using a key

        //Dictionary<UInt64, Node> ClosedList = new Dictionary<UInt64,Node>();
        //This is replaced by the HashSet below - O(1) instead of O(n) for searching and removing data.
        //Also O(1) for adding, unless the size needs to be increased (then O(n))

        HashSet<Node> ClosedList = new HashSet<Node>(); //Explored nodes


        Point CurrentPoint = new Point(0, 0);
        Node Current = null;
        List<Node> Path = null;

        OpenList.Add(Grid[start.X, start.Y]); //Add the starting point to OpenList

        while (OpenList.Count > 0)
        {
            //Explores for the "best" choice in the Openlist
            Current = OpenList[0];
            CurrentPoint.X = Current.X;
            CurrentPoint.Y = Current.Y;
            if (CurrentPoint == end) break; //If we have reached the end

            OpenList.RemoveAt(0); //Removes the starting point
            ClosedList.Add(Current);

            foreach (Node neighbour in GetNeighbours(CurrentPoint)) //Checks all the squares adjacent to the current point
            {
                //Skips fully explored nodes which have been explored fully
                if (ClosedList.Contains(neighbour)) continue;

                //Skips the node if it's a wall
                if (neighbour.IsWall) continue;

                //If parent is null, it's our first visit to the node
                if (neighbour.Parent == null)
                {
                    neighbour.G = Current.G + 10; //10 is the cost for each horizontal or vertical node moved
                    neighbour.Parent = Current; //Where it came from, final path can be found by linking parents

                    //The following way of calculating the H value is called the Manhattan method, it ignores any obstacles
                    neighbour.H = Math.Abs(neighbour.X - end.X)
                        + Math.Abs(neighbour.Y - end.Y); //Calculates total cost by combining the X distance by the Y
                    neighbour.H *= 10; //Then multiply H by 10 (The cost movement for each square)
                    OpenList.Add(neighbour);
                }
                else
                {
                    //Is this a more efficient route than last time?
                    if (Current.G + 10 < neighbour.G)
                    {
                        neighbour.Parent = Current;
                        neighbour.G = Current.G + 10;
                    }
                }
            }

            //OpenList.Sort(); //This uses the IComparible interface and CompareWith() method to sort
            //This is very slow to do every time
            //Could be replaced with a SortedSet
            //Also very slow - O(In N)

            OpenList = MergeSort.Sort(OpenList).ToList();
        }

        //If we finished, end will have a parent, otherwise not
        Path = new List<Node>();
        Current = Grid[end.X, end.Y]; //Current = end desination node
        Path.Add(Current);
        while (Current.Parent != null) //Won't run if end doesn't have a parent
        {
            Path.Add(Current.Parent);
            Current = Current.Parent;
        }

        //Path.Reverse();
        //.reverse() (Above) is replaced with the below code
        for (int i = 0; i < Path.Count() / 2; i++)
        {
            Node Temp = Path[i];
            Path[i] = Path[Path.Count() - i - 1];
            Path[Path.Count() - i - 1] = Temp;
        }

        //Checks if we've found our path or used all our options
        return OpenList.Count > 1 ? Path : null;
        //Below replaced by Ternary Statement above
        /*if (OpenList.Count > 1)
            return Path;
        else
            return null;*/
    }

    private static List<Node> GetNeighbours(Point p) //Finds all adjacent nodes to the node at point p
    {
        List<Node> Result = new List<Node>();

        //All the IF statements below are to check that we're not adding nodes outside of the grid, causing an error
        //All the code within the IF statements add the nodes adjacent to the node at point p

        if (p.X - 1 >= 0)
        {
            Result.Add(Grid[p.X - 1, p.Y]); //Left
        }

        if (p.X < Grid.GetUpperBound(0))
        {
            Result.Add(Grid[p.X + 1, p.Y]); //Right
        }

        if (p.Y - 1 >= 0)
        {
            Result.Add(Grid[p.X, p.Y - 1]); //Below
        }

        if (p.Y < Grid.GetUpperBound(1))
        {
            Result.Add(Grid[p.X, p.Y + 1]); //Above
        }

        return Result; //Returns all neighbours
    }
}
}

Node class:

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

namespace prjT02L08_Predator_Prey

{
    public class Node// : IComparable<Node> //Inherits from the interface IComparable, allows the nodes to be sorted using .sort()
    {
        public int X; //Position on the X axis
        public int Y; //Position on the Y axis
        public Node Parent; //The node which this node has just come from
        public bool IsWall; //States whether the given node is a wall or not
        public int G; //The amount needed to move from the starting node to the given other
        public int H; //The estimated cost to move from that given node to the end point - Called Heuristic (Because it's a guess)
        public int F //G+H
        {
            get { return G + H; } //Automatically calculates the latest value when F is accessed
        }

    /*This must be added due to IComparable (It requires a method called "CompareTo" to work)
    - specifies how to sort the nodes*/
    //public int CompareTo(Node other)
    //{
    //    if (this.F < other.F) return -1;
    //    else if (this.F == other.F) return 0;
    //    else return 1;
    //}

    //If a bool is given to reset G, H and Parent then this resets them back to the default values, otherwise makes Result equal to this node
    public Node Clone(bool ResetGHandParent)
    {
        Node Result = new Node();
        Result.X = this.X;
        Result.Y = this.Y;
        Result.IsWall = this.IsWall;
        if (ResetGHandParent)
        {
            Result.G = 0;
            Result.H = 0;
            Result.Parent = null;
        }
        else
        {
            Result.G = this.G;
            Result.H = this.H;
            Result.Parent = this.Parent;
        }
        return Result;
    }

    //Same as above, but in case the boolean isn't given - false is assumed
    public Node Clone()
    {
        //The code below sets all the variables of results to the same variables of the current node
        Node Result = new Node();
        Result.X = this.X;
        Result.Y = this.Y;
        Result.IsWall = this.IsWall;
        Result.G = this.G;
        Result.H = this.H;
        return Result;
    }

    public static Node[,] MakeGrid(int Width, int Height) //This function is just to prevent any accidental errors I may make in the Form1 by not wanting any walls
    {
        //If a value isn't set for PercentWallChance in Form1, we assume they don't want walls and set the chance to 0
        return MakeGrid(Width, Height, 0); //Calls upon the other make grid, so no code is repeated, with 0 as the PercentWallChance
    }

    public static Node[,] MakeGrid(int Width, int Height, int PercentWallChance) //Same name as the MakeGrid above, but with different parameters
    {
        Node[,] Result = new Node[Width, Height]; //Produces the grid
        Random r = new Random(); //A random variable to be used later in this method

        //These two loops mean all nodes in the grid are covered - from 0, 0 to Width - 1, Height - 1
        for (int x = 0; x < Width; x++) //Loops through all X co-ordinates
        {
            for (int y = 0; y < Height; y++) //Loops through all Y co-ordinates
            {
                //Sets all the variables within the Result nodes to default values
                Result[x, y] = new Node();
                Result[x, y].Parent = null; //It has no parent as it hasn't been explored
                Result[x, y].X = x; //Sets it's X location
                Result[x, y].Y = y; //Sets it's Y location
                Result[x, y].G = 0; //Not in use yet
                Result[x, y].H = 0; //Not in use yet

                //This section of code below confuses me, so I will reference Jaz's comments:
                //This takes advantage of the fact that < is a comparison operator, and will give a boolean result
                //r.Next(100) will generate a number from 0 to 99.
                //If % wallchance is 100, then r cannot NOT be less than it, and the "<" will always return true (which in turn always sets IsWall to true)
                //If % wallchance is 0, then r literally cannot be less it, and the comparison will return false (which in turn always  sets IsWall to false)
                Result[x, y].IsWall = r.Next(100) < PercentWallChance;
            }
        }
        return Result; //Returns the grid
    }
}
}

Answer 1

• It is better to declare by interface instead of implementation.

  List<Node> OpenList = new List<Node>();
  HashSet<Node> ClosedList = new HashSet<Node>();
  

  Can become:

  IList<Node> OpenList = new List<Node>();
  ISet<Node> ClosedList = new HashSet<Node>();
  

  This allows you to more easily change the implementation without having to change on multiple spaces. (This is extra important when passing objects between methods!)

• Initialize CurrentPoint to null instead of creating a new point at (0, 0). That point is currently not used.

• 3 10 is a magic number, yes it is, it's a magic number. If you would like to change the move cost on the map you would have to modify at multiple places, modifying some but not all of the occurrences would lead to unexpected behavior (bugs!). Declare a const int MoveCost = 10; and use that throughout your code.

• I am not so sure about that ternary statement and the condition OpenList.Count > 1. It's been a while since I used A* but I believe it's possible for all nodes to be added to ClosedList and thus the entire map has been exhausted before finally a path was found (consider a map where there is only one possible path to go, entirely surrounded by walls). I would use a different condition here, like Path.Count > 1.

• In your GetNeighbours method you can use the yield keyword and use the return type IEnumerable<Node> to avoid having to initialize a list.

• Split the FindPath method at least in two, one for reaching the goal and one for backtracking.

• Overall, your code is well formatted and very easy to read. You use quite good variable and method names. It has been a pleasure reading your code. You seem to know what you are doing and I hope you will continue on your path. (Where-ever the ClosedList leads you)

Answer 2

Just a couple random observations...

public int X; //Position on the X axis
public int Y; //Position on the Y axis
public Node Parent; //The node which this node has just come from
public bool IsWall; //States whether the given node is a wall or not
public int G; //The amount needed to move from the starting node to the given other
public int H; //The estimated cost to move from that given node to the end point - Called Heuristic (Because it's a guess)
public int F //G+H
{
    get { return G + H; } //Automatically calculates the latest value when F is accessed
}

Except for F (a get-only property), those are public fields, it would probably be best to turn them into properties.

The naming for G, H and F is... without XML comments, not meaningful at all. Naming is hard, but it's worth taking the time to name things properly, for readability's sake.

I find it odd that you're using a Point in GetNeighbours, but that you're not using it as a single Location property for your nodes (instead of having a int X and a int Y field/property, I'd have a single Point Location property there).

F has no reason to be public, it's only used in IComparable.CompareTo and could very well be made private.

---

That part:

Result[x, y] = new Node();
Result[x, y].Parent = null; //It has no parent as it hasn't been explored
Result[x, y].X = x; //Sets it's X location
Result[x, y].Y = y; //Sets it's Y location
Result[x, y].G = 0; //Not in use yet
Result[x, y].H = 0; //Not in use yet

Would be clearer it written like this:

var node = new Node 
   { 
       Location = new Point(x, y),
       Parent = null, // redundant default value
       G = 0, // redundant default value
       H = 0, // redundant default value 
       IsWall = r.Next(100)
   };
result[x, y] = node;

Now from what I'm reading, it looks like a Node's Location and IsWall members should be readonly. You can enforce this with a constructor:

public Node(Point location, bool isWall)
{
    _location = location;
    _isWall = isWall;
}

private readonly Point _location;
public Point Location { get { return _location; } }

private bool _isWall;
public bool IsWall { get { return _isWall; } }

Introducing a parameterized constructor will remove the class' default, parameterless constructor unless you explicitly provide one, but here it wouldn't be needed. Instead, you can change your newing up code to this:

var node = new Node(new Point(x, y), r.Next(100));
result[x, y] = node;

---

The Point structure overrides ValueType.Equals, which means this condition:

if (start.X == end.X && start.Y == end.Y)

Could be rewritten like this:

if (start.Equals(end))