Какая структура (структуры) данных поддержать Заключительную Фэнтезийную очередь ATB-стиля? (очередь задержки)
Ситуация: в моделируемой среде существует несколько объектов, которая имеет искусственное понятие времени, названного "галочками", который не имеет никакой ссылки на реальное время. Каждый объект берет его по очереди для перемещения, но некоторые быстрее, чем другие. Это выражается задержкой в галочках. Так объект A мог бы иметь задержку 10, и B 25. В этом случае порядок поворота пошел бы:
B A
Я задаюсь вопросом что структуру данных использовать. Сначала я автоматически думал "приоритетная очередь", но задержки относительно "текущего времени", которое усложняет ситуацию. Кроме того, будут объекты с большими задержками, и это весьма обозримо, что программа пробежит миллионы галочек. Это кажется глупым для внутреннего в противоречии с создать выше и выше когда сами задержки остаются относительно маленькими и не увеличиваются.
Таким образом, как Вы решили бы это?
5 ответов
Вы храните объекты в куче и группируете их по времени, оставшемуся для ожидания. Группа объектов, которые будут перемещены следующей, будет наверху кучи. Вам нужно только обновить эти объекты. Когда оставшееся время ожидания упадет до 0, вы удалите их из кучи. Поместите следующую группу объектов в строку вверху кучи, уменьшив их время ожидания на количество времени, которое только что прошло перед предыдущим ходом.
Например:
Ваша куча имеет 3 узла (A, B и C), вершина - это узел A с двумя объектами, у каждой из которых осталось по 5 тиков. У детей осталось 10 и 12 клещей соответственно.
- В момент t = 5 вы перемещаете все объекты, которые разделены на сегменты в узле A
- Удалите A из кучи
- B перемещается в верхнюю часть кучи с оставшимися 10-5 = 5 тиками, затем
- повторить.
Мне кажется по вашему описанию, что понятие «что дальше?» важнее, чем «сколько времени до следующего действия?». В этом случае отсортируйте свою очередь по «следующей очереди» или по наименьшему количеству оставшихся тиков до наибольшего. Вставки, конечно, вводятся в соответствующем порядке, а измененные записи (заклинания «Ускорение») удаляются из очереди, изменяются, а затем повторно вводятся соответствующим образом.
Затем вы просто выталкиваете следующее задание из очереди. Какое бы количество тактов не оставалось, это должно быть «прошедшее время». Проходит по очереди, уменьшая оставшееся поле тиков каждой записи на количество тиков, которое вы только что обнаружили.
Это дает преимущество в отслеживании концепции оставшегося времени, но также в том, что вам не нужно запускать события или выполнять какой-либо другой код для тиков, которые проходят, когда не нужно предпринимать никаких действий. Вы можете себе это позволить, ведь к реальному времени нет никакого отношения. Есть только «что дальше?» И «сколько времени понадобилось, чтобы добраться туда?».
Если мы предположим, что ваши сущности наблюдают или следят за временем симуляции, то каждая из них могла бы реализовать интерфейс, который заставляет их отслеживать оставшиеся тики и предоставляет метод для получения количества оставшихся тиков для конкретной сущности. При каждом тике сущность уменьшает свое количество оставшихся тиков на 1.
Затем вы могли бы вести отсортированную очередь (отсортированную, потому что каждая сущность будет в очереди только один раз) из этих сущностей, отсортированных на основе количества оставшихся тиков, так что 0-я сущность будет двигаться следующей, а N-я - самой "медленной".
Когда метод get ticks left сущности равен 0, она удаляется из отсортированного набора, таймер ticks left сбрасывается, и она снова вставляется в отсортированный набор.
Вариант #1: Опрос
Я бы, вероятно, создал контроллер, который может определить задержку для всех различных сущностей и поддерживать тики, оставшиеся для каждой сущности. Контроллер будет циклически перебирать тики и на каждом тике уменьшать тик-остаток для всех сущностей в игре.
Как только значение тиков, сохраняемых сущностями, достигнет нуля, вы узнаете, что настал их черед, либо под контролем метода heartbeat, который обрабатывает тики, либо метода, который вызываете вы.
Вариант #2 События
Подумайте, как в парадигме пользовательского интерфейса, интерфейс не опрашивает постоянно кнопку, чтобы узнать, когда она нажата. Скорее, он позволяет кнопке уведомлять пользовательский интерфейс о нажатии с помощью событий. Пусть ваши сущности (или EntityBattleContext) вызывают событие, когда они готовы. Вам придется каким-то образом обрабатывать игровое время, поскольку оно не основано на реальном времени, вам может понадобиться, чтобы все сущности слушали событие GameTick и при получении этого события обновляли свою промежуточную переменную TicksRemaining.
Прежде чем следовать маршруту, основанному на событиях, убедитесь, что маршрут с опросом не сработает. Помните кардинальное правило всегда оптимизируйте позже, потому что чаще всего оптимизация не нужна.