[Обновил мои вопросы в конце]
Я создаю многопользовательскую RTS-игру, которая происходит внутри лабиринта. Я использовал алгоритм Growing Tree для случайного создания лабиринта. Я думал, что лабиринт будет справедливым для каждой команды, если кратчайший путь каждой команды к решению лабиринта равен другой команде. Я убедился в этом, разработав в своей игре правило, согласно которому стартовая точка каждой команды является конечной точкой другой команды, и наоборот, поэтому кратчайший путь всегда будет одинаковым для обеих команд. но на практике я заметил кое-что еще.
этот вопрос возник у меня, когда я пытался превратить получающийся в результате идеальный лабиринт в неидеальный лабиринт, используя это решение , в частности, ответ @ tobias-k.
, если у вас уже есть лабиринт с одной формой пути от начала до цели, используйте этот вариант:
Выполните поиск в ширину как с начала, так и с цели, и для каждой ячейки в лабиринте запишите количество шагов, которое эта ячейка прошла
как с самого начала, так и с цели.
Разделите лабиринт, поместив все ячейки, которые находятся ближе к началу, в стартовый набор и все ячейки, которые ближе к цели
в поставленной цели.
Удалите стену между двумя регионами, чтобы добавить дополнительный путь от начала до цели.
Сгенерированные пути могут иметь (возможно, даже существенные) части в
общие, но они должны быть уникальными без петель пути от начала до цели.
Вот иллюстрация первого случая:
результат разделения лабиринта в соответствии с расстоянием каждой ячейки
от начальной или конечной точки
Однако, когда я использую BFS для вычисления всех расстояний от моей начальной и конечной точки, и перед удалением стены для создания неидеального лабиринта, я в основном получаю что-то вроде этого:
на этой картинке 336 ячеек ближе к начальной точке команды Red и только 105 ближе к начальной точке команды Blue.
Даже удаление стены (или более чем одной стены) между этими двумя секциями не помогает ситуации.
Моя игра состоит в том, чтобы собирать сокровища, которые случайным образом распределяются по лабиринту, и выходить из него до того, как другая команда выйдет из лабиринта. Эти лабиринты совершенно несправедливы, поскольку дают одной команде больший шанс достичь большего количества сокровищ в лабиринте раньше. по сравнению с другой командой.
так что мои предложения:
- Означает ли упомянутые результаты генерации растущего лабиринта деревьев, что лабиринт не справедлив для многопользовательской игры (для простоты давайте просто представим, что игра происходит между двумя игроками)?
- Нужно ли мне менять генератор лабиринта на что-то, что создает однородную текстуру, например алгоритм Уилсона или Олдос-Бродера? (это основано на алгоритмах, введенных Astrolog )
- @ btilly предлагает использовать симметричный лабиринт для решения проблемы справедливости лабиринта, но теперь я должен спросить , какой из них гарантирует создание справедливого случайного лабиринта: симметричный подход ( как тот предложенный в этой статье или унифицированный (например, алгоритм Вильсона )?