import tkinter as tk
from tkinter import messagebox
import random

class MazeGame:
    def __init__(self, root):
        self.root = root
        self.root.title("迷宫游戏")
        self.root.resizable(False, False)
        
        # 游戏设置
        self.cell_size = 30  # 每个格子的大小（像素）
        self.maze_size = 15  # 迷宫大小（奇数列）
        
        # 颜色设置
        self.colors = {
            'wall': '#2C3E50',      # 墙壁颜色
            'path': '#ECF0F1',      # 路径颜色
            'start': '#27AE60',     # 起点颜色
            'end': '#E74C3C',       # 终点颜色
            'player': '#3498DB',    # 玩家颜色
            'visited': '#F39C12'    # 访问过的路径颜色
        }
        
        # 游戏变量
        self.maze = None
        self.player_pos = None
        self.visited = set()
        
        # 创建界面
        self.setup_ui()
        
        # 开始新游戏
        self.new_game()
    
    def setup_ui(self):
        """设置用户界面"""
        # 控制框架
        control_frame = tk.Frame(self.root)
        control_frame.pack(pady=10)
        
        tk.Button(control_frame, text="新游戏", command=self.new_game, 
                 font=('Arial', 12), bg='#3498DB', fg='white', padx=20).pack(side=tk.LEFT, padx=5)
        
        self.status_label = tk.Label(control_frame, text="使用方向键或WASD移动", 
                                     font=('Arial', 12))
        self.status_label.pack(side=tk.LEFT, padx=20)
        
        # 画布
        canvas_size = self.maze_size * self.cell_size
        self.canvas = tk.Canvas(self.root, width=canvas_size, height=canvas_size, 
                                bg=self.colors['wall'])
        self.canvas.pack(padx=10, pady=10)
        
        # 绑定键盘事件
        self.root.bind('<Up>', lambda e: self.move_player(0, -1))
        self.root.bind('<Down>', lambda e: self.move_player(0, 1))
        self.root.bind('<Left>', lambda e: self.move_player(-1, 0))
        self.root.bind('<Right>', lambda e: self.move_player(1, 0))
        self.root.bind('w', lambda e: self.move_player(0, -1))
        self.root.bind('s', lambda e: self.move_player(0, 1))
        self.root.bind('a', lambda e: self.move_player(-1, 0))
        self.root.bind('d', lambda e: self.move_player(1, 0))
        
        # 确保画布获得焦点
        self.canvas.focus_set()
    
    def generate_maze(self):
        """使用深度优先生成迷宫"""
        # 初始化迷宫（全为墙壁）
        maze = [[1 for _ in range(self.maze_size)] for _ in range(self.maze_size)]
        
        # 起点（1,1）为路径
        start_x, start_y = 1, 1
        maze[start_y][start_x] = 0
        
        # 使用栈进行DFS
        stack = [(start_x, start_y)]
        
        while stack:
            x, y = stack[-1]
            
            # 获取未访问的邻居
            neighbors = []
            # 上下左右方向（步长为2）
            for dx, dy in [(0, -2), (0, 2), (-2, 0), (2, 0)]:
                nx, ny = x + dx, y + dy
                if 0 < nx < self.maze_size-1 and 0 < ny < self.maze_size-1:
                    if maze[ny][nx] == 1:
                        neighbors.append((nx, ny, dx//2, dy//2))
            
            if neighbors:
                # 随机选择一个邻居
                nx, ny, wall_x, wall_y = random.choice(neighbors)
                # 打通墙壁
                maze[y + wall_y][x + wall_x] = 0
                # 打通邻居
                maze[ny][nx] = 0
                stack.append((nx, ny))
            else:
                stack.pop()
        
        # 设置终点（右下角）
        maze[self.maze_size-2][self.maze_size-2] = 0
        
        return maze
    
    def draw_maze(self):
        """绘制迷宫"""
        self.canvas.delete("all")
        
        for y in range(self.maze_size):
            for x in range(self.maze_size):
                x1 = x * self.cell_size
                y1 = y * self.cell_size
                x2 = x1 + self.cell_size
                y2 = y1 + self.cell_size
                
                if self.maze[y][x] == 1:  # 墙壁
                    color = self.colors['wall']
                elif (x, y) == self.player_pos:  # 玩家
                    color = self.colors['player']
                elif (x, y) == (self.maze_size-2, self.maze_size-2):  # 终点
                    color = self.colors['end']
                elif (x, y) == (1, 1):  # 起点
                    color = self.colors['start']
                elif (x, y) in self.visited:  # 访问过的路径
                    color = self.colors['visited']
                else:  # 普通路径
                    color = self.colors['path']
                
                self.canvas.create_rectangle(x1, y1, x2, y2, fill=color, outline='')
                
                # 添加网格线
                self.canvas.create_line(x2, y1, x2, y2, fill='#BDC3C7', width=1)
                self.canvas.create_line(x1, y2, x2, y2, fill='#BDC3C7', width=1)
    
    def new_game(self):
        """开始新游戏"""
        self.maze = self.generate_maze()
        self.player_pos = (1, 1)  # 起点
        self.visited = {(1, 1)}
        self.draw_maze()
        self.status_label.config(text="找到红色终点即可胜利！")
    
    def move_player(self, dx, dy):
        """移动玩家"""
        if not self.maze:
            return
        
        x, y = self.player_pos
        new_x, new_y = x + dx, y + dy
        
        # 检查是否在边界内
        if 0 <= new_x < self.maze_size and 0 <= new_y < self.maze_size:
            # 检查是否是路径（不是墙壁）
            if self.maze[new_y][new_x] != 1:
                self.player_pos = (new_x, new_y)
                self.visited.add((new_x, new_y))
                self.draw_maze()
                
                # 检查是否到达终点
                if (new_x, new_y) == (self.maze_size-2, self.maze_size-2):
                    messagebox.showinfo("胜利！", f"恭喜你完成了迷宫！\n总共移动了{len(self.visited)}步")
                    self.new_game()
                else:
                    # 更新状态显示
                    steps = len(self.visited)
                    remaining = self.calculate_remaining_path()
                    self.status_label.config(text=f"步数: {steps} | 距离终点: {remaining}步")
    
    def calculate_remaining_path(self):
        """计算到终点的曼哈顿距离"""
        px, py = self.player_pos
        ex, ey = self.maze_size-2, self.maze_size-2
        return abs(px - ex) + abs(py - ey)

class MazeSolver:
    """迷宫求解器（可选功能）"""
    
    @staticmethod
    def solve(maze, start, end):
        """使用BFS求解迷宫"""
        from collections import deque
        
        size = len(maze)
        queue = deque([(start[0], start[1], [start])])
        visited = set([start])
        
        while queue:
            x, y, path = queue.popleft()
            
            if (x, y) == end:
                return path
            
            for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < size and 0 <= ny < size:
                    if maze[ny][nx] != 1 and (nx, ny) not in visited:
                        visited.add((nx, ny))
                        queue.append((nx, ny, path + [(nx, ny)]))
        
        return None

class MazeGameWithSolver(MazeGame):
    """带求解器功能的迷宫游戏"""
    
    def setup_ui(self):
        """设置带求解器按钮的界面"""
        control_frame = tk.Frame(self.root)
        control_frame.pack(pady=10)
        
        tk.Button(control_frame, text="新游戏", command=self.new_game,
                 font=('Arial', 12), bg='#3498DB', fg='white', padx=20).pack(side=tk.LEFT, padx=5)
        
        tk.Button(control_frame, text="显示解法", command=self.show_solution,
                 font=('Arial', 12), bg='#9B59B6', fg='white', padx=20).pack(side=tk.LEFT, padx=5)
        
        self.status_label = tk.Label(control_frame, text="使用方向键或WASD移动",
                                     font=('Arial', 12))
        self.status_label.pack(side=tk.LEFT, padx=20)
        
        # 画布
        canvas_size = self.maze_size * self.cell_size
        self.canvas = tk.Canvas(self.root, width=canvas_size, height=canvas_size,
                                bg=self.colors['wall'])
        self.canvas.pack(padx=10, pady=10)
        
        # 绑定键盘事件
        self.root.bind('<Up>', lambda e: self.move_player(0, -1))
        self.root.bind('<Down>', lambda e: self.move_player(0, 1))
        self.root.bind('<Left>', lambda e: self.move_player(-1, 0))
        self.root.bind('<Right>', lambda e: self.move_player(1, 0))
        self.root.bind('w', lambda e: self.move_player(0, -1))
        self.root.bind('s', lambda e: self.move_player(0, 1))
        self.root.bind('a', lambda e: self.move_player(-1, 0))
        self.root.bind('d', lambda e: self.move_player(1, 0))
    
    def show_solution(self):
        """显示迷宫解法"""
        start = (1, 1)
        end = (self.maze_size-2, self.maze_size-2)
        
        solution = MazeSolver.solve(self.maze, start, end)
        
        if solution:
            # 高亮显示解法路径
            self.draw_maze()  # 先重绘当前状态
            
            for i, (x, y) in enumerate(solution):
                x1 = x * self.cell_size
                y1 = y * self.cell_size
                x2 = x1 + self.cell_size
                y2 = y1 + self.cell_size
                
                # 使用半透明的颜色显示路径
                if i % 2 == 0:
                    color = '#FFD700'  # 金色
                else:
                    color = '#FFA500'  # 橙色
                
                # 不覆盖起点、终点和玩家位置
                if (x, y) != start and (x, y) != end and (x, y) != self.player_pos:
                    self.canvas.create_rectangle(x1, y1, x2, y2, fill=color, outline='')
            
            # 5秒后恢复
            self.root.after(5000, lambda: self.draw_maze())
            messagebox.showinfo("解法提示", f"找到解法！共{len(solution)}步")
        else:
            messagebox.showwarning("无解", "当前迷宫无法到达终点！")

def main():
    """主函数"""
    root = tk.Tk()
    
    # 选择游戏模式
    choice = messagebox.askyesno("选择模式", "是否启用求解器功能？\n是：启用求解器\n否：普通模式")
    
    if choice:
        game = MazeGameWithSolver(root)
    else:
        game = MazeGame(root)
    
    root.mainloop()

if __name__ == "__main__":
    main()