Представление Gameworld, который имеет неправильную форму

Question

Я работаю над проектом, в котором игровой мир имеет неправильную форму (подумайте о форме озера). эта форма имеет сетку с расположенными над ней координатами. Мир игры находится только внутри формы. (Еще раз, думаю, озеро)

Как я могу эффективно представлять игровой мир? Я знаю, что многие миры в основном квадратные и хорошо работают в массиве размером 2 или 3. Я чувствую, что если я использую массив, который является квадратным, тогда я в основном теряю пространство и увеличиваю время, необходимое мне для итерации по массиву. Тем не менее, я не уверен, как здесь будет работать зубчатый массив.

Пример форма игрового мира

X 
XX 
XX X XX 
XXX XXX 
    XXXXXXX 
XXXXXXXX 
XXXXX XX 
    XX X 
    X 

Edit: Мир игры, скорее всего, нужно каждый правильное местоположение переступил. Поэтому я бы использовал метод, который упростил бы это.

Answer 1

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

Answer 2

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

Answer 3

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

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

Пример весьма нерегулярной карта:

x 
x x 
    x x x 
    x  x 
    x xxx 
    x 
    x 
    x 
    x 

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

xxxxxx x 
xxxxxxxxx 
    xxxxxxxxx 
    xx xxxx 

Answer 4

проще всего просто использовать массив, и просто отметьте позиции не-игрового пространства с некоторым специальным маркером. Может работать и неровный массив, но я не так сильно их использую.

Answer 5

Вы можете использовать quadtree, чтобы свести к минимуму количество свободного пространства в своем представлении. Квадратные деревья хороши для разбиения 2-мерного пространства с разной степенью детализации - в вашем случае лучшая гранулярность - игровой квадрат. Если бы у вас была целая площадь 20x20 без квадратов игры, представление квадратного дерева позволило бы использовать только один узел для представления всей области, а не 400, как в представлении массива.

Answer 6

Используйте любую структуру, с которой вы столкнулись, - вы всегда можете изменить ее позже. Если вам удобно использовать массив, используйте его. Не беспокойтесь о структуре данных, которую вы собираетесь использовать, и начните кодирование.

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

Answer 7

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

Answer 8

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

Answer 9

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

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

Этот район должен быть как можно более простым, легким и быстрым в доступе. Это определенно должен быть массив (или набор массивов, которые поменяются при перемещении игрока). На него будут ссылаться часто и на многие подсистемы вашего игрового движка: графика и физика будут обрабатывать загрузки моделей, рисовать их, удерживать игрока на вершине местности, столкновения и т. Д .; звук должен знать, какой тип земли находится в данный момент, играть соответствующий звук; и так далее. Вместо того, чтобы транслировать и дублировать эти данные среди всех подсистем, если вы просто храните их в глобальных массивах, они могут получить к нему доступ по желанию и со скоростью 100% и эффективностью. Это может действительно упростить вещи (но быть в курсе последствий глобальных переменных!).

Однако на диске вы определенно хотите сжать его. Некоторые из этих ответов дают хорошие предложения; вы можете сериализовать структуру данных, такую ​​как хэш-таблица, или список только заполненных мест. Вы, конечно же, могли бы хранить октет. В любом случае вы не хотите хранить пустые места на диске; согласно вашей статистике, это означает, что 66% пространства будет потрачено впустую. Конечно, есть время, чтобы забыть об оптимизации и сделать его просто работающим, но вы не хотите распространять 66% -ный файл конечным пользователям. Также имейте в виду, что диски - это не идеальные машины с произвольным доступом (кроме SSD); механические жесткие диски по-прежнему должны быть примерно на несколько лет, и они работают лучше всего последовательно. Посмотрите, можете ли вы организовать структуру данных, чтобы операции чтения были последовательными, поскольку вы перемещаете более близкую территорию, пока игрок перемещается, и вы, вероятно, обнаружите, что это заметная разница. Не верьте мне на слово, хотя я на самом деле не проверял подобные вещи, это просто имеет смысл?