用python演示A星算法

1
f(n) = g(n) + h(n)

1
h(n) = |n.row - end.row| + |n.col - end.col|

1
1. 将起点加入 Open Set，初始化 g(start) = 0
2
2. 循环：
3
   a. 从 Open Set 中取出 f(n) 最小的节点 current
4
   b. 若 current == 终点，回溯路径，算法结束
5
   c. 将 current 移入 Closed Set（已探索）
6
   d. 对 current 的每个邻居 neighbor：
7
      - 跳过障碍物和已在 Closed Set 中的节点
8
      - 计算 tentative_g = g(current) + 移动代价
9
      - 若 tentative_g 更优，更新 came_from、g、f，加入 Open Set
10
3. Open Set 为空仍未到达终点 → 无可行路径

1
import tkinter as tk
2
import heapq
3
import time
4

5
ROWS = 20
6
COLS = 20
7
CELL_SIZE = 30
8

9
# 颜色定义
10
COLORS = {
11
    "empty":  "white",
12
    "wall":   "black",
13
    "start":  "green",
14
    "end":    "red",
15
    "open":   "deepskyblue",   # Open Set：待探索
16
    "closed": "gold",           # Closed Set：已探索
17
    "path":   "purple",         # 最终路径
18
}
19

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

25
        self.canvas = tk.Canvas(
26
            root,
27
            width=COLS * CELL_SIZE,
28
            height=ROWS * CELL_SIZE,
29
            bg="white"
30
        )
31
        self.canvas.pack()
32

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

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

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

42
        self.draw_grid()
43

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

52
                color = COLORS["empty"]
53
                if self.grid[r][c] == 1:
54
                    color = COLORS["wall"]
55
                elif self.start == (r, c):
56
                    color = COLORS["start"]
57
                elif self.end == (r, c):
58
                    color = COLORS["end"]
59

60
                self.canvas.create_rectangle(
61
                    x1, y1, x2, y2,
62
                    fill=color, outline="gray"
63
                )
64

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

72
        if not self.start:
73
            self.start = (r, c)
74
        elif not self.end:
75
            self.end = (r, c)
76
        else:
77
            self.grid[r][c] = 1  # 标记为障碍物
78

79
        self.draw_grid()
80

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

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

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

99
        # 初始化数据结构
100
        open_set   = []
101
        heapq.heappush(open_set, (0, self.start))
102
        came_from  = {}
103
        g_score    = {self.start: 0}
104
        f_score    = {self.start: self.heuristic(self.start, self.end)}
105
        open_nodes = {self.start}
106

107
        while open_set:
108
            _, current = heapq.heappop(open_set)
109
            open_nodes.discard(current)
110

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

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

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

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

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

136
        print("未找到路径")
137

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

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

157

158
if __name__ == "__main__":
159
    root = tk.Tk()
160
    app  = AStarGUI(root)
161
    root.mainloop()