2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – aepot
    Dec 2 '20 at 22:36
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.