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

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

Я программирую игру, которая имеет место в 2d случайном порожденном бесконечном мире на карте на основе плитки (nitpicking: я знаю, что она не будет по-настоящему бесконечной. Я просто ожидаю, что мир будет довольно большим). Обычный подход к многомерному массиву map [x] [y] начался как основная идея, но поскольку Java не предоставляет способ для нецелого (т.е. Отрицательного) массива shenanigans, такого как PHP, я не могу правильно иметь (- x, + x, -y, + y) с помощью клавиш массива.

Мне нужно найти объекты на плитке с определенной координатой x, y, а также найти "смежные плитки" определенной плитки. (Тривиально, если я могу getObjectAt (x, y), я могу получить (x + 1, y) и т.д.)

Я читал о квадровых деревьях и R-деревьях и т.п. Концепция увлекательна, однако я не видел никакой простой, простой пример реализации на Java. И кроме того, я не совсем уверен, что именно это мне нужно.

Любые советы приветствуются

Спасибо

Ответ 1

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

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

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

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

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

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

Update:

Для кого-то интересно, почему в Java нет класса Pair(), здесь пояснение.

Ответ 2

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)

Ответ 3

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

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

Ответ 4

Деревья, Квадратные деревья, Двоичные деревья, красные и черные деревья - и все другие виды деревьев НЕОБХОДИМО для вас (если вы не планируете иметь карту с огромным лесом).

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

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

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

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

Ответ 5

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

Ответ 6

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

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

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

Ответ 7

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

x/y координаты
c1/c2 координаты блока

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

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

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

Ответ 8

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

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

Ответ 9

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

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

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

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");

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

Ответ 10

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

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

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

Ответ 11

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

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

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

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

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