#python #algorithm #recursion #maze
#python #алгоритм #рекурсия #Лабиринт
Вопрос:
В настоящее время я создаю генератор случайных лабиринтов на 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]]
Комментарии:
1. В
if orientation == HORIZONTAL
, я предполагаю,w_coor = set_wall(w); d_coor = set_door(w)
вместо этого должно бытьw_coor = set_wall(w); d_coor = set_door(h)
. И аналогично вelse
.2. Когда вам удастся исправить свой алгоритм, я предлагаю опубликовать ваш код на codereview.stackexchange.com поскольку есть много вещей, которые технически правильны, но могут быть написаны субъективно лучшим способом.