Я на самом деле не уверен, что «лабиринт» является правильным термином. В основном пользователи начинают с одного, 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)) и сохраните каждую сгенерированную комнату в словаре / хэш-карте по координатам.
Определить соседние координаты для каждой комнаты тривиально, что можно использовать, чтобы проверить, существует ли комната уже. Вы можете вставить нулевые значения для представления местоположений, в которых уже определено, что комнаты не существует. (или, если это невозможно, я не уверен, что это отдельный словарь / hasmap для координат, которые не содержат комнату)
источник
Room
, искать соседние комнаты в словаре и добавлять их ссылки наRoom
объект, прежде чем добавлять новые комнаты на оставшиеся стороны. Таким образом, единственный раз, когда поиск по словарю происходит при создании новогоRoom
объекта, а не при путешествии между нимиRooms
Room
объекта вообще. Если вы находитесь в комнате(x,y)
и хотите отправиться на север, вы ищите комнату(x,y+1)
в словаре, создавая ее, если она не существует. Поиск в словаре очень быстрыйO(1)
.(x,y+1)
может существовать, но не может быть ориентирована на(x,y)
север. То есть, что край не может перейти непосредственно от(x,y)
к(x,y+1)
.В большинстве случаев то, что вы описываете, звучит как график. Учитывая некоторые ваши требования (растущий аспект), я бы, вероятно, выбрал список смежности в качестве реализации (другой распространенный вариант - матрица смежности ).
Я не уверен, какой язык вы используете, но хороший урок / объяснение с подробностями реализации для графа, реализованного со списком смежности в .NET, здесь .
источник
Несколько мыслей по поводу реализации (я подумал о Каркассоне, у которого есть ряд других сложных аспектов построения матрицы - это был даже вопрос интервью, который мне когда-то задавали).
Есть несколько вопросов, которые задаются этой структурой:
Проблема с простыми списками и графиками
Трудность с простыми списками состоит в том, что нужно пройтись по структуре, чтобы проверить, можно ли что-то разместить в данном месте. Системе нужен способ доступа к произвольному местоположению O (1).
Рассмотреть возможность:
Чтобы найти информацию о возможном местоположении «?», Когда на 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 для хранения разреженной матрицы.
источник
Как насчет этого..
Дайте каждой ячейке ссылку на каждого из ее соседей. Дайте каждой ячейке какое-то имя (например, «0/0», «-10/0» (предположим, вы начинаете с 0,0)). Добавьте HashSet со всеми именами в нем. Когда вы пытаетесь перейти в другую ячейку, просто убедитесь, что сосед не существует в HashSet.
Кроме того, если вы создаете отверстие в другой комнате, значит ли это, что комнаты существуют? Таким образом, вы бы создали ссылку на пустую комнату без ссылок на какие-либо комнаты. Возможно, вы также хотели бы проверить новые комнаты соседей. Если он существует и откроется в вашей новой комнате, добавьте дверь в эту комнату.
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 / Стена
Вы также должны убедиться, что вы даете каждой новой комнате хотя бы одну несмежную (в другую комнату) дверь, чтобы лабиринт мог расти в этом направлении.
источник
То, что вы разрабатываете, очень похоже на график.
Они часто представляются в виде набора состояний Q , начального состояния q 0 ∈ Q и некоторых переходов Δ . Итак, я бы посоветовал вам хранить это так.
У большинства разумных языков есть и карты, и наборы.
источник
Вы могли бы рассмотреть 4-сторонний связанный список ...
Вы все еще можете использовать [] [] для этого. Динамический рост может быть медленным, особенно при добавлении в начале, но, возможно, не все так плохо. Вы должны профиль, чтобы проверить. Попытка манипулировать каким-либо связанным списком или картой на самом деле может быть хуже и на постоянном уровне, а не случайным.
Вы можете построить только посещенные комнаты, внедрив ленивую оценку. Может быть объект, который содержит комнату и не строит эту комнату до тех пор,
room()
пока к ней не призовут. Затем он просто возвращает один и тот же каждый раз после этого. Не сложно сделать.источник
Я научился делать это через книгу «Создание приключенческих игр на вашем компьютере». Если вы хотите разобраться с кодом BASIC (эта книга старая), прочитайте здесь:
http://www.atariarchives.org/adventure/chapter1.php
Для краткости, у них есть массив комнат, с элементом в каждом массиве, который является указателем на другую комнату, в которую вы можете перейти, с 0 (я бы использовал -1 в эти дни), чтобы указать, что вы не можете идти по этому пути. Например, вы сделали бы структуру комнаты (или класс, или что у вас есть)
Тогда у вас может быть массив или структура связанного списка, или вы хотите управлять своими комнатами. Для стиля массива (или векторов C ++) я бы использовал этот код, а в направлениях содержался бы индекс комнаты, на которую они ссылаются; для связанного списка, вы можете использовать указатели на следующую комнату.
Как уже говорили другие, если вам нужно динамически генерировать новые комнаты, когда люди входят в них, вы также можете сделать это.
источник
Не пытайтесь решить все проблемы с одной структурой.
Определите объект вашей комнаты, чтобы хранить вещи о комнате, а не ее связь с другими комнатами. Тогда одномерный массив, список и т. Д. Могут расти как вам угодно.
Отдельная структура может содержать «достижимость» - какие комнаты доступны из комнаты, в которой я нахожусь. Затем решите, должен ли переходной достижимость быть быстрым расчетом или нет. Вы могли бы хотеть вычисление грубой силы и тайник.
Избегайте ранней оптимизации. Используйте действительно простые структуры и простые понятные алгоритмы, а затем оптимизируйте те, которые используются.
источник