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

Question

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

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

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

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

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

Спасибо

Answer 1

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)

Answer 2

Я пришел к этой теме с той же проблемой, но мое решение было использовать 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?Поскольку списки массивов намного более линейны, чем отображение, и, на мой взгляд, сложнее добавлять и извлекать плитки, особенно в 2 измерениях.

Обновление:

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

Answer 3

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

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

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

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

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

Answer 4

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

Answer 5

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

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

Answer 6

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

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

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

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

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

Answer 7

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

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

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

Answer 8

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

Что-то вроде квадродерева или октодерева идеально, за исключением того, что оно не бесконечно, это произвольный размер (мир различий)там).

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

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

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

Answer 9

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

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

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

Answer 10

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

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

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

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

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