用python演示A星算法

import tkinter as tk
import heapq
import time

ROWS = 20
COLS = 20
CELL_SIZE = 30

# 颜色定义
COLORS = {
    "empty":  "white",
    "wall":   "black",
    "start":  "green",
    "end":    "red",
    "open":   "deepskyblue",   # Open Set：待探索
    "closed": "gold",           # Closed Set：已探索
    "path":   "purple",         # 最终路径
}

class AStarGUI:
    def __init__(self, root):
        self.root = root
        self.root.title("A* 算法演示")

        self.canvas = tk.Canvas(
            root,
            width=COLS * CELL_SIZE,
            height=ROWS * CELL_SIZE,
            bg="white"
        )
        self.canvas.pack()

        self.grid  = [[0 for _ in range(COLS)] for _ in range(ROWS)]
        self.start = None
        self.end   = None

        self.canvas.bind("<Button-1>", self.on_click)

        btn = tk.Button(root, text="开始 A*", command=self.run_astar)
        btn.pack(pady=5)

        self.draw_grid()

    def draw_grid(self):
        """重绘整个网格"""
        self.canvas.delete("all")
        for r in range(ROWS):
            for c in range(COLS):
                x1, y1 = c * CELL_SIZE, r * CELL_SIZE
                x2, y2 = x1 + CELL_SIZE, y1 + CELL_SIZE

                color = COLORS["empty"]
                if self.grid[r][c] == 1:
                    color = COLORS["wall"]
                elif self.start == (r, c):
                    color = COLORS["start"]
                elif self.end == (r, c):
                    color = COLORS["end"]

                self.canvas.create_rectangle(
                    x1, y1, x2, y2,
                    fill=color, outline="gray"
                )

    def on_click(self, event):
        """依次设置起点 → 终点 → 障碍物"""
        r = event.y // CELL_SIZE
        c = event.x // CELL_SIZE
        if r >= ROWS or c >= COLS:
            return

        if not self.start:
            self.start = (r, c)
        elif not self.end:
            self.end = (r, c)
        else:
            self.grid[r][c] = 1  # 标记为障碍物

        self.draw_grid()

    def heuristic(self, a, b):
        """曼哈顿距离启发函数"""
        return abs(a[0] - b[0]) + abs(a[1] - b[1])

    def neighbors(self, node):
        """生成四方向有效邻居（排除越界和障碍物）"""
        r, c = node
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < ROWS and 0 <= nc < COLS:
                if self.grid[nr][nc] == 0:
                    yield (nr, nc)

    def run_astar(self):
        """A* 主循环，含逐帧动画"""
        if not self.start or not self.end:
            return

        # 初始化数据结构
        open_set   = []
        heapq.heappush(open_set, (0, self.start))
        came_from  = {}
        g_score    = {self.start: 0}
        f_score    = {self.start: self.heuristic(self.start, self.end)}
        open_nodes = {self.start}

        while open_set:
            _, current = heapq.heappop(open_set)
            open_nodes.discard(current)

            # 到达终点，回溯并绘制路径
            if current == self.end:
                self.reconstruct_path(came_from, current)
                return

            # 标记为已探索（Closed Set）
            r, c = current
            self.draw_cell(r, c, COLORS["closed"])
            self.root.update()
            time.sleep(0.02)

            for neighbor in self.neighbors(current):
                tentative_g = g_score[current] + 1  # 均匀代价网格，每步代价为 1

                if tentative_g < g_score.get(neighbor, float("inf")):
                    came_from[neighbor] = current
                    g_score[neighbor]   = tentative_g
                    f_score[neighbor]   = tentative_g + self.heuristic(neighbor, self.end)

                    if neighbor not in open_nodes:
                        heapq.heappush(open_set, (f_score[neighbor], neighbor))
                        open_nodes.add(neighbor)
                        nr, nc = neighbor
                        self.draw_cell(nr, nc, COLORS["open"])

        print("未找到路径")

    def reconstruct_path(self, came_from, current):
        """从终点回溯 came_from，逐步绘制最短路径"""
        while current in came_from:
            current = came_from[current]
            if current != self.start:
                r, c = current
                self.draw_cell(r, c, COLORS["path"])
                self.root.update()
                time.sleep(0.05)

    def draw_cell(self, r, c, color):
        """以指定颜色绘制单个格子"""
        x1, y1 = c * CELL_SIZE, r * CELL_SIZE
        x2, y2 = x1 + CELL_SIZE, y1 + CELL_SIZE
        self.canvas.create_rectangle(
            x1, y1, x2, y2,
            fill=color, outline="gray"
        )


if __name__ == "__main__":
    root = tk.Tk()
    app  = AStarGUI(root)
    root.mainloop()