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

Question

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

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

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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

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

Answer 5

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

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

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

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