Allgemeine Fragen zur PROFAN Programmierung
Views (Heute): 241094 (2530)
  Suchen
 Zurück zur Übersicht
 AutorThema: Wegfindung
Lukas Baumann
Datum:11.07.01 13:37 Antwortenals Email verschicken (lukas_baumann@freesurf.ch) 


Hallo,

Ich bin dabei, ein Spiel in der Art von Pacman zu schreiben.
Das Problem sind jedoch diese "Geister" ,welche die Spielfigur verfolgen sollten. Hat jemand schon mal eine Wegfindung programmiert, die sich für solche Zwecke verwenden liesse?
Bin für jede Hilfe dankbar!

Lukas


Frank Abbing
Datum:11.07.01 15:33 Antwortenals Email verschicken (frankabbing@12move.de) 


Hallo,

ja, ich hab' schon mal eine Routine programmiert, die den Weg aus jedem Labyrinth findet, auch von Labyrinthen, deren Wege unterschiedlich breit sind.
Einen Code hab' ich leider nicht für dich (war programmiert für Amiga) aber ich kann's dir genau beschreiben, wie's geht. Am besten meldest du dich nochmal per email bei mir.

Frank


Frank Abbing
Datum:12.07.01 01:06 Antwortenals Email verschicken (frankabbing@12move.de) 


Ich gehe mal von folgendem Level von Lukas aus:

list$ 1="SSSSSSSSSSSSSSSSSSSSSSSS" 'S = Stein, W = Weg, P = Punkt
list$ 2="SSWWWPWSSWWSSSWPWWWSSWWS" 'G = Gegner und H = Spielfigur
list$ 3="SWWSSSWWWWSSSWWSSSWWPWSS"
list$ 4="SWSSSSWSSWWPWWSSSSWSSSSS"
list$ 5="SHSSSSWWSSWSSSSSSSWWSSSS"
list$ 6="SWWWPWWSSSWSSWWWPWWSSSSS"
list$ 7="SSSSSSWWSSWSSSSSSSWWSSSS"
list$ 8="SSSSSSWSSWWSSSSSSSWSSSSS"
list$ 9="SSSSWWWPWWSSSSSSWWPWWWSS"
list$ 10="SWPWWSSSSWWWWPWGWSSSSWSS"
list$ 11="SWSSWSSSSWSSSWSSSSSSSWSS"
list$ 12="SSSSWPWSSSSSSWWSSSSSSSSS"
list$ 13="SSSSSSWSSSSSSSWSSSSSSSSS"
list$ 14="SSWPWWWSSWWSSSWWWWWSSWWS"
list$ 15="SWWSSSWWWWSSSWWSSSWWWWSS"
list$ 16="SWSSSSWSSWWPWWSSSSWSSWSS"
list$ 17="SSSSSSWWSSSSSSSSSSWWSSSS"
list$ 18="SSWWPWWSSSSSSSSWPWWSSSSS"
list$ 19="SSSSSSWPSSSSSSSSSSWWSSSS"
list$ 20="SSSSSSWSSSSSSSSSSSWSSSSS"
list$ 21="SSSSWPWWWWSSSSSSWWWWWWSS"
list$ 22="SWWWWSSSSWWSSWWPWSSSSWWS"
list$ 23="SWSSSSSSSWSSSWSSSSSSSWSS"
list$ 24="SSSSSSSSSSSSSSSSSSSSSSSS"

Deine Level-Methode ist natürlich komplizierter und dauert länger, als wenn du Bereiche verwenden würdest. Egal es muß auch so klappen.
Für die Wegsuche gehst du am besten so vor (mehrere Schritte).

1). Kopiere deinen Level quasi als Schwarzweiss-Bild, in einen Bereich mit Bytes, sodaß nur zwei unterschiedliche Möglichkeiten von Feldern entstehen:

0=freies Feld
255 = besetztes Feld / Wand

Da deine Level an den Seiten immer zu sind, erleichtert das die Suche im Labyrinth.


2).Vom Startpunkt der Suche aus geht's los. Jetzt stell dir vor, du schickst eine Kugel los, die immer dahin rollt, wo der Boden am niedrigsten ist (0 ist ganz unten und 255 ist ganz oben).
Jetzt überprüfe die vier Felder neben dem Startfeld. Das Feld, dessen Wert am niedrigsten ist (wenn mehrere gleich niedrig sind entscheidet der Zufall), dahin rollt die Kugel. Und dort, wo eben die Kugel noch lag, erhöhst du den Wert um 1.
Wichtig! Jede Position der Kugel notierst du in einer Tabelle, also nicht den Wert, sondern die Position.
So machst du immer weiter. Laß die virtuelle Kugel immer weiter rollen (vergess aber nicht den Wert immer um 1 anzuheben, wo die Kugel lag).
Irgendwann hat sie den Zielpunkt erreicht (oder ist vom 255zigern umzingelt, in diesem Fall gibt es keinen Weg).
So, der Weg ist gefunden und jede Station in der Tabelle festgehalten, aber du wirst feststellen, das der Weg sehr umständlich ist und nicht direkt zum Ziel führt.

