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!

Pyramids of Ra Pathfinding Algorithmus

  • 1
  • 2

Werbeanzeige

Maggot

Frischling

  • »Maggot« ist der Autor dieses Themas

Beiträge: 51

Wohnort: Wien

Beruf: Software Entwickler

  • Private Nachricht senden

1

10.11.2016, 12:26

Pyramids of Ra Pathfinding Algorithmus

Hallo,

ich bin auf der Suche nach einem Algorithmus, der überprüft, ob auf einem Grid basierten Spielfeld alle Felder 1x besucht werden können. So wie in dem Spiel "Pyramids of Ra" (Demo: http://www.emanueleferonato.com/2016/10/…pyramids-of-ra/)

Das wäre insofern interessant, wenn man die Level zufällig generieren möchte, um zu überprüfen, ob es lösbar ist.

Brauche ich da einen Graphalgorithmus? Gibt es vielleicht Beispiele?

Danke schon mal :)

Colin117

Frischling

Beiträge: 16

Beruf: Azubi Fachinformatiker - Anwendungsentwickler

  • Private Nachricht senden

2

10.11.2016, 15:48

Schau mal das hier an. Macht eigentlich genau was du brauchst, du musst halt dann noch schauen ob er alle tiles erreichen kann. Dafür gibt es auch haufenweise Beispiele in allen möglichen Sprachen, google mal danach ;)

Edit: Ich glaube ich hab's erst falsch verstanden, du willst genau einmal auf jedes Feld, das ist natürlich etwas schwerer, Entschuldigung. >.<

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Colin117« (10.11.2016, 16:07)

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

3

10.11.2016, 16:08

Das ist kein Pathfinding. Und auch kein Floodfill wie hier behauptet wird. Da kommen noch Randbedingungen hinzu, welche das eine Groessenordnung schwerer machen.

Man kann (muss aber nicht) das ganze in einem Graph formulieren. Dann ist ein Hamiltonkreis gesucht (evtl. noch mit Nebenbedingungen, kenne das Spiel nicht so genau). Darueber ist momentan bekannt, das es durch systematisches Probieren loesbar ist. D.h. es ist praktisch unloesbar fuer grosse Graphen.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

4

10.11.2016, 16:33

Für zufällige Generierung würde ich den umgekehrten Weg vorschlagen: Von einem Punkt aus starten, wild durch die Gegend laufen (und prüfen, dass es noch immer einen validen Rückweg gibt, was ja mit Pathfinding einfach ist) und am Ende wieder zum Ausgangspunkt laufen. Das Ergebnis ist auf jeden Fall erfüllbar. Allerdings nicht unbedingt sehr kompliziert, je nachdem, wie der "zufällige" Pfad generiert wurde.
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]

Maggot

Frischling

  • »Maggot« ist der Autor dieses Themas

Beiträge: 51

Wohnort: Wien

Beruf: Software Entwickler

  • Private Nachricht senden

5

11.11.2016, 07:14

Okay, danke schon mal für eure Antworten.

Lassen wir mal das zufällige Generieren weg und konzentrieren wir sich auf das Lösen von vorgegebenen Leveln mit dem Hamiltonkreis.

Als ausgangsbasis nehme ich jetzt einmal das verlinkte von oben

(Link)


Würde die Nummerierung so passen?

Nehme ich jetzt mal den Startpunkt 26 und wie gehe ich weiter? Probiere einfach einen zufälligen weg?

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

6

11.11.2016, 12:58

Was ist der Sinn der Nummerierung? Willst du jemand verwirren? Dafuer erscheint sie mir gut geeignet.

Du kannst einen zufälligen Weg probieren. Du kannst aber auch systematisch probieren.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Nox

Supermoderator

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

7

11.11.2016, 13:28

wie kommt man beim Beispiel von der 24 zur 25?
PRO Lernkurs "Wie benutze ich eine Doku richtig"!
CONTRA lasst mal die anderen machen!
networklibbenc - Netzwerklibs im Vergleich | syncsys - Netzwerk lib (MMO-ready) | Schleichfahrt Remake | Firegalaxy | Sammelsurium rund um FPGA&Co.

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

8

11.11.2016, 13:32

Erwartest du jetzt ein Liste aller 7 Millionen Moeglichkeiten?
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

9

11.11.2016, 13:47

Zitat von »Nox«

wie kommt man beim Beispiel von der 24 zur 25?

Ich denke die Zahlen repräsentieren einen möglichen Weg wobei eben auch diagonale Bewegungen möglich sind.
„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.“

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

10

11.11.2016, 13:53

Die Nummern muss er willkürlich vergeben haben, denn selbst bei diagonalen Schritten sind Anfang und Ende nicht dasselbe Feld. ;) Ich glaube er wollte einfach nur Nummern haben anhand denen er jetzt die Funktionalität des Algorithmus erklärt haben wollte.
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]

Werbeanzeige

  • 1
  • 2

Ähnliche Themen