A* Pathfinding Algorithm

Question

I have programmed a A* Pathfinding algorithm in the Console. I would now like to know if there are any things that I could do to improve the time it takes, to find a path. Right now it takes around 80ms.

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

Those are the necessary Using directories

class Node
{
 public bool wall; //Ist die Node eine Wand
 public bool start; //Ist die Node die Start-Node
 public bool end; //Ist die Node die End-Node
 public Node previous; //Vorherige Node / weg zu dieser Node
 public int x, y; // X und Y position
 public int g, h, f; //G = Distance from starting node / H = Distance from end node / F = G + H
 public Node(int x, int y) //Initialsierung
 {
 this.x = x;
 this.y = y;
 }
}
class Map
{
 public int Width { get; private set; }
 public int Height { get; private set; }
 public Node start;
 public Node end;
 public Node[,] map;
 public readonly List<Node> searching = new List<Node>(); //Auch offene Liste gennant
 public readonly List<Node> searched = new List<Node>(); //Auch geschlossene Liste gennant
 public Map(int wi, int he) //Initialisierung
 {
 Width = wi;
 Height = he;
 map = new Node[wi, he];
 for (int i = 0; i < Width; i++)
 {
 for (int j = 0; j < Height; j++)
 {
 map[i, j] = new Node(i, j); //Generisch Initialisiert
 }
 }
 }
 public void SetStart(int x, int y) //Setzt den Startpunkt
 {
 map[x, y].start = true;
 map[x, y].end = false;
 map[x, y].g = 0;
 start = map[x, y];
 }
 public void SetEnd(int x, int y) //Setzt den Endpunkt
 {
 map[x, y].end = true;
 map[x, y].start = false;
 map[x, y].h = 0;
 end = map[x, y];
 }
 public void SetWalls(List<int[]> walls) //Setzt die Wände an Ihre Positionen
 {
 for (int i = 0; i < walls.Count; i++)
 {
 map[walls[i][0], walls[i][1]].wall = true;
 }
 }
 private void CalculateGCost(int x, int y, Node previous) //Errechnet die G Cost / die Distanz zu dem Startpunkt
 {
 int cost = 10;
 if (!map[x, y].start && !map[x, y].end)
 {
 if (previous.x != x && previous.y != y) //neu
 {
 cost += 4;
 }
 map[x, y].g = previous.g + cost;
 map[x, y].previous = previous;
 }
 }
 public void CalculateAllHCost() //Errechnet für die ganze Karte die H Cost / die Distanz zu dem Endpunkt
 {
 for (int i = 0; i < Width; i++)
 {
 for (int j = 0; j < Height; j++)
 {
 CalculateHCost(i, j);
 }
 }
 }
 private void CalculateHCost(int x, int y) //Errechnet für dieses eine Feld die H Cost / die Distanz zu dem Endpunkt
 {
 if (map[x, y] != end)
 {
 int xstep = Math.Abs(end.x - x); //Wie weit das ende von dem jetzigen Punkt in der X Achse entfernt ist
 int ystep = Math.Abs(end.y - y); //Wie weit das ende von dem jetzigen Punkt in der Y Achse entfernt ist
 map[x, y].h = (xstep + ystep) * 10; //Beides zusammen ist die Insgesamte entfernung
 }
 }
 private void CalculateFCost(int x, int y) => map[x, y].f = map[x, y].g + map[x, y].h; //F Cost ist H Cost + G Cost
 public void StartPathFinding() //Startet den Algorithmus
 {
 searching.Add(start); //Fügt die Start Node der offenen liste Searching hinzu.
 ShowMap();
 Search();
 }
 private void PathFinding(int x, int y) //Findet die benachbarten Nodes und fügt sie in die offene Liste hinzu, wenn sie dort nicht schon sind mit einem besseren vorgänger.
 {
 for (int i = -1; i < 2; i++)
 {
 for (int j = -1; j < 2; j++)
 {
 if ((x + i >= 0 && x + i < Width) & (y + j >= 0 && y + j < Height))
 {
 if (!map[x + i, y + j].wall)
 {
 if (map[x + i, y + j].g == 0 & !map[x + i, y + j].start)
 {
 map[x + i, y + j].previous = map[x, y];
 searching.Add(map[x + i, y + j]);
 }
 else if (map[x + i, y + j].g > map[x, y].g + (i == 0 && j == 0 ? 10 : 14))
 {
 map[x + i, y + j].previous = map[x, y];
 Node t = searched.Find(item => item.x == x + i && item.y == y + j);
 searched.Remove(t);
 searching.Add(map[x + i, y + j]);
 }
 }
 }
 }
 }
 }
 private void Search() //Das Herzstück des Algorithmus, der die Anweisungen gibt, wie der Weg gefunden wird
 {
 Node node;
 do
 {
 foreach (var item in searching) //Für jede Node in der offenen Liste
 {
 CalculateGCost(item.x, item.y, item.previous); //Berechnet die G Cost / die Distanz zu dem Startpunkt
 CalculateFCost(item.x, item.y); //Berechnet die F Cost / die Distanz zu dem Startpunkt + die Distanz zu dem Endpunkt
 }
 int lowestF = searching.Min(c => c.f); //Sucht die niedrigste F Cost
 List<Node> nodes = searching.FindAll(c => c.f == lowestF); //Sucht in der offenen Liste nach den Nodes mit der niedrigsten F Cost
 int lowestH = nodes.Min(c => c.h); //Sucht unter den niedrigsten F Cost Nodes nach der niedrigsten H Cost
 node = nodes.Find(c => c.h == lowestH); //Wählt die Node mit der niedrigsten F und H Cost aus
 if (node == end) //Sollte die Node zufälligerweise die End-Node sein, wird die Suche nach der End-Node abgebrochen (weil sie gefunden wurde)
 {
 break;
 }
 PathFinding(node.x, node.y); //Sucht für die Node mit der niedrigsten F und H Cost die Nachbarn und fügt sie der offenen Liste hinzu
 searching.Remove(node); //Entfernt die Node von der offenen Liste
 searched.Add(node); //und fügt sie der geschlossenen Liste hinzu
 } while (searching.Count != 0 && node != end); //Sollte die End-Node gefunden werden oder die offene Liste leer sein, ist ein fehler aufgetreten oder die End-Node wurde gefunden
 }
 public void ShowMap() //Zeigt die Karte an
 {
 for (int i = 0; i < Width; i++)
 {
 for (int j = 0; j < Height; j++)
 {
 Console.SetCursorPosition(i, j);
 if (map[i, j].start)
 {
 Console.ForegroundColor = ConsoleColor.Blue; //Makiert den Start mit einer blauen Schriftfarbe
 }
 else if (map[i, j].end)
 {
 Console.ForegroundColor = ConsoleColor.Yellow; //Makiert das Ende mit einer gelben Schriftfarbe
 }
 else
 {
 Console.ForegroundColor = ConsoleColor.Gray; //Alles andere wird mit einer grauen Schriftfarbe geschrieben
 }
 Console.WriteLine(map[i, j].wall | map[i, j].end | map[i, j].start ? "X" : " "); //Schreibt ein X wenn es sich bei dem Feld um eine Wand / das Ende / den Start handelt
 }
 }
 }
 public void ShowPath(Node node) //Malt den schnellsten Weg von der Start-Node zu der End-Node an.
 {
 System.Threading.Thread.Sleep(100);
 Console.SetCursorPosition(node.x, node.y);
 Console.BackgroundColor = ConsoleColor.White;
 Console.WriteLine("X");
 Console.BackgroundColor = ConsoleColor.Black;
 if (node != start)
 {
 ShowPath(node.previous); //Zeigt die nächste Node in der Reihe
 }
 else
 {
 Console.SetCursorPosition(0, Height + 1); //Die Reihe ist fertig, es wird an das ende der Map gesetzt um weiter Infos auf der Konsole auszugeben ohne die Karte zu überschreiben
 }
 }
}
class Program
{
 static void Main(string[] args)
 {
 Console.ReadKey(true);
 int counter = 0; //Wieviele Linien es gibt
 int longestLine = 0; //Die Längste Linie
 string line; //Was die Linie beinhaltet
 List<int[]> walls = new List<int[]>(); //Die Wände, die durch die Input Text Datei gesetzt wurden
 int[] start = new int[2]; //Start-Node Koordinaten
 int[] end = new int[2]; //End-Node Koordinaten
 System.IO.StreamReader file =
 new System.IO.StreamReader(@"PUT THE PATH TO YOUR TXT FILE HERE");
 while ((line = file.ReadLine()) != null)
 {
 if (line.Length > longestLine)
 {
 longestLine = line.Length; //Guckt nach der längsten Linie (Die breite der Karte)
 }
 int counter2 = 0;
 foreach (char x in line)
 {
 if (x == 'X') //Sollte ein "X" angegeben sein, bedeutet das, dass dort eine Wand gestzt werden muss
 {
 walls.Add(new int[] { counter2, counter });
 }
 else if (x == 'S') //Sollte ein "S" angegeben sein, bedeutet das, dass dort der Startpunkt / die Start-Node gesetzt werden muss
 {
 start[0] = counter2;
 start[1] = counter;
 }
 else if (x == 'E') //Sollte ein "E" angegeben sein, bedeutet das, dass dort der Endpunkt / die End-Node gesetzt werden muss
 {
 end[0] = counter2;
 end[1] = counter;
 }
 counter2++;
 }
 counter++; //Guckt nach der Anzahl der Linien (Die Höhe der Karte)
 }
 Map map = new Map(longestLine, counter); //Karte wird Initialisiert
 map.SetStart(start[0], start[1]); //Start wird gesetzt
 map.SetEnd(end[0], end[1]); //Ende wird gesetzt
 map.SetWalls(walls); //Wände werden gesetzt
 System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
 sw.Start();
 map.CalculateAllHCost(); //Alle H Costs werden berechnet
 map.StartPathFinding(); //Der Algorithmus startet
 sw.Stop();
 map.ShowMap();
 map.ShowPath(map.end);
 Console.WriteLine("The Path took {0} ms to calculate", sw.ElapsedMilliseconds);
 foreach (Node node in map.searched)
 {
 Console.WriteLine("{0,-6} : G = {1,-4}| H = {2,-4}| F = {3,-4}", node.x + ", " + node.y, node.g, node.h, node.f); //Alle untersuchten Nodes werden einmal aufgeführt
 }
 Console.ReadKey(true);
 }
}

