Wegfindung

[Toto]

Hallo,

seit einigen Wochen/Monaten programmiere ich nun an einer Mini-Adventure-Engine. Sie soll mit möglichst wenig Informationen ein einfaches, aber funktionstüchtiges Adventure erstellen und vor allem erweiterbar sein.
Das ganze mache ich aus Spaß und ich weiß auch nicht, ob ich jemals ein Adventure damit entwerfen werde/kann.
Arbeitstitel der Engine ist sAsU. Sie wird komplett in Java geschrieben.

So, nun aber zu meinem Problem.
Die Engine läuft, man könnte theoretisch schon Spiele damit entwerfen.
Bis jetzt existiert der Held, also die steuerbare Figur jedoch nur formal.
Über Animationen und deren Verwaltung habe ich mir bereits Gedanken gemacht und sehe da keine Probleme.
Das Problem wird wohl die Wegfindung werden...

Nun habe ich die Wahl zwischen richtiger Wegfindung (Algorithmus ala Dijkstra) oder einem Pfadsystem.
Da ich mich nicht entscheiden kann, habe ich mir über beides Gedanken gemacht:

Richtige Wegfindung:
- Man müsste Bereiche festlegen, in denen sich der Held bewegen darf. Vielleicht mittels Quadraten? Ein Bereich könnte also aus vier Punkten bestehen. Bei der Initialisierung des Algorithmus müsste ich jetzt alle betretbaren Punkte als Knoten definieren...
Aber wie lasse ich den Helden dann wirklich einen Schritt vorwärts laufen? Parallel zum Algorithmus? Ich denke es ist intelligenter den Weg finden zu lassen und erst dann zu laufen. Dann müsste ich allerdings wieder eine Klasse "Pfad" entwerfen, die Rückgabetyp von der Wegfindung ist. Ich könnte dann position = Pfad.nextStep(); aufrufen und bekäme damit den nächsten Schritt.
Ist dieser Gedanke so richtig?
- Wenn ich mit der Maus auf die Spieloberfläche klicke, wird der Lauf-Thread gestartet. Es muss der Punkt ermittelt werden, der in einem betretbaren Bereich liegt und am nächsten an der Mausposition ist...

Pfadsystem:

Eigentlich sollte das Pfadsystem ja die einfachere Alternative sein... aber so einfach finde ich die garnicht.
Wie lege ich den Pfad fest? Sollte ich jeden einzelnen Pixel des Pfades angeben oder nur Positionen, an denen sich die Laufrichtung ändert? Und wie stelle ich den Pfad da? Als eine Art Binärbaum? Also so, dass jeder Punkt eine "linke" und eine "rechte" abzweigung haben kann?


______________________________________________________

Hat hier jemand schonmal versucht eine Engine zu schreiben und kann mir sagen, ob meine Grundgedanken richtig sind?

lg Toto

[Lebostein]

Bei meiner QBasic-Engine hab ich mich damals an dem hier orientiert:
http://shatteredrealmproductions.com/Tw ... inding.htm

Grundidee: Alle begehbaren Flächen in Quadranten einteilen. Anhand der Verbindungen zwischen 2 Quadranten eine große Matrix mit Quadranten x Quadranten generieren (erfordert einige Matrixoperationen). Dann gibt man lediglich Start- und Zielquadrant vor und erhält den nächstbesten Quadranten. Diesen wieder mit dem Zielquadrant kombinieren und so weiter. Ich kann ja mal gucken, wie ich das im Detail damals gemacht habe...

Das Thema gabs schon mal:
http://www.adventure-treff.de/forum/vie ... athfinding

[Toto]

Hallo,

Habe mir mittlerweile eine ziemlich unkomplizierte Lösung ausgedacht, die für meine Zwecke allerdings völlig ausreichend ist.

Die begehbaren Flächen habe ich als Quadrate definiert.
Ich starte nun einen Lauf vom Startpunkt zum Zielpunkt:

Code: Alles auswählen

Distanz <- unendlich
        Solange der aktuelle Punkt nicht das Ziel ist
                 Wenn der Pixel oberhalb begehbar ist
                     Distanz von diesem Pixel zum Ziel kleiner als Distanz?
                              neuer Aktueller Punkt: Pixel oberhalb
                 Distanz <- unendlich

Und das natürlich mit allen Richtungen. Ist natürlich gefährlich, weil bei diesem Algorithmus Kreise entstehen können. Da die begehbaren Flächen aber allesamt sehr einfach strukturiert sind, kommt dies aber zum Glück nicht vor.
(Sollte ich merken, dass es doch passiert, muss ich halt abfragen, ob der aktuelle Punkt schonmal besucht wurde.)

Jetzt geht es an die Animation, was scheinbar noch viel furchtbarer wird. Das liegt aber wohl am ehesten daran, dass ich zu blöd bin, eine vernünftige Laufanimation zu erstellen So sieht es noch aus, als "rutscht" der Charakter...

[Simon]

Mit dem Problem des Rutschens bist du ja nicht allein, das kam (kommt) ja selbst in kommerziellen Produktionen vor. Meine Vermutung, ohne mich je mit der Materie befasst zu haben, ist, dass es an dem Verhältnis zwischen Schrittlänge und Animationsdauer liegt, die an die Abstände in deinem Hintergrund angepasst werden müssen, also liegt es vermutlich an der Feineinstellung von Zahlen. Wäre spannend, selbst mal an soetwas zu arbeiten.

[KhrisMUC]

Der Trick ist lediglich, bereits beim Erstellen der Laufanimation darauf zu achten, dass sich ein Fuß, der den Boden berührt, immer die gleiche Anzahl Pixel rückwärts bewegt. Im Spiel muss sich der Charakter dann nur dieselbe Anzahl Pixel pro Frame vorwärts bewegen und schon gibt's kein Rutschen mehr.

Komplett vermeiden lässt es sich natürlich nicht (es sei denn man benutzt ein spezielles Pathfinding, siehe z.B. Baphomets Fluch*). In der Regel wird sich die Figur selten exakt seitlich oder hoch/runter bewegen und deswegen ist leichtes Rutschen immer dabei.

* George geht immer in eine der vier Himmelsrichtungen oder in einem festgelegten Winkel schräg; die entsprechenden acht Laufanimationen und eine Skalierung der Schrittweite sorgen für praktisch perfektes Laufverhalten.