Как мне построить структуру данных для динамического «лабиринта» неограниченного размера?

43

Я на самом деле не уверен, что «лабиринт» является правильным термином. В основном пользователи начинают с одного, Roomкоторый имеет 4 двери (N, S, E и W). Они могут идти в любом направлении, и каждая последующая комната содержит отдельную комнату с от 1 до 4 дверными проемами, которые ведут в другие комнаты.

Предполагается, что «лабиринт» неограничен по размеру и будет расти по мере перемещения комнат. Доступно ограниченное количество Roomsдоступных, однако доступное число является динамическим и может изменяться.

Моя проблема в том, что я не уверен в лучшей структуре данных для этого типа шаблона

Сначала я подумал только об использовании массива Roomобъектов [X] [X] , но я действительно предпочел бы избегать этого, поскольку объект должен расти в любом направлении, и следует строить только комнаты, которые «посещают».

Другая мысль состояла в том, чтобы каждый Roomкласс содержал 4 связанных Roomсвойства для N, S, E и W и просто ссылался на предыдущий Room, но проблема в том, что я не знаю, как определить, входит ли пользователь в комнату, которая соседняя комната уже "построена"

Например,

--- --- ----------
| | | |
   Начало 5 4
| | | |
--- --- --- ---
--- --- ---------- --- ---
| | | | | |
| 1 2 3
| | | | | |
--- --- --- --- ----------

Если пользователь переходит от Start> 1> 2> 3> 4> 5, тогда Room№ 5 должен знать, что W содержит начальную комнату, S - это комната № 2, и в этом случае он не должен быть доступен, а N может быть либо новый Roomили стена (ничего).

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

Есть ли лучший способ построения структуры данных для этого типа "лабиринта"? Или я нахожусь на правильном пути с моим текущим мыслительным процессом, и мне просто не хватает нескольких фрагментов информации?

(Если вам интересно, проект представляет собой игру, очень похожую на Munchkin Quest )

Рейчел
источник
Я не думаю, что какой-либо массив будет работать, так как комнаты будут расти в любом направлении ... Так что, если вы начнете с [0,0] и двигаетесь влево? было бы попробовать [-1, 0].
Пол
@Paul Добавьте строку / столбец, переместите все данные массива, затем сместите также все позиции игрока, чтобы соответствовать новому массиву карты. Медленный и может быть трудным в зависимости от того, сколько должно быть сдвинуто, но возможно. Тем не менее, Bubblewrap ответ гораздо лучше.
Изката
Я, наверное, не прав, но разве это не будет лучше на GameDev.SE?
Динамичный
1
@Dynamic Это вопрос структуры данных, поэтому он отлично вписывается.
Изката

Ответы:

44

Задайте координаты каждой комнаты (начало будет (0,0)) и сохраните каждую сгенерированную комнату в словаре / хэш-карте по координатам.

Определить соседние координаты для каждой комнаты тривиально, что можно использовать, чтобы проверить, существует ли комната уже. Вы можете вставить нулевые значения для представления местоположений, в которых уже определено, что комнаты не существует. (или, если это невозможно, я не уверен, что это отдельный словарь / hasmap для координат, которые не содержат комнату)

Bubblewrap
источник
2
Сделайте так, чтобы каждый объект комнаты содержал информацию о северо-востоке-юго-западе для других объектов комнаты, так что вы можете использовать словарь / хэш-карту, а также кардинальные направления комнаты для навигации по лабиринту (иногда вам может понадобиться найти абсолютные координаты и иногда вам захочется узнать, что находится к северу от комнаты объекта X).
Нейл
2
@Paul Я думаю, что идея состоит в том, чтобы создать словарь комнат, и при создании новой Room, искать соседние комнаты в словаре и добавлять их ссылки на Roomобъект, прежде чем добавлять новые комнаты на оставшиеся стороны. Таким образом, единственный раз, когда поиск по словарю происходит при создании нового Roomобъекта, а не при путешествии между нимиRooms
Рэйчел
7
Нет никакой причины хранить ссылки на другие комнаты внутри Roomобъекта вообще. Если вы находитесь в комнате (x,y)и хотите отправиться на север, вы ищите комнату (x,y+1)в словаре, создавая ее, если она не существует. Поиск в словаре очень быстрый O(1).
Карл Билефельдт
3
@KarlBielefeldt: Комната @ (x,y+1)может существовать, но не может быть ориентирована на (x,y)север. То есть, что край не может перейти непосредственно от (x,y)к (x,y+1).
Стивен Эверс
2
Вы, ребята, делаете это сложно. Это в основном то же самое, что и массив ... за исключением того, что вы ищете его в словаре, а не в двухмерном массиве. Любые проблемы, с которыми вы столкнетесь с массивом, также будут там ... но он все равно собирался использовать массив.
user606723
15

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

