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
}
}
}
List
, use the correct data structure for the open list and the closed list. 3. If the graph is unweighted, why use a weight of10
rather than just1
? \$\endgroup\$openList
is supposed to be a priority queue - I linked above to an implementation I wrote which is specifically optimized for pathfinding. TheclosedList
should be a set with O(1).Add()
and.Contains()
, such as aHashSet<T>
. Doing this should significantly speed up your pathfinding, while simultaneously making your code easier to read. \$\endgroup\$