Verwalten von Abhängigkeiten zwischen Kachelkarte und Einheiten

11

Ich habe eine 2D-Kachel-basierte Strategie in Arbeit. Ich überlege, wie ich mit der Beziehung zwischen der Karte und den Einheiten auf der Karte umgehen soll.

Bei einer gegebenen Kachelkoordinate muss ich in der Lage sein, die Einheit darauf zu stellen, falls vorhanden. Wenn ich eine Einheit habe, möchte ich gleichzeitig in der Lage sein, die Koordinate der Einheit zu erhalten.

Ich habe zwei Lösungen dafür gesehen. Die erste Lösung wäre, dass Einheiten eine Koordinate speichern und die Karten Einheitenreferenzen in ihren Kacheln speichern. Dies erzeugt eine zyklische Abhängigkeit zwischen der Karte und den Einheiten. Ich müsste sicherstellen, dass die Karte einer beliebigen Einheit synchron bleibt, wenn sich die Einheit bewegt.

Die zweite Lösung wäre, nur die Einheiten ihre Koordinaten verfolgen zu lassen. Um festzustellen, ob eine Kachel eine Einheit enthält, und um diese Einheit zu erhalten, würde ich den gesamten Satz von Einheiten durchlaufen. Ich finde eine Einheit mit übereinstimmenden Koordinaten. Dadurch werden die zyklischen Abhängigkeiten beseitigt, aber die O (1) -Eigenschaft, die die erste Lösung zum Nachschlagen von Einheiten auf der Karte hatte, wird verloren. Dies kann sich summieren, da ich die Karte regelmäßig nach Pfaden suchen, den Bewegungsbereich bestimmen und gültige Ziele für eine bestimmte Einheit finden möchte.

Ich kann die Einheiten auch nicht einfach auf der Karte speichern (oder?). Einheiten sind mit "Armeen" verbunden, entweder Spieler oder KI. Eine Armee sollte in der Lage sein, leicht auf alle ihre Einheiten zuzugreifen und diese zu durchlaufen.

Gibt es neben den beiden Mustern, die ich für die Verwaltung der Beziehungen zwischen Einheiten und Karten beschrieben habe, noch andere Muster, da dies in Strategiespielen ein häufiges Problem zu sein scheint?

tiles maps character AJM
quelle

Antworten:

3

Es ist kein beliebtes Muster, aber die relationale Datenbankwelt bietet einen dritten Weg: Verwenden Sie eine Datenstruktur mit mehreren Schlüsseln. In tabellarischer Form könnte es so aussehen:

Unit id    Location
-------------------
  1309     13,15
  2357      7,93
  8552      7,93

Sie möchten fragen können: "Wo ist die Einheit 2357?" und zurück 7,93. Sie möchten auch fragen können: "Was ist in Standort 7,93?" und zurück 2357 und 8552. Es gibt Datenstrukturen, die mehrere Schlüssel zum Nachschlagen ermöglichen. Sie können dies außerhalb der Einheiten und außerhalb der Karte speichern, wenn Sie Abhängigkeiten entfernen möchten.

In der Praxis ist es jedoch üblicher, den Standort in jeder Einheit zu speichern und dann nebenbei eine räumliche Partitionierungsdatenstruktur zu verwenden, die angibt, welche Einheiten sich in einer bestimmten Region befinden. Da es sich um eine separate Struktur handelt, müssen die Regionen keine Rasterräume sein. Sie können größere Flächen sein.

Ich empfehle, das Einfachste zu tun (Ihre zweite Lösung). Wenn es sich später um ein Leistungsproblem handelt, können Sie eine räumliche Partition hinzufügen, um die Suche zu beschleunigen.

amitp
quelle
Die von Ihnen erwähnte räumliche Partitionierungsdatenstruktur könnte also nur die Karte sein (in meinem Fall angeblich ein 2D-Kachelraster). Ich gehe davon aus, dass ich beim Verschieben (oder Hinzufügen oder Entfernen) einer Einheit immer noch sowohl die Einheit als auch die räumliche Partitionierungsstruktur aktualisieren muss, um sie synchron zu halten. Vielleicht ist es eines dieser Dinge, mit denen ich leben muss?
AJM
1
Ja, die Karte ist die feinkörnigste räumliche Partition, die Sie verwenden würden. Die globale Liste aller Einheiten ist die grobkörnigste Partition. ;) Sie müssen die Partition nur aktualisieren, bevor sie verwendet wird. Wenn Sie es ständig verwenden, möchten Sie es wahrscheinlich jedes Mal aktualisieren, wenn das Gerät bewegt wird. Wenn Sie es jedoch nur für einige Phasen der Aktualisierungslogik verwenden, können Sie die Einheitenliste in einem Durchgang durchgehen, die Partitionsdatenstruktur berechnen und sie dann verwerfen, wenn Sie fertig sind. Auf diese Weise müssen Sie sie nicht immer synchron halten.
Amitp
5

Nun, wenn Sie nicht mehrere tausend Einheiten pro Spieler haben, würde ich mir keine Sorgen um die Speichernutzung machen und die erste Lösung verwenden. Speicher ist billiger als CPU, wie es scheint.

Selbst wenn Sie 4000 Einheiten pro Spieler hatten und zwei Ganzzahlen zum Speichern des Standorts und 8 Spieler verwendeten, dauert dies nur 2 MB. Bei der ersten Lösung können Sie jedoch einen O (1) -Koordinator verwenden, anstatt O (n) (unter der Annahme unsortiert), was bei vielen Einheiten langsam sein kann.

Die meisten Spiele scheinen heutzutage eher pixelbasiert als kachelbasiert zu sein, sodass sie nur noch das Gerät zum Speichern der Koordinaten benötigen.

Ray Britton
quelle
Ich mache mir keine Sorgen um die Speichernutzung, sondern bin mehr an der Verwaltung von Abhängigkeiten interessiert (im Sinne von Object Oriented Design). Es ist nicht der zusätzliche Speicher, den die erste Lösung mit sich bringen würde, der mich beunruhigt, sondern die zyklische Abhängigkeit, der ich misstrauisch gegenüber bin, so sehr ich den O (1) -Koordinator mag. Ich weiß auch, dass viele Spiele jetzt pixelbasiert sind, aber ich mag Kacheln, also benutze ich sie. : P
AJM
@AJM, ebenso werden die kostenpflichtigen Apps, die ich auf Android veröffentlichen werde, Kacheln verwenden.
Ray Britton