Какие структуры данных для поддержки очереди в стиле Final Fantasy ATB? (очередь задержки)

Question

Ситуация: в моделируемой среде есть несколько объектов, у которых есть искусственное представление о времени, называемое «тиками», которое не имеет связи с реальным временем. Каждая сущность по очереди движется, но некоторые быстрее других. Это выражается в задержке, в тиках. Таким образом, сущность A может иметь задержку 10, а B 25. В этом случае порядок хода будет следующим:

A A B A A

Мне интересно, какую структуру данных использовать. Сначала я автоматически подумал «очередь с приоритетами», но задержки относятся к «текущему времени», что усложняет ситуацию. Также будут существовать объекты с большими задержками, и не исключено, что программа будет проходить через миллионы тиков. Кажется глупым, что внутренний счетчик строит все выше и выше, когда сами задержки остаются относительно небольшими и не увеличиваются.

Так как бы вы решили это?

Answer 1

Вы сохраняете сущности в куче и группируете их по времени ожидания. Группа сущностей, которые находятся рядом с движением, будет в верхней части кучи. Вам нужно только обновить эти объекты. Когда их оставшееся время ожидания падает до 0, вы удаляете их из кучи. Поместите следующую группу сущностей в линию в верхней части кучи, уменьшив при этом время ожидания на количество времени, прошедшее до предыдущего хода.

Например:

Ваша куча имеет 3 узла (A, B и C), верх - это узел A с двумя объектами, у каждого из которых осталось 5 тиков. У детей 10 и 12 тиков, оставшихся соответственно.

• В момент времени t = 5 вы перемещаете все сущности, объединенные в узел A
• Удалить A из кучи
• B движется к вершине кучи с оставшимися 10-5 = 5 тиками, затем
• повторить.

Answer 2

По твоему описанию мне кажется, что понятие "что дальше?" важнее, чем «сколько времени до следующего действия?». В таком случае сортируйте свою очередь по «ближайшим» или по наименьшему количеству оставшихся тиков по наибольшему. Разумеется, вставки вводятся в соответствующем порядке, а измененные записи (заклинания «Ускорение») удаляются из очереди, изменяются и затем снова вводятся соответствующим образом.

Затем вы просто выталкиваете следующую работу из очереди. Какое бы количество тиков у него не оставалось, оно должно быть «прошедшим время». Делает проход по очереди, уменьшая поле оставшихся тиков каждой записи на количество только что обнаруженных тиков.

Это имеет преимущество в отслеживании концепции оставшегося времени, а также в том, что нет необходимости запускать события или выполнять какой-либо другой код для тиков, которые проходят, когда не предпринимается никаких действий. Вы можете себе это позволить, поскольку никакого отношения к реальному времени нет вообще. Есть только «что дальше?» И «Сколько времени понадобилось, чтобы туда добраться?».

Answer 3

Посмотрите, как реализован Java DelayQueue .

Answer 4

Если мы предположим, что ваши сущности наблюдают или наблюдают за временем симуляции, каждый из них может реализовать интерфейс, который заставляет их отслеживать ticks left и предоставляет метод, чтобы узнать, сколько тиков осталось для конкретной сущности. На каждом тике сущность уменьшает свои ticks left на 1.

Затем можно сохранить отсортированную очередь набора (установленную, потому что каждый объект будет в очереди только один раз) этих объектов, отсортированных по get ticks left, так что 0-й объект - это тот, который должен двигаться дальше, а N-й сущность самая "медленная".

Когда метод get ticks left объекта имеет значение 0, он удаляется из отсортированного набора, таймер ticks left сбрасывается и снова вставляется в отсортированный набор.

Answer 5

Вариант № 1: опрос

Я бы, вероятно, построил бы контроллер, который мог бы обнаружить задержку для всех различных объектов и поддерживать остаточные значения для каждого объекта. Контроллер будет циклически проходить через тики, и на каждом тике он будет уменьшать оставшиеся тики для всех объектов в игре.

Как только оставшееся значение тиков сущностей достигает нуля, вы знаете, что это их очередь, управляемая методом тактового импульса, который обрабатывает тики, или методом, который вы вызываете.

Вариант № 2 События

Думайте как парадигма пользовательского интерфейса, интерфейс не постоянно опрашивает кнопку, чтобы увидеть, когда она нажата. Вместо этого давайте кнопку уведомим пользовательский интерфейс, когда он был нажат через события. Пусть ваши сущности (или EntityBattleContext) запустят событие, когда оно будет готово. Вам придется каким-то образом обрабатывать игровое время, поскольку оно вообще не основано на реальном времени, вам может потребоваться, чтобы все сущности прослушивали событие GameTick, и когда они получают это событие, обновляют свою внутреннюю переменную TicksRemaining.

Прежде чем следовать по маршруту, управляемому событиями, убедитесь, что маршрут опроса не работает. Помните кардинальное правило , всегда оптимизируйте позже , потому что чаще всего вам не нужна оптимизация.