ASSISTANT
Конечно! Ниже представлен пример реализации вашей задачи на языке Python. Программа включает два алгоритма генерации лабиринта, два алгоритма поиска пути и взаимодействие с пользователем через консоль.
## Необходимые библиотеки
Убедитесь, что у вас установлены необходимые библиотеки. Для этой реализации используются стандартные библиотеки Python, поэтому дополнительных установок не требуется.
## Структура Программы
1. **Генерация Лабиринта:**
- **Алгоритм Прим (Prim's Algorithm)**
- **Алгоритм Рекурсивного Обхода (Recursive Backtracker)**
2. **Добавление Слоёв:**
- **Болото (🟫)**
- **Монетка (🟨)**
3. **Поиск Пути:**
- **Алгоритм Дейкстры (Dijkstra's Algorithm)**
- **Алгоритм A***
4. **Взаимодействие с Пользователем:**
- Ввод размеров лабиринта
- Выбор алгоритма генерации
- Ввод начальной и конечной точек
- Выбор алгоритма поиска пути
- Вывод итогового лабиринта с выделенным путем
## Полный Код
```python
import random
from collections import deque
import heapq
# Символы для отображения
WALL = '⬛️'
PATH = '⬜️'
SWAMP = '🟫'
COIN = '🟨'
PATH_MARK = '🪙'
def initialize_maze(width, height):
maze = [[WALL for _ in range(width)] for _ in range(height)]
return maze
def print_maze(maze):
for row in maze:
print(' '.join(row))
print()
def generate_maze_prim(width, height):
maze = initialize_maze(width, height)
start_x = random.randint(0, height-1)
start_y = random.randint(0, width-1)
maze[start_x][start_y] = PATH
walls = []
# Добавляем соседние стены
for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
nx, ny = start_x + dx, start_y + dy
if 0 <= nx < height and 0 <= ny < width:
walls.append((nx, ny, start_x, start_y))
while walls:
wx, wy, px, py = walls.pop(random.randint(0, len(walls)-1))
if maze[wx][wy] == WALL:
# Подсчет соседей пути
neighbors = 0
for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
nx, ny = wx + dx, wy + dy
if 0 <= nx < height and 0 <= ny < width:
if maze[nx][ny] == PATH:
neighbors += 1
if neighbors == 1:
maze[wx][wy] = PATH
for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
nx, ny = wx + dx, wy + dy
if 0 <= nx < height and 0 <= ny < width:
if maze[nx][ny] == WALL:
walls.append((nx, ny, wx, wy))
add_features(maze)
return maze
def generate_maze_recursive_backtracker(width, height):
maze = initialize_maze(width, height)
stack = []
start_x = random.randint(0, height-1)
start_y = random.randint(0, width-1)
maze[start_x][start_y] = PATH
stack.append((start_x, start_y))
while stack:
x, y = stack[-1]
neighbors = []
for dx, dy in [(-2,0), (2,0), (0,-2), (0,2)]:
nx, ny = x + dx, y + dy
if 0 <= nx < height and 0 <= ny < width:
if maze[nx][ny] == WALL:
neighbors.append((nx, ny))
if neighbors:
nx, ny = random.choice(neighbors)
maze[nx][ny] = PATH
# Убираем стену между текущей и соседней клеткой
wall_x, wall_y = x + (nx - x) // 2, y + (ny - y) // 2
maze[wall_x][wall_y] = PATH
stack.append((nx, ny))
else:
stack.pop()
add_features(maze)
return maze
def add_features(maze):
height = len(maze)
width = len(maze[0])
for x in range(height):
for y in range(width):
if maze[x][y] == PATH:
feature = random.choices(
[PATH, SWAMP, COIN],
weights=[80, 10, 10],
k=1
)[0]
maze[x][y] = feature
def get_user_input(prompt, min_val=3, max_val=50):
while True:
try:
value = int(input(prompt))
if min_val <= value <= max_val:
return value
else:
print(f"Пожалуйста, введите число от {min_val} до {max_val}.")
except ValueError:
print("Некорректный ввод. Пожалуйста, введите число.")
def choose_maze_generation():
print("Выберите алгоритм генерации лабиринта:")
print("1. Алгоритм Прима")
print("2. Алгоритм Рекурсивного Обхода")
while True:
choice = input("Введите 1 или 2: ")
if choice in ['1', '2']:
return choice
else:
print("Некорректный выбор. Пожалуйста, выберите 1 или 2.")
def get_coordinates(prompt, width, height):
while True:
try:
coords = input(prompt)
x, y = map(int, coords.strip().split())
if 0 <= x < height and 0 <= y < width:
return (x, y)
else:
print(f"Координаты должны быть в диапазоне от (0,0) до ({height-1},{width-1}).")
except ValueError:
print("Некорректный ввод. Введите два числа через пробел.")
def choose_pathfinding_algorithm():
print("Выберите алгоритм поиска пути:")
print("1. Алгоритм Дейкстры")
print("2. Алгоритм A*")
while True:
choice = input("Введите 1 или 2: ")
if choice in ['1', '2']:
return choice
else:
print("Некорректный выбор. Пожалуйста, выберите 1 или 2.")
def is_path(cell):
return cell in [PATH, SWAMP, COIN]
def dijkstra(maze, start, end):
height = len(maze)
width = len(maze[0])
distances = [[float('inf') for _ in range(width)] for _ in range(height)]
prev = [[None for _ in range(width)] for _ in range(height)]
heap = []
sx, sy = start
ex, ey = end
distances[sx][sy] = 0
heapq.heappush(heap, (0, (sx, sy)))
while heap:
current_distance, (x, y) = heapq.heappop(heap)
if (x, y) == (ex, ey):
break
for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < height and 0 <= ny < width and is_path(maze[nx][ny]):
# Определение стоимости клетки
if maze[nx][ny] == SWAMP:
cost = 1 # Можно использовать -1 к привлекательности при подсчете
elif maze[nx][ny] == COIN:
cost = -1
else:
cost = 0
new_distance = current_distance + cost
if new_distance < distances[nx][ny]:
distances[nx][ny] = new_distance
prev[nx][ny] = (x, y)
heapq.heappush(heap, (new_distance, (nx, ny)))
# Восстановление пути
path = []
at = (ex, ey)
if prev[ex][ey] is None and (ex, ey) != (sx, sy):
return None # Путь не найден
while at:
path.append(at)
at = prev[at[0]][at[1]]
path.reverse()
return path
def a_star(maze, start, end):
height = len(maze)
width = len(maze[0])
open_set = []
heapq.heappush(open_set, (0, start))
came_from = {}
g_score = {start: 0}
ex, ey = end
while open_set:
_, current = heapq.heappop(open_set)
if current == end:
break
x, y = current
for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
nx, ny = x + dx, y + dy
neighbor = (nx, ny)
if 0 <= nx < height and 0 <= ny < width and is_path(maze[nx][ny]):
# Определение стоимости клетки
if maze[nx][ny] == SWAMP:
tentative_g = g_score[current] + 1
elif maze[nx][ny] == COIN:
tentative_g = g_score[current] - 1
else:
tentative_g = g_score[current]
if neighbor not in g_score or tentative_g < g_score[neighbor]:
came_from[neighbor] = current
g_score[neighbor] = tentative_g
# Эвристическая функция: манхэттенское расстояние
h = abs(ex - nx) + abs(ey - ny)
f = tentative_g + h
heapq.heappush(open_set, (f, neighbor))
# Восстановление пути
path = []
at = end
if at not in came_from and at != start:
return None # Путь не найден
while at in came_from:
path.append(at)
at = came_from[at]
path.append(start)
path.reverse()
return path
def mark_path(maze, path):
for x, y in path:
if maze[x][y] not in [SWAMP, COIN]:
maze[x][y] = PATH_MARK
else:
# Сохранение особенностей клетки
if maze[x][y] == SWAMP:
maze[x][y] = PATH_MARK
elif maze[x][y] == COIN:
maze[x][y] = PATH_MARK
def main():
print("Генерация Лабиринта")
width = get_user_input("Введите ширину лабиринта (3-50): ")
height = get_user_input("Введите высоту лабиринта (3-50): ")
algo = choose_maze_generation()
if algo == '1':
maze = generate_maze_prim(width, height)
else:
maze = generate_maze_recursive_backtracker(width, height)
print("\nСгенерированный Лабиринт:")
print_maze(maze)
# Ввод начальной и конечной точек
while True:
start = get_coordinates("Введите координаты начала (x y): ", width, height)
if is_path(maze[start[0]][start[1]]):
break
else:
print("Выбранная начальная точка не является проходимой. Попробуйте снова.")
while True:
end = get_coordinates("Введите координаты конца (x y): ", width, height)
if is_path(maze[end[0]][end[1]]):
break
else:
print("Выбранная конечная точка не является проходимой. Попробуйте снова.")
search_algo = choose_pathfinding_algorithm()
if search_algo == '1':
path = dijkstra(maze, start, end)
algo_name = "Алгоритм Дейкстры"
else:
path = a_star(maze, start, end)
algo_name = "Алгоритм A*"
if path is None:
print("Путь не найден.")
return
else:
mark_path(maze, path)
print(f"\nЛабиринт с найденным путем ({algo_name}):")
print_maze(maze)
if __name__ == "__main__":
main()
```
## Пояснение Кода
1. **Инициализация Лабиринта:**
- `initialize_maze` создает сетку лабиринта, заполненную стенами.
2. **Генерация Лабиринта:**
- **Алгоритм Прима (`generate_maze_prim`):** Начинает с случайной клетки и постепенно добавляет соседние стены, создавая проходимые пути.
- **Алгоритм Рекурсивного Обхода (`generate_maze_recursive_backtracker`):** Рекурсивно создает пути, углубляясь до тех пор, пока не может найти новые клетки для расширения.
3. **Добавление Особенностей:**
- `add_features` случайным образом заменяет некоторые клетки пути на болото (`🟫`) или монетку (`🟨`), исходя из заданных вероятностей.
4. **Ввод Пользователем:**
- Функции `get_user_input`, `choose_maze_generation`, `get_coordinates`, `choose_pathfinding_algorithm` обеспечивают ввод и выбор пользователем параметров.
5. **Поиск Пути:**
- **Алгоритм Дейкстры (`dijkstra`):** Находит путь с минимальной суммарной стоимостью, учитывая особенности клеток.
- **Алгоритм A* (`a_star`):** Использует эвристическую функцию для ускорения поиска оптимального пути.
6. **Маркировка Пути:**
- `mark_path` заменяет клетки на пути на символ монетки (`🪙`), сохраняя особенности клеток, если они присутствуют.
7. **Основная Функция (`main`):**
- Объединяет все компоненты: генерация лабиринта, ввод точек, выбор алгоритма поиска, поиск пути и вывод результатов.
## Пример Использования
```
Генерация Лабиринта
Введите ширину лабиринта (3-50): 10
Введите высоту лабиринта (3-50): 10
Выберите алгоритм генерации лабиринта:
1. Алгоритм Прима
2. Алгоритм Рекурсивного Обхода
Введите 1 или 2: 1
Сгенерированный Лабиринт:
⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️
⬛️ 🟫 🪙 ⬜️ 🟨 🟫 ⬜️ 🟨 🟨 ⬛️
⬛️ ⬜️ ⬜️ ⬜️ 🟨 ⬜️ ⬜️ ⬜️ ⬜️ ⬛️
⬛️ ⬛️ ⬛️ ⬜️ 🟨 ⬛️ ⬛️ ⬜️ ⬛️ ⬛️
⬛️ ⬜️ ⬜️ ⬜️ 🟫 ⬜️ 🟫 ⬜️ ⬜️ ⬛️
⬛️ 🟨 🟫 ⬛️ ⬜️ ⬜️ ⬜️ 🟨 🟨 ⬛️
⬛️ ⬜️ ⬛️ ⬜️ ⬛️ ⬛️ ⬜️ ⬛️ ⬜️ ⬛️
⬛️ ⬜️ ⬜️ ⬜️ ⬜️ 🟨 🟫 🟨 ⬜️ ⬛️
⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️
⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️
Введите координаты начала (x y): 1 1
Введите координаты конца (x y): 7 8
Выберите алгоритм поиска пути:
1. Алгоритм Дейкстры
2. Алгоритм A*
Введите 1 или 2: 2
Лабиринт с найденным путем (Алгоритм A*):
⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️
⬛️ 🪙 🪙 🪙 🪙 🪙 🪙 🟨 🟨 ⬛️
⬛️ 🪙 🪙 🪙 🟨 🪙 🪙 🪙 🪙 ⬛️
⬛️ ⬛️ ⬛️ 🪙 🟨 ⬛️ ⬛️ 🪙 ⬛️ ⬛️
⬛️ 🪙 🪙 🪙 🟫 🪙 🟫 🪙 🪙 ⬛️
⬛️ 🟨 🟫 ⬛️ 🪙 🪙 🪙 🟨 🟨 ⬛️
⬛️ 🪙 ⬛️ 🪙 ⬛️ ⬛️ 🪙 ⬛️ 🪙 ⬛️
⬛️ 🪙 🪙 🪙 🪙 🟨 🟫 🟨 🟙 ⬛️
⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️
⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️ ⬛️
```
## Заключение
Этот пример предоставляет основу для вашей программы генерации и поиска пути в лабиринте. Вы можете расширять функциональность, например, добавлять дополнительные типы клеток, улучшать интерфейс пользователя или оптимизировать алгоритмы для больших лабиринтов.