using System.Collections.Generic;
static (int, int)[] directions = { (0, 1), (1, 0), (0, -1), (-1, 0) };
class Node : IComparable<Node>
public int X { get; set; }
public int Y { get; set; }
public int G { get; set; }
public int H { get; set; }
public Node Parent { get; set; }
public Node(int x, int y, int g, int h, Node parent = null)
public int CompareTo(Node other) => F.CompareTo(other.F);
static int Heuristic(int x, int y, int goalX, int goalY)
return Math.Abs(x - goalX) + Math.Abs(y - goalY);
static List<(int, int)> AStarSolve(int startX, int startY, int goalX, int goalY)
var openList = new SortedSet<Node>();
var closedList = new HashSet<(int, int)>();
var startNode = new Node(startX, startY, 0, Heuristic(startX, startY, goalX, goalY));
while (openList.Count > 0)
var currentNode = openList.Min;
openList.Remove(currentNode);
if (currentNode.X == goalX && currentNode.Y == goalY)
return ReconstructPath(currentNode);
closedList.Add((currentNode.X, currentNode.Y));
foreach (var direction in directions)
int newX = currentNode.X + direction.Item1;
int newY = currentNode.Y + direction.Item2;
if (IsValid(newX, newY) && !closedList.Contains((newX, newY)))
int newG = currentNode.G + 1;
int newH = Heuristic(newX, newY, goalX, goalY);
var neighbor = new Node(newX, newY, newG, newH, currentNode);
static List<(int, int)> ReconstructPath(Node node)
var path = new List<(int, int)>();
path.Add((node.X, node.Y));
static bool IsValid(int x, int y)
return x >= 0 && x < N && y >= 0 && y < N && maze[x, y] == 0;
var path = AStarSolve(0, 0, N - 1, N - 1);
Console.WriteLine("Path found:");
foreach (var (x, y) in path)
Console.WriteLine($"({x}, {y})");
Console.WriteLine("No solution exists.");