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!

[Erledigt] Wegsuche: Teilpfad für unmöglichen Pfad

Werbeanzeige

Glocke

Treue Seele

  • »Glocke« ist der Autor dieses Themas

Beiträge: 341

  • Private Nachricht senden

1

04.05.2016, 08:16

[Erledigt] Wegsuche: Teilpfad für unmöglichen Pfad

Hi, ich arbeite (immernoch) an meinem Dungeoncrawler ^^ Inzwischen steht die Lua-Anbindung, damit verschiedene KIs gescriptet werden können. Daher habe ich vor einiger Zeit eine Wegsuche mit A* implementiert, die über ein Lua-Script ausgelöst werden kann. Allerdings liefert eine klassische A*-Implementierung genau dann einen kürzesten Pfad wenn dieser existiert. Nun gibt es verschiedene Szenarien in denen ein KI-Objekt den Spieler gar nicht erreichen kann. In diesen Fällen durchsucht mein A* (was imho dem erwarteten Verhalten entsprechen sollte), das gesamte (erreichbare) Dungeon. Was mir fehlt ist also eine Art "Abbruchbedingung" mit Hilfe derer der Algorithmus festlegt, dass "dieser unvollständige Pfad" ziemlich nah an das Ziel führt.

Beispiel
  • Leerzeichen sind begehbare Felder
  • # sind Wände
  • S ist der Start
  • Z ist das Ziel
  • T könnte eine Tür sein, die den Spieler vom Gegner trennt.

Quellcode

 
1
2
3
4
5

#########
#    T Z#
#    #  #
# S  #  #
#########

Das Ergebnis ist, dass kein Pfad von S zu Z existiert - hilfreicher wäre allerdings ein Ergebnis wie folgt, wobei * der zurückgegebene Pfad sei:

Quellcode

 
1
2
3
4
5

#########
#   *T Z#
#   *#  #
# S* #  #
#########

Entsprechend frage ich mich, wie ich den Algorithmus umgestalten könnte, damit er "nah genug" am Ziel stehen bleibt, ohne (aus menschlicher Sicht) offensichtliche Pfad zu sehr zu ignorieren, wie:

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11

#########
#       #
# S**#Z #
#########

vs.

#########
#    *  #
# S**#Z #
#########


Zur Erkennung, ob ein Pfad existiert könnte ich prinzipiell zwei Wegsuchen (S nach Z und Z nach S) abwechselnd schrittweise ausführen, bis einer von beiden Abbricht. Allerdings könnten auch beide "Dungeonhälften" ziemlich groß sein :S Abhilfe würde ggf. eine maximale Pfadlänge schaffen, sodass alle längeren Pfade ignoriert werden... Allerdings führt das u.A. natürlich auch zu falschen Ergebnissen.

Wie wird so etwas klassischerweise gelöst? Ist A* überhaupt noch das richtige für meine Problemstellung?

LG Glocke

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Glocke« (04.05.2016, 11:22)

Schrompf

Alter Hase

Beiträge: 1 470

Wohnort: Dresden

Beruf: Softwareentwickler

  • Private Nachricht senden

2

04.05.2016, 08:37

Bei Splatter habe ich damals auch immer den aktuell nahesten bekannten Node zum Ziel behalten, natürlich Luftlinie. Den kann man dann natürlich noch verbasteln mit der schon gelaufenen Strecke, so dass die Wegesuche lieber einen Endpunkt bevorzugt, der zwar weiter weg vom Zielpunkt liegt, aber dafür nicht um ein großes Hindernis drumrum läuft.

Das sind aber alles schon Grenzfall-Optimierungen, die man nicht überbewerten sollte, weil sie ja nur im seltenen Randfall auftreten. Meiner Meinung nach ist es in diesem Fall auch völlig ok, wenn das Monster einfach komplett stehen bleibt.

Außerdem suchst Du eine Abbruchbedingung, die es vermeiden soll, dass der A* den ganzen Dungeon mit Floodfill durchströmt. Ich habe dafür damals eine maximale Laufstrecke von Node zu Node mitgerechnet, die Du bei A* eh brauchst. Als frühzeitige Abbruchbedingung empfiehlt sich dann z.B. "Nicht weiter als die dreifache Strecke der Luftlinie suchen, mindestens jedoch X". Das Minimum ist notwendig, wenn der Wegsucher z.B. vor einer Mauer steht und auf die andere Seite will. Dann ist die Luftlinie sehr gering, und obige Abbruchbedingung würde auf halben Wege um die Mauer drumrum zuschlagen.

Das braucht alles ein bisschen Ausprobieren und Ausgewichten, aber das siehst Du dann ja im Spiel.
Häuptling von Dreamworlds. Baut aktuell an nichts konkretem, weil das Vollzeitangestelltenverhältnis ihn fest im Griff hat. Baut daneben nur noch sehr selten an der Open Asset Import Library mit.

TrommlBomml

Community-Fossil

Beiträge: 2 117

Wohnort: Berlin

Beruf: Software-Entwickler

  • Private Nachricht senden

3

04.05.2016, 08:43

Alternativ kenne ich noch den Ansatz, dass man ein "hierarchisches" A* implementiert. Das könnte bei deinem Dungeon Crawler vielleicht so aussehen, dass man erst pro Raum prüft, ob das Ziel erreichbar ist. Also muss man pro Raum einen Node haben, die man mit A* testet. Hierbei müsste man natürlich wissen, welche Räume zueinander begehbar sind, also was durch Türen, Geröll etc. versperrt ist. Wenn man das Weiß, kriegst du bei großen Strecken schon schnell raus, ob etwas erreichbar ist. Danach wendet man den normalen A* auf Feldebene an.

