Java: Какова хорошая структура данных для хранения карты координат бесконечного игрового мира?

Я пришел в эту тему с той же проблемой, но мое решение состояло в том, чтобы использовать Map/HashMaps, но они одномерные.

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

Итак, при определении карты: Map<Pair, Tile> tiles = new HashMap<Pair, Tile>;

Для размещения тайловых объектов на карте я использовал tiles.put(new Pair(x, y), new GrassTile());, а для получения объекта tiles.get(new Pair(x, y));.

[x/y может быть любой координатой, которую вы хотите разместить (это позволяет использовать отрицательные координаты без какой-либо путаницы!), "new GrassTile()" - это просто пример размещения плитки определенного типа во время карты. творчество. Очевидно, как было сказано ранее, класс Pair заменяем.]

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

Обновление:

Для тех, кто интересуется, почему в Java нет класса Pair(), вот объяснение.

1) Вместо массива вы можете использовать Map<Integer, Map<Integer, Tile>> или Map<Point, Tile>, что, конечно, позволит использовать отрицательные индексы.

2) Если вы знаете размеры своего мира с самого начала, вы можете просто изменить свой геттер, чтобы позволить API принимать негативы и [линейно] преобразовывать их в позитивы. Так, например, если ваш мир имеет размер 100x1000 плиток и вы хотите (-5,-100), у вас будет WorldMap.getTile(-5,-100), что будет переведено в return tileArray[x+mapWidth/2][y+mapHeight/2];, что равно (45 400)

Деревья, квадродеревья, бинарные деревья, красные и черные деревья - и все остальные виды деревьев для вас БЕСПОЛЕЗНЫ (если только вы не планируете иметь карту с огромным лесом).

Специализированные структуры данных имеют свое специфическое применение. Если вы не можете придумать вескую причину, по которой вашей игре нужен пространственный индекс, не создавайте его. Если ваш типичный сценарий — «перебрать видимую область, выяснить, какая плитка видна в каждом из квадратов», то вам нужна структура, которая дает вам быстрый, случайный доступ к значению, хранящемуся под определенным ключом. Такой структурой является HashMap (то, что использует PHP, является своего рода LinkedHashMap, но вы, вероятно, не использовали «связанную» часть).

Вам нужно последовать совету xephox (и отдать ему должное), а именно:

• создать класс, описывающий местоположение (Pair, Location, Point, что угодно);
• сделать все поля (возможно, x и y) окончательными. Важно, что сама локация не может меняться (это НАМНОГО облегчит вам жизнь);
• генерировать методы equals и hashcode (с этим вам поможет любая IDE. Помните, что реализации ДОЛЖНЫ использовать и x, и y — вам поможет мастер в вашей IDE);
• ваша карта будет: Map map = new HashMap();

Самое лучшее: если вы продолжите использовать интерфейс карты, вы не будете заблокированы и сможете внести множество улучшений. Например, обернуть HashMap в объект, который создает части карты с использованием некоторых алгоритмических методов.

Я не эксперт в программировании игр, но если с массивами все в порядке, вы можете просто перевести свои координаты из (-x, +x) в (0, 2x) (то же самое для оси y).

Или, если вы привыкли к ассоциативным массивам, таким как PHP, используйте соответствующую структуру в Java, которая является Map (HashMap будет в порядке): определите класс Coordinate с соответствующими методами equals и hashCode и используйте HashMap<Coordinate>. Неизменяемость координат делает код более надежным и позволяет кэшировать хэш-код.

вы можете попробовать QuadTree (хороший пример здесь: http://www.mikechambers.com/blog/2011/03/21/javascript-quadtree-implementation/ )

Как насчет того, чтобы разделить вашу карту на куски (да, фанаты Minecraft, я тоже знаю, где это используется :P)? Итак, у вас есть две системы координат, обе с одним и тем же началом:

• x/y координаты
• c1/c2 координаты чанка

Чанк всегда имеет фиксированный размер координат реального мира (скажем, 128x128). Затем у вас есть класс Chunk, где у вас есть фиксированный массив (128x128) со всей информацией для каждого пикселя. И вы сохраняете свои куски в Map<ChunkCoordinates, Chunk>, как уже объясняли другие. Я бы порекомендовал HashMap.

Всякий раз, когда ваш игрок находится в определенном регионе, необходимые фрагменты загружаются с карты, а затем вы можете получить доступ к массиву фиксированного размера. Если чанк знает, где он находится в координатах x/y, у вас может быть даже какая-то функция поддержки, например, Pixel Chunk#getPixel(long x, long y) или около того...

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

Я написал пару экспериментальных запасных структур данных на Java, которые могут вас заинтересовать.

Самым интересным из них был Octreap, который, как мне кажется, представляет собой совершенно новый гибрид Treap и Octree со следующими функциями:

• 60-битные мировые координаты (приблизительно 1 000 000 * 1 000 000 * 1 000 000 сетки)
• Отрицательные координаты поддерживаются
• Пустое пространство не требует хранения (поддерживает очень разреженные миры)
• Сжимает объемы идентичных ячеек (например, большие блоки одного и того же материала будут эффективно храниться)
• O(log n) для чтения и записи

Вероятно, вы захотите использовать реализацию Map. HashMap, SortedMap и т. д., в зависимости от объема данных, которые вы собираетесь хранить, и шаблонов доступа (отсортированная карта очень хороша для последовательного доступа, HashMap лучше подходит для произвольного доступа).

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

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

Что касается первого вопроса, то одним из приемов будет поддержка четырех отдельных матриц (матриц?), по одной для каждого квадранта. Тогда все индексы могут быть положительными.

По второму вопросу вам нужна разреженная карта. Один не очень эффективный способ — иметь хэш-карту хэш-карт. На самом деле, это может решить и первую проблему:

HashMap<String, HashMap> x = new HashMap()
HashMap<String, Tile> y = new HashMap()

// get the tile at coordinates 1,2
Tile myTile = x.get("1").get("2");

// this would work as well
myTile = x.get("-1").get("-2");

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

Если вы хотите быть действительно быстрым и действительно масштабируемым, обязательно используйте разреженное октодерево.

http://en.wikipedia.org/wiki/Octree

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

Решения в стиле хэш-карты ужасны для вычислений смежности, они требуют итерации всего набора данных.

Что-то вроде дерева квадрантов или октодерева идеально, ЗА ИСКЛЮЧЕНИЕМ того, что оно не бесконечно, а имеет произвольный размер (там мир различий).

Однако, если подумать, ArrayList не бесконечен, это просто произвольный размер, который растет, верно?

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

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