Блог

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

У меня нет опыта работы с Python.

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

 def dimensions():
    height = int(input("Desired height: "))
    width = int(input("Desired width: "))

    res = (height, width)
    return res
  

В соответствии с правилами алгоритма я создаю пустой массив, окруженный стенами, с начальной и конечной точками, заданными:

 def create_array(height, width):
    maze = np.zeros((height, width), dtype = int)

    for i in range(height):
        maze[i][0] = 1
        maze[i][width - 1] = 1
    
    for i in range(width):
        maze[0][i] = 1
        maze[height - 1][i] = 1
        

    return maze

def set_start_end(start, height = 0, width = 0):
    if start == True:
        elems = [0,1]
        random.shuffle(elems)

    else:
        elems = [[height - 1, width - 2], [height - 2, width - 1]]
        elems = random.choice(elems)

    res = (elems[0], elems[1])

    return res
  

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

Следуя этому, я создал 3 вспомогательные функции:

 def choose_orientation(height, width):
    if width > height:
        return VERTICAL
    elif width < height:
        return HORIZONTAL
    else:
        return random.choice((VERTICAL, HORIZONTAL))

def set_wall(length):
    coor = int(length/2)

    if (coor % 2 != 0):
        coor  = random.choice([-1, 1])
    
    return coor

def set_door(length):
    coor = random.randrange(1, length - 1)

    if (coor % 2 == 0):
        coor  = random.choice([-1, 1])
    
    return coor
  

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

Мой основной рекурсивный цикл заключается в следующем:

 def divide(maze, x, y, height, width, resolution):
    h = height
    w = width

    if w <= resolution or h <= resolution:
        return

    orientation = choose_orientation(h, w)

    w_coor = 0
    w_length = 0
    d_coor = 0
    
    if orientation == HORIZONTAL:
        w_coor = set_wall(w)
        d_coor = set_door(w)

        w_length = w

        for i in range(w_length):
            maze[x   w_coor][i] = 1
        
        maze[w_coor][d_coor] = 0
    
        for elem in [[y, w_coor - y   1], [w_coor, y   h - w_coor - 1]]:
            divide(maze, x, elem[0], elem[1], w, resolution)

    else:
        w_coor = set_wall(h)
        d_coor = set_door(h)

        w_length = h
         
        for i in range(w_length):
            maze[i][y   w_coor] = 1
        
        maze[d_coor][w_coor] = 0

        for elem in [[x, w_coor - x   1], [w_coor, x   w - w_coor - 1]]:
            divide(maze, elem[0], y, h, elem[1], resolution)
  

И все же результат почему-то всегда напоминает следующее:

 [[1 5 1 1 1 1 1 1 1 1]
 [1 0 0 0 1 0 0 0 1 1]
 [1 1 1 0 1 0 0 0 1 1]
 [1 0 0 0 1 0 0 0 1 1]
 [1 0 1 1 1 1 1 1 1 1]
 [1 0 0 0 0 0 0 0 1 1]
 [1 0 0 0 0 0 0 0 0 1]
 [1 0 0 0 0 0 0 0 0 1]
 [1 1 1 1 1 1 0 0 0 1]
 [1 1 1 1 1 1 1 1 5 1]]
  

Я не смог обнаружить проблему и не знаю, что еще делать

Согласно ответу @ Stef, я переключил приведенные аргументы на set_wall и set_door , что дало мне немного лучший результат

 [[1 1 1 1 1 1 1 1 1 1]
 [5 0 1 0 1 0 1 0 1 1]
 [1 0 1 0 1 0 1 0 1 1]
 [1 0 0 0 0 0 1 0 1 1]
 [1 1 1 0 1 1 1 0 1 1]
 [1 0 0 0 0 0 1 0 1 1]
 [1 1 1 1 0 0 0 0 0 1]
 [1 0 0 0 0 0 0 0 0 1]
 [1 0 0 0 0 0 0 0 0 5]
 [1 1 1 1 1 1 1 1 1 1]]