Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Ansatz zur Wegfindung

Werbeanzeige

MitgliedXYZ

Alter Hase

  • »MitgliedXYZ« ist der Autor dieses Themas

Beiträge: 1 369

Wohnort: Bayern

  • Private Nachricht senden

11

27.03.2013, 12:18

Zitat von »EternalPain«

Ich habe nach deiner Schilderung mal versucht etwas zu basteln...
Dabei müssen zuerst alle Wegpunkte 'ermittelt' werden... anschließend habe ich die Distanz ausgehen vom letzten Wegpunkt bzw Anfänglich der Spieler-Position berechnet und dann als nächstes den Wegpunkt genommen der am nächsten liegt usw, bis zum letzten ermittelten Wegpunkt
Daraus ergibt sich dann eine Wegpunktliste.... anschließend kann dann diese Liste wiederum an einen Wegfindungs-Algorithmus übergeben werden...
So ähnlich habe ich es jetzt auch gelöst, ich gehe von jedem Punkt immer zu dessen nächstem Nachbarn, bis ich alle durch habe, ist zwar nicht ganz optimal, aber reicht mir.

An deinem Beispielbild sieht man auch gut, dass zwar ein relativ kurzer Weg gefunden wird, der aber nicht unbedingt der kürzeste (ich hab in mal blau markiert) ist.


Edit: Seit wann sieht man die Angehängten Bilder nur noch als Link? Das war doch früher mal anders...

Jonathan_Klein

Community-Fossil

Beiträge: 3 820

  • Private Nachricht senden

12

27.03.2013, 13:36

Ja, wie gesagt, das Problem ist schon sehr intensiv erforscht (und es kam raus, dass es ein wirklich schweres ist). Natürlich spricht nichts dagegen, sich eigene Gedanken zu machen, aber die Sachen auf Wikipedia dürften schon so ziemlich der aktuelle Stand der Forschung sein und damit im Zweifelsfalle besser als man sich mal eben so einfach überlegen kann.
Lieber dumm fragen, als dumm bleiben!

MitgliedXYZ

Alter Hase

  • »MitgliedXYZ« ist der Autor dieses Themas

Beiträge: 1 369

Wohnort: Bayern

  • Private Nachricht senden

13

03.04.2013, 14:34

Mh, jetzt muss ich diesen Thread doch noch mal wiederbeleben...

Die aktuelle Frage ist nicht mehr, in welcher Reihenfolge ich die Blätter ablaufen will, die Frage ist wie ich von meinem jetzigen Standpunkt zum nächsten komme.

Ich habe als Daten ja nur mein Array[x][y] das mir das jeweilige Objekt zurück gibt, und meine x und y position und die des Ziel Objektes. Zudem kann ich nur hoch/runter/links/rechts gehen, nicht schräg.
Zur Weiterverarbeitung bräuchte ich ein String-Array, das von meiner Position aus die benötigten Schritt-Richtungen speichert (also "links", "rechts", "oben", "unten").

Der FloodFill-Algorithmus sieht ja ziemlich verständlich aus, ich verstehe allerdings nicht, was er mir nutzt...

Quellcode

 
1
2
3
4
5
6
7
8
9
10

fill4(x, y) {

  if (getPixel(x, y) == 0) {
markierePixel(x, y, neueFarbe); //Das müsste geändert werden
fill4(x, y + 1); // unten
fill4(x - 1, y); // links
fill4(x, y - 1); // oben
fill4(x + 1, y); // rechts 
  }  return;
}


Angenommen ich würde diese Funktion mit meinen Koordinaten aufrufen, wie müsste ungefähr der Code statt markierePixel aussehen?
Mir ist klar, dass ich keinen Code bekommen werde, das hätte ja auch keinen lern Effekt, aber evtl. hat jemand eine Idee...

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

14

03.04.2013, 14:42

Wieso muss das geaendert werden? Ich glaube das muesste genau so bleiben.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

MitgliedXYZ

Alter Hase

  • »MitgliedXYZ« ist der Autor dieses Themas

Beiträge: 1 369

Wohnort: Bayern

  • Private Nachricht senden

15

03.04.2013, 14:51

Zitat von »TGGC«

