Kleines Wort, große Auswirkung... und ein äußerst interessantes Kapitel nicht nur in der Spieleprogrammierung.

Gehen wir von folgendem Szenario aus:
Ihr habt eine Tilemap (a la C&C, AOE oder eigentlich fast jedes andere 2D-Strategiespiel sowie RPG). Diese Map soll im Prinzip beliebig groß werden (wie wärs mit 100000x100000 Feldern AOE-Maps? *g*).

Auf der Map gibt es verschiedene Felder, z.B.
- Grass
- andere Terraintypen wie Sumpf, durch die man nur langsam durchkommt
- Wasser
- Felsen (da kommt man nicht durch...)
- Wald (kommt man auch nicht durch, aber irgendwann ist der Wald weg und man kann durch)

Außerdem stehen noch Gebäude rum, Mauern etc.. die potentiell zerstört werden können.

Wie würdet ihr einen Pathfinding-Algorithmus hier ansetzen?

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

Nachdem ich nun von DP im Chat folgende Zeile bekommen habe:

<darthpaul> Prefect der nachteil ist wenn man alles weiss dass keiner einem helfen kann :|

Ich erwarte hier keine überintelligente, nobelpreisgewinnende Hilfe von irgendjemandem. Um genau zu sein, ich stehe im Moment nicht wirklich vor diesem Problem. Ich würde nur gern wissen, was ihr von Pathfinding wißt, wie ihr damit zusammengestoßen seid, und wie ihr so ein Problem angehen würdet (wenns sein muß).

Außerdem weiß ich nicht alles. Wie oft muß ich das noch sagen? :/

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

Naja....aber fast!

Auf jeden Fall habe ich mich mit einem Pathfinding-Alogorithmus noch überhaupt nicht auseinandergesetzt und ich bin auch noch nicht so der Held in C++ aber ich schreib mal trotzdem was.
Ich würde mal eine Linie von Startpunkt des Players und dem Zielpunkt ziehen. Da das ja Luftlinie ist, geht es nicht mehr kürzer!
Das Problem ist, dass es ja Hindernise gibt, die der Player ja umlaufen muss!
Hierzu würde ich einen 3. Punkt definieren, der auf dem Umkreis des Hindernisses liegt!
Und dann von Punkt 1 zu Punkt 2 zu Punkt 3 und schon ist man am Ziel!
Ich weiß nicht, ob man das in Code umsetzten kann, oder ob es überhaupt funktioniert, aber irgendjemand muss ja mal einen Ansatz bringen.....

BattleTech-MOD:
http://bthl.unitedgaming.net/

Ich würde die ganze Sache klassisch angehen.

Wir starten bei dem roten Feld (ok - ist nicht wirklich rot *g*) und wollen zu dem Blauen. Dummerweise steht zwischen Start und Ziel ein Hinderniss (Gebierge, Wand, was weiss ich). Nun werden sämmtliche Felder markiert, die von dem Zielpunkt direkt erreichbar sind. Die Markierung erfolgt mittels eines Zählers.

Das wird für die markierten Felder solange wiederholt, bis der Startpunkt erreicht ist.

Nun müssen wir nur den Markierungen folgen, also von dem Feld '8' auf eines mit '7' - '6' u.s.w.

Das Sumpf-Problem (man kommt zwar durch, aber nicht so schnell) und das Problem der zerstörbare Hindernisse sollte eigentlich auch relativ einfach lösbar sein.

Der Horizont vieler Menschen ist ein Kreis mit Radius Null - und das nennen sie ihren Standpunkt.

Gar nicht dumm...wirklich nicht.

--
It's not a BUG, it's an undocumented feature!

du musst aber noch beachten das verschiedene Bodenfelder verschiedene "qualitäten" haben die ja auch auswirkungen auf die geschwindigkeit haben, also sollte bei der entscheidung noch ein gewisser "qualitätsfaktor" den weg entscheidend beeinflussen

... ui das hast du ja erwähnt *fg*

Another1

...relaxing..atm =)
... und Schweiz suckt!

Hmm ist ja nett! :)

Was bedeutet in dem Zusammenhang eigentlich "Pattern"?

shielding people from their own stupidity is an evolutionary step backwards anyway.

/* God is dead!............Nietzsche */
/* Nietzsche is dead!......God */
/* Nietzsche is God!.......The Dead */

um

"wie wärs mit 100000x100000 Feldern AOE-Maps?"

wäre das nicht _etwas_ langsam mit obiger methode?

