Pfadfindung zwischen mehreren Karten

7

Ich bin daran interessiert, Wege zwischen mehreren Karten zu finden - dies können Karten für Innen- und Außenbereiche, verschiedene Ebenen in einem Gebäude usw. sein, aber die Haupteinschränkung besteht darin, dass sich zwischen den verschiedenen Karten ein (oder mehrere) Ein- / Ausstiegspunkte befinden. Ich habe nach guten Lösungen gesucht und konnte sie nicht finden, aber mir sind mehrere Spiele bekannt, die ähnliche Systeme verwenden.

Ich habe dieses Papier gefunden - Hierarchische Suche nach kürzesten Pfaden für die Routenplanung für Rollstuhlfahrer, das ein ähnliches Problem zu lösen scheint, aber rein theoretisch ist.

Hat jemand ähnliche Erfahrungen gemacht, die er teilen könnte, oder einige Tipps?

path-finding Martyn
quelle
Ich werde keine Antwort geben, da ich noch nie einen solchen Fall implementieren musste, der diese Aussage spekulativ macht, aber ich bezweifle, dass es neben der offensichtlichen eine Lösung gibt, dass Sie Ihre Knoten auch von Karten laden müssen, die sind noch nicht geladen (was kein Problem sein sollte, da Wegpunkt- oder Navigationsnetzdaten selbst bei großen Karten möglicherweise einige Kilobyte betragen). Ohne die Knoten gibt es keine Informationen, die Ihre Algorithmen verwenden können. Davon abgesehen sollte es ziemlich einfach sein - laden Sie alle Grafiken und verbinden Sie sie an den Kreuzungspunkten (Türen usw.). edit: oh und +1
TravisG
Einverstanden - ich glaube nicht, dass das Laden der Knoten das Problem ist - es ist ein bisschen intelligenter, wie die verschiedenen Karten zusammen hängen. Wie Sie sagen, ist es vielleicht ein einfacher Fall, einen Standardalgorithmus (A *?) Zu verwenden, alle fraglichen Karten zu laden und die Karten dann künstlich zu verbinden. Wenn es 2+ mehrere Ebenen gäbe, sollte ich vielleicht zwei Sätze der Pfadfindung verwenden, da ich wahrscheinlich nicht den gesamten Pfad benötige - nur den Pfad aus der aktuellen Karte?
Martyn
Genau. Es ist wahrscheinlich am schnellsten, wenn Sie eine "Karte" (das Gebäude oder was auch immer, in das Ihr A * laufen muss) als einen großen Knoten darstellen, bis Ihre KI tatsächlich davor steht. Finden Sie dann den kürzesten Weg zu diesem großen Knoten Laden Sie dort den gesamten Graphen dieser Unterkarte und berechnen Sie den genaueren Pfad. Am Anfang alles auf einmal zu berechnen ist imo verschwenderisch, da zwischen dieser Berechnung und Ihrer KI, die sich dorthin bewegt, viel passieren kann.
TravisG

Antworten:

5

Ich habe vor einigen Jahren etwas Ähnliches für eine Modelldemo des Cyberpunk-Klons "Jagged Alliance" gemacht, der große Karten mit Wolkenkratzern haben sollte. Es war eine blöde Idee, anscheinend sollten Karten für taktische Kämpfe ordentlich und leicht verständlich sein :)

Um eine schnellere Wegfindung zu erreichen, wurde eine globale Karte in mehrere diskrete quadratische Bereiche unterteilt. Sobald wir ein Kriterium für Gebiete haben, ist es Zeit, mögliche "Eingänge" zwischen jedem Paar benachbarter Gebiete zu finden. "Eingang" ist ein Übergangspunkt, der zeigt, dass dieser Agent diesen Bereich an diesem Punkt betreten kann.

In Ihrem Beispiel mit mehreren Stockwerken wäre jedes Stockwerk ein Bereich mit Grenzen, die durch Boden, Decke und Außenwände definiert sind. und verschiedene Löcher in Wand oder Boden oder Leitern wären Eingänge, von denen es viele geben könnte. Eingänge verbinden also grundsätzlich Pfadknoten von einem Bereich mit Pfadknoten im anderen Bereich.

Sobald Sie die Eingänge identifiziert haben, müssen Sie alle möglichen Wege finden, um jedes Gebiet zu durchqueren. Dies führt zu einer "Karte der Gebietseingänge zu benachbarten Gebietseingängen", wobei die Kanten zwischen den Eingängen die Länge dieses Pfades durch das Gebiet anzeigen.

Wenn alles richtig gelaufen ist, kann Ihr Agent, der im 1. Stock steht, schnell den Weg zu dieser speziellen Box im 4. Stock finden. Vielleicht könnte etwas Ähnliches in Ihrem Problem mit mehreren Karten verwendet werden, also hoffen Sie, dass es hilft.

Genug Tee
quelle
1

Ich glaube, Sie suchen nach einem hierarchischen Pfad suchenden A-Stern, wie hier beschrieben:

HPA- *

Pieter Geerkens
quelle