Wieso muss das geaendert werden? Ich glaube das muesste genau so bleiben.
Ok, und wie müsste ich es dann erweitern?
Das wichtige müsste dann eben in der Funktion markierePixel passieren, ich muss allerdings kein Pixel umfärben, wenn dann wäre der Code komplett, aber ich bräuchte ja einen Weg, so habe ich mit diesem Code nur alle theoretisch erreichbaren Felder bekommen.

Und da ich in meinem Array auch nichts umfärben kann würde der Code in der Form unendlich lange weiterlaufen :S

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »MitgliedXYZ« (03.04.2013, 15:08)

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

16

03.04.2013, 16:34

Zitat von »MitgliedXYZ«

Ok, und wie müsste ich es dann erweitern?
Mit einer Abbruchbedingung, ob dein Zielpixel gerade umgefaerbt werden soll und dann ein Backtracking zum Start.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

MitgliedXYZ

Alter Hase

  • »MitgliedXYZ« ist der Autor dieses Themas

Beiträge: 1 369

Wohnort: Bayern

  • Private Nachricht senden

17

03.04.2013, 17:32

Zitat von »TGGC«

Zitat von »MitgliedXYZ«

Ok, und wie müsste ich es dann erweitern?
Mit einer Abbruchbedingung, ob dein Zielpixel gerade umgefaerbt werden soll und dann ein Backtracking zum Start.
...und das heißt auf deutsch?

Klar brauch ich ne Abbruchbedingung, evtl. wenn das gerade überprüfte Feld das des "Ziels" ist. Also ungefähr so:

Quellcode

 
1
2
3
4
5
6
7
8
9
10

fill4(x, y) {

  if (getPixel(x, y) == 0 && x != xZiel && y != yZiel) {
markierePixel(x, y, neueFarbe); //Das müsste geändert werden
fill4(x, y + 1); // unten
fill4(x - 1, y); // links
fill4(x, y - 1); // oben

fill4(x + 1, y); // rechts 
  }  return; }



Aber wie sollte mir das nun bei der Wegberechnung weiterhelfen?

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

18

03.04.2013, 17:48

Die Idee ist bei Floodfill ja eigentlich nur rekursiv Nachbarpixel (oder auch Elemente) zu besuchen. Ist ein besuchter Pixel schon markiert, kann abgebrochen werden. Ist ein Pixel nicht markiert wird er markiert und das ganze rekursiv für die Nachbarn aufgerufen. Es geht dabei also eigentlich darum irgendwie Pixel/Elemente in einem Raster zu markieren.
Eigentlich gedacht war FloodFill afair zum füllen von Flächen in Grafikprogrammen. Dabei werden also einzelne Pixel durchgegangen und umgefärbt (entspricht in meiner oberen Erklärung dem markieren). Dabei wird normal noch beachtet, ob der jeweilige Pixel eine gewisse Farbe hat. Willst du eine rote Fläche in eine blaue umfärben, so muss ein Pixel die Farbe rot haben damit er umgefärbt werden soll. Sollte denke ich klar sein. Wenn nicht guck dir im Internet noch mal weiteres zu FloodFill an.
So du willst nun keine Flächen füllen sondern kurze Wege finden.
Du hast dein 2D Raster. Eine Pixelgrafik ist ja im Prinzip auch ein 2D Raster. Ein Pixel würde jetzt einer Zelle in deinem Raster entsprechen. Du musst eine Zelle irgendwie markieren können, damit du bereits besuchte Zellen nicht noch mal besuchst.
Normal würdest du von deinem Startknoten expandieren, bis alle von dort aus erreichbaren Knoten markiert wurden. Zu diesen Knoten kannst du dir nun den Abstand zum Startknoten Speichern. Dein Startknoten erhält den Wert 0, da man ihn von sich selbst aus in 0 Schritten erreichen kann. Alle Punkte die in einem Schritt erreicht werden können bekommen die Länge 1, da sie in einem Schritt erreicht werden können. Im Prinzip kannst du diesen Abstandswert schon als Markierung nehmen. Jetzt würdest du nicht abfragen, ob eine Zelle schon markiert ist, sondern ob sie mit einem geringeren Wert als dem neuen markiert ist. Ist der neue Wert kleiner, so wurde ein kürzerer Weg gefunden und die Zelle muss neu expandiert werden. Am Ende hast du für jede Zelle eine Zahl, die den Abstand zu deinem Startwert darstellt. Willst du jetzt von einer Zelle den Weg zu deinem Startknoten finden, so nimmst du diese Zelle und betrachtest dessen Nachbarn. Du wählst den Nachbarn mit dem geringsten Wert. Das machst du jetzt so lange bis du bei deiner Startzelle bist. Diese durchlaufenen Zellen sind dann dein Pfad in falscher Reihenfolge. Du drehst das ganze um und hast es.
Bei diesem Ansatz bestimmst du aber Wege von einem Punkt zu allen anderen. Dijkstra oder A* würden das ganze noch etwas schneller lösen können. Sind dafür etwas aufwendiger zu implementieren. Je nach Anforderung reicht da die Variante mit FloodFill vermutlich mehr als aus.