Nein, ich denke nicht, dass das langsam wäre. Denn, wenn man das Teil wirklich realistisch machen will, dann sollte man sowieso nur wenige Schritte im Voraus abklären. Denn im Nebel des Krieges und so sollen ja die Computergegner auch Probleme haben.
Es ist allerdings noch folgendes: Man sollte einen einfachen & schnellen Weg finden, bekannte Wege zu speichern. So dass diese schneller benutzt werden können, ohne viel Vorberechnung. Das kann man aber glaub ich mit Wegpunkten erreichen. Der Computer weiß die Wegpunkte, und berechnet dann nur den Weg zwischen diesen Punkten (damit das immer ein bisschen zufällig ist). Dann sollte er aber natürlich diese Wege nicht statisch benutzen, sondern dynamisch anpassen, beispielsweise, wenn ein Handelsweg aufgeflogen ist und dort immer Gegner lauern...

TheTinySteini
Coder Poke646
"Don't Panic" - Hitchhiker's Guide to the Galaxy

Killing Me Softly's Methode ist in der Tat klassisch, und heißt übrigens Dijkstra's Algorithmus :)
Unterschiedliche Feldqualitäten einzubauen wäre simpel: Wenn man über einen Sumpf oder so drübergehen müßte erhöht man den Zähler z.B. um 1,5 anstatt um 1.
So ähnlich würde das natürlich auch mit Gegnern gehen: Felder werden, nachdem eine eigene Einheit dort vom Gegner überfallen wurde, als gefährlich markiert. Wenn nun ein Sammler/Dorfbewohner dort pathfindet müßte er seinen Zähler um 2 anstatt um 1 erhöhen (nur so als Beispiel).
Generell gilt: je größer der Erhöhungsschritt, desto "teurer" wird ein Feld, und desto eher wird es umgangen.

Natürlich hat diese Methode auch ihre Probleme, wie dp ja gesagt hat. Sie wird verdammt langsam. Das führt zur Entwicklung von Algorithmen wie A* (A star).
Bei A* schätzt der Algorithmus ab, wieviele Felder noch bis zum Endpunkt draufgehen. Dijkstra's Algorithmus wird ja im Endeffekt in einer Schleife realisiert, in der der Computer immer ein noch nicht bearbeitetes Feld mit möglichst niedrigem Kostenwert untersucht. Bei A* wird zu dem bereits vorhandenen Kostenwert noch die abgeschätzten Kosten dazugerechnet.
Vorsicht: Wenn die abgeschätzten Kosten größer sind als die tatsächlichen Kosten, dann liefert A* nicht mehr den optimalen Weg zurück. Je größer allerdings der Anteil der abgeschätzten Kosten, desto effektiver wird A* im Durchschnitt.
Ach ja, Dijkstra's Algorithmus ist im Endeffekt der Sonderfall von A*, bei dem der abgeschätzte Kostenanteil auf 0 gesetzt wird.
Ich hoffe die Erklärung ist verständlich, vielleicht zeichne ich noch ein paar nette Bilder :)

Wenn man sich die untersuchten Felder bei Dijkstra anschaut, sieht man, dass der Computer kreisförmig alle Felder um den Startpunkt herum untersucht. Bei A* dagegen untersucht der Computer bevorzugt Felder, die in die richtige generelle Richtung gehen. Wenn gar kein Hindernis vorhanden ist, untersucht der Computer nur die direkte "Vogelflug"-Linie zwischen Start- und Endpunkt. Einiges besser, stimmts?

Leider immer noch nicht gut genug. Eine Option, die ich mir überlegt habe, wäre ein doppelter A*, d.h. man beginnt die Suche gleichzeitig vom End- als auch vom Startpunkt. Dadurch könnte man die Anzahl der untersuchten Felder herunterbringen.

Aber auch das ist nicht "scalable" genug. Tatsächlich wäre es eine gute Idee, häufig benötigte Wege zu cachen. Allerdings hat das einige Schwächen, da die Einheitenbewegung dadurch evtl. ins lächerliche gezogen wird - die Einheit bewegt sich erst nach rechts, erreicht dann den Startpunkt des gespeicherten Weges und geht dann wieder nach links - das ist zwar jetzt überzogen, aber in der Art durchaus denkbar.
Um so etwas zu umgehen sollte man vielleicht eine Art Metapathfinding einführen, d.h. man teilt die Karte erstmal in Zonen ein, und sucht dann zunächst potentielle Wege durch verschiedene Zonen. Bloß, wie teilt man die Zonen auf?

