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!

Algorithmus zum Finden aller begehbaren Tiles

  • 1
  • 2

Werbeanzeige

Phalax

Frischling

  • »Phalax« ist der Autor dieses Themas

Beiträge: 82

Beruf: Student Media Systems

  • Private Nachricht senden

1

24.03.2011, 20:09

Algorithmus zum Finden aller begehbaren Tiles

Hi,

ich arbeite zur Zeit an einem Rundenbasierten - Strategiespiel und suche nun eine Möglichkeit von einer Einheit aus, alle im Bereich der Bewegungsreichweite liegenden, begehbaren Tiles zu finden. Hierbei sollen auch die Kosten berücksichtigt werden (Wald kostet mehr als Grasland zu druchqueren, also soll der Wald zum beispiel die Bewegungreichweite um 1 verringern).
Ist dafür der A* Algorithmus geeignet? denn eigentlich will ich ja alle Möglichen Wege und nicht den schnellsten Weg von A nach B finden.

Architekt

Community-Fossil

Beiträge: 2 481

Wohnort: Hamburg

Beruf: Student

  • Private Nachricht senden

2

24.03.2011, 20:14

Aber der A* enthält deine Kosten bereits. Es war ja so, dass z.B. schräge Tiles mehr kosten als direkt (horizontal/vertikal) benachbarte. Das könntest du entsprechend per Abfrage je nach Tile-Art abändern.
Und naja du suchst ja schon von A (der Position deines Spielers) zu B (zum ende des Sichtradius). Also lässt du dir alle Möglichkeiten berechnen bis du keine oder, besser gesagt, nur noch bereits gefundene Wege erhälst.
Der einfachste Weg eine Kopie zu entfernen ist sie zu löschen.
- Stephan Schmidt -

Phalax

Frischling

  • »Phalax« ist der Autor dieses Themas

Beiträge: 82

Beruf: Student Media Systems

  • Private Nachricht senden

3

24.03.2011, 20:16

Also rufe ich den Algorithmus für jede Position am Sichtrand auf? Denn dann gibt es ja schon ein paar mehr Zieltiles. Naja ich denke ich werds mal so probieren, Dank dir. :)

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

4

24.03.2011, 20:22

Bloß nicht. Denn um den Weg von A nach B auszurechnen müsstest Du ja immer wieder die Tiles dazwischen neu ausrechnen, was ja aber überflüssig ist.
Ich würde ehrlich gesagt einfach iterativ oder rekursiv alle abklappern, Kreis- oder Spiral-artig. Müssen eh alle berechnet werden, also gibt es da genau genommen auch keine Optimierung.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Architekt

Community-Fossil

Beiträge: 2 481

Wohnort: Hamburg

Beruf: Student

  • Private Nachricht senden

5

24.03.2011, 20:22

Frag mich eher, warum du das machen willst. Um zu sehen, ob die nächsten/unmittelbaren Tiles begehbar sind oder wie?
Der einfachste Weg eine Kopie zu entfernen ist sie zu löschen.
- Stephan Schmidt -

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

6

24.03.2011, 20:24

Ich schätze mal, er will sowas wie bei Civilisation machen oder bei Schach mit einer Vorschau der möglichen Züge. Durchaus ja 'ne feine Sache für rundenbasierte Strategiespiele.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Architekt

Community-Fossil

Beiträge: 2 481

Wohnort: Hamburg

Beruf: Student

  • Private Nachricht senden

7

24.03.2011, 20:26

Zitat von »BlueCobold«

Ich schätze mal, er will sowas wie bei Civilisation machen oder bei Schach mit einer Vorschau der möglichen Züge. Durchaus ja 'ne feine Sache für rundenbasierte Strategiespiele.

Was war denn bei Civilisation?
Prüfen, ob der Platz für ein Gebäude ausreicht?
Der einfachste Weg eine Kopie zu entfernen ist sie zu löschen.
- Stephan Schmidt -

Phalax

Frischling

  • »Phalax« ist der Autor dieses Themas

Beiträge: 82

Beruf: Student Media Systems

  • Private Nachricht senden

8

24.03.2011, 20:26

@Architekt: Einmal das, ich will ja nicht das meine Infanterie einfach durch Wassertiles rennt, und anderer Seits kann jede Einheit ja nur eine Bestimmte Anzahl an Feldern zurücklegen, wobei natürlich Wald mehr "Bewegungspunkte" braucht als eine Staße.

@BlueCobolt: Du hast recht, da würde man ja vieles mehrmals durchlaufen.

Ja ich will eine Vorschau machen, um dann eben den Bewegungsbefehl zu geben.

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

9

24.03.2011, 20:28

Zitat von »Architekt«

Zitat von »BlueCobold«

Ich schätze mal, er will sowas wie bei Civilisation machen oder bei Schach mit einer Vorschau der möglichen Züge. Durchaus ja 'ne feine Sache für rundenbasierte Strategiespiele.

Was war denn bei Civilisation?
Prüfen, ob der Platz für ein Gebäude ausreicht?

Gebäude konnte man da nicht bauen. Eine Einheit hatte als Vorschau die Felder markiert, zu denen sie sich bewegen kann. Durchaus praktisch das vorher zu wissen, bevor man sich verschätzt und dann nicht so weit schieben kann wie gehofft.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Architekt

Community-Fossil

Beiträge: 2 481

Wohnort: Hamburg

Beruf: Student

  • Private Nachricht senden

10

24.03.2011, 20:28

Für die "ist begehbar Sache" würde ich eher pro Schritt testen, ob das nächste Tile (errechenbar aus derzeitiger Position und Richtung(s-Vektor) begehbar ist.
Was die Zeit-pro-Tile Sache angeht: ganz klar wie BlueCobold sagte rund herum abklappern.

edit: Achso, hab's nie gespielt. Dann ist mein obiges Statement ja hinfällig, denn du berechnest den Weg zu einem Ziel sicher vorab mittels des A*.
Der einfachste Weg eine Kopie zu entfernen ist sie zu löschen.
- Stephan Schmidt -

Werbeanzeige

  • 1
  • 2

Ähnliche Themen