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!

Erreichbare Felder auf Grid berechnen

  • 1
  • 2

Werbeanzeige

Garzec

Alter Hase

  • »Garzec« ist der Autor dieses Themas

Beiträge: 693

Wohnort: Gießen

  • Private Nachricht senden

1

15.05.2018, 18:44

Erreichbare Felder auf Grid berechnen

Hallo,
bei gridbasierten Spielen bekommt man vor der Bewegung alle erreichbaren Punkte angezeigt. Dabei hat der Spieler eine bestimmte Bewegungsreichweite. Ebenso haben alle Felder unterschiedliche Feldkosten, manche Felder sind gar nicht begehbar und ein Umweg muss in Kauf genommen werden.

Steht der Spieler auf einer Position (2D Grid) möchte ich alle erreichbaren Punkte berechnen. Meine wahrscheinlich umständlichste Idee wäre:

- über den Punkt und die Reichweite die beiden Außenpunkte obenLinks und untenRechts berechnen
- über dieses aufgespannte Rechteck alle Punkte holen
- für jeden Punkt den A* laufen lassen, ob der Punkt anhand der Feldkosten (nicht begehbare Punkte berücksichtigt) und der Bewegungsreichweite erreichbar ist

Ich bin mir relativ sicher, dass es irgendwie einfacher geht, natürlich werden nur Integer miteinander verrechnet aber bei einem großen Grid könnte es möglicherweise doch rechenintensiv sein. Über eine Schleife kann ich schnell alle Punkte auf der horizontalen und vertikalen Linie berechnen. Bei den abweichenden Punkten, also beispielsweise die diagonalen Punkte, wüsste ich dann nicht mehr, wie ich diese berechne.

Typische Beispiele von Spielen wären Advance Wars oder Fire Emblem.

Hat jemand schon einmal sowas gemacht? Mit ein wenig mehr Mathe geht es bestimmt leichter :thumbup:

DNKpp

Alter Hase

Beiträge: 635

  • Private Nachricht senden

2

15.05.2018, 19:11

Was spricht da gegen eine https://de.wikipedia.org/wiki/Breitensuche ?
Damit gehst du vom Zentrum alle Punkte ab, und das zuerst in die Breite (in deinem Fall also in einem immer größer werdenden Radius um deinen Mittelpunkt). Damit kannst du die Kosten doch super akkumulieren.

EDIT: eine Abbruchbedingung für einen Branch wäre eben, dass die Kosten die Reichweite überschreiten.

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

3

15.05.2018, 20:21

Du kannst dafür auch Floodfill nutzen. Die Idee hatte TGGC vor längerer Zeit mal hier in den Raum geworfen und ich finde sie gar nicht schlecht. Floodfill ist in etwa das was das Bucket-Tool bei Programmen wie Paint, Photoshop und Co macht. Du startest bei deinem Startpunkt und guckst welche Nachbarn begehbar sind. Bei jedem begehbaren Nachbarn startest du den Floodfill neu. Hierbei merkst du dir welche Felder du bereits betreten hast. Das machst du so lange bis kein neues Feld mehr da ist. Anstatt also eine Grafik mit einer Farbe zu füllen markierst du einfach Kacheln in deinem Raster. Du kannst für die Markierung theoretisch auch Zahlen nehmen. Dein Startfeld hat den Wert 0, jedes darauf markierte Feld bekommt den aktuellen Wert +1, wodurch die direkt an das Startfeld angrenzenden Felder den Wert 1 bekommen, alle daran angrenzenden Felder bekommen den Wert 2 und so weiter. Hier brichst du jetzt nicht ab sobald ein Feld bereits markiert ist, sondern überschreibst die Markierung, falls der neue Zahlenwert kleiner dem vorherigen Wert ist. Dadurch erhältst du am Ende die Wege die du zu jedem Punkt gehen musst.
„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.“

Garzec

Alter Hase

  • »Garzec« ist der Autor dieses Themas

Beiträge: 693

Wohnort: Gießen

  • Private Nachricht senden

4

15.05.2018, 21:05

Da muss ich mal beide ausprobieren :)

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

5

15.05.2018, 22:15

Ob man Breiten- oder Tiefensuche macht, wird hier letztendlich egal sein, denn das Ergebnis ist das Gleiche. Nur auf die Rechenzeit wird Breitensuche evtl. schneller sein, da weniger Updates der Entfernungen noetig sind, wenn es viele verschiedene Wege gibt (und so hoert sich die Beschreibung an). Als Voraussetzung muss ja jede deiner Feldkosten über 0 liegen, sonst kann man theoretisch unendlich weit laufen. Daher kann man aufhören, sobald alle Felder betrachtet wurden bei denen die bisherigen Wegkosten kleiner der Reichweite waren.