Я не уверен, какой язык вы используете, но хороший урок / объяснение с подробностями реализации для графа, реализованного со списком смежности в .NET, здесь .

Стивен Эверс
источник
1
Не уверен, что для описания этого достаточно графика, поскольку N / E / S / W на самом деле не являются частью концепции графа; есть только подключение и, возможно, вход / выход.
Эдвард Стрендж
3
@CrazyEddie: имейте в виду, что структура данных / a не предназначена для непосредственного сопоставления с каким-либо конкретным доменом (в этом и заключается их преимущество). В этом конкретном примере график будет направленным, а ребра могут быть тривиально помечены перечислением.
Стивен Эверс
Аннотация может тривиально навязывать отношения восток-запад, север-юг. Это устранит проблемы перехода на запад из комнаты A в комнату B, а затем на восток из комнаты B в комнату C (вместо комнаты A) из-за плохой связи.
Питер Смит
3
Допустим, мы хотели реализовать комнату, заполненную волшебником, который защищает себя, телепортируя игрока на десять квадратов в случайном направлении. Поиск этой точки в структуре данных на основе графика будет очень дорогим, особенно если эта комната не существует, и вам нужно было сгенерировать все комнаты, связывающие эту комнату с другой комнатой на графике (поскольку структура не допускает многократное использование, взаимно отключенные участки подземелья).
Марк Бут
2
@MarkBooth, но тогда мы изменили требования, нет?
Джошуа Дрейк
9

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

Есть несколько вопросов, которые задаются этой структурой:

  1. есть ли комната в X, Y?
  2. есть ли комната [N / S / E / W] пустого места X, Y?

Проблема с простыми списками и графиками

Трудность с простыми списками состоит в том, что нужно пройтись по структуре, чтобы проверить, можно ли что-то разместить в данном месте. Системе нужен способ доступа к произвольному местоположению O (1).

Рассмотреть возможность:

1 2 3 ? 4
5 . . * 6
7 8 9 A B

Чтобы найти информацию о возможном местоположении «?», Когда на 3 нужно пройти весь путь, чтобы добраться до 4. Ответ по ссылке с дополнительной информацией о том, сколько узлов он прыгает (так что 3 будет связано с 4 с дополнительной информацией «прыжок 1») по-прежнему требуются прогулки, чтобы найти смежность «*» от 6 или A.

Простые, большие, массивы

Доступно ограниченное количество номеров

Если это небольшое число, просто создайте массив 2N x 2N и оставьте его там. Массив 100 x 100 - это «всего» 10 000 указателей и 50 объектов. Индексируйте прямо в массив.

Это может быть уменьшено до просто NxN, если из-за пределов действия переместили массив вокруг, чтобы всегда быть в пределах ограничений. Например, если должна быть добавлена ​​комната, которая опустит массив, создайте сетку, чтобы сдвинуть каждый элемент на одну позицию, чтобы больше не было переполнения. На данный момент размер мира для 50 комнат будет 2500 указателей и 50 объектов.

Разреженные массивы и матрицы

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

Мой предпочтительный подход состоит в том, чтобы иметь комнаты как структуру (указатели на соседние комнаты и координаты), и чтобы в комнате была указатель из хеш-таблицы, которая хэшируется по координатам. В этой ситуации, чтобы спросить, какая комната [N / S / E / W] из нулевой комнаты, нужно было бы запросить хеш-таблицу. Кстати, это формат DOK для хранения разреженной матрицы.

