Welche Datenstruktur (en), um eine Final Fantasy ATB-artige Warteschlange zu unterstützen? (eine Verzögerungswarteschlange)

Question

Situation: Es gibt mehrere Entitäten in einer simulierten Umgebung, die eine künstliche Zeitvorstellung haben, die "Ticks" genannt wird, die keine Verbindung zu Echtzeit hat. Jede Einheit bewegt sich abwechselnd, aber manche sind schneller als andere. Dies äußert sich in einer Verzögerung in Ticks. So Entität A könnte eine Verzögerung von 10 haben, und B 25. In diesem Fall wird die reihum gehen würde:

A A B A A

Ich frage mich, welche Datenstruktur zu verwenden. Zuerst dachte ich automatisch "Priority Queue", aber die Verzögerungen sind relativ zur "aktuellen Zeit", was die Dinge kompliziert macht. Es wird auch Entitäten mit größeren Verzögerungen geben und es ist nicht unvorhersehbar, dass das Programm Millionen von Ticks durchlaufen wird. Es scheint albern, wenn ein interner Schalter höher und höher wird, wenn die Verzögerungen selbst relativ klein bleiben und nicht zunehmen.

Also, wie würdest du das lösen?

Answer 1

Sie speichern die Entitäten in einem Heap und gruppieren sie nach ihrer Wartezeit. Die Gruppe der Einheiten, die sich als nächstes bewegen, befindet sich an der Spitze des Heaps. Sie müssen diese Entitäten nur aktualisieren. Wenn die verbleibende Wartezeit auf 0 fällt, entfernen Sie sie aus dem Heapspeicher. Setzen Sie die nächste Gruppe von Entitäten in die Reihe oben auf dem Heap, während Sie ihre Wartezeit um die Zeit verringern, die gerade vor dem vorherigen Zug verstrichen ist.

Zum Beispiel:

Ihre Heap hat 3 Knoten (A, B, und C), die Oberseite ist der Knoten A mit zwei Einheiten sowohl 5 ticks aufweist verbleiben. Die Kinder haben 10 bzw. 12 Ticks.

• Zum Zeitpunkt t = 5 Sie alle Einheiten bewegen, das mit A
• entfernen, um einem aus dem Heap
• B bewegt mich in der Spitze des Haufens mit 10-5 = 5 in Knoten bucketed verbleibt dann ticks
• wiederholen.

Answer 2

Option # 1: Polling

Ich würde wahrscheinlich einen Controller bauen, die die Verzögerung für die verschiedenen Einheiten zu entdecken und Zecken-Rest für jede Einheit aufrechtzuerhalten. Der Controller würde Ticks durchlaufen und bei jedem Tick würde er die verbleibenden Ticks für alle Entitäten im Spiel reduzieren.

Sobald ein Entities-Ticks-Restwert Null erreicht, wissen Sie, dass er an der Reihe ist, entweder durch die Heartbeat-Methode gesteuert, die die Ticks behandelt, oder eine Methode, die Sie aufrufen.

Option # 2 Veranstaltungen

Denken wie das UI-Paradigma, wird die Schnittstelle nicht ständig die Taste abfragen, um zu sehen, wenn es angeklickt wird. Stattdessen lässt es die Schaltfläche die Benutzeroberfläche benachrichtigen, wenn sie über Ereignisse angeklickt wurde. Lassen Sie Ihre Entitäten (oder einen EntityBattleContext) ein Ereignis auslösen, wenn es fertig ist. Sie müssen mit Ihrer Spielzeit in irgendeiner Weise umgehen, da sie nicht auf der realen Welt basiert, müssen Sie möglicherweise alle Entitäten auf ein GameTick-Ereignis warten lassen und wenn sie dieses Ereignis empfangen, ihre interne TicksRemaining-Variable aktualisieren.

Bevor Sie der ereignisgesteuerten Route folgen, vergewissern Sie sich, dass die Abfrageroute nicht funktioniert. Denken Sie daran, die Grundregel immer später optimieren weil häufiger dann nicht Sie die Optimierung nicht benötigen.

Answer 3

Wenn wir annehmen, dass Ihre Entitäten die Simulationszeit beobachten oder beobachten, könnten sie jeweils eine Schnittstelle implementieren, die sie der ticks left nachverfolgt und eine Methode bereitstellt, wie viele Ticks für eine bestimmte Entität übrig bleiben. Bei jedem Tick verringert die Entität ihre ticks left um 1.

Sie könnten dann eine sortierte Set-Warteschlange (gesetzt, weil jede Entität nur einmal in der Warteschlange sein wird) dieser Entitäten sortiert nach get ticks left, so dass die 0th Die Entität ist diejenige, die als nächstes bewegt wird, und die N-te Entität ist die "langsamste" Entität.

Wenn die get ticks left-Methode der Entität 0 ist, wird sie aus der sortierten Menge entfernt, der ticks left-Zeitgeber wird zurückgesetzt und erneut in die sortierte Menge eingefügt.

Answer 4

Es scheint mir durch Ihre Beschreibung, dass das Konzept von "was kommt als nächstes?" ist wichtiger als "Wie lange dauert es bis zur nächsten Aktion?". Sortieren Sie in diesem Fall Ihre Warteschlange nach "Weiter" oder der niedrigsten verbleibenden Anzahl von Ticks.Einfügungen werden natürlich in der richtigen Reihenfolge eingegeben, und geänderte Einträge ("Beschleunigungs-" Sprüche) werden aus der Warteschlange entfernt, geändert und dann wieder entsprechend eingegeben.

Dann Pop nur den nächsten Job aus der Warteschlange. Die Anzahl der verbleibenden Ticks muss die "verstrichene Zeit" sein. Führt einen Durchlauf über die Warteschlange durch und verringert das verbleibende Feld der Ticks jedes Eintrags um die Anzahl der Ticks, die Sie gerade entdeckt haben.

Dies hat den Vorteil, dass Sie das Konzept der verbleibenden Zeit verfolgen, aber auch keine Ereignisse auslösen oder anderen Code für Ticks ausführen müssen, wenn keine Aktion stattfindet. Sie können sich das leisten, da es keine Beziehung zu Echtzeit gibt. Es gibt nur "Was kommt als nächstes?" Und "Wie lange hat es gedauert, um dorthin zu gelangen?".

Answer 5

Schauen Sie sich an, wie Javas DelayQueue implementiert ist.