You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
103 lines
3.9 KiB
103 lines
3.9 KiB
# DFS: Depth First Search |
|
import random |
|
import tkinter as tk |
|
import json |
|
|
|
class MazeGenerator: |
|
def __init__(self, width=10, height=10 ): |
|
self.width = width |
|
self.height = height |
|
self.generate_maze(width // 2) # Use integer division for size |
|
self.window = tk.Tk() |
|
self.window.title("Maze") |
|
self.canvas = tk.Canvas(self.window, width=(self.width+1)*10, height=(self.height+1)*10) |
|
self.canvas.pack() |
|
self.arrival_point = (self.width - 1, self.height - 1) # Set the arrival point near the bottom-right corner |
|
self.backtrack = [] |
|
|
|
|
|
def generate_maze(self, size): |
|
# Initialize the maze with walls (True) |
|
self.maze = [[True for _ in range(size * 2 + 1)] for _ in range(size * 2 + 1)] |
|
|
|
# Define the directions (W, E, S, N) |
|
self.directions = [(-2, 0), (2, 0), (0, 2), (0, -2)] |
|
|
|
# Start from the upper-left cell |
|
start_x, start_y = (1, 1) |
|
self.maze[start_x][start_y] = False |
|
self.stack = [(start_x, start_y)] |
|
|
|
def stack_iteration(self): |
|
if not self.stack: # Check if the stack is empty |
|
return |
|
|
|
current_x, current_y = self.stack[-1] |
|
|
|
# Function to get the unvisited neighbors |
|
def get_unvisited_neighbors(x, y): |
|
neighbors = [] |
|
if not (self.arrival_point == (x,y)): |
|
for dx, dy in self.directions: |
|
nx, ny = x + dx, y + dy |
|
if 1 <= nx < len(self.maze) - 1 and 1 <= ny < len(self.maze[0]) - 1 and self.maze[nx][ny]: |
|
neighbors.append((nx, ny)) |
|
return neighbors |
|
|
|
neighbors = get_unvisited_neighbors(current_x, current_y) |
|
|
|
if neighbors: |
|
# Choose a random unvisited neighbor |
|
chosen_x, chosen_y = random.choice(neighbors) |
|
|
|
# Remove the wall between the current cell and the chosen cell |
|
self.maze[(current_x + chosen_x) // 2][(current_y + chosen_y) // 2] = False |
|
|
|
# Mark the chosen cell as visited |
|
self.maze[chosen_x][chosen_y] = False |
|
|
|
# Push the chosen cell to the stack |
|
self.stack.append((chosen_x, chosen_y)) |
|
else: |
|
# Backtrack if no unvisited neighbors are found |
|
self.backtrack.append(self.stack.pop()) |
|
|
|
def update_maze(self): |
|
self.stack_iteration() |
|
self.draw_maze() |
|
if self.stack: # Continue updating only if there are cells left to visit |
|
self.window.after(10, self.update_maze) |
|
else: |
|
# After the maze is generated, remove some walls randomly |
|
for _ in range(int(self.width * self.height * 0.1)): # Remove 10% of the total cells as walls |
|
x = random.randint(1, self.width - 2) |
|
y = random.randint(1, self.height - 2) |
|
self.maze[x][y] = False |
|
self.draw_maze() |
|
with open('maze.json', 'w') as json_file: |
|
json.dump(self.maze, json_file) |
|
|
|
|
|
def draw_maze(self): |
|
self.canvas.delete("all") |
|
for i in range(len(self.maze)): |
|
for j in range(len(self.maze[i])): |
|
color = "black" if self.maze[i][j] else "white" |
|
# if (i, j) in self.backtrack: |
|
# color="yellow" |
|
if (i, j) == self.arrival_point: |
|
color = "green" # Color the arrival point green |
|
elif (i, j) == (1 ,1): |
|
color = "red" # Color the arrival point green |
|
elif self.stack and (i, j) == self.stack[-1]: |
|
color = "blue" # Color the current position blue |
|
self.canvas.create_rectangle(j*10, i*10, (j+1)*10, (i+1)*10, fill=color) |
|
|
|
|
|
def run(self): |
|
self.update_maze() |
|
self.window.mainloop() |
|
|
|
# Crea e avvia il generatore di labirinti |
|
generator = MazeGenerator(20, 20) |
|
generator.run()
|
|
|