Алгоритм самого длинного пути для генерации лабиринтов

10

У меня есть простая сеточная карта, состоящая из комнат, например: (A = вход, B = выход):

   0 1 2 3
  #########
0 # B # #####
  #########
1 # ### #
  #########
2 # # #
  # # #
3 # # #
  #########
4 # ### #
  #########
5 ### A #
  ### #
6 ### #
  #########

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

Другими словами, я пытаюсь найти самый длинный возможный путь от А до В .

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

РЕДАКТИРОВАТЬ: Другой пример, где комнаты соединены с помощью заливки, и выход выбран в качестве самой дальней комнаты от входа:

   0 1 2 3
  #########
0 # B # #
  # # - #####
1 # | # #
  ### # #
2 ### # #
  ### - # - ###
3 # | ###
  # - #######
4 #A | #
  # # #
5 # # #
  # # #
6 # # #
  #########

Обратите внимание, что путь к выходу - это не самый длинный путь.

Пользователь не найден
источник
Если вы заставляете игрока идти по максимально длинному пути, вы фактически строите прямой путь, который притворяется сложным. Это плохо.
о0 '.
Это неплохо (например, это основа жанра железнодорожных шутеров), но вы должны знать, что вы делаете это, и разрабатывать остальную часть своей игры, чтобы хорошо с ней работать.
Также легче контролировать темп игры, когда уровни в основном линейные. Это позволяет добавить, например, комнату восстановления после особенно сложной комнаты монстров. Если бы не было основного пути, распределение задач и наград было бы случайным.
Пользователь не найден

Ответы:

11

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

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

Так что, дайте шанс игроку найти выход, пропорциональный проценту карты, которая была исследована до сих пор . Скажем, на уровне есть X комнат, и персонаж игрока исследовал Y. В следующий раз, когда персонаж войдет в комнату, разместите выход там с вероятностью f (Y, X). Тривиальным примером f может быть (Y * Y) / (X * X) - например, для 10 комнат 100% -ный шанс выхода в последнюю комнату, 81% -ый шанс, что он находится рядом с последней комнатой - и только 1% шанс, что это в первой комнате.

Вы можете настроить уравнение так, как вы хотите, чтобы игра выглядела правильно, и, возможно, даже дать игроку некоторые возможности, чтобы сделать его более вероятным. Ключевая часть: не генерируйте выход, пока персонаж действительно не войдет в комнату. Этот метод также невосприимчив к знаниям игрока об алгоритме генерации подземелий; даже если у игрока есть странные модели движения, такие как прыжок коня в NetHack или телепортация, ему придется исследовать больше комнат, чтобы найти выход.

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

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


источник
Динамическая генерация кажется довольно хорошей идеей, если игрок этого не замечает. В противном случае я думаю, что они чувствовали бы себя довольно обманутыми. Мне нравится идея затопления.
Пользователь не найден
2
Ну, все ваше предложение в некотором смысле обманывает игрока. Не обвиняйте меня в том, что я улучшил математику, чтобы не требовать модели мира. ;) Но вы можете использовать конструктивные приемы, чтобы сделать его более привлекательным - например, выход помещается априори, но ключ, необходимый для его использования, генерируется в методе, который я описал, или помещается в монстра, который появляется только после изучения X комнаты / убийство X монстров или открытие двери требует щелчка переключателями X, по одному в каждой комнате и т. д.
Я попробовал подход к заливке. Он хорошо соединяет каждую комнату и создает короткие ветви, но на самом деле не дает максимально длинного пути к выходу, даже если выход является последним посещенным узлом (или, в моей реализации, самым дальним). (пример добавлен в мой вопрос)
Пользователь не найден
Я все для лабиринтов на основе ключей / переключателей, хотя. Кажется, проще реализовать такие вещи с деревьями, потому что тогда, если у вас есть две ветви, вы можете определить, какая ветвь ведет к выходу, заблокировать ее и поместить ключ в другую ветку.
Пользователь не найден
Но я признаю, что ошибался, думая, что это была проблема поиска пути от А до Б. Я понимаю, что имеет больше смысла находить выход как результат алгоритма, а не как цель.
Пользователь не найден
6

Возможной альтернативой было бы создание (максимального?) Связующего дерева с использованием Prim / Kruskal (чтобы исключить циклы) и применение традиционного алгоритма самого длинного пути к остовному дереву.

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

РЕДАКТИРОВАТЬ: Результат использования алгоритма на основе Крускала и размещения выхода в конце самой длинной ветви:

   0 1 2 3
  #########
0 #A | #
  # ##### - #
1 # # #
  ### #
2 ### #
  ### #
3 ### #
  ### - #####
4 # | #
  # - ##### - #
5 # ### #
  # - #######
6 # # B #
  # # - #
7 # | #
  #########
Пользователь не найден
источник
1
Я тоже собирался предложить Primm :-), +1, я думаю, что возврат также является важной частью многих игр ... проверьте
Diablo
2

Вот что поиграть:

Connect each room with a door to another room.
N = 0.75*TotalNumberOfRooms
Until (pathSize > N) {
  Use A* pathing to get a path from A to B. (G being size of room, or # of monsters)
  if (pathSize < N) remove a connection/door
  if (noPath) choose a different door/connection
  if (room.doors < 1) choose a different door/connection
}

Я бы случайно убрал двери вдоль пути, иначе у вас будет 1 дверь на выходе и тонны дверей на старте.

Я думаю, что это O(n^2)не очень хорошо для больших карт.

Стивен Фурлани
источник
Очень элегантное решение в принципе. В следующий раз я должен попытаться придумать что-то подобное, прежде чем переходить к запутанным методам.
Пользователь не найден
Ну, может быть, элегантно, но это будет процессорный боров. O (n ^ 2) не будет хорошо масштабироваться с большими картами.
Стивен Фурлани
1

Я полагаю, что у вас уже есть отличные ответы, но вот мое теоретическое решение проблемы за 0,02 доллара.

То, что вы хотите, это НЕ самый длинный путь, но самый длинный самый короткий путь. Вам нужна самая дальняя комната, учитывая, что вы рассматриваете кратчайший путь к комнате. Это, вероятно, звучит запутанно, но это очень легко рассчитать.

  1. Начните с вашей стартовой комнаты. Отметьте каждого из его соседей 1. Они находятся на расстоянии 1 от начальной комнаты.
  2. Для каждой комнаты, отмеченной 1, посетите каждого из ее НЕПРАВИЛЬНЫХ соседей и отметьте их 2. Они находятся на расстоянии 2 от начала.
  3. Продолжайте, пока вы не охватите все комнаты. Комната с максимальным количеством находится дальше всего от начала.

Вычисление фактического самого длинного пути (не займет слишком много времени, скажем, для 10 комнат) не будет работать, потому что вы не можете заставить игрока выбрать этот самый длинный путь. Поэтому лучше всего размещать вход и выход в двух комнатах, наиболее удаленных друг от друга. Чтобы найти это, рассчитайте самую дальнюю комнату из случайной комнаты. Затем из этой комнаты найдите самую дальнюю комнату. Это называется поиск диаметра графика, пожалуйста, Google его.

Сид Датта
источник