data-structures - 哪种数据结构支持最终幻想 ATB 风格的队列？ (一个延迟队列)

Question

情况:模拟环境中有多个实体，它们有一个人工时间概念，称为“滴答”，与实时没有联系。每个实体轮流移动，但有些实体比其他实体更快。这由延迟表示，以滴答为单位。因此实体 A 可能有 10 的延迟，B 可能有 25 的延迟。在这种情况下，转弯顺序将变为:

A A B A

我想知道要使用什么数据结构。起初我不自觉地想到“优先队列”，但延迟与“当前时间”有关，这使问题复杂化。此外，会有更大延迟的实体，并且程序将运行数百万个滴答声并不是不可预见的。当延迟本身保持相对较小且不增加时，内部计数器越来越高似乎很愚蠢。

那么你会如何解决这个问题呢？

Answer 1

您将实体存储在堆中，并按剩余等待时间对它们进行分组。接下来移动的实体组将位于堆的顶部。您只需更新这些实体。当它们的剩余等待时间降至 0 时，您将它们从堆中移除。将下一组实体排在堆的顶部，同时减少它们等待前一次移动之前的时间。

例如:

您的堆有 3 个节点(A、B 和 C)，顶部是节点 A，其中两个实体都剩余 5 个滴答声。 childern 分别剩余 10 和 12 滴答声。

在时间 t=5 时，您移动节点 A

中存储的所有实体。

从堆中删除 A

B 移动到堆的顶部，剩余 10-5 = 5 个滴答然后

重复。