Problem
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.
Solution
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.