Ach ja: Wenn man mit A* arbeitet, ist Nebel des Krieges eigentlich leicht einzubauen: Man beschreitet beim Pathfinding einfach keine Felder, die im unerkundeten Bereich liegen... der Algorithmus stoppt dann an dem Punkt, an dem die Länge des bekannten Weges + die Länge der Vogelfluglinie kleiner ist als alle bekannten Wege.

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

hm wie wäres es, wenn man die map einfach in 'leaves' unterteilt und dann die klassischen hl-vis-berechnungen im 2dimensionalen raum durchführt =)

aber mal was anderes

was ist ein rts ohne folgendes problem:

zwei sammler treffen sich auf einer brücke ...

*G*

d.h. man müsste ja die pathfind berechnung des öfteren durchführen, wenn sich irgendetwas ändern z.b. durch einen einheitenpulk oder durch deformiertes gelände dass dazu führt dass der weg 'teurer' wird .. ?

Was wäre, wenn man von Anfang an allen Feldern der Karte eine Zahl zuordnen würde. Normales Terrain ne 1.
Wenn dann das nächste Feld in einem höheren Level liegt, dann bekommt es halt ne 2 oder noch höher ne 3 usw... (So hätte man auch ganz einfach 3D-Terrain)
Dann könnte man doch alles in Echzeit berechnen - der Computer nimmt immer den Weg von einem Feld zum nächsten mit der geringsten Differenz.
Das Problem wäre, dass die Einheit sich evvtl im Kreis bewegt oder riesen Umwege geht und so mehr „Differenzen“ zurücklegt als es nötig wäre. Man müsste halt zwischen Startpunkt und Ziel eine Art Korridor legen, der meineetwegen 10 Felder breit ist, indem sich die Einheit bewegén darf. Kommt dann ein Fluß oder so dazwischen müsste halt an dem Punkt von dem aus die Einheit den Fluß erkennt ein neuer Startpunkt gelegt werden und somit auch der Korridor auch. Wenn das nicht hilft dann muß man den Korridor vergrößern.
Ein anderes Problem das man beseitigen könnte wäre, das untersucht werden muss ob der Startpunt einen unter schiedlichen Level als der Endpunkt hat. Denn wenn das nicht geschieht, dann läuft die Einheit immer weiter schön auf das Ziel zu und ein Feld vorm Ziel merkt sie, dass eine Differenz von 2 vorherrscht und sie diese „Klippe“ nicht hoch bzw runter kommt (Die einheit kann nur Felder mit einer Differenz von 1 überqueren) und müsste erst dann noch nen riesen Umweg um diese Klippe machen. Deswegen muss diese Situation ausgeschloßen werden.
Und wenn auf einem Feld ein Sumpf oder ähnliches ist, dann bekommt das Feld halt noch ein Zeichen (z.B. einen Buchstaben) als zweites Merkmal zugewiesen, welches in die Berechnung mit einbezogen wird.
...So und jetzt entwickeln wir das so weit, bis es Perfekt läuft und wir hier die beste uns schnellste KI der Welt haben. ;-))

mhh, da isses doch schon besser nen typischen A* algorithm oder so zu nehmen, prefect hatte auch schon gesagt das es ganz einfach wäre in dem Beispiel von KMS einfach boden "qualitäten" und höhenunterschiede einfliessen zu lassen, indem man die zahl im nächsten kästchen eben noch von Steigung und Bodenqualität etc abhängig macht (je größer desto "schlechter")

Another1

...relaxing..atm =)
... und Schweiz suckt!

Hm, hier gäb's was nettes über A*:
http://theory.stanford.edu/~amitp/GameProgramming/

... aber die Seite ist euch höchstwahrscheinlich bekannt (zumindest Prefect).

TheTinySteini
Coder Poke646
"Don't Panic" - Hitchhiker's Guide to the Galaxy

Psychodad, nur allein von Höhenunterschieden kannst du kein Pathfinding machen. Sieh dir z.B. C&C2 an, da gibts gar keine Höhenunterschiede. Das Pathfinding bei C&C2 ist übrigens kein Pathfinding sondern einfach ein Drauflosmarschieren. Wenn dan (oh Wunder!) ein Hindernis kommt, versuchen die Einheit, einen Weg an dem Hindernis entlang zu "tasten".

Darthpaul, so eine BSP-Unterteilung hab ich mir auch schon überlegt, aber ich denke doch, dass eine typische RTS-Map besser durch Tiles dargestellt wird...

Ach ja, und man macht die Brücke einfach breiter ;)

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

