Datenstruktur zur Darstellung von Verbindungen zwischen Ländern auf einer Karte

9

In einem Spiel, das ich für einen Kunden entwickle, besteht ein Schlüsselspielkonzept darin, sich auf einer Karte zu bewegen. In diesem Fall sind die Größen und Formen und die verschiedenen Länder irrelevant: Der Wechsel von einem Land in ein benachbartes Land zählt als ein einziger Schritt.

Ich versuche, die beste Datenstruktur für die interne Darstellung der Verbindungen zwischen den Ländern herauszufinden. Für ein bestimmtes Land muss das Spiel wissen, welche Länder benachbart sind, sowohl um zu wissen, auf welche Weise sich die Spieler bewegen können, als auch um der KI des Spiels zu ermöglichen, Routen zu zeichnen und mögliche Wege von einem Land zum anderen zu bestimmen. Die KI muss auch bewerten, wie gut ein Land verbunden ist, nicht nur mit seinen unmittelbar benachbarten Nachbarn, sondern auch mit den Nachbarn dieser Länder usw.

Ich habe ein paar Möglichkeiten herausgefunden, aber sie scheinen unansehnlich und ineffizient zu sein. Da die KI eine Reihe möglicher Routen berechnen muss, um gute Entscheidungen über ihre Bewegung zu treffen, ist "ineffizient" äußerst problematisch.

Ich vermute, dass dies ein etwas verbreitetes CS-Puzzle ist und dass es eine gemeinsame Lösung gibt, aber ich konnte durch Suchen nicht viel finden. Anregungen sind willkommen.

maps efficiency Matthew Frederick
quelle
Wenn ich dies auf GameDev.StackExchange fragen sollte, lass es mich einfach wissen. Ich frage hier, weil ich sicher bin, dass so etwas für alle Arten von Entwicklungsproblemen benötigt wird und ich keine Hilfe bei der "Spiel" -Seite per se brauche, nur bei der Routenplanung.
Matthew Frederick
Sie benötigen entweder ein Diagramm oder eine Konnektivitätsmatrix (was praktisch ist, da das Schließen einfach zu berechnen ist). Vielleicht brauchst du beides. Schlage sie nach.
2
Werfen Sie einen Blick auf Diagrammdatenstrukturen und Algorithmen: en.wikipedia.org/wiki/Graph_%28data_structure%29
1
Das sieht für mich nicht thematisch aus. Es sollte entweder auf GameDev oder Stack Overflow sein, da es hier ein zu objektives Thema ist.

Antworten:

6

Auf jeden Fall ein Graph. Schauen Sie sich das hier an. Graphentheorie , im Grunde haben Sie Knoten und Kanten. Ein Knoten kann 0 oder mehr Kanten zu anderen Knoten enthalten.

Es gibt viele Algorithmen, um den kürzesten Weg (Hopfen oder Entfernung) zu berechnen, nach Zikeln zu suchen (mehr als ein Weg, um ein Selbst zu erreichen) usw.

Um effiziente Lösungen implementieren zu können, ist das etwas komplexer, aber wie immer gibt es Möglichkeiten.


quelle
Großartig, vielen Dank. Haben Sie Vorschläge, wo Sie solche Algorithmen finden können? Ich brauche nicht so sehr den kürzesten Weg, aber Dinge wie das Suchen nach Kreisen usw. wären sehr praktisch.
Matthew Frederick
2

Wie bereits erwähnt, benötigen Sie ein Diagramm, das alle möglichen Verbindungen zwischen Ländern darstellt. Jede Verbindung würde auch die Entfernung zwischen zwei Ländern halten.

Dann kann ein Pfadfindungsalgorithmus wie A * verwendet werden, um den kürzesten Pfad zwischen zwei Ländern zu bestimmen.

Es gibt auch einige gute Bücher über Spiel ai: Spiel KI am Beispiel von Mat Buckland http://www.ai-junkie.com/books/toc_pgaibe.html

oder die AI Game Programming Wisdom-Serie. http://www.aiwisdom.com/ Das erste Buch enthält mehrere Kapitel über die Pfadfindung.

Stephen
quelle
Hervorragend, danke für die Buchhinweise. Es scheint eine Menge KI-Bücher zu geben, und persönliche Empfehlungen sind viel besser als die allgemeinen Ergebnisse, die ich bei der Suche erzielt habe.
Matthew Frederick