Оптимальный многопользовательский алгоритм генерации лабиринтов

Question

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

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

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

Answer 1

Альтернативой ответу freespace может быть создание случайного лабиринта, а затем присваивание каждой ячейке значения, представляющего количество ходов, чтобы достичь конца лабиринта (вы можете сделать оба сразу, если решите, что начинаете конец'). Затем выберите расстояние (возможно, самое высокое с n точками на этом расстоянии?) И разместите игроков на клетках с этим значением.

Answer 2

Как насчет того, чтобы сначала выбрать положение игроков, цель и путь равной длины, а затем построить лабиринт, соблюдая определенные пути? Если пути не пересекаются, это легко сработает, я полагаю

Answer 3

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

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

Answer 4

Выберите точку выхода где-то посередине

Начните с этого N путей, добавив 1 к каждому пути в цикле, пока они не станут такими, какими вы хотите, чтобы они были.

Есть ваши N начальных точек, и все они имеют одинаковую длину.

Добавляйте дополнительные ветви вне линий, пока лабиринт не заполнится.

Answer 5

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