Ja, ich heute auch noch mal Zeit drüber nachzudenken! Ich denke meine Idee wäre auch fast eher so ein drauflosmarschieren. Der Weg muss wirklich schon komplett vorberechnet sein, bevor die Einheit losläuft.
Ich denke auch, dass das Pathfinding nicht so das Problem wär. Eher schon, dass der Computer angemessen reagiert, wenn er durch ne einfache Patroullie die vom Menschen geschickte Flotte endeckt, welche über die linke Flanke des Gebirges über die Brücke kommen wird (Ihr versteht was ich meine?!?).
Bzw dass der PC es geregelt bekommt wenn zum Bsp es absehbar ist, dass sich zwei Sammler auf einer Brücke (o.ä.) treffen werden.

Ich glaube bei gamasutra gab's mal ein Feature über Path-Finding...

*such*

ahja, hier:

http://www.gamasutra.com/features/19990212/sm_01.htm

Sollte man sich wirklich mal durchlesen, meiner Meinung nach sehr interessant, das Ende könnte vielleicht auch Prefect hilfreich sein, schau halt mal rein...=)

Masterstroke
resourcecode.de

... kenn ich schon ;)

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

http://www.gameai.com

----------------------------------------
[url="mailto:polymorph@gdnmail.net"]Polymorph[/url]
Lead Programmer of Paroxysm - Alien Encounters

Hmm.. ich mußte in den letzten Tagen feststellen, daß auch die Kollision selbst schon eine nette Herausforderung sein kann. Kryos verwendet eine Mischung aus Tile-basierter Kollision und 100%ig feiner Auflösung der Koordinaten von Einheiten.

Die TraceLine-Funktion für Kollisionen, die noch nicht mal auf Kollisionen mit anderen Einheiten prüft ist bereits 250 Zeilen lang :)
Und durch die ganze Fixedpoint-Arithmetik wirds auch nicht übersichtlicher *g*

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

ja Kollisionsabfrage zu coden is echt nen hartes stück arbeit :D
aber du schaffst das ;)

Another1

...relaxing..atm =)
... und Schweiz suckt!

nun ich klasischen qb-zeiten hab ich das so gemacht:
hab die ganze karte auch gecodet, also ich hab zb eine wand geht von koordinate 1 bis zu korrdinate 2.
und dann hab ich anhand ner if abfrage die kordinaten des "mäxchens" bestimmt und ihm dann gesagt:1. da darfst du durchgehen
2.:nein da is was im weg geh nen andern weg (zb die wand entlang)

is sicher nict die beste methode, aber ich war erst 13

„Und da wir uns ja seit heute etwas näher gekommen sind, kann ich nur sagen: Mir hilft da immer Norther volle Lautstärke (so wie jetzt), sodass die ganzen unrasierten, Wasserpfeife rauchenden, alternativen Wichsstudenten aus ihren, aus Bananenschalen und Abfall gebastelten, Sitzkissen fliegen.“

Hm, tile-based Collision? Also etwa so: wenn in einem Tile 2+ Einheiten stehen, dann soll er Kollisionsabfrage machen, ja?
Kann man dann die eigentliche Kollisionsabfrage nicht mit Bounding Boxes erledigen, die immer gleich ausgerichtet sind (á la HL)? Wäre vermutlich am einfachsten, ist bei Gebäuden zuverlässig und scheint auch bei AoE so zu gehen (denn da stecken manchmal Einheiten ineinander, aber nur, wenn sie in ner bestimmten Richtung stehen).
Um es ganz genau zu haben, könnte man natürlich auch ne Bitmap-Maske nehmen, und gucken, ob dort Pixel überlappen... naja =)

TheTinySteini
Coder Poke646
"Don't Panic" - Hitchhiker's Guide to the Galaxy

mhhh.. kannst du das mnal auf deutsch übersetzen?
ich bin zwar kein nuB aber das war mir zu hoch.

„Und da wir uns ja seit heute etwas näher gekommen sind, kann ich nur sagen: Mir hilft da immer Norther volle Lautstärke (so wie jetzt), sodass die ganzen unrasierten, Wasserpfeife rauchenden, alternativen Wichsstudenten aus ihren, aus Bananenschalen und Abfall gebastelten, Sitzkissen fliegen.“

Ja, die Abfrage erfolgt komplett mit Bounding Boxes. Aber gerade dadurch, dass die Einheit, die sich bewegt eine Größe hat (und nicht einfach ein Punkt ist), wird das ganze ja komplizierter...

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.