# Path finding - again

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;

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

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)
}
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
while (Current.Parent != null) //Won't run if end doesn't have a 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)
{
}

if (p.X < Grid.GetUpperBound(0))
{
}

if (p.Y - 1 >= 0)
{
}

if (p.Y < Grid.GetUpperBound(1))
{
}

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
}
}
}

• 1. Split that giant method into smaller methods 2. Don't use List, use the correct data structure for the open list and the closed list. 3. If the graph is unweighted, why use a weight of 10 rather than just 1? – BlueRaja - Danny Pflughoeft Sep 1 '13 at 5:33
• @BlueRaja-DannyPflughoeft What do you mean don't use List? What should I use instead, where and why? – Shivam Malhotra Sep 1 '13 at 5:34
• Sorry, I was still writing my comment. openList is supposed to be a priority queue - I linked above to an implementation I wrote which is specifically optimized for pathfinding. The closedList should be a set with O(1) .Add() and .Contains(), such as a HashSet<T>. Doing this should significantly speed up your pathfinding, while simultaneously making your code easier to read. – BlueRaja - Danny Pflughoeft Sep 1 '13 at 5:39
• A simple one would not be too difficult if you understand how a heap works. But, if this is for an assignment, I would just not use one. Though, I'm surprised your professor didn't provide you with one - emulating a priority queue with a list will cause A* to run insanely slower. – BlueRaja - Danny Pflughoeft Sep 1 '13 at 6:11
• @BlueRaja-DannyPflughoeft you should post all your comments as one answer to this post, so that it shows it has been answered, it looks like you have helped the OP Quite a bit, you should get credit for it. – Malachi Oct 31 '13 at 18:49

• 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)

• I'd mention, that the declaration by interface becomes useless when you want to access implementation-specific methods. Thus it somewhat depends on what you want to use, but as there's nothing specific used in OP's code I guess it's fine ;) – Vogel612 Mar 28 '14 at 13:13

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;
}

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))

• The naming for G, H and F is perfect if you are familiar with the A* algorithm. I would actually name them the same thing. No need to describe the variable names such as cost, heuristic and sumOfCostAndHeuristic if you are familiar with the algorithm and therefore know what F, G and H is. F = G + H just as y = kx + m or E = mc2. +1 for the rest of it though. – Simon Forsberg Mar 28 '14 at 13:16
• Thanks, indeed that's not an algorithm I'm familiar with ;) – Mathieu Guindon Mar 28 '14 at 13:31