This shows you the differences between two versions of the page.
z:pathfinding [2007/04/07 17:16] cabalistic angelegt |
z:pathfinding [2015/08/23 13:59] |
||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== Z Revival - Pathfinding ====== | ||
- | ===== Ausgangslage ===== | ||
- | |||
- | Für die Pfadfindung benutzen wir eine Gittereinteilung der Karten gemäß ihrer Heightmapgrößen, | ||
- | |||
- | {{z: | ||
- | |||
- | Die schwarzen Felder umranden einen isolierten Bereich, der nicht betreten oder verlassen werden kann. Einheiten müssen ihren Weg um diesen Bereich finden. Als Grundlage dient die A*-Graphensuche. | ||
- | |||
- | ==== Probleme ==== | ||
- | |||
- | Ein wesentliches Problem ist, dass eine A*-Suche über 256x256 Felder zu viel Zeit in Anspruch nehmen würde, sinnvolle Suchgrößen liegen wohl bei Ausschnitten von 60x60 Feldern. Das heißt, wir brauchen eine zweigeteilte hierarchische Suche, damit Einheiten auch über eine volle Kartenlänge navigieren können. | ||
- | |||
- | Unbewegliche Objekte auf der Karte (Fabriken, Flaggen, Dekoration) sind ebenfalls nicht passierbar, allerdings weder in Position noch Richtung mit dem Suchgitter angeglichen. Eine Fabrik, die vielleicht größenmäßig etwa 3x3 Feldern entsprechen könnte, kann völlig quer zum Gitter platziert sein. Es muss geklärt werden, welche der angrenzenden Felder noch als passierbar gelten und welche nicht mehr. | ||
- | |||
- | Andere Einheiten bzw. generell mobile Objekte stellen ebenfalls Hindernisse verschiedener Größen dar. Es braucht eine Strategie für die Wegsuche, halbwegs mit anderen Einheiten klarzukommen. Gerangel mit querlaufenden Einheitenverbänden wird sich kaum vermeiden lassen, aber zumindest innerhalb einer Gruppe, die einen gemeinsamen Bewegungsbefehl erhält, sollten möglichst wenig Reibereien entstehen. | ||
- | |||
- | Einheiten haben unterschiedliche Größen, grob als Abschätzung können Fahrzeuge evtl. etwa ein Feld belegen, Roboter eher 1/9 eines Feldes. Demzufolge könnten Roboter teilweise noch Felder betreten, die für Fahrzeuge bereits blockiert sind. Je nach Gemüt muss man dies entweder berücksichtigen und die Passierbarkeit von Feldern abweichend für Roboter und Fahrzeuge definieren, oder aber hier eben ein Auge zudrücken und ein etwas schlechteres Suchverhalten für die Roboter in Kauf nehmen. Theoretisch könnte man auch ein feineres Suchgitter für die Roboter anlegen, aber das vergrößert Problem Nr. 1 nur noch erheblich. | ||
- | |||
- | Roboter können durch Wasser schwimmen, Fahrzeuge nicht. Wasserfelder müssen entsprechend unterschiedlich behandelt werden. Natürlich ist die Passiergeschwindigkeit durchs Wasser geringer. | ||
- | |||
- | Brücken können Verbindungswege zwischen Stellen schaffen, die anderweitig nicht verknüpft wären. Brücken sind aber zerstörbar, | ||
- | |||
- | |||
- | ===== Ansätze ===== | ||
- | |||
- | ==== Sektorensuche ==== | ||
- | |||
- | Da die detaillierte Pfadsuche über eine volle Map zu langsam ist, braucht es eine gröbere Einteilung, auf der ein erster gröberer Pfad gesucht werden kann. Zu diesem Zweck wird auf der Map eine Anzahl von Sektoren (haben nichts mit den zu erobernden Sektoren im Gameplay zu tun) konstruiert. Dazu wird, ausgehend von einem Feld auf der Karte, jedes benachbarte betretbare Feld zum Sektor hinzugefügt, | ||
- | |||
- | {{z: | ||
- | |||
- | Von jedem Sektor wird ein ungefährer Mittelpunkt bestimmt, anschließend wird mit einer Graphensuche limitiert auf je zwei Sektoren überprüft, | ||
- | |||
- | Es ist klar, dass durch die gröbere Vorsuche eine Abschätzung getroffen wird, denn je nachdem, wo die Einheit sich befindet und wo sie hin will, mögen die Sektorenmittelpunkte eine gute oder mäßige Orientierung bieten. Dadurch kann es sein, dass insbesondere bei extrem verwinkelten Karten nicht aus jeder Situation wirklich der optimale Pfad gefunden wird. Auf normalen Karten sollte es aber eigentlich auch keine nennenswerten Patzer geben. | ||
- | |||
- | Brücken müssen zwingend als eigene Sektoren behandelt werden, diese werden gleich zu Beginn erstellt und die Felder der Brücke dann von der weiteren Sektorenkonstruktion ausgenommen. Auf diese Weise kann die Brückenzerstörung auch auf Sektorenebene korrekt behandelt werden. Wenn Brücken in normalen Sektoren eingelagert wären, könnte es leicht passieren, dass mit der Zerstörung von Brücken die Pfadsuche kein gültiges Ergebnis mehr finden würde. | ||
- | Bei Wasser könnte man das ähnlich machen, damit die unterschiedliche Passierbarkeit von Wasser zwischen Fahrzeugen und Robotern berücksichtigt werden kann. Alternativ könnte man auch für Fahrzeuge und Roboter ein unterschiedliches Sektorenmapping konstruieren, | ||
- | |||
- | |||
- | Zusammenfassend wäre das Vorgehen bei einer anstehenden Pfadsuche etwa dieses: | ||
- | 1. Ermittle die Felder, in denen Start- und Zielpunkt liegen. | ||
- | 2. Ermittle die Sektoren, in denen Start- und Zielfeld liegen. | ||
- | 3. Suche einen groben Pfad zwischen dem Start- und Zielsektor. | ||
- | 4. Plane auf feiner Ebene Pfade zwischen den gewählten Sektorenmittelpunkten sowie vom jeweiligen Sektormittelpunkt zum Start- bzw. Zielfeld | ||
- | 5. Glätte die Pfade, soweit möglich. | ||
- | |||
- | |||
- | ==== Andere Einheiten ==== | ||
- | |||
- | Es gibt neuere Ansätze für eine Modifizierung der A*-Pfadsuche, | ||
- | |||
- | Falls eine Suche zwischen zwei Sektorenmittelpunkten fehlschlägt, |