A* ist hier unnoetig kompliziert, da man kein Ziel hat.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

6

15.05.2018, 22:45

Ja, Breitensuche ist hier definitiv der beste Ansatz. Einfach zu implementieren und maximal schnell.
David Scherfgens Website | Konzentrationstest Polizei

Damocles

Frischling

Beiträge: 26

  • Private Nachricht senden

7

16.05.2018, 09:28

Hab ich schön öfters implementiert. Das einfachste ist ein Floodfill (von der Spielerposition aus) zu benutzen, und die Tiles mit Kosten (Abstand vom Startpunkt) zu versehen.
Die fertige (Kosten) Map gibt dann für jeden Tile an, von welchem vorherigen Tile man ihn erreicht (derjenige Nachbarknoten mit den geringsten Kosten).
Den Pfad zwischen Spieler und Tile kann man dann rückwärts vom Zieltile aus berechnen (was dann sehr viel schneller ist als A*) indem Man immer den Tile mit den geringsten Kosten nimmt, bis man an der
Spielerposition ist.

A* hat einen anderen Anwendungsfall (effizient den Pfad zwischen genau zwei Punkten zu berechnen)

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »Damocles« (16.05.2018, 09:35)

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

8

16.05.2018, 10:00

Zitat von »Damocles«

Hab ich schön öfters implementiert. Das einfachste ist ein Floodfill (von der Spielerposition aus) zu benutzen, und die Tiles mit Kosten (Abstand vom Startpunkt) zu versehen.

Die Kosten sind aber hier nicht dasselbe wie der geometrische Abstand vom Startpunkt, darum funktioniert klassisches Floodfill hier nicht. Jedes Feld kann nämlich mit verschiedenen Kosten verbunden sein, z. B. ist es anstrengender durch Sand zu laufen als über Eis zu rutschen ... ;) Darum Breitensuche mit gewichteten Kanten - dieser Algorithmus ist optimal und recht einfach zu implementieren. Vielleicht meintest du das auch, hast es aber irrtümlich Floodfill genannt (ist was anderes)?
David Scherfgens Website | Konzentrationstest Polizei

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

9

16.05.2018, 10:07

Ob es "maximal schnell" ist, haengt vom konkreten Graph, Kosten und Reichweite ab. Breitensuche hat das Problem, das es oft quer durch den Speicher springt, wodurch es oft langsamer als erwartet läuft auf modernen Maschinen. Ich vermute aber in dem Fall ist das wenig relevant.

P.S: Der Unterschied zu einem Floodfill ist lediglich das man Knoten wieder oeffnet, wen man einen kuerzeren Weg findet. Da ist im Algorithmus eine if Abfrage anders, man ersetzt ein != durch ein <.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Damocles

Frischling

Beiträge: 26

  • Private Nachricht senden

10

16.05.2018, 10:29

Zitat von »David Scherfgen«

Die Kosten sind aber hier nicht dasselbe wie der geometrische Abstand vom Startpunkt, darum funktioniert klassisches Floodfill hier nicht. Jedes Feld kann nämlich mit verschiedenen Kosten verbunden sein, z. B. ist es anstrengender durch Sand zu laufen als über Eis zu rutschen ... ;) Darum Breitensuche mit gewichteten Kanten - dieser Algorithmus ist optimal und recht einfach zu implementieren. Vielleicht meintest du das auch, hast es aber irrtümlich Floodfill genannt (ist was anderes)?


Die Breitensuche in dem Beispiel hier, bricht aber ab wenn der Zielknoten gefunden wurde.

if(node == goal_node) {
return true; // testen, ob Ziel-Knoten gefunden
}

Bei dem Verfahren was ich nutze (Ob jetzt Floodfill der richtige Begriff ist, ich nenns einfach mal so) bricht die Suche aber nicht beim erreichen des Zielknotens ab, sondern wenn keine Weiteren Knoten gefunden werden können.
Also die Liste der offenen Knoten leer ist. -> Die gesamte Map wird immer gefüllt (wenn erreichbar)
Es werden da die Kosten von Tile zu Tile beachtet, je nach Tiletyp (also nicht nur die euklidische Distanz zwischen Ihnen)

Ich kann später man ein Pseudocode Beispiel machen.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Damocles« (16.05.2018, 10:59)

Werbeanzeige

  • 1
  • 2

Ähnliche Themen