edit: Und noch ein wenig Pseudocode:

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

FloodFill(x, y, n)
{
    if feldIstNichtBetretbar(x, y) // Wenn hier kein Weg möglich
        return;

    if gibAktuellenWert(x, y) > n // Neuer Weg wäre länger
        return;
    
    setzeNeuenWert(x, y, n); // markieren
    
    FloodFill(x-1, y, n+1);
    FloodFill(x+1, y, n+1);
    FloodFill(x, y-1, n+1);
    FloodFill(x, y+1, n+1);
}


Willst du jetzt einen Weg finden müssen die Werte zu deinen Zellen zuerst alle auf Unendlich (Int.Max oder was auch immer) gesetzt werden. Dann führst du FloodFill aus. Der Parameter ist am Anfang natürlich 0, da der Weg vom Start zum Start 0 ist. Wie du danach vom Ziel zum Start findest, steht ja weiter oben. Als Tipp, wenn ein Algorithmus dir einen Pfad rückwärts zurück gibt, so kannst du den Algorithmus auch einfach verdreht ausführen. Damit meine ich, dass du Start und Ziel einfach vertauschst. So bekommst du den Weg direkt in richtiger Reihenfolge. Oder man fügt neu gefundene Knoten vorne an eine Liste an und nicht hinten. Dazu benötigt man aber passende Datenstrukturen. Das sprengt jetzt hier aber auch das Thema denke ich.
„Es ist doch so. Zwei und zwei macht irgendwas, und vier und vier macht irgendwas. Leider nicht dasselbe, dann wär's leicht.
Das ist aber auch schon höhere Mathematik.“

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Schorsch« (03.04.2013, 18:00)

MitgliedXYZ

Alter Hase

  • »MitgliedXYZ« ist der Autor dieses Themas

Beiträge: 1 369

Wohnort: Bayern

  • Private Nachricht senden

19

03.04.2013, 18:06

Wow, danke für die gute Erklärung, ich werde mich gleich mal an die Umsetzung machen.
Vielen Dank schon mal.

EternalPain

Frischling

Beiträge: 87

  • Private Nachricht senden

20

03.04.2013, 19:35

Zitat von »"MitgliedXYZ"«

Und da ich in meinem Array auch nichts umfärben kann würde der Code in der Form unendlich lange weiterlaufen

Dafür habe ich in meiner Funktion ein Temporäres Array erzeugt.
Schorsch's Erklärung war sehr gut, hinzufügen möchte ich allerdings noch das rekursiv zwar schnell und einfach aber wegen des Stacks auch seine Grenzen hat (daher nur bedingt oder bei kleinen Maps einsetzbar)
Iterativ ist nur geringfügig komplizierter (bei C++, Java und Co gibt es glaube schon von Haus aus Listen daher sollte das da wohl weniger ein Problem sein...) dafür aber (beinahe) unbegrenzt einzusetzen...

Zitat von »"Schorsch"«

Willst du jetzt einen Weg finden müssen die Werte zu deinen Zellen zuerst alle auf Unendlich (Int.Max oder was auch immer) gesetzt werden.


Persönlich finde ich es einfacher (durch das Temporäre Array) bei 0 anzufangen (0 = noch nicht erreicht/geprüft), der Startpunkt bekommt Wert 1 dann aufsteigend... spart mMn Zeit...

Wenn das Ziel erreicht/gefunden wurde hast Du dessen Wert und suchst dann wieder rückwärts nach den nächst kleineren bis Du wieder bei 1 angekommen bist...

Werbeanzeige

Ähnliche Themen