Skip to content

Instantly share code, notes, and snippets.

@Jalalx
Created February 8, 2014 14:00
Show Gist options
  • Save Jalalx/8884178 to your computer and use it in GitHub Desktop.
Save Jalalx/8884178 to your computer and use it in GitHub Desktop.
class AStar
{
private static bool InBounds(int x, int y, bool[,] map)
{
if (x >= 0 && y >= 0 && y < map.GetLength(0) && x < map.GetLength(1))
return true;
return false;
}
private static List<Node> GetSurroundingNodes(Node node, bool[,] map)
{
List<Node> surroundingNodes = new List<Node>();
/* Adds all the nodes surrounding the parameter node to the
* surrounding nodes list (quite the mouthful)
*/
surroundingNodes.Add(new Node(node.X + 1, node.Y, node, node.TargetNode));
surroundingNodes.Add(new Node(node.X - 1, node.Y, node, node.TargetNode));
surroundingNodes.Add(new Node(node.X, node.Y + 1, node, node.TargetNode));
surroundingNodes.Add(new Node(node.X, node.Y - 1, node, node.TargetNode));
List<Node> tempNodes = new List<Node>(surroundingNodes);
foreach (var surroundingNode in tempNodes)
{
/* Removes a node from the surrounding node list if it is
* out of bounds or if it is impassable on the collision map
*/
if (map[surroundingNode.Y, surroundingNode.X]
&& InBounds(surroundingNode.X, surroundingNode.Y, map))
{
surroundingNodes.Remove(surroundingNode);
}
}
return surroundingNodes;
}
public static List<Node> FindPath(int startX, int startY, int targetX, int targetY, bool[,] map)
{
Node targetNode = new Node(targetX, targetY, null, null);
Node startNode = new Node(startX, startY, null, targetNode);
List<Node> openList = new List<Node>();
List<Node> closedList = new List<Node>();
openList.Add(startNode);
while (openList.Any())
{
/* Sorts the open list of nodes according to the CompareTo method in the
* Node class. Creates a new node object from the first (lowest f value)
* node in the open list.
*/
openList.Sort();
Node currentNode = openList[0];
if (currentNode == targetNode)
return ReconstructPath(openList[0]);
openList.Remove(currentNode);
closedList.Add(currentNode);
/* Adds all of the accessible surronding nodes to the open list if they
* are not currently in the closed list.
*/
openList.AddRange(from neighborNode in GetSurroundingNodes(currentNode, map)
let contained = closedList.Any(node => node == neighborNode)
where !contained
select neighborNode);
}
/* This function will only return null if there are no available paths from the
* start node to the end node.
*/
return null;
}
private static List<Node> ReconstructPath(Node node)
{
List<Node> path = new List<Node>();
while (node.G != 0)
{
path.Add(node);
node = node.ParentNode;
}
path.Add(node);
return path;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment