[C#] Automatische "Wegfindung"

[Gateway_man]

Grüßt euch,

 

ich bin auf der Suche nach Inspiration und Ideen :).

Folgende Aufgabenstellung:

Es ist ein Labyrinth gegeben, das einen beliebigen Aufbau hat. Es gibt einen "KI Player" der zu Beginn immer in der Mitte platziert wird.

Jetzt soll die "KI Player" Instanz alleine alle erreichbaren Punkte im Labyrinth ablaufen. (Ohne schummeln, das heißt durch Wände springen ;))

Ich hatte mir überlegt das ich mit einer Rastersuche arbeite. Das heißt ausgehend von der aktuelle Position des KI Spielers ermittle ich alle umliegenden Punkte. Befindet sich dort ein noch nicht besuchter Punkt, so wird ein passender Weg ermittelt (bei diesem Punkt bin ich mir über die technische Umsetzung noch nicht so ganz im klaren), Ist jeder der Punkte bereits besucht, so wird der Suchraster erweitert.

 

Ich habe aktuell das Gefühl, das ich viel zu kompliziert gedacht habe. Wie würdet Ihr das ganze angehen?

 

Beste Grüße

Gateway

[sas86ks]

Ich würde bei sowas schauen wie es andere gemacht haben...

 

Z.B.: https://www.dotnetperls.com/pathfinding

[MartinSt]

Was ist denn das Problem aus dem betrieblichen Alltag zu dem Du diese Lösung bauen willst?

[Gateway_man]

@sas86ks: Danke ich schau es mir mal an.

@MartinSt: Es ist keine Aufgabe aus dem betrieblichen Alltag. Stell dir einfach ein Packman Spiel ohne Gegner vor.

Das Labyrinth existiert schon. Man kann es auch selbst ablaufen, jedoch fehlt jetzt noch die Möglichkeit, das die Spielfigur das auch autonom machen kann.

In der Aufgabenstellung selbst steht, wie man es machen könnte. Jedoch enthält diese Beschreibung mehrere Gedankliche Fehler. Wenn ich das so machen würde, dann würde ich irgendwann in einer Endlos Schleife landen oder es würde einfach nicht mehr weitergehen.

Aber ich kann gerne die Aufgabenstellung inklusive des "möglichen" Lösungsvorschlags hier zitieren:

Zitat

 Die Spielfigur soll nun alle Items in dem Labyrinth automatisch aufsammeln. Hierzu müssen Sie einen Wegefindungsalgorithmus implementieren, wofür sich beispielsweise eine Breitensuche gut eignet. Für die Breitensuche benötigen Sie eine Warteschlange (eine Queue) sowie eine Hashtable (alternativ: Dictionary). Der Algorithmus lässt sich wie folgt skizzieren:

1. füge die aktuelle Spielerposition (x,y-Koordinaten) in die leere Queue ein;

2. so lange die Queue nicht leer ist,   

2.1   hole das erste Koordinatenpaar aus der Queue;   

2.2   falls sich hier ein Item befindet, breche ab: die Suche war erfolgreich.    

2.3   für alle direkten Nachbarn (links, oben, rechts, und unten) dieser Koordinaten:
  2.3.1   falls nicht blockiert (kein '#') und noch nicht in der Hashtable enthalten:
             füge den Nachbarn in die Queue ein; füge den Nachbarn als Key und die aktuellen Koordinaten als Value in die  Hashtable ein;   

2.4   weiter mit 2.

 

Die Hashtable enthält nun Koordinatenpaare, wobei jedes besuchte Feld als Key vorkommt. Der zugehörige Value ist das Koordinatenpaar, von dem aus man in der Suche gekommen ist (from). Um nun von der Spielerposition zum Ziel zu finden, müssen Sie den Weg rückwärts in der Hashtable suchen. Hierzu eignet sich ein Stack in der folgenden Art:

1. falls ein Ziel gefunden wurde, lege die Zielposition auf den leeren Stack;

2. lese den zugehörigen Value (die vorherige Position from) aus der Hashtable;

3. so lange from nicht der Ausgangsposition entspricht:
  3.1   lege from auf den Stack;
  3.2   lese die vorherige Position von from aus der Hashtable und weise diese from zu; 
  3.3   weiter mit 3.

Für den Weg der Spielfigur zum Ziel müssen Sie nun nur noch den Stack abarbeiten. Machen Sie sich an einem einfachen Beispiel klar, dass der Algorithmus funktioniert. Schreiben Sie eine Klasse ComputerPlayer, die diesen Wegefindungsalgorithmus implementiert. Die Spielfigur soll nun selbständig mit einem Timer gesteuert alle Items des Labyrinths aufsammeln.  Die Suche startet also erneut von der aktuellen Position, wenn ein item aufgesammelt wurde. Das wird solange wiederholt, bis das komplette Labyrinth leer gefressen ist. Erstellen Sie auch mindestens ein eigenes Labyrinth. Hinweis: verwenden Sie die Klasse System.Drawing.Point zur Speicherung der Koordinaten in den Collections-Datenstrukturen, da diese Klasse bereits die für die Hashtable benötigten Methoden Equals und GetHashCode implementiert. 

 

 

Beste Grüße

Gateway

Bearbeitet 15. Dezember 2016 von Gateway_man

[Whiz-zarD]

Auf Wikipedia stehen dafür gleich mehrere Ansätze.

Sofern es keine Säulen im Labyrinth gibt und die Länge des Weges egal ist, gibt es einen einfachen Algorithmus: Immer nach Rechts gehen.

Bearbeitet 15. Dezember 2016 von Whiz-zarD

[Chiyoko]

Das einfachste ist es, bei einer Abzweigung immer nach rechts zu gehen. So gelangst du über kurz oder lang zu jedem erreichbarem Punkt im Labyrinth.

[Ulfmann]

vor 4 Minuten schrieb Chiyoko:

Das einfachste ist es, bei einer Abzweigung immer nach rechts zu gehen. So gelangst du über kurz oder lang zu jedem erreichbarem Punkt im Labyrinth.

Da nimmst du aber an, dass es keine "Insel" gibt, die in deinem Fall nur über links-abbiegen zu erreichen ist.

[Chiyoko]

Nein, das nehme ich nicht an. Wenn ich immer nach rechts gehe, komme ich irgendwann in eine Sackgasse. Dort drehe ich um, komme zurück an die Abzweigung und laufe dann wieder rechts -> Geradeaus vom Originalweg. Das ganze wiederholt sich und somit laufe ich dann links vom Originalweg aus gesehen.

Sollte es mal nur geradeaus und links geben, so fällt einfach das erste drittel weg. ich laufe gerade, drehe irgendwann um, und komme dann zurück an die Abzweigung. Dort laufe ich dann rechts -> Also praktisch links von der Originalposition aus gesehen.

Es ist sehr unperformant und langsam, aber es kommt definitiv an alle erreichbaren Stellen.

Ich hoffe ich habs hlbwegs verständlich erklärt. Ist doof, ohne Zeichnung xD.

Sollte so funktionieren, oder habe ich einen Denkfehler?

[Mttkrb]

Hi,
bei diesem Beispiel sollte die Methode nicht klappen.

[Ulfmann]

Genau sowas mein ich  

[Guybrush Threepwood]

Mal so als nicht zu Ende gedachte Idee:

Mit einer Rekursion kannst du einfach alle erreichbaren Felder auffinden. Dabei kannst du deine Spielfigur auch direkt darstellen, dass sie immer im aktuell untersuchtem Feld steht und diese somit durch das Labyrinth wandert.

Das Problem ist aber, dass wenn du an das Ende eines Pfades kommst welche den aktuellen Rekursionslauf beenden würde du einen Sprung der Spielfigur zum letzten Feld hättest an dem es mehr als eine mögliche Richtung gibt und von dem dann die Rekursion fortgesetzt wird. Das heißt du müsstest im Fall einer Sackgasse die Rekursion (irgendwie) wieder Rückwärts bis zur letzten Kreuzung laufen lassen und von da an dann wieder ganz normal weiter in die nächste Richtung...

[Gateway_man]

Hallo Leute,

 

ich hab jetzt statt der vorgeschlagenen breitensuche, eine tiefensuche verwendet. Das gefällt mir besser und ist auch effizienter.

Danke für eure Ideen :).

Beste Grüße und schöne Feiertage

Gateway

[Chiyoko]

Am ‎16‎.‎12‎.‎2016 um 10:14 schrieb Mttkrb:

Hi,
bei diesem Beispiel sollte die Methode nicht klappen.

An sowas hab ich gar nicht gedacht.

Danke  Wieder etwas schlauer geworden.

 

Am ‎16‎.‎12‎.‎2016 um 10:36 schrieb Ulfmann:

Genau sowas mein ich  

Nach nochmaligen Lesen hab ich deine Anmerkung verstanden Ulfmann. Manchmal ist man einfach blind. Sorry

Bearbeitet 21. Dezember 2016 von Chiyoko

[pr0gg3r]

Ich würde das so lösen:

1. Man bildet alle Wege in einem Baum ab. Der Startpunkt ist hierbei die Wurzel.
2. Nun wird für jedes erreichbare Feld um den Spieler als ein Knoten hinzugefügt.
3. Anschließend wird jeder Knoten weiter abgearbeitet, also jedes erreichbare Feld um den Knoten an diesen wiederum an den Knoten angehängt.
4. Dies wiederhole man so lange, bis das Ziel erreicht ist.
5. Die verbundenen Knoten an den Kanten Start-Ziel stellen nun die zu gehenden Felder von Start bis Ziel dar.
6. Das ganze dann wiederholen, bis alle Punkte erreicht wurden

Um das zu optimieren, kann man noch die "Himmelsrichtung" hinzufügen und sich nur in diese bewegen. Also, wenn sich das Ziel rechts befindet, arbeite nur die Felder nach rechts ab. Muss dann aber auch rückgängig funktionieren, falls man in eine Sackgasse läuft.

 

Bearbeitet 23. Dezember 2016 von pr0gg3r