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

Question

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

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

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

Answer 1

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

Answer 2

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

Answer 3

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

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

Answer 4

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

Answer 5

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

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

Есть N начальных точек, и все они одинаковой длины.

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