Первоначальные проблемы
Хорошо, поэтому для начала вам обычно не нужно настраивать рекурсивную функцию, подобную этой. Поскольку вам нужно вызывать одну и ту же функцию снова и снова, вы не хотите заново создавать свой объект-лабиринт при каждом вызове. Вы хотите выполнить все настройки и вычисления вне рекурсивного вызова функции и выполнить только одну очень конкретную c рекурсивную работу.
Настройка
I ' Я предполагаю, что ваши настройки для класса лабиринта немного похожи на это:
import random
class Maze:
def __init__(self, width, height):
self.width = width // 2 * 2 + 1
self.height = height // 2 * 2 + 1
# this creates a 2d-array for your maze data (False: path, True: wall)
self.cells = [
[True for x in range(self.width)]
for y in range(self.height)
]
def set_path(self, x, y):
self.cells[y][x] = False
def set_wall(self, x, y):
self.cells[y][x] = True
Способы думать о нашем лабиринте
Хорошо, так что теперь я могу начать с самого рекурсивного генерирования. Теперь вместо того, чтобы подходить к добавлению стен, я вместо этого заполняю весь лабиринт стенами и «копаю» себе пути.
В нашем лабиринте, даже если мы рассматриваем его как простое включение / выключение 2d сетка со стенами и путями, полезно представить ее более похожей на серию узлов (узлов) и связей между ними. Я вижу, что вы начали реализовывать это так, как вы убедились, что ширина и высота вашего лабиринта были нечетными числами, например, с (Width // 2) * 2 + 1, и что вы выбрали только четные ячейки (хотя я не мог понять, для чего).
Вот краткая диаграмма для визуализации того, что я имею в виду:
Каждый красный круг - это узел, и, как вы можете видеть каждый нечетная плитка содержит узел , а всегда является плиткой пути. Мы будем автоматически предполагать, что каждая нечетная плитка будет содержать путь (и, следовательно, узел). Это означает, что при создании нашего лабиринта, когда мы «копаем» наш путь, мы будем перемещать две ячейки за раз, так что мы создадим связь между узлами (ячейки серого цвета).
Алгоритм
Суть алгоритма, который я буду реализовывать, будет следующей:
- Двигайтесь в случайных направлениях, "копая" мой путь вперед, следя за места, в которых я был
- Повторяю, пока не достигну тупика
- "Откат" через места, где я был, пока не найду путь хотя бы с одним жизнеспособным путем. Go до шага 1
Вот те же самые шаги, более подробно:
Перемещение в случайных направлениях, отслеживать, где я был
1.1. Мы смотрим вокруг каждого направления и видим, где находятся наши варианты перемещения
1.2. Выберите случайное направление, где есть правильный путь
1.3. Перейти к новому узлу (помните, мы движемся на две ячейки)
Повторяйте, пока я не достигну тупика
2.1. Продолжайте повторять процесс на первом шаге
2.2. Если во время первого шага вы не нашли вариантов пути, вы попали в тупик
Возврат через места, где я был
3.1. Следуйте по вашим стопам (backtrack) через ранее посещенные узлы
3.2. Повторяйте, пока не найдете узел с хотя бы одним непосещенным путем, чтобы попробовать
3.3. Go для первого шага (например, начните идти в произвольном направлении по новому пути)
Теперь, чтобы реализовать эти шаги с помощью рекурсивной функции , Каждый шаг к новому узлу (путем перемещения двух ячеек) будет новым вызовом функции с новыми координатами xy. Вот те же шаги, но рекурсивно:
Перемещение в случайных направлениях, отслеживая, где я был
1.1. Случайным образом выберите направление и убедитесь, что оно еще не посещено (например, если бы мы уже шли по нему, мы бы уже «покопались», чтобы это был путь). Поэтому выберите любое направление, которое является стеной (например, не посещено)
1.2. Теперь переместите две ячейки в этом направлении (но не забудьте установить для обеих ячеек узла и ячейку связи между двумя узлами на пути, иначе вы просто перепрыгнули через стену). Помните, что при «перемещении» в новую ячейку мы собираемся снова вызвать функцию с координатами xy нового узла
Повторять до достижения тупика
2.1. Если во время первого шага вы обнаружили, что все ваши направления содержат пути (например, вы уже посетили каждое направление в этом узле), вам необходимо откатить
2.2. Теперь, чтобы вернуться назад, мы собираемся выйти текущего вызова функции. Это означает, что мы перемещаем назад в предыдущую функцию, которая первоначально переместила нас в этот текущий узел
Возврат, пока вы не найдете путь
3.1 , После выхода из вызова функции вы теперь вернулись в предыдущий узел с предыдущими координатами xy. Теперь вы go делаете первый шаг, где вы ищите возможные направления, а если нет, вы go делаете второй шаг и возвращаетесь еще больше
Код
Итак, после завершения всей теории и планирования, мы можем теперь реализовать наш дизайн в коде.
Я собираюсь создать рекурсивную функцию как метод нашего класса Maze следующим образом:
class Maze:
# ...
# constructor and other methods go here
# ...
def create_maze(self, x, y):
# our recursive function goes here
Это означает, что для полного создания нашего лабиринта мы называем maze.create_maze(1, 1) (заменяя 1, 1 на ваши начальные координаты).
Итак, давайте пройдемся по каждому из шагов, которые мы разработали ранее, и превратить их в код.
1.1 Выбрать случайное, жизнеспособное направление
def create_maze(self, x, y):
# set the current cell to a path, so that we don't return here later
self.set_path(self, x, y)
# we create a list of directions (in a random order) we can try
all_directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
random.shuffle(all_directions)
# we keep trying the next direction in the list, until we have no directions left
while len(all_directions) > 0:
# we remove and return the last item in our directions list
direction_to_try = all_directions.pop()
# calculate the new node's coordinates using our random direction.
# we *2 as we are moving two cells in each direction to the next node
node_x = x + (direction_to_try[0] * 2)
node_y = y + (direction_to_try[1] * 2)
# check if the test node is a wall (eg it hasn't been visited)
if self.is_wall(node_x, node_y):
# success code: we have found a path
# failure code: we find no paths
# a function to return if the current cell is a wall, and if the cell is within the maze bounds
def is_wall(self, x, y):
# checks if the coordinates are within the maze grid
if 0 <= x < self.width and 0 <= y < self.height:
# if they are, then we can check if the cell is a wall
return self.cells[y][x]
# if the coordinates are not within the maze bounds, we don't want to go there
else:
return False
1.2. Переместите две ячейки в этом направлении и создайте ячейку пути ссылки
Итак, теперь вопрос в том, что нам делать, если мы нашли опцию приемлемого пути? Ответ: мы превращаем ячейку ссылки в путь (чтобы не перепрыгивать через стену в наш новый узел) и перемещаем две ячейки в нашем новом направлении.
Это становится:
# success code: we have found a path
# set our linking cell (between the two nodes we're moving from/to) to a path
link_cell_x = x + direction_to_try[0]
link_cell_y = y + direction_to_try[1]
self.set_path(link_cell_x, link_cell_y)
# "move" to our new node. remember we are calling the function every
# time we move, so we call it again but with the updated x and y coordinates
self.create_maze(node_x, node_y)
и затем для интеграции нашего кода успеха в нашу функцию create_maze он становится:
def create_maze(self, x, y):
self.set_path(x, y)
all_directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
random.shuffle(all_directions)
while len(all_directions) > 0:
direction_to_try = all_directions.pop()
node_x = x + (direction_to_try[0] * 2)
node_y = y + (direction_to_try[1] * 2)
if self.is_wall(node_x, node_y):
# success code: we have found a path
# set our linking cell (between the two nodes we're moving from/to) to a path
link_cell_x = x + direction_to_try[0]
link_cell_y = y + direction_to_try[1]
self.set_path(link_cell_x, link_cell_y)
# "move" to our new node. remember we are calling the function every
# time we move, so we call it again but with the updated x and y coordinates
self.create_maze(node_x, node_y)
# failure code: we find no paths
2.1. Если все наши направления содержат пути (они были посещены), то нам нужно вернуться
2.2. Чтобы вернуться назад, мы выходим из вызова функции, что приводит нас к предыдущему узлу
. Простой способ завершить функцию - это вызвать return. Это останавливает дальнейший запуск кода в функции и возвращает к предыдущей функции, которая его вызывала.
# failure code: we find no paths
return
И чтобы добавить это в нашу рекурсивную функцию, теперь она становится:
def create_maze(self, x, y):
self.set_path(x, y)
all_directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
random.shuffle(all_directions)
while len(all_directions) > 0:
direction_to_try = all_directions.pop()
node_x = x + (direction_to_try[0] * 2)
node_y = y + (direction_to_try[1] * 2)
if self.is_wall(node_x, node_y):
link_cell_x = x + direction_to_try[0]
link_cell_y = y + direction_to_try[1]
self.set_path(link_cell_x, link_cell_y)
self.create_maze(node_x, node_y)
# failure code: we find no paths
return
3.1. Попробуйте еще раз шаг один, если не go, то шаг второй
По сути, мы сейчас запрограммировали полнофункциональную программу генерации лабиринтов, используя (насколько мне известно) довольно хороший рекурсивный метод. Как только функция попадает в тупик, она вернется, вернется к предыдущей функции и продолжит процесс, пока эта функция не зайдет в тупик и т. Д. c ..
Окончательный код
import random
class Maze:
def __init__(self, width, height):
self.width = width // 2 * 2 + 1
self.height = height // 2 * 2 + 1
# this creates a 2d-array for your maze data (False: path, True: wall)
self.cells = [
[True for x in range(self.width)]
for y in range(self.height)
]
def set_path(self, x, y):
self.cells[y][x] = False
def set_wall(self, x, y):
self.cells[y][x] = True
# a function to return if the current cell is a wall,
# and if the cell is within the maze bounds
def is_wall(self, x, y):
# checks if the coordinates are within the maze grid
if 0 <= x < self.width and 0 <= y < self.height:
# if they are, then we can check if the cell is a wall
return self.cells[y][x]
# if the coordinates are not within the maze bounds, we don't want to go there
else:
return False
def create_maze(self, x, y):
# set the current cell to a path, so that we don't return here later
self.set_path(x, y)
# we create a list of directions (in a random order) we can try
all_directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
random.shuffle(all_directions)
# we keep trying the next direction in the list, until we have no directions left
while len(all_directions) > 0:
# we remove and return the last item in our directions list
direction_to_try = all_directions.pop()
# calculate the new node's coordinates using our random direction.
# we *2 as we are moving two cells in each direction to the next node
node_x = x + (direction_to_try[0] * 2)
node_y = y + (direction_to_try[1] * 2)
# check if the test node is a wall (eg it hasn't been visited)
if self.is_wall(node_x, node_y):
# success code: we have found a path
# set our linking cell (between the two nodes we're moving from/to) to a path
link_cell_x = x + direction_to_try[0]
link_cell_y = y + direction_to_try[1]
self.set_path(link_cell_x, link_cell_y)
# "move" to our new node. remember we are calling the function every
# time we move, so we call it again but with the updated x and y coordinates
self.create_maze(node_x, node_y)
return
И вот мы go! Рекурсивный алгоритм создания лабиринта. Извините, что я не использовал больше вашего кода, но так как я не был совершенно уверен, куда вы идете с этим, я подумал, что мог бы по крайней мере помочь, показывая вам некоторый рабочий код.
Последнее, что мы Можно быстро добавить это функция печати, так что мы можем распечатать наш лабиринт на экран. Используя «метод двойного подчеркивания» (dundermethod) __repr__ ( update: вместо этого используйте имя метода __str__, см. Комментарии), мы можем перезаписать функциональность print. Следующий код генерирует строку, представляющую наш недавно сгенерированный лабиринт:
def __repr__(self):
string = ""
conv = {
True: "██",
False: " "
}
for y in range(self.height):
for x in range(self.width):
string += conv[self.cells[y][x]]
string += "\n"
return string
Поместив это в класс лабиринта, мы можем теперь выполнить следующее, и оно даже работает, начиная с четных ячеек!
>>> maze.create_maze(1, 1)
>>> print(maze)
██████████████████
██ ██ ██
██████ ██ ██ ██
██ ██ ██ ██ ██
██ ██ ██████ ██
██ ██ ██
██ ██████████ ██
██ ██
██████████████████
>>> maze.create_maze(4, 4)
██
██████ ██████
██
██████████████
██ ██
██ ██████████
██ ██
██████████ ██
██
Надеюсь, это помогло!