Сообщество
источник
1
Хороший ответ, как предполагает Bubblewrap , - словарь с кортежем позиции в качестве ключа - разумная структура для использования разреженной матрицы.
Марк Бут
2

Как насчет этого..

Дайте каждой ячейке ссылку на каждого из ее соседей. Дайте каждой ячейке какое-то имя (например, «0/0», «-10/0» (предположим, вы начинаете с 0,0)). Добавьте HashSet со всеми именами в нем. Когда вы пытаетесь перейти в другую ячейку, просто убедитесь, что сосед не существует в HashSet.

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

   Empty   
   (0,1)        

---    ---            ----------
|        |            |        |
    0,0       1,0        2,0       Empty
|        |            |        |   (3,0)
---    --- ---------- ---    ---
|        | |        | |        |
|   0,-1      1,-1       2,-1      Empty
|        | |        | |        |   (3,-1)
---    --- ---    --- ----------

   Empty     Empty   
  (0,-2)    (1,-2)

HashSet = {0 | 0, 1 | 0, 2 | 0, 3 | 0, 0 | -1, 1 | -1 ....} 1,0: W = 0,0 / Дверь; 1,0: N = 1,1 / пусто; Е = 2,0 / Дверь; S = 1, -1 / Стена

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

Павел
источник
1

То, что вы разрабатываете, очень похоже на график.

График лабиринта

Они часто представляются в виде набора состояний Q , начального состояния q 0Q и некоторых переходов Δ . Итак, я бы посоветовал вам хранить это так.

  • Набор Q : {s, 1, 2, 3, 5, 6}
  • Начальное состояние q 0 : s
  • Карта переходных отношений Δ : {s → 1, s → 5, 1 → 2, 2 → 3, 3 → 4, 4 → 5}

У большинства разумных языков есть и карты, и наборы.

KBA
источник
0

Вы могли бы рассмотреть 4-сторонний связанный список ...

Сначала я подумал только об использовании массива объектов Room [X] [X], но я действительно предпочел бы избегать этого, поскольку объект должен расти в любом направлении, и следует строить только комнаты, которые «посещают».

Вы все еще можете использовать [] [] для этого. Динамический рост может быть медленным, особенно при добавлении в начале, но, возможно, не все так плохо. Вы должны профиль, чтобы проверить. Попытка манипулировать каким-либо связанным списком или картой на самом деле может быть хуже и на постоянном уровне, а не случайным.

Вы можете построить только посещенные комнаты, внедрив ленивую оценку. Может быть объект, который содержит комнату и не строит эту комнату до тех пор, room()пока к ней не призовут. Затем он просто возвращает один и тот же каждый раз после этого. Не сложно сделать.

Эдвард Стрендж
источник
1
Не могли бы вы рассказать о том, что вы подразумеваете под «4-сторонним связным списком»? Единственной вещью, которую я смог найти, была статья CodeProject, которая сводилась к тому, чтобы быть списком смежности.
Стивен Эверс
0

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

http://www.atariarchives.org/adventure/chapter1.php

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

room {
 int north_dir;
 int south_dir;
 int west_dir;
 int east_dir;
 // All other variables and code you care about being attached to the rooms here
}

Тогда у вас может быть массив или структура связанного списка, или вы хотите управлять своими комнатами. Для стиля массива (или векторов C ++) я бы использовал этот код, а в направлениях содержался бы индекс комнаты, на которую они ссылаются; для связанного списка, вы можете использовать указатели на следующую комнату.

Как уже говорили другие, если вам нужно динамически генерировать новые комнаты, когда люди входят в них, вы также можете сделать это.

laaph
источник
0

Не пытайтесь решить все проблемы с одной структурой.

Определите объект вашей комнаты, чтобы хранить вещи о комнате, а не ее связь с другими комнатами. Тогда одномерный массив, список и т. Д. Могут расти как вам угодно.

Отдельная структура может содержать «достижимость» - какие комнаты доступны из комнаты, в которой я нахожусь. Затем решите, должен ли переходной достижимость быть быстрым расчетом или нет. Вы могли бы хотеть вычисление грубой силы и тайник.

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

юлианский
источник