В этой директории хранится курсовая работа по дисциплине "Высокоуровневый язык программирования Python"
Используемые модули: pygame, time, random
Время разработки: ноябрь - декабрь 2019
Установим следующее правило для определения стартовой точки генерации лабиринта. Пусть ширина лабиринта равна m, а высота n, а OX и OY оси координат. При этом нумерация клеток лабиринта начинается с нуля, и клетка с координатами (0, 0) находится в левом верхнем углу. Начальная точка нашего лабиринта должна находится с краю, т. е. одна из координат должна равняться либо нулю, либо координата x=n-1, либо y=m-1 соответственно (см. Рис. 1.1)
Рис. 1. 1. – Координаты матрицы лабиринта и место генерации начальной точки.
После того, как мы определили точку начала нашего лабиринта, можно приступить к генерации самого лабиринта. При генерации мы должны соблюдать некоторые правила:
- Лабиринт не должен иметь циклов, т. е. к каждой клетке лабиринта существует только единственный путь.
- В лабиринте должны отсутствовать замкнутые области, к каждой клетке мы должны иметь доступ.
Из начальной точки программа должна найти все доступные пути перехода. Затем мы «переходим» в клетку, которую мы выберем из доступных. При переходе мы будем отмечать, в каких клетках мы уже побывали. И тогда эти клетки уже не будут доступны, как варианты перехода. Так мы исключаем циклы. Выбор будет происходить случайным образом, это как раз и сделает лабиринт запутанным и непредсказуемым. В ходе выполнения алгоритма может наступить момент, когда у нас не будет доступных вариантов для перехода (см. рис. 1.2). Тогда мы вернёмся обратно туда, откуда пришли в эту клетку и проверим, есть ли из этой клетки варианты для перехода. Если да, то переходим по этому варианту (если вариантов несколько, выбираем случайным образом один из вариантов). Так образуется разветвление лабиринта. Если же мы и в этой клетке, не нашли вариантов для перехода, то тогда возвращаемся в клетку, из которой мы пришли в текущую клетку и так до тех пор, пока мы не найдём вариант для перехода.
Рис. 1. 2. – Механизм образования разветвлений лабиринта.
И только лишь когда все летки заняты, мы останавливаем работу алгоритма и считаем, что лабиринт полностью сгенерирован. Так мы исключаем замкнутые области (см. рис. 1.3.).
Рис. 1. 3. – Обход всех клеток матрицы.
Для хранения информации о переходах и о клетках, которые мы уже посещали создадим две таблицы – таблицу переходов и таблицу достижимости.
Конечная точка лабиринта в программе определяется простым способом по формуле (n-1-x_(нач.); m-1- y_(нач.)), n и m – ширина и высота лабиринта, а x_(нач.) и y_(нач.) – координаты точки начала лабиринта. Благодаря такой генерации конечной точки лабиринта, она будет располагаться на противоположной стороне от точки начала, что увеличит путь при прохождении лабиринта, а значит сделает его интереснее.
Однако у такого расположения начальной и конечной точки также есть свой определённый недостаток. В случае, когда высота или ширина лабиринта будет являться нечётным числом, начальная и конечная точки могут быть сгенерированы на одной линии в центре (см. рис. 1.4). В таком случае мы заново генерируем лабиринт.
Рис. 1. 4. – Вариант генерации простого лабиринта.
Создадим вспомогательные функции генерации точек начала и конца лабиринта start_point_generate и finish_point_generate, которые будут принимать ширину и высоту лабиринта и возвращать координаты начальной и конечной точки согласно алгоритму, который был описан выше (см. листинг 2. 1).
Листинг 2.1. – Функции генерации начальной и конечной точки лабиринта
def start_point_generate(n, m):
"""Функция выбора точки начала лабиринта"""
if random.choice([True, False]):
if random.choice([True, False]):
start = (0, random.randint(0, m - 1))
else:
start = (n - 1, random.randint(0, m - 1))
else:
if random.choice([True, False]):
start = (random.randint(0, n - 1), 0)
else:
start = (random.randint(0, n - 1), m - 1)
return start
def finish_point_generate(start, n, m):
"""Выбор точки конца лабиринта"""
return n - 1 - start[0], m - 1 - start[1]
С помощью функций из модуля random случайным образом определяется с какой стороны будет точка начала, а затем также случайным образом определяется вторая координата.
Далее нам нужно описать процесс самой генерации лабиринта. Нам понадобится вспомогательная функция transition_choice (см. листинг 2.2), которая будет определять клетку, в которую мы перейдём далее. Создаётся список, в который мы будем добавлять доступные вокруг текущей клетки соседние клетки, а потом по порядку проверяется были ли мы в конкретной из соседних клеток. Если нет, то координаты этой клетки мы добавляем в список. Когда все соседние клетки будут проверены, мы проверяем список доступных для перехода соседей на наличие в нём хотя бы одного элемента. Если список непустой, случайным образом выбирается один из элементов списка. Это и будут координаты следующей для перехода точки. Пересчитаем эти координаты для матрицы переходов (подробнее о матрице переходов я расскажу далее). Если список окажется пустым, функция вернёт несуществующие координаты, чтобы далее мы смогли обработать возврат в клетку из которой мы пришли.
Листинг 2.2. – Функция выбора дальнейшего пути в генерации лабиринта.
def transition_choice(x, y, rm):
"""Функция выбора дальнейшего пути в генерации лабиринта"""
choice_list = []
if x > 0:
if not rm[x - 1][y]:
choice_list.append((x - 1, y))
if x < len(rm) - 1:
if not rm[x + 1][y]:
choice_list.append((x + 1, y))
if y > 0:
if not rm[x][y - 1]:
choice_list.append((x, y - 1))
if y < len(rm[0]) - 1:
if not rm[x][y + 1]:
choice_list.append((x, y + 1))
if choice_list:
nx, ny = random.choice(choice_list)
if x == nx:
if ny > y:
tx, ty = x * 2, ny * 2 - 1
else:
tx, ty = x * 2, ny * 2 + 1
else:
if nx > x:
tx, ty = nx * 2 - 1, y * 2
else:
tx, ty = nx * 2 + 1, y * 2
return nx, ny, tx, ty
else:
return -1, -1, -1, -1
В основной функции (см. листинг 2.3.), которая и будет генерировать лабиринт, мы будем использовать матрицу достижимости, чтобы сохранить информацию о том в каких точках мы уже были, а в каких нет; матрицу переходов, хранящую информацию о расположении стенок в лабиринте; маршрут пройденного пути в виде списка, чтобы мы в случае необходимости вернуться в клетку из которой пришли. На рис. 2.1. показано, как будут заполнятся матрицы переходов и достижимости в процессе работы программы (0 и 1 – значения True и False).
Рис. 2. 1. – Изменения матриц достижимости и переходов в ходе генерации лабиринта
Для начала мы сгенерируем начальную точку, которая и будет первым элементом в маршрутном списке. Далее с помощью функции transition_choice определяем клетку, в которую произойдёт переход. Если такой клетки нет, удаляем текущее положение из маршрутного списка и переходим назад до тех пор, пока не найдём, куда перейти (здесь хорошо подошёл цикл while). Функция генерации возвращает координаты точки начала и конца лабиринта и матрицу переходов, c помощью которой мы далее сможем изобразить лабиринт не полотне.
Листинг 2.3. – Функция генерации лабиринта.
def create_labyrinth(n=5, m=5):
"""Генерация лабиринта"""
reach_matrix = []
for i in range(n): # создаём матрицу достижимости ячеек
reach_matrix.append([])
for j in range(m):
reach_matrix[i].append(False)
transition_matrix = []
for i in range(n * 2 - 1): # заполнение матрицы переходов
transition_matrix.append([])
for j in range(m * 2 - 1):
if i % 2 == 0 and j % 2 == 0:
transition_matrix[i].append(True)
else:
transition_matrix[i].append(False)
start = start_point_generate(n, m)
finish = finish_point_generate(start, n, m)
list_transition = [start]
x, y = start
reach_matrix[x][y] = True
x, y, tx, ty = transition_choice(x, y, reach_matrix)
for i in range(1, m * n):
while not (x >= 0 and y >= 0):
x, y = list_transition[-1]
list_transition.pop()
x, y, tx, ty = transition_choice(x, y, reach_matrix)
reach_matrix[x][y] = True
list_transition.append((x, y))
transition_matrix[tx][ty] = True
x, y, tx, ty = transition_choice(x, y, reach_matrix)
return transition_matrix, start, finish # возвращаем матрицу проходов,начальную и конечную точку
Для создания графического интерфейса я использовал Pygame. Pygame – это библиотека модулей для языка Python, созданная для разработки 2D игр. Также Pygame могут называть фреймворком. В программировании понятия "библиотека" и "фреймворк" несколько разные. Но когда дело касается классификации конкретного инструмента, не все так однозначно.
В любом случае, фреймворк является более мощным по-сравнению с библиотекой, он накладывает свою специфику на особенности программирования и сферу использования продукта. С точки зрения специфики Pygame – это фреймворк. Однако его сложно назвать "мощным инструментом". По своему объему и функционалу это скорее библиотека.
Также существует понятие "игрового движка" как программной среды для разработки игр. По своему назначению Pygame можно считать игровым движком. В то же время, с точки зрения классификации программного обеспечения, Pygame является API для Питона к API библиотеки SDL.
API – это интерфейс (в основном набор функций и классов) для прикладного (часто более высокоуровневого) программирования, который предоставляет, например, та или иная библиотека. SDL – это библиотека, которая работает с мультимедийными устройствами компьютера.
В чём преимущество Pygame? Оно в легком вхождении в отрасль и прототипировании. Pygame – небольшая библиотека. Сам Python позволяет писать короткий и ясный код. Так что это хорошее начало, чтобы познакомиться с особенностями разработки игр. Более опытными программистами Pygame может использоваться для быстрого создания прототипа игры, чтобы посмотреть, как все будет работать. После этого программа переписывается на другом языке. Другими словами, преимущество Pygame в легком обучении и быстрой разработке.
Для того, чтобы изобразить на полотне лабиринт я создал специальную функцию draw_labyrinth (см. листинг 2. 4). Функция принимает следующие значения:
- Матрицу переходов
- Координаты начала
- Координаты конца
- Толщина проходов
- Толщина стен
- Цвет проходов (картеж из 3-ёх элементов)
- Цвет стен (картеж из 3-ёх элементов)
- Толщина границ вокруг лабиринта
- Цвет точки начала
- Цвет точки конца
Листинг 2.4. – Функция рисования лабиринта
def draw_labyrinth(matrix, start, finish, width_line=20, width_walls=5, color_way=(255, 255, 255),
color_wall=(0, 0, 0),
border=5, color_start=(0, 255, 0), color_finish=(255, 0, 0)):
"""Рисование лабиринта"""
width = (len(matrix) // 2 + 1) * width_line + (len(matrix) // 2) * width_walls + border * 2
height = (len(matrix[0]) // 2 + 1) * width_line + (len(matrix[0]) // 2) * width_walls + border * 2
for i in range(width):
for j in range(height):
if i < border or width - i <= border or j < border or height - j <= border: # отображение границ лабиринта
pygame.draw.line(window, color_wall, [i, j], [i, j], 1)
else:
if (i - border) % (width_line + width_walls) <= width_line:
x = (i - border) // (width_line + width_walls) * 2
else:
x = (i - border) // (width_line + width_walls) * 2 + 1
if (j - border) % (width_line + width_walls) <= width_line:
y = (j - border) // (width_line + width_walls) * 2
else:
y = (j - border) // (width_line + width_walls) * 2 + 1
if matrix[x][y]:
pygame.draw.line(window, color_way, [i, j], [i, j], 1)
else:
pygame.draw.line(window, color_wall, [i, j], [i, j], 1)
pygame.draw.rect(window, color_start, (
border + start[0] * (width_line + width_walls), border + start[1] * (width_line + width_walls), width_line,
width_line))
pygame.draw.rect(window, color_finish, (
border + finish[0] * (width_line + width_walls), border + finish[1] * (width_line + width_walls), width_line,
width_line))
Сначала мы определяем размер изображения, которое должно получаться в результате рисования, а затем проходим по каждому пикселю и закрашиваем его в нужный нам цвет в зависимости от координаты точки. Мы проверяем, является эта точка проходом, стеной или рамкой лабиринта. А в самом конце закрашиваем точки начала и конца в необходимый нам цвет. В результате работы этой функции мы получаем изображение случайно сгенерированного лабиринта (рис. 2. 2.), на котором в дальнейшем можно создать игрока с возможностью перемещения его по полю.
Рис. 2. 2. – Графический интерфейс программы
Создадим игрока, который будет перемещаться по лабиринту, когда пользователь будет нажимать определённые клавиши на клавиатуре. Каждый основной игровой цикл мы будем проверять, были ли нажаты клавиши и в зависимости от это выполнять или не выполнять определённые действия.
Для того, чтобы изобразить игрока на поле лабиринта используем функцию draw_player (см. листинг 2.5).
После перемещения игрока необходимо удалить его старое положение. Для этого я использую функцию delete_player (см. листинг 2.5.). Затем снова нарисуем игрока, но уже на другом месте. В программе я предусмотрел оставление меток в лабиринте, чтобы игрок понимал, где он уже проходил. Эту возможность можно подключить при нажатии на определённую клавишу на клавиатуре.
Также программа может подсчитывать количество пройденных лабиринтов, время, затраченное на прохождение лабиринта, а также может сохранять и рекордное время прохождения лабиринта. Все эта информация выводится на информационное табло внизу экрана. Чтобы работать с временем, мне понадобился модуль time.
Листинг 2.5. – Функции изображения игрока на полотне и его удаления.
def draw_player():
"""Отрисовка игрока на экране"""
pygame.draw.circle(window, color_player, (border + player[0] * (width_line + width_walls) + width_line // 2,
border + player[1] * (width_line + width_walls) + width_line // 2),
width_line // 2 - 3)
def delete_player():
"""Функция удаления игрока при движении и оставления следов"""
if (player[0], player[1]) == start:
pygame.draw.circle(window, color_start, (border + player[0] * (width_line + width_walls) + width_line // 2,
border + player[1] * (width_line + width_walls) + width_line // 2),
width_line // 2 - 3)
else:
pygame.draw.circle(window, color_way, (border + player[0] * (width_line + width_walls) + width_line // 2,
border + player[1] * (width_line + width_walls) + width_line // 2),
width_line // 2 - 3)
if trace:
pygame.draw.circle(window, color_trace, (border + player[0] * (width_line + width_walls) + width_line // 2,
border + player[1] * (width_line + width_walls) + width_line // 2),
width_line // 3 - 3)
Ещё предусмотрена возможность минимизации повторений лабиринта. Все лабиринты сохраняются в список и при каждой новой генерации происходит проверка на наличие вновь сгенерированного лабиринта на наличие в списке лабиринтов, которые уже были сгенерированы ранее. Если сгенерированный лабиринта найден в списке, генерация происходит повторно, если подряд прошло 20 повторных генераций программа начинает выдавать лабиринты с прямым проходом, т. е. те лабиринты в которых точка начала находится на одной линии с точкой конца лабиринта, а затем начинает повторятся.
Можно генерировать новый лабиринт, не доходя до конца текущего лабиринта, а также возвращаться в точку начала по нажатию специальных клавиш на клавиатуре.
Все вышеперечисленные действия определены функциями (см. код в файле labyrinth_main.py), которые вызываются при нажатии клавиш.
- Python 3 для начинающих и чайников – уроки программирования [Электронный ресурс] URL: https://pythonworld.ru (дата обращения: 14.12.2019)
- Pygame и разработка игр. [Электронный ресурс] URL: https://younglinux.info/pygame/pygame (дата обращения: 24.12.19)
- Язык программирования Python: что такое и где используется – Логотип и история [Электронный ресурс] URL: https://all-python.ru/osnovy/yazyk-programmirovaniya.html (дата обращения: 24.12.2019)