Pathfinder

[Raumi]

Hallo,
Eine kleine Knobelaufgabe, ich brauchte das mal wieder nach einiger Zeit. Das ganze ist eine Klassenbibliothek (.dll) und hat drei Klassen.

Vorweg muss glaube ich erklärt werden, was ein Pathfinder überhaupt ist.
Ein Pathfinder findet auf einer Map (in meinem Fall 2D) den Weg zu einer bestimmten Zielkoordinate und umgeht wenn nötig Blockaden (wie z.B. Wände).

In meinem Pathfinder ist aber nicht nur eine Pathfinder-Klasse sondern auch eine Map und eine Character Klasse. Man kann ohne viel ändern zu müssen, diese gleich für ein einfaches Spiel oder whatever nutzen.

Map Klasse (Int32 Width, Int32 Height)
Die wichtigste Variable in der Map Klasse ist die fields Variable (String[,]), ein mehrdeminsionaler String. Jede Koordinate hat einen String zugeordnet der Informationen enthält über die Koordinate, in meiner Klasse jetzt nur ob sie begehbar ist oder nicht, aber man kann durch die Funktion „AddFieldInfo(String name, String value, Int32 x, Int32 y)” eigene Infos dazupacken. Wie z.B. das Aussehen des Tiles (Gras / Wasser - wenn man es auf eine Spiel-Map abgesehen hat) oder was man eben gerne mag.

Character Klasse (String heroname)
Die Character Klasse erstellt einen Charakter den man auf eine Map spawnen kann, mithilfe der Spawn(Map map, Int32 x, Int32 y) Funktion. Der String im Konstruktor ist eigentlich nur so da, bis jetzt keine Funktion.

Spannend wird es, nachdem man seinen Character gespawnt hat und ihn via move(Int32 x, Int32 y) bewegt. Man übergibt x & y Koordinate und dieser ruft dann folgendes auf ...

Pathfinder Klasse
Hat eine statische Funktion „Find(Character c, Int32 x, Int32 y)”, welche die Schritte zurückgibt wie man zu seiner Zielkoordinate hinkommt (x, y). Kommt man nicht hin, wird eine leere List<Int[]> zurückgegeben. Den Charakter könnte man auf einer grafischen Oberfläche dann in etwa so bewegen, dass man die List<Int[]> mit einer Forschleife durchgeht und dann den Char dahinbewegen lässt.


Der Aufruf würde in etwa so lauten

Map justmap = new Map(10, 10);
Character c = new Character("Drilon");

for (int i = 4; i < 10; i++) { justmap.BlockField(i, 2); }
c.Spawn(justmap, 5, 0);
c.Move(6, 6);

Das würde in dem Beispiel einen Charakter auf den Koordinaten x:5,y:0spawnen lassen, der läuft dann nach oben und trifft bis x:5,y:1 weil auf x:5,y:2 das Feld blockiert ist. Er probiert dann nach rechts zu laufen bis es auf der Y-Achse weiter nach oben geht oder bis er die Wand rechts erreicht. Wenn er keinen Weg nach oben findet, geht er an seine letzte Position zurück, wo er zum ersten Mal auf die Mauer gestoßen ist (x:5,y:1) und versucht es weiter indem er nach links geht bis es nach oben geht.

Falls einer keine Lust hat das ganze runterzuladen, hier die Pathfinder Funktion im Spoiler. Die Console.WriteLines() könnt ihr gerne rausnehmen, sind nur zum Test da.

Spoiler:

