Как управлять зависимостями между картой тайлов и юнитами

11

У меня есть 2D-стратегия на основе плиток в работах. Я брожу, как справиться с отношениями между картой и единицами на карте.

Учитывая координаты тайла, я должен быть в состоянии заставить юнит стоять на нем, если таковой имеется. В то же время, если мне дадут единицу, я захочу получить координату единицы.

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

Второе решение состоит в том, чтобы только единицы отслеживали свои координаты. Чтобы узнать, содержит ли тайл единицу, и чтобы получить эту единицу, я бы перебрал весь набор единиц юнитов, и я нашел одну с соответствующими координатами. Это избавляет от циклической зависимости, но при этом теряется свойство O (1), которое было в первом решении для поиска единиц на карте. Это может сложиться так, как я хочу, чтобы иметь возможность регулярно сканировать карту на предмет таких вещей, как поиск пути, определение диапазона движения и нахождение допустимых целей для данного подразделения.

Я также не могу просто хранить единицы на карте (или я могу?). Юниты связаны с «армиями», будь то игрок или ИИ. Армия должна иметь возможность легко получить доступ и перебирать все свои подразделения.

Так как это кажется распространенной проблемой в стратегических играх, есть ли какие-либо другие шаблоны, кроме двух, которые я описал для управления отношениями юнит / карта?

AJM
источник

Ответы:

3

Это не популярный шаблон, но мир реляционных баз данных предлагает третий способ: использовать структуру данных, которая имеет несколько ключей. В табличной форме это может выглядеть так:

Unit id    Location
-------------------
  1309     13,15
  2357      7,93
  8552      7,93

Вы хотите быть в состоянии спросить: «Где блок 2357?» и вернись 7,93. Вы также хотите иметь возможность спросить: «Что находится в локации 7,93?» и вернитесь 2357 и 8552. Существуют структуры данных, которые позволяют несколько ключей для поиска вещей. Вы можете сохранить это вне единиц и вне карты, если вы хотите удалить зависимости.

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

Я рекомендую делать все, что проще (ваше второе решение), а затем, если это проблема с производительностью, вы можете добавить пространственный раздел, чтобы ускорить поиск.

amitp
источник
Итак, структура данных пространственного разделения, которую вы упоминаете, может быть просто картой (которая в моем случае якобы представляет собой двумерную сетку плиток). Я предполагаю, что когда единица перемещается (или добавляется, или удаляется), мне все еще нужно обновить и единицу, и структуру пространственного разделения, чтобы поддерживать их синхронизацию. Возможно, это одна из тех вещей, с которыми мне придется жить?
AJM
1
Да, карта - это самый мелкозернистый пространственный раздел, который вы бы использовали. Глобальный список всех единиц является наиболее грубым разделом. ;) Вам нужно только обновить раздел, прежде чем он будет использован. Если вы используете его все время, возможно, вы захотите обновлять его каждый раз, когда устройство перемещается. Однако, если вы используете его только для некоторых этапов логики обновления, вы можете пройти список модулей за один проход и вычислить структуру данных раздела, а затем отбросить его, когда закончите. Таким образом, вам не нужно постоянно синхронизировать их.
amitp
5

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

На самом деле, даже если у вас было 4000 юнитов на игрока, используя два целых числа для хранения там местоположения, и 8 игроков, которые занимают всего 2 МБ, но с первым решением вы получаете вместо O (1) координатор, а не O (n) (при условии отсутствия сортировки), что с большим количеством единиц может быть медленным.

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

Рэй Бриттон
источник
Меня не беспокоит использование памяти, меня больше интересует управление зависимостями (в смысле объектно-ориентированного проектирования). Меня беспокоит не лишняя память, которую может вызвать первое решение, а циклическая зависимость, которой я опасаюсь, насколько мне нравится метод получения O (1) координат. Кроме того, я знаю, что многие игры в настоящее время основаны на пикселях, но мне нравятся плитки, поэтому я и использую их. : P
AJM
@ AJM, так же, платные приложения, которые я буду выпускать на Android, будут использовать плитки.
Рэй Бриттон