1)Реализуй 2 мощных алгоритма генерации лабиринтов. Состоящих только из ⬜️: Проход (путь…
- User
1)Реализуй 2 мощных алгоритма генерации лабиринтов. Состоящих только из ⬜️: Проход (путь по которому можно передвигаться, размер пути не больше одной клеточки) ⬛️: Стена (не проходимый путь, размер стены не больше одной клеточки) 🟫: Болото (-1 к привлекательности пути, встречается на местах прохода вкраплениями) 🟨: монетка (+1 к привлекательности пути, встречается на местах прохода вкраплениями) Мы вводим в консоль ширину и высоту лабиринта и затем выбираем алгоритм построения и в консоль выводится наш сгенерированный лабиринт 2)Затем мы в этом лабиринте указываем начальную и конечную точку нашего пути по координатам. Если это невозможно просим переопределить точки. Реализация как минимум 2-х алгоритмов для поиска пути из заданной начальной точки А в конечную точку Б. Мы выбираем один из предложенных алгоритмов, и программа строит самый оптимальный путь. 🪙 – так обозначить каждую клетку нашего оптимального маршрута между заданными нами координатами. Затем программа выводит изменённый лабиринт, но уже с построенным путём
- Assistant
Creating a maze generator and pathfinding tool with the specifications you've provided is an exciting project! Below, I'll guide you through implementing this in Python. The program will:
- Generate a Maze using two different algorithms.
- Populate the Maze with special cells: Swamps and Coins.
- Allow User Interaction to set start and end points.
- Find the Optimal Path using one of two pathfinding algorithms.
- Display the Final Maze with the path highlighted.
We'll use Python's standard libraries to accomplish this. Let's break down the solution step by step.
Table of Contents
- Setting Up the Maze Structure
- Maze Generation Algorithms
- Populating the Maze with Swamps and Coins
- Displaying the Maze
- Pathfinding Algorithms
- Putting It All Together
- Complete Python Code
- Running the Program
1. Setting Up the Maze Structure
We'll represent the maze as a 2D grid where each cell can be:
⬜️: Path⬛️: Wall🟫: Swamp🟨: Coin🪙: Path in the optimal route
We'll create a
Mazeclass to handle the maze's creation, population, and display.import random from collections import deque import heapq class Maze: def __init__(self, width, height): self.width = width if width % 2 == 1 else width + 1 # Ensure odd dimensions self.height = height if height % 2 == 1 else height + 1 self.grid = [['⬛️' for _ in range(self.width)] for _ in range(self.height)] def in_bounds(self, x, y): return 0 <= x < self.width and 0 <= y < self.height def neighbors(self, x, y): dirs = [(-2, 0), (2, 0), (0, -2), (0, 2)] result = [] for dx, dy in dirs: nx, ny = x + dx, y + dy if self.in_bounds(nx, ny): result.append((nx, ny)) return result def set_cell(self, x, y, value): if self.in_bounds(x, y): self.grid[y][x] = value def get_cell(self, x, y): if self.in_bounds(x, y): return self.grid[y][x] return None def display(self): for row in self.grid: print(''.join(row))
2. Maze Generation Algorithms
Algorithm 1: Recursive Backtracking (Depth-First Search)
This algorithm starts at a random cell, marks it as part of the maze, and recursively visits neighboring cells in a randomized order. If a neighbor hasn't been visited, it removes the wall between them and continues.
def generate_maze_dfs(maze): stack = [] start_x, start_y = 1, 1 maze.set_cell(start_x, start_y, '⬜️') stack.append((start_x, start_y)) while stack: current_x, current_y = stack[-1] neighbors = maze.neighbors(current_x, current_y) unvisited = [] for nx, ny in neighbors: if maze.get_cell(nx, ny) == '⬛️': unvisited.append((nx, ny)) if unvisited: chosen_x, chosen_y = random.choice(unvisited) wall_x, wall_y = (current_x + chosen_x) // 2, (current_y + chosen_y) // 2 maze.set_cell(wall_x, wall_y, '⬜️') maze.set_cell(chosen_x, chosen_y, '⬜️') stack.append((chosen_x, chosen_y)) else: stack.pop()Algorithm 2: Prim's Algorithm
Prim's algorithm starts with a grid full of walls. It picks a random cell, marks it as part of the maze, and adds its walls to a list. It then randomly selects a wall from the list, and if the cell beyond the wall isn't part of the maze, it removes the wall and marks the cell as part of the maze.
def generate_maze_prim(maze): walls = [] start_x, start_y = 1, 1 maze.set_cell(start_x, start_y, '⬜️') walls.extend(get_adjacent_walls(maze, start_x, start_y)) while walls: wx, wy = random.choice(walls) walls.remove((wx, wy)) # Determine the opposite cell dx, dy = wx - start_x, wy - start_y ox, oy = wx + dx, wy + dy if maze.in_bounds(ox, oy) and maze.get_cell(ox, oy) == '⬛️': maze.set_cell(wx, wy, '⬜️') maze.set_cell(ox, oy, '⬜️') walls.extend(get_adjacent_walls(maze, ox, oy))Helper function to get adjacent walls:
def get_adjacent_walls(maze, x, y): walls = [] directions = [(-2, 0), (2, 0), (0, -2), (0, 2)] for dx, dy in directions: nx, ny = x + dx, y + dy if maze.in_bounds(nx, ny) and maze.get_cell(nx, ny) == '⬛️': walls.append((nx, ny)) return walls
3. Populating the Maze with Swamps and Coins
After generating the maze paths, we'll randomly sprinkle swamps (
🟫) and coins (🟨) within the paths. The density of these features can be adjusted as needed.def populate_maze(maze, swamp_prob=0.1, coin_prob=0.1): for y in range(1, maze.height, 2): for x in range(1, maze.width, 2): if maze.get_cell(x, y) == '⬜️': rand = random.random() if rand < swamp_prob: maze.set_cell(x, y, '🟫') elif rand < swamp_prob + coin_prob: maze.set_cell(x, y, '🟨')
4. Displaying the Maze
The
Mazeclass has adisplaymethod that prints the maze to the console using the specified emojis.def display_maze(maze): maze.display()
5. Pathfinding Algorithms
Algorithm 1: A* Search
A* search uses heuristics to efficiently find the shortest path. We'll use Manhattan distance as the heuristic.
def a_star_search(maze, start, end): open_set = [] heapq.heappush(open_set, (0, start)) came_from = {} g_score = {start: 0} f_score = {start: manhattan_distance(start, end)} while open_set: current = heapq.heappop(open_set)[1] if current == end: return reconstruct_path(came_from, current) for neighbor in get_neighbors(maze, current): tentative_g = g_score[current] + movement_cost(maze, neighbor) if neighbor not in g_score or tentative_g < g_score[neighbor]: came_from[neighbor] = current g_score[neighbor] = tentative_g f_score[neighbor] = tentative_g + manhattan_distance(neighbor, end) if neighbor not in [i[1] for i in open_set]: heapq.heappush(open_set, (f_score[neighbor], neighbor)) return NoneAlgorithm 2: Dijkstra's Algorithm
Dijkstra's algorithm finds the shortest path without using heuristics. It's similar to A* but explores uniformly.
def dijkstra_search(maze, start, end): open_set = [] heapq.heappush(open_set, (0, start)) came_from = {} cost_so_far = {start: 0} while open_set: current_cost, current = heapq.heappop(open_set) if current == end: return reconstruct_path(came_from, current) for neighbor in get_neighbors(maze, current): new_cost = cost_so_far[current] + movement_cost(maze, neighbor) if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]: cost_so_far[neighbor] = new_cost heapq.heappush(open_set, (new_cost, neighbor)) came_from[neighbor] = current return NoneHelper Functions for Pathfinding
def manhattan_distance(a, b): return abs(a[0] - b[0]) + abs(a[1] - b[1]) def get_neighbors(maze, pos): x, y = pos neighbors = [] directions = [(-1,0), (1,0), (0,-1), (0,1)] for dx, dy in directions: nx, ny = x + dx, y + dy if maze.in_bounds(nx, ny): cell = maze.get_cell(nx, ny) if cell in ['⬜️', '🟫', '🟨']: neighbors.append((nx, ny)) return neighbors def movement_cost(maze, pos): cell = maze.get_cell(pos[0], pos[1]) if cell == '🟫': return 2 # Higher cost for swamps elif cell == '🟨': return 1 # Same as normal path else: return 1 # Normal path def reconstruct_path(came_from, current): path = [current] while current in came_from: current = came_from[current] path.append(current) path.reverse() return path
6. Putting It All Together
We'll create an interactive console application that:
- Takes user input for maze dimensions.
- Allows the user to choose a maze generation algorithm.
- Generates and populates the maze.
- Displays the maze.
- Takes user input for start and end points.
- Validates the points.
- Allows the user to choose a pathfinding algorithm.
- Finds and displays the optimal path in the maze.
def main(): # Step 1: Get maze dimensions width = int(input("Enter maze width (odd number >=5): ")) height = int(input("Enter maze height (odd number >=5): ")) if width < 5 or height < 5: print("Width and height should be at least 5.") return # Initialize maze maze = Maze(width, height) # Step 2: Choose maze generation algorithm print("Choose maze generation algorithm:") print("1. Recursive Backtracking (DFS)") print("2. Prim's Algorithm") algo_choice = input("Enter 1 or 2: ") if algo_choice == '1': generate_maze_dfs(maze) elif algo_choice == '2': generate_maze_prim(maze) else: print("Invalid choice.") return # Step 3: Populate with swamps and coins populate_maze(maze, swamp_prob=0.1, coin_prob=0.1) # Step 4: Display the maze print("\nGenerated Maze:") display_maze(maze) # Step 5: Input start and end points while True: try: start_x = int(input(f"Enter start X (1 to {maze.width -2}): ")) start_y = int(input(f"Enter start Y (1 to {maze.height -2}): ")) end_x = int(input(f"Enter end X (1 to {maze.width -2}): ")) end_y = int(input(f"Enter end Y (1 to {maze.height -2}): ")) if not all([ maze.in_bounds(start_x, start_y), maze.in_bounds(end_x, end_y), maze.get_cell(start_x, start_y) in ['⬜️', '🟫', '🟨'], maze.get_cell(end_x, end_y) in ['⬜️', '🟫', '🟨'] ]): print("Start or end points are invalid or on walls. Please try again.") continue break except ValueError: print("Please enter valid integer coordinates.") start = (start_x, start_y) end = (end_x, end_y) # Step 6: Choose pathfinding algorithm print("Choose pathfinding algorithm:") print("1. A* Search") print("2. Dijkstra's Algorithm") path_choice = input("Enter 1 or 2: ") if path_choice == '1': path = a_star_search(maze, start, end) elif path_choice == '2': path = dijkstra_search(maze, start, end) else: print("Invalid choice.") return if path is None: print("No path found between the selected points.") return # Step 7: Mark the path in the maze for pos in path: if pos == start or pos == end: continue # Keep start and end symbols x, y = pos maze.set_cell(x, y, '🪙') # Step 8: Display the maze with path print("\nMaze with Optimal Path:") display_maze(maze)
7. Complete Python Code
Here is the complete Python script combining all the components mentioned above. You can copy this into a Python
.pyfile and run it.import random from collections import deque import heapq class Maze: def __init__(self, width, height): self.width = width if width % 2 == 1 else width + 1 # Ensure odd dimensions self.height = height if height % 2 == 1 else height + 1 self.grid = [['⬛️' for _ in range(self.width)] for _ in range(self.height)] def in_bounds(self, x, y): return 0 <= x < self.width and 0 <= y < self.height def neighbors(self, x, y): dirs = [(-2, 0), (2, 0), (0, -2), (0, 2)] result = [] for dx, dy in dirs: nx, ny = x + dx, y + dy if self.in_bounds(nx, ny): result.append((nx, ny)) return result def set_cell(self, x, y, value): if self.in_bounds(x, y): self.grid[y][x] = value def get_cell(self, x, y): if self.in_bounds(x, y): return self.grid[y][x] return None def display(self): for row in self.grid: print(''.join(row)) def generate_maze_dfs(maze): stack = [] start_x, start_y = 1, 1 maze.set_cell(start_x, start_y, '⬜️') stack.append((start_x, start_y)) while stack: current_x, current_y = stack[-1] neighbors = maze.neighbors(current_x, current_y) unvisited = [] for nx, ny in neighbors: if maze.get_cell(nx, ny) == '⬛️': unvisited.append((nx, ny)) if unvisited: chosen_x, chosen_y = random.choice(unvisited) wall_x, wall_y = (current_x + chosen_x) // 2, (current_y + chosen_y) // 2 maze.set_cell(wall_x, wall_y, '⬜️') maze.set_cell(chosen_x, chosen_y, '⬜️') stack.append((chosen_x, chosen_y)) else: stack.pop() def get_adjacent_walls(maze, x, y): walls = [] directions = [(-2, 0), (2, 0), (0, -2), (0, 2)] for dx, dy in directions: nx, ny = x + dx, y + dy if maze.in_bounds(nx, ny) and maze.get_cell(nx, ny) == '⬛️': walls.append((nx, ny)) return walls def generate_maze_prim(maze): walls = [] start_x, start_y = 1, 1 maze.set_cell(start_x, start_y, '⬜️') walls.extend(get_adjacent_walls(maze, start_x, start_y)) while walls: wx, wy = random.choice(walls) walls.remove((wx, wy)) # Determine the opposite cell # Find direction dx = wx - start_x dy = wy - start_y ox, oy = wx + dx, wy + dy if maze.in_bounds(ox, oy) and maze.get_cell(ox, oy) == '⬛️': maze.set_cell(wx, wy, '⬜️') maze.set_cell(ox, oy, '⬜️') walls.extend(get_adjacent_walls(maze, ox, oy)) def populate_maze(maze, swamp_prob=0.1, coin_prob=0.1): for y in range(1, maze.height, 2): for x in range(1, maze.width, 2): if maze.get_cell(x, y) == '⬜️': rand = random.random() if rand < swamp_prob: maze.set_cell(x, y, '🟫') elif rand < swamp_prob + coin_prob: maze.set_cell(x, y, '🟨') def display_maze(maze): maze.display() def manhattan_distance(a, b): return abs(a[0] - b[0]) + abs(a[1] - b[1]) def get_neighbors(maze, pos): x, y = pos neighbors = [] directions = [(-1,0), (1,0), (0,-1), (0,1)] for dx, dy in directions: nx, ny = x + dx, y + dy if maze.in_bounds(nx, ny): cell = maze.get_cell(nx, ny) if cell in ['⬜️', '🟫', '🟨']: neighbors.append((nx, ny)) return neighbors def movement_cost(maze, pos): cell = maze.get_cell(pos[0], pos[1]) if cell == '🟫': return 2 # Higher cost for swamps elif cell == '🟨': return 1 # Same as normal path else: return 1 # Normal path def reconstruct_path(came_from, current): path = [current] while current in came_from: current = came_from[current] path.append(current) path.reverse() return path def a_star_search(maze, start, end): open_set = [] heapq.heappush(open_set, (0, start)) came_from = {} g_score = {start: 0} f_score = {start: manhattan_distance(start, end)} while open_set: current = heapq.heappop(open_set)[1] if current == end: return reconstruct_path(came_from, current) for neighbor in get_neighbors(maze, current): tentative_g = g_score[current] + movement_cost(maze, neighbor) if neighbor not in g_score or tentative_g < g_score[neighbor]: came_from[neighbor] = current g_score[neighbor] = tentative_g f_score[neighbor] = tentative_g + manhattan_distance(neighbor, end) if neighbor not in [i[1] for i in open_set]: heapq.heappush(open_set, (f_score[neighbor], neighbor)) return None def dijkstra_search(maze, start, end): open_set = [] heapq.heappush(open_set, (0, start)) came_from = {} cost_so_far = {start: 0} while open_set: current_cost, current = heapq.heappop(open_set) if current == end: return reconstruct_path(came_from, current) for neighbor in get_neighbors(maze, current): new_cost = cost_so_far[current] + movement_cost(maze, neighbor) if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]: cost_so_far[neighbor] = new_cost heapq.heappush(open_set, (new_cost, neighbor)) came_from[neighbor] = current return None def main(): # Step 1: Get maze dimensions try: width = int(input("Enter maze width (odd number >=5): ")) height = int(input("Enter maze height (odd number >=5): ")) except ValueError: print("Please enter valid integer values for width and height.") return if width < 5 or height < 5: print("Width and height should be at least 5.") return if width % 2 == 0: width +=1 print(f"Adjusted width to {width} to make it odd.") if height % 2 ==0: height +=1 print(f"Adjusted height to {height} to make it odd.") # Initialize maze maze = Maze(width, height) # Step 2: Choose maze generation algorithm print("\nChoose maze generation algorithm:") print("1. Recursive Backtracking (DFS)") print("2. Prim's Algorithm") algo_choice = input("Enter 1 or 2: ") if algo_choice == '1': generate_maze_dfs(maze) elif algo_choice == '2': generate_maze_prim(maze) else: print("Invalid choice.") return # Step 3: Populate with swamps and coins populate_maze(maze, swamp_prob=0.1, coin_prob=0.1) # Step 4: Display the maze print("\nGenerated Maze:") display_maze(maze) # Step 5: Input start and end points while True: try: print("\nEnter Start Point:") start_x = int(input(f"X (1 to {maze.width -2}, odd numbers): ")) start_y = int(input(f"Y (1 to {maze.height -2}, odd numbers): ")) print("\nEnter End Point:") end_x = int(input(f"X (1 to {maze.width -2}, odd numbers): ")) end_y = int(input(f"Y (1 to {maze.height -2}, odd numbers): ")) if not all([ maze.in_bounds(start_x, start_y), maze.in_bounds(end_x, end_y), maze.get_cell(start_x, start_y) in ['⬜️', '🟫', '🟨'], maze.get_cell(end_x, end_y) in ['⬜️', '🟫', '🟨'] ]): print("Start or end points are invalid (either out of bounds or on walls). Please try again.") continue break except ValueError: print("Please enter valid integer coordinates.") start = (start_x, start_y) end = (end_x, end_y) # Step 6: Choose pathfinding algorithm print("\nChoose pathfinding algorithm:") print("1. A* Search") print("2. Dijkstra's Algorithm") path_choice = input("Enter 1 or 2: ") if path_choice == '1': path = a_star_search(maze, start, end) elif path_choice == '2': path = dijkstra_search(maze, start, end) else: print("Invalid choice.") return if path is None: print("No path found between the selected points.") return # Step 7: Mark the path in the maze for pos in path: if pos == start or pos == end: continue # Keep start and end symbols x, y = pos maze.set_cell(x, y, '🪙') # Step 8: Display the maze with path print("\nMaze with Optimal Path:") display_maze(maze) if __name__ == "__main__": main()
8. Running the Program
-
Prerequisites: Ensure you have Python installed on your system (Python 3.x is recommended).
-
Save the Script: Copy the complete Python code above into a file named
maze_generator.py. -
Run the Script:
- Open your terminal or command prompt.
- Navigate to the directory containing
maze_generator.py. - Execute the script using the command:
python maze_generator.py
-
Follow the Prompts:
- Enter Maze Dimensions: Input the desired width and height (preferably odd numbers and >=5).
- Choose Maze Generation Algorithm: Enter
1for Recursive Backtracking or2for Prim's Algorithm. - View Generated Maze: The program will display the maze using the specified emojis.
- Set Start and End Points: Input the X and Y coordinates for both start and end points. Ensure they are on valid path cells.
- Choose Pathfinding Algorithm: Enter
1for A* Search or2for Dijkstra's Algorithm. - View Optimal Path: The maze will be displayed again with the optimal path marked using
🪙.
Notes and Customizations
-
Maze Dimensions: The program adjusts even dimensions to the next odd number to maintain maze consistency.
-
Special Cells:
- Swamp (
🟫): Increases the movement cost, making paths through swamps less desirable. - Coin (
🟨): While coins add attractiveness, in this implementation, they have the same cost as normal paths. You can modify themovement_costfunction to give coins a bonus or adjust path preferences.
- Swamp (
-
Path Marking: The path is marked with
🪙, excluding the start and end points to preserve their original symbols. -
Error Handling: The program includes basic error handling for invalid inputs. Ensure to input valid integers and choose existing cells.
-
Further Enhancements:
- Visualization: For larger mazes, the console display can become cluttered. Consider integrating with graphical libraries like
pygamefor better visualization. - Advanced Features: Implement additional maze features or more complex cell types as needed.
- Visualization: For larger mazes, the console display can become cluttered. Consider integrating with graphical libraries like
I hope this comprehensive guide helps you build and understand the maze generator and pathfinder. Feel free to customize and expand upon it to fit your specific requirements!
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.