/// <summary>
        /// Findet den Weg zu einer bestimmten Koordinate auf der aktuellen Map
        /// </summary>
        /// <param name="c">Charakter, welcher sich bewegen soll</param>
        /// <param name="x">Die X Zielkoordinate</param>
        /// <param name="y">Die Y Zielkoordinate</param>
        /// <returns>Gibt eine Liste mit den Koordinaten wieder, wie man zum Ziel gelangt</returns>
        static public List<Int32[]> Find(Character c, Int32 x, Int32 y)
        {
            List<Int32[]> rtnList = new List<int[]>();
            Int32[] anker;
            Map map = c.map;
            
            while(c.x != x || c.y != y)
            {
                if (c.y < y)
                {
                    if(map.IsFieldBlocked(c.x, c.y + 1))
                    {
                        Console.WriteLine("[!] Mauer auf " + c.x.ToString() + ":" + (c.y + 1).ToString() + " entdeckt");
                        anker = new Int32[] {c.x, c.y};
                        do
                        {
                            Console.WriteLine("# " + c.x.ToString() + ":" + c.y.ToString());
                            if((c.x + 1) < map.Width && !map.IsFieldBlocked(c.x + 1, c.y))
                            { 
                                c.x++;
                                rtnList.Add(new Int32[] { c.x, c.y });
                                Console.WriteLine("[ADD] " + c.x.ToString() + ":" + c.y.ToString());
                            }
                            else
                            {
                                for(int i = rtnList.Count - 1; i >= 0; i--) {
                                    Console.WriteLine("[CHECK FOR REM] " + rtnList[i][0].ToString());
                                    if (rtnList[i][0] > anker[0]) { Console.WriteLine("[REM] " + rtnList[i][0].ToString()); rtnList.Remove(rtnList[i]); }
                                }

                                c.x = anker[0];
                                c.y = anker[1];
                                Console.WriteLine("[WALL] Nach rechts geht es nicht weiter ... zurück zum Anker");
                                do
                                {
                                    Console.WriteLine("# " + c.x.ToString() + ":" + c.y.ToString());
                                    if ((c.x - 1) > -1 && !map.IsFieldBlocked(c.x - 1, c.y)) 
                                    { 
                                        c.x--;
                                        rtnList.Add(new Int32[] { c.x, c.y });
                                    }
                                    else
                                    {
                                        Console.WriteLine("[!] Es gibt keinen Weg zum Ziel, sorry.");
                                        return new List<Int32[]>();
                                    }
                                } while(map.IsFieldBlocked(c.x, c.y + 1));
                                break;
                            }
                        } while(map.IsFieldBlocked(c.x, c.y + 1));
                    }
                    else 
                    {
                        Console.WriteLine("# " + c.x.ToString() + ":" + c.y.ToString());
                        c.y++;
                        rtnList.Add(new Int32[] {c.x, c.y});
                        Console.WriteLine("[ADD] " + c.x.ToString() + ":" + c.y.ToString());
                    }
                }

                if(c.y == y && c.x < x)
                {
                    Console.WriteLine("[Y REACHED] # " + c.x.ToString() + ":" + c.y.ToString());
                    c.x++;
                    rtnList.Add(new Int32[] {c.x, c.y});
                }

                if (c.y == y && c.x > x)
                {
                    Console.WriteLine("[Y REACHED] # " + c.x.ToString() + ":" + c.y.ToString());
                    c.x--;
                    rtnList.Add(new Int32[] { c.x, c.y });
                }

                if (c.y > y)
                {
                    if (map.IsFieldBlocked(c.x, c.y - 1))
                    {
                        anker = new Int32[] { c.x, c.y };

                        do
                        {
                            if ((c.x + 1) < map.Width && !map.IsFieldBlocked(c.x + 1, c.y))
                            {
                                c.x++;
                                rtnList.Add(new Int32[] { c.x, c.y });
                            }
                            else
                            {
                                c.x = anker[0];
                                c.y = anker[1];

                                for (int i = rtnList.Count - 1; i >= 0; i--)
                                {
                                    if (rtnList[i][0] > anker[0]) { rtnList.Remove(rtnList[i]); }
                                }

                                do
                                {
                                    if ((c.x - 1) > -1 && !map.IsFieldBlocked(c.x - 1, c.y))
                                    {
                                        c.x--;
                                        rtnList.Add(new Int32[] { c.x, c.y });
                                    }
                                    else
                                    {
                                        return new List<Int32[]>();
                                    }
                                } while (map.IsFieldBlocked(c.x, c.y - 1));
                                break;
                            }
                        } while (map.IsFieldBlocked(c.x, c.y - 1));
                    }
                    else
                    {
                        c.y--;
                        rtnList.Add(new Int32[] { c.x, c.y });
                    }
                }
            }

            Console.WriteLine("[!] ZIEL ERREICHT (" + c.x.ToString() + ":" + c.y.ToString() + ")");
            return rtnList;
        }

[Raumi]

So, habe das ganze in ein GUI gepackt als .exe. Ich glaube das illustiert am besten die Art und Weise wie der Pathfinder funktioniert.

Download: SimplePathfinderGUI.rar

Blau: Character
Rot: Wand
Gelb: Ziel