Wie soll ich dynamische Spieleinheiten für eine effiziente flächenbasierte Auswahl speichern?

7

In meinem 2D-Block-basierten Spiel versuche ich, eine Datenstruktur zu implementieren, in der Entitäten auf eine Weise gespeichert werden, die Folgendes ermöglicht:

  • Direkte Auswahl anhand der Koordinate.

  • Wiederholung

  • Die Iteration ist auf einen Bereich beschränkt

Ich dachte an diese Lösungen:

Für 1,3 dachte ich, dass ein zweidimensionales Array von Entitätskoordinaten geeignet wäre, aber ich habe bereits ein zweidimensionales Array von Blockkoordinaten und möchte auch kein anderes haben. Und diese Lösung ist mit 2 nicht geeignet, es gibt zu viele Lücken beim Iterieren des Arrays und dies ist ein Leistungsverlust.

Die nächste Lösung, von der ich dachte, dass sie einfach ein Array verwendet und neue Entitäten einfach durch arr [length] hinzufügt, ist leistungsmäßig für 2, aber es ist schwierig, 1 und 3 auszuführen (verwenden Sie jedes Mal eine for-Schleife, um zu überprüfen, ob ich kollidiere eine Entität (duh)).

Die letzte Lösung besteht einfach darin, Entitätsdaten zu meinem (bereits vorhandenen) zweidimensionalen blockList-Array hinzuzufügen. Dieses hat fast die gleichen Vor- und Nachteile wie die erste Lösung.

Und es gibt immer die Alternative, erste und zweite Lösung zusammen zu verwenden, indem sie sich auf dasselbe Objekt beziehen.


Welche dieser Lösungen sollte ich verwenden, weil alle ihre Vor- und Nachteile haben und ich etwas weniger Platz beanspruchen muss, weil die Spielkarte nicht repariert ist.

MindlessRanger
quelle
Ich habe das Gefühl, dass Sie den Begriff Entitätssystem möglicherweise verwirren. Habe ich Recht, wenn Sie nach einer Möglichkeit fragen, Objektpositionen für räumliche Abfragen effizient zu speichern?
Anko
Ups, tut mir leid, dass du recht hast.
MindlessRanger
Haben Sie getestet, dass Ihre aktuelle Methode wirklich zu langsam ist? Nach meiner Erfahrung ist das Durchlaufen von bis zu etwa hundert Objekten schnell genug, um auf den meisten Geräten mit interaktiven Raten in JS ausgeführt zu werden.
Anko
@Anko Derzeit habe ich keine Methoden zum Speichern von Entitäten (habe gerade den Entitätskonstruktor fertiggestellt), aber es ist kein Problem mit der Geschwindigkeit. Ich habe die Updater- und Renderer-Funktionen bereits auf das Ansichtsfenster des Benutzers beschränkt. Mein Problem ist: Ich habe bereits ein Raster zum Speichern von Blöcken und möchte kein Raster zum Speichern von Entitäten verwenden, da die Lücken zwischen Entitäten groß sind und aus diesem Grund zu viele leere Array-Schlüssel vorhanden wären, wenn ich ein Raster verwende Ich habe nur nach einer anderen Lösung gesucht, aber nachdem ich mir die anderen Techniken für räumliche Speichersysteme angesehen habe, denke ich, dass die Verwendung eines Rasters die beste Option ist.
MindlessRanger

Antworten:

1

Eine andere Option kann die Verwendung einer Quadtree- Struktur oder ein räumlicher Hashing- Ansatz sein, wenn Sie viele sich bewegende Objekte haben.

dnk drone.vs.drones
quelle
1
Aber müsste ich den Baum nicht bei jedem Update neu erstellen?
MindlessRanger
Ich habe kein räumliches Hashing gesehen.
MindlessRanger
1
Was ist mit Gittern, Begrenzungsbereichshierarchien, binärer Raumpartitionierung, kd-Bäumen, ...?
Exilyth
0

In dem Spiel, das ich mache, speichere ich die Entitäten (tatsächlich ihre Komponenten) in einem Array (Struktur von Arrays) und erstelle dann ein räumliches Gitter, das in jeder Zelle den Array-Index der Entitäten enthält, die zu diesem Bereich gehören. und ja, Sie müssen jeden Frame für dynamische Objekte neu erstellen, aber die Tutorials, die ich gesehen habe (an die ich mich erinnere), tun dies, insbesondere für Quad / Octrees. Dies ist schnell für eine einfache Iteration und für die Bereichsauswahl. Im Falle einer Neuerstellung des Rasters ist dies nur ein 'array.push_back' pro Entität pro Frame.

Sie können in Betracht ziehen, die Entitäten im Array nach ihrer Position zu ordnen, um Cache-Fehler bei der Auswahl nach Bereich zu vermeiden (wenn Sie alle Daten zusammengefasst haben, vermeiden Sie es, hier und da in den RAM zu springen). Aber Sie müssen das nicht in jedem Frame tun, sondern möglicherweise einen Index des "Chaos des Systems" erstellen, der darauf basiert, wie viel sich die Entitäten bewegen, wie viele sterben usw., und die Sortierung durchführen, wenn sie zu hoch ist (versuchen Sie es) und Profil, falls erforderlich)

Das Erstellen verschiedener Arrays für verschiedene Bereiche ist meiner Meinung nach keine gute Idee, sowohl im Hinblick auf die Aufrechterhaltung Ihres Codes als auch auf die Leistung, da weiterhin Entitäten zwischen einem Bereich und dem anderen ausgetauscht werden (und somit viele sich bewegende Daten). Vielleicht habe ich diesen Ansatz noch nie ausprobiert. Sie können diesen Weg gehen, wenn Sie große, unterschiedliche Bereiche haben, die nicht zu viel kommunizieren, aber ich denke nicht, dass dies Ihr Fall ist.

Liuka
quelle
0

Ich habe 2 einfache schmutzige Tricks benutzt.

1 - Level geteilt durch "Chunks". Angenommen, 10x10 (CHUNK_SIZE = 10) abstrakte Einheiten. Also dein Level in der Nähe von 10x10 Chunks. Angenommen, Chunks-Array - es ist eine Art Karte mit geringen Details, wenn sich nur wenige Einheiten in einer Zelle befinden können. Jedes Mal, wenn sich eine Entität bewegt (oder alle 10 Spiel-Ticks), berechne ich eine neue Chunk-Chunk-Position neu (wie enity.chunk_x = enity.x / CHUNK_SIZE). Nachdem die Blockposition für die Entität geändert wurde (wir sind zu einem anderen Block gewechselt), entferne ich den Link vom vorherigen Block und setze den Link auf die Entität.

Nehmen wir an, Ihr Charakter kann 2 Brocken herum sehen. Viel schneller in der Nähe von Stücken zu betrachten, als durch eine Reihe von Entitäten zu gehen.

2 - Beobachtungsliste: Jeder spielbare Charakter, der Entitäten beobachten kann, kann eine Beobachtungsliste führen und verwalten. (mit 1. schmutzigen Trick).

Für Javascript ist diese Technik mehr als genug.

Vladimir Ishenko
quelle