Im sorry that all my Comments are in german, but the code should still be readable. Somewhere in the Main Method you have to Specify a Path to a txt file, that is used as the map.

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X X XX X X X X
X XXX X X X X X
X X X XXXXXXXXXXXXX XXXXXXX
X XX XX X X X
X XXX XX X X X
X X X XXXX X
X X E XXXXXX X
X X X XXXXXXX X
X XX XXXX X
X X X
X X X
X X X
X X XXXXXXXXXXXX X
X X XXXXXXXXXXXX X
X XXXX XXXX X X XXXXX X
X X X XXXXXS X X
X X X X X
X X X X XX XX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

you can copy this map into the txt file and youll have the same one as I do.

I hope you can help me or give me feedback on the overall quality of the code.

• aepot: 1) if-else-if-else-if => switch-case. 2) 3 bools start, wall, end => enum with cell type. 3) split path and map logic, map should contain only cell types, nodes - dedicated for paths.
• coderodde: Do you have this (entire) program available somewhere, say, in GitHub?
• Pablu: Hello this Thread itself is pretty old but, yes I actually added it to my Github 2 weeks ago. Heres the link

Answer 1

I cannot comment on the pathfinding algorithm yet because i don't remember how it should work. But your ellapsed time capture includes ShowMap and that isnt part of the algorithm. ShowMapis the most time consuming part of your time measurement, so i suggest you remove that and re-measure. If you havent yet, you can use the built in performance profiler in Visual Studio.

This image shows the hot path in your application. enter image description here