3). Wir müssen den Weg der Kugel optimieren.
Jetzt generieren wir eine zweite Tabelle. Lies den ersten Positionswert aus der ersten Tabelle und schreibe ihn in die zweite Tabelle.
Jetzt suche in der ersten Tabelle von hinten nach vorne nach, ob der Wert nochmal in ihr vorkommt (hier ist die Kugel zweimal vorbeigekommen, hat also eine unnötige Wanderung gemacht). Wenn das der Fall ist, machst du an dieser Stelle in der ersten Tabelle weiter und schreibt den nächsten Wert in die zweite Tabelle. Wenn du am Ende der ersten Tabelle angelangt bist, ist der (fast) optimale Weg gefunden und befindet sich in der zweiten Tabelle und du kannst deine Spielfigur den Weg entlang laufen lassen.


So, ich hoffe das war verständlich.
Diese Wegsuche ist von mir entwickelt worden und ich hab' sie den Marble-Algorhythmus genannt. Er funktioniert auch dann, wenn die Wege innerhalb eines Labyrinths verschieden breit sind, was andere Labyrinthalgorhythmen nicht tun, z.B. der Right-Hand-On-right-Wall Algorhythmus, nur zu eurer Information.


Frank Abbing


Andreas Gebel
Datum:11.07.01 21:53 Antwortenals Email verschicken (Gaby007@freenet.de) 


Hallöchen.....
Sowas ähnliches habe ich auch mal gemacht.....
Das Prinzip:

Kontroliere ob Ziel
links/rechts
hoch/runter
ist.
"Eine" Richtung wird Fest vorgegeben, die andere wird ständig Kontrolliert.

Lege fest das jede feste Richtung midestens 10 Schritte beinhaltet (oder durch Zufallsgenerator)
Wecksel nach Ablauf der festen Schritte, zbs (H/R Fest L/R Abfrage)..... zu (L/R Fest H/R Abfrage)......
Beispiel:
Pos. Objekt Links/Oben
...also 10 schritte nach "links" (falls frei)...Pro Schritt "hoch" wenns geht...

Ich hoffe du hast verstanden wie ichs meine wenn nicht, dann Mail mal an.
PS.: Nach diesem Prinzip, hatte ich fast keine Chance zu entkommen ) ;-)



Frank Abbing
Datum:01.06.02 11:29 Antwortenals Email verschicken (frankabbing@12move.de) 


Hallo,

die ProSpeed.dll wird in der nächsten Version eine Funktion für die Wegfindung anbieten, und zwar wird jeder Weg innerhalb einer Bitmap gefunden. Der Weg wird in einer Tabelle gespeichert und kann so von einem Sprite abgefahren werden. Demnächst mehr.

Webpage
Zum ProSpeed-Forum

Gruß, Frank


Thorsten
Datum:01.06.02 15:41 Antwortenals Email verschicken (mrk@mrk-soft.de) 


Hi,

Das Original PacMan (Atari Clone) wurde mit Profan und
der Prospeed.dll umgesetzt.
Zu finden auf meiner Page ... www.mrk-soft.de

Im Tagebuch sind einige lustige Infos bei der Entstehung
zu Finden, sowie ein wenig über die Technik.



Frank Abbing
Datum:03.06.02 21:17 Antwortenals Email verschicken (frankabbing@12move.de) 


Hallo,

die ProSpeed Wegfinde-Funktion ist fertig.
Ich hab' mal ein Programm entwickelt, um die Wegsuche bequem zu testen.
Sollten noch auf irgendeinem Windows-System Fehler entstehen, wäre es nett, wenn ihr mir Bescheid gebt.
Fröhliches Labyrinth-Zeichnen ;-))

Hier downloaden.

Gruß, Frank


Alexander Schoenfeld
Datum:04.06.02 08:18 Antwortenals Email verschicken (alexander.schoenfeld@chronologic.de) 


Hallo Frank !

irgendwie will das bei mir nicht klappen (Win2000 / SP2).
Selbst wenn ich in der Mitte eine riesige Schwarze Fläche erzeuge und Start/Zielpunkt da reinlege, kriege ich die Meldung das kein Weg gefunden werden konnte...

Mit freundlichem Gruss / kind regards,
Alexander Schoenfeld

Email: alexander.schoenfeld@chronologic.de


Frank Abbing
Datum:04.06.02 12:13 Antwortenals Email verschicken  


Hallo Alexander,

die schwarzen Flächen sind die Mauern !!!
Wege werden nur in weißen Flächen gefunden, und diese Wege sollten mindestens so dick/groß sein, wie die Breite, die man per rechten Mausknopf erzeugt.
Start- und Zielpunkt müßen ebenfalls großräumig frei sein (weiß).
Dann sollte alles klappen...

Gruß, Frank


Alexander Schoenfeld
Datum:04.06.02 12:26 Antwortenals Email verschicken (alexander.schoenfeld@chronologic.de) 


Hallo Frank,

Da hatte ich mich wohl verlesen, bzw nicht deutlich genug gelesen ^^;
Jetzt funktioniert's auf jedenfall ^^

Mit freundlichem Gruss / kind regards,
Alexander Schoenfeld

Email: alexander.schoenfeld@chronologic.de


Frank Abbing
Datum: 04.06.02 16:53 Antwortenals Email verschicken  


Danke Alexander !

Gruß, Frank


 Zurück zur Übersicht