Glocke

Treue Seele

  • »Glocke« ist der Autor dieses Themas

Beiträge: 341

  • Private Nachricht senden

4

04.05.2016, 08:59

Zitat von »Schrompf«

Bei Splatter habe ich damals [...]

Hab mir gerade mal Screens von Splatter angesehen... Respekt dazu btw (auch wenn's offtopic ist ^^)

Zitat von »Schrompf«

Meiner Meinung nach ist es in diesem Fall auch völlig ok, wenn das Monster einfach komplett stehen bleibt.

Wäre auch ok notfalls ^^

Zitat von »Schrompf«

Außerdem suchst Du eine Abbruchbedingung, die es vermeiden soll, dass der A* den ganzen Dungeon mit Floodfill durchströmt. Ich habe dafür damals eine maximale Laufstrecke von Node zu Node mitgerechnet, die Du bei A* eh brauchst. Als frühzeitige Abbruchbedingung empfiehlt sich dann z.B. "Nicht weiter als die dreifache Strecke der Luftlinie suchen, mindestens jedoch X". Das Minimum ist notwendig, wenn der Wegsucher z.B. vor einer Mauer steht und auf die andere Seite will. Dann ist die Luftlinie sehr gering, und obige Abbruchbedingung würde auf halben Wege um die Mauer drumrum zuschlagen.

Ganz genauso ist es! Das mit Min+Max klingt gut, danke für den Hinweis. Bisher hatte ich nur eine viel zu große, absolute Grenze für die Pfadlänge genommen ^^

Zitat von »TrommlBomml«

Also muss man pro Raum einen Node haben, die man mit A* testet. Hierbei müsste man natürlich wissen, welche Räume zueinander begehbar sind, also was durch Türen, Geröll etc. versperrt ist. Wenn man das Weiß, kriegst du bei großen Strecken schon schnell raus, ob etwas erreichbar ist. Danach wendet man den normalen A* auf Feldebene an.

So im Sinne broadphase und dann narrowphase?

TrommlBomml

Community-Fossil

Beiträge: 2 117

Wohnort: Berlin

Beruf: Software-Entwickler

  • Private Nachricht senden

5

04.05.2016, 10:10

Zitat von »Glocke«

Zitat von »TrommlBomml«
Also muss man pro Raum einen Node haben, die man mit A* testet. Hierbei müsste man natürlich wissen, welche Räume zueinander begehbar sind, also was durch Türen, Geröll etc. versperrt ist. Wenn man das Weiß, kriegst du bei großen Strecken schon schnell raus, ob etwas erreichbar ist. Danach wendet man den normalen A* auf Feldebene an.

So im Sinne broadphase und dann narrowphase?


Sozusagen ;)

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

6

04.05.2016, 11:15

Geht ein wenig in die Richtung von TrommlBomml, du könntest dir die Flächen einzelner Räume merken. Für jeden Zusammenhängenden Raum ein Polygon. Dann musst du vorher erst mal "nur" prüfen ob sich Start und Ziel im selben Raum/Polygon befinden. Falls ja kannst du ganz normal A* darauf jagen. Falls nein könntest du wie du schon selbst sagst den deinem Ziel nächsten Punkt im aktuellen Raum bestimmen und darauf A* anwenden.
„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.“

Glocke

Treue Seele

  • »Glocke« ist der Autor dieses Themas

Beiträge: 341

  • Private Nachricht senden

7

04.05.2016, 11:21

Den Ansatz werde ich im Hinterkopf behalten; im Moment hat mir Schrompfs MinMaxLength-Ansatz aber schonmal geholfen! Danke :)

Nochmal die vollständige Modifikation für den geneigten Leser:
  • Ich übergebe der Wegsuche eine maximale Pfadlänger (im Stile max(10, luftlinie*3), ggf. mit anderen Konstanten).
  • Die Suche merkt sich jeweils den nächstgelegenen Knoten (d.h. der mit der kürzesten heuristischen Distanz zum Ziel).
  • Wird die maximale Pfadlänge überschritten, wird der Knoten ignoriert (damit wird nicht mehr das ganze Dungeon erforscht)
  • Schließlich kann der Pfad entweder zwischen Start und erreichtem Ziel - oder zwischen Start und nächstgelegenem Knoten - konstruiert werden. Im Endeffekt ist das Ziel der "nächstgelegene Knoten" mit Restdistanz 0.

LG Glocke

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Glocke« (04.05.2016, 13:05)

Schorsch

Supermoderator

Beiträge: 5 145

Wohnort: Wickede

Beruf: Softwareentwickler

  • Private Nachricht senden

8

04.05.2016, 12:17

Zitat von »Glocke«

im Moment hat mir Schorschs MinMaxLength-Ansatz aber schonmal geholfen! Danke

Werde ich an Schrompf weiter leiten ;) Schrompf != Schorsch :)
„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.“

Glocke

Treue Seele

  • »Glocke« ist der Autor dieses Themas

Beiträge: 341

  • Private Nachricht senden

9

04.05.2016, 13:05

Zitat von »Schorsch«

Zitat von »Glocke«

im Moment hat mir Schorschs MinMaxLength-Ansatz aber schonmal geholfen! Danke

Werde ich an Schrompf weiter leiten ;) Schrompf != Schorsch :)


ups xD

Werbeanzeige

Ähnliche Themen