Хранение больших 2D игровых миров

Квадродеревья - довольно эффективное решение для хранения данных о большом двумерном мире и объектах в нем.

Разбейте мир на более мелкие области и разберитесь с ними. Любое решение этой проблемы будет сводиться к этой концепции (например, квадродеревья, упомянутые в другом ответе). Различия будут в том, как они подразделяют мир.

Сколько данных хранится на тайле? Как быстро игроки могут перемещаться по миру? Как ведут себя неигровые персонажи и т. Д., Находящиеся за кадром? Они просто сбрасываются, когда игрок возвращается (как в старых играх Zelda)? Они просто возобновят работу с того места, где были? Выполняют ли они какой-то догоняющий сценарий?

Сколько разных данных рендеринга потребуется для разных областей?

Какую часть мира можно увидеть одновременно?

Все эти вопросы повлияют на ваше решение, а также на возможности вашей платформы.

Вы можете получить некоторые идеи о том, как реализовать это, из некоторых структур пространственных данных, таких как деревья диапазона или kd.

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

Мы говорим о 2D-платформере с 10 врагами на экране, еще 20 за кадром, но «активными», и неизвестным числом, более «неактивными»? Если это так, вы, вероятно, можете сохранить весь свой уровень в виде массива «экранов», где вы будете управлять ближайшими к вам.

Или вы имеете в виду настоящую 2D-игру с большим количеством движений вверх / вниз? Возможно, вам придется быть здесь немного осторожнее.

Платформа также имеет некоторое значение. Если вы реализуете простой платформер для настольных ПК, вам, вероятно, не придется беспокоиться о производительности так же сильно, как на встроенном устройстве. Это не оправдание, чтобы быть наивным в этом вопросе, но, возможно, вам также не нужно быть ужасно умным.

Я думаю, это несколько интересный вопрос. Предположительно, кто-то умнее меня, имеющий опыт внедрения платформеров, уже придумал эти вещи.

Предполагая, что ваша игра обновит только видимое и некоторую область вокруг видимого, просто разбейте мир на «экраны» («экран» - это прямоугольная область на тайловой карте, которая может заполнить весь экран). Храните в памяти «экраны» вокруг видимой области (и некоторые другие, если вы хотите обновить сущности, которые близки к персонажу - но нет особых причин обновлять сущность, которая находится далеко), а остальное храните на диске с кешем чтобы избежать загрузки / разгрузки часто посещаемых мест при перемещении. Некоторые настройки, например:

+---+---+---+---+---+---+---+
|FFF|FFF|FFF|FFF|FFF|FFF|FFF|
+---+---+---+---+---+---+---+
|FFF|NNN|NNN|NNN|NNN|NNN|FFF|
+---+---+---+---+---+---+---+
|FFF|NNN|NNN|NNN|NNN|NNN|FFF|
+---+---+---+---+---+---+---+
|FFF|NNN|NNN|VVV|NNN|NNN|FFF|
+---+---+---+---+---+---+---+
|FFF|NNN|NNN|NNN|NNN|NNN|FFF|
+---+---+---+---+---+---+---+
|FFF|NNN|NNN|NNN|NNN|NNN|FFF|
+---+---+---+---+---+---+---+
|FFF|FFF|FFF|FFF|FFF|FFF|FFF|
+---+---+---+---+---+---+---+

Где часть "V" - это "экран", где находится центр (герой или что-то еще), части "N" - это те, кто находится поблизости и имеет активные (обновляемые) объекты, проверяются на столкновения, и т.д. и "F" части - это далеко не все части, которые могут обновляться нечасто и могут быть «выгружены» (сохранены на диск). Конечно, вы можете захотеть использовать больше "N" экранов, чем два: -).

Обратите внимание на то, что, поскольку 2D-игры обычно не хранят много данных, вместо того, чтобы сохранять удаленные части на диск, вы можете просто сохранить их память сжата.

Возможно, вы захотите использовать один массив int или байтов, который ссылается на типы блоков. Если вам нужна дополнительная оптимизация оттуда, вы захотите связать с более сложными структурами данных, такими как деревья Oct из вашего массива. Здесь есть хорошее обсуждение на игровом форуме Java: http://www.javagaming.org/index.php/topic,20505.30.html text

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

Надеюсь, этого достаточно для вас. : -)