# A* Pathfinding Algorithm

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;


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

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

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
}

}
}


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.

• 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. Dec 2, 2020 at 22:36
• Do you have this (entire) program available somewhere, say, in GitHub? Jan 18, 2023 at 13:51
• Hello this Thread itself is pretty old but, yes I actually added it to my Github 2 weeks ago. Heres the link Jan 23, 2023 at 19:21

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.