Убедитесь, что лабиринт карты дома с лифтами можно решить?

13

В моей игре мы видим этажи дома со стороны, и герой может делать подъемы - подъемник либо поднимается вверх (до следующего подъема вверх), либо вниз (до следующего подъема вниз), в зависимости от стрелки как показано, и всегда есть пара ровно двух связанных лифтов. Это единственный способ, которым герой может двигаться вертикально, хотя он может свободно двигаться горизонтально. Карта дома представляет собой рандомизированную сетку 11x5 с различными предметами и непроходимыми стенами слева, справа и иногда в одной из двух средних позиций:

поднимает пример

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

Для чего это стоит, я использую язык Lua для разработки. Спасибо!

Филипп Ленсен
источник

Ответы:

14

То, что вы хотите сделать, - это создать График таким образом, чтобы каждый узел находился в положении лифта, а края между ними означают, что вы можете ходить / подниматься там. Как только вы создали график, вы можете использовать dfs / bfs, чтобы увидеть, можете ли вы добраться от начального узла до конечного узла.

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

узлы

Луис Эстрада
источник
Спасибо, это очень полезно! Я должен был больше подчеркнуть в своем вопросе, что карта также должна быть сгенерирована в первую очередь. Теперь я размышляю о том, что если не будет проще - вместо того, чтобы снова и снова генерировать полностью рандомизированные комбинации лифта / стены и проверять их разрешимость, - сделать так, чтобы алгоритм прошел по дому, как герой, и так генерировать случайные подъемы и двери (например, принимая случайные расстояния подъема и повороты влево-вправо, а также добавляя стены). Как и в «Пройдите направо на 0, 4 или 8 поворотов; создайте восходящий подъем, поднимитесь на 1–4 этажа ...»
Филипп Ленсен,
@PhilippLenssen Это, по сути, «рандомизированный поиск в глубину» для создания лабиринта на графе.
Кевин Рид
5

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

Кевин Рид
источник