Создание "жесткого" лабиринта с использованием алгоритма Прима

Question

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

Экстрим № 1 - это совершенно случайный выбор ячеек в списке потенциальных проходов, в котором каждая ветвь развивается примерно одинаковыми темпами. У этого есть много различных ветвей, но как только вы доберетесь до места происхождения, вы можете в значительной степени следовать по прямой линии к желаемому месту. Вот изображение, показывающее этот подход:

Extreme # 2 - это место, где выбирается последняя вещь, добавленная в список, создавая длинный, утомительный и легкий лабиринт. Он формируется, когда вы выбираете только последний элемент, помещенный в список потенциальных проходов. Вот изображение, показывающее этот подход:

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

Самый интересный способ попытаться сделать это, когда я пытался получить 50% -ный шанс на добавление последнего блока, который будет размещен, затем 50-процентный шанс на следующий, если этот блок не удался, и так далее. Однако я все испортил и попытался сначала сделать индекс [-0], делая 50% вероятности добавления первого блока, затем последнего, второго последнего и так далее. Это создало интересный лабиринт, но когда я "починил" его, лабиринт был похож на второй край.

Другой подход, который я попробовал, - тот, который используется в моем коде:

for i in range(1, len(potential_passage_list) + 1):
        if randint(0, int(len(passage_list) / 50)) == 0:
            maze_passage(potential_passage_list[-i][0], potential_passage_list[-i][1])

Это было сделано для того, чтобы попытаться разместить разумный блок, добавленный в потенциально-пассивный_список ранее.

Итак, мой вопрос, как вы можете создать "жесткий" лабиринт, содержащий множество ответвлений, но непредсказуемый шаблон? Какие алгоритмы могут быть использованы для этого?

Я использую Python 3 и библиотеку Pygame, чтобы отобразить все.

Вот мой код, если вы можете понять это:

import pygame
from random import shuffle, randint

# variables
######
# changeable variables
cell_size = 7  # cannot be less than 3
maze_length = 160 * cell_size + 1
maze_height = 100 * cell_size + 1
######

# colours
black = (0, 0, 0)
white = (245, 245, 245)
red = (255, 0, 0)
blue = (0, 0, 255)

# other variables
passage_list = []
potential_passage_list = []
impossible_passage = []
random_cell = []
done = False

# initialize pygame and display screen
pygame.init()
screen = pygame.display.set_mode((maze_length, maze_height))
pygame.display.flip()


def one_connection(cell_x, cell_y):
    # ensure that it will only touch one passage
    count = 0

    if [cell_x + cell_size, cell_y] in passage_list:
        count += 1
    if [cell_x - cell_size, cell_y] in passage_list:
        count += 1
    if [cell_x, cell_y + cell_size] in passage_list:
        count += 1
    if [cell_x, cell_y - cell_size] in passage_list:
        count += 1

    if count <= 1:
        return True
    else:
        return False


def valid_cell(cell_x, cell_y):
    # check if already in potential_passage_list
    if [cell_x, cell_y] in potential_passage_list:
        impossible_passage.append([cell_x, cell_y])
    # check if in impossible list
    elif [cell_x, cell_y] in impossible_passage:
        impossible_passage.append([cell_x, cell_y])
    # check if out of boundary
    elif cell_x < 0 or cell_x >= maze_length - cell_size or cell_y < 0 or cell_y >= maze_height - cell_size:
        impossible_passage.append([cell_x, cell_y])
    # ensure that it will only touch one passage
    elif not one_connection(cell_x, cell_y):
        impossible_passage.append([cell_x, cell_y])
    # check if it isolates any walls / cut off unconnected corners
    elif (([cell_x + cell_size, cell_y + cell_size] in passage_list and [cell_x + cell_size, cell_y] not in
           passage_list and [cell_x, cell_y + cell_size] not in passage_list) or
          ([cell_x + cell_size, cell_y - cell_size] in passage_list and [cell_x + cell_size, cell_y] not in
           passage_list and [cell_x, cell_y - cell_size] not in passage_list) or
          ([cell_x - cell_size, cell_y + cell_size] in passage_list and [cell_x - cell_size, cell_y] not in
           passage_list and [cell_x, cell_y + cell_size] not in passage_list) or
          ([cell_x - cell_size, cell_y - cell_size] in passage_list and [cell_x - cell_size, cell_y] not in
           passage_list and [cell_x, cell_y - cell_size] not in passage_list)):

        impossible_passage.append([cell_x, cell_y])
    # check if already in passage_list
    elif [cell_x, cell_y] not in passage_list:
        return True


# functions
def maze_passage(cell_x, cell_y):
    # reset block_passage_list
    block_passage_list = []

    # remove from list so it does not interfere with valid_cell procedure
    potential_passage_list.remove([cell_x, cell_y])
    if valid_cell(cell_x, cell_y):
        # display rectangle
        pygame.draw.rect(screen, white, [cell_x, cell_y, cell_size, cell_size])
        pygame.display.update()

        passage_list.append([cell_x, cell_y])

        # add valid walls to block_passage_list
        if valid_cell(cell_x + cell_size, cell_y):
            block_passage_list.append([cell_x + cell_size, cell_y])
        if valid_cell(cell_x - cell_size, cell_y):
            block_passage_list.append([cell_x - cell_size, cell_y])
        if valid_cell(cell_x, cell_y + cell_size):
            block_passage_list.append([cell_x, cell_y + cell_size])
        if valid_cell(cell_x, cell_y - cell_size):
            block_passage_list.append([cell_x, cell_y - cell_size])

        shuffle(block_passage_list)

        for j in block_passage_list:
            potential_passage_list.append(j)


# create initial cell
start_cell = [randint(0, int(maze_height / cell_size))*cell_size, randint(0, int(maze_height / cell_size))*cell_size]
potential_passage_list.append([start_cell[0], start_cell[1]])


# loop for creating maze
while not done:
    for event in pygame.event.get():
        # exit screen when exit pressed in pygame
        if event.type == pygame.QUIT:
            done = True

    # select cell
    for i in range(1, len(potential_passage_list) + 1):
        if randint(0, int(len(passage_list) / 50)) == 0:
            maze_passage(potential_passage_list[-i][0], potential_passage_list[-i][1])
            break

    # check if maze completion finished
    if not potential_passage_list:
        # create start and end
        passage_list.sort()
        pygame.draw.rect(screen, red, [passage_list[0][0] + 1, passage_list[0][1] + 1, cell_size - 2, cell_size - 2])
        pygame.draw.rect(screen, blue, [passage_list[-1][0] + 1, passage_list[-1][1] + 1, cell_size - 2, cell_size - 2])
        pygame.display.update()

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

Спасибо!

Answer 1

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

Это позволяет создавать лабиринты с различными характеристиками. Вы можете попробовать демо здесь: https://mtimmerm.github.io/webStuff/maze.html

Если вы предпочитаете варианты, которые расширяют существующие пути (ползунок 1, 2 и 3), это усложнит лабиринты.