[Python] 纯文本查看 复制代码
import tkinter as tk
from tkinter import ttk, messagebox
from collections import deque
from typing import List, Tuple, Set, Optional, Dict
import threading
import time
import heapq
import random
class CatAIBlock:
def __init__(self, parent_graph: 'CatAIGraph', i: int, j: int, is_wall: bool):
self.parent_graph = parent_graph
self.i = i
self.j = j
self.is_wall = is_wall
self.distance = float('inf')
self._routes_count: Optional[int] = None
self.is_edge = (i == 0 or i == parent_graph.width - 1 or
j == 0 or j == parent_graph.height - 1)
def neighbors(self) -> List[Optional['CatAIBlock']]:
neighbor_coords = self.parent_graph.solver.get_neighbors(self.i, self.j)
blocks = []
for ni, nj in neighbor_coords:
blocks.append(self.parent_graph.get_block(ni, nj))
return blocks
def neighbor_coords(self) -> List[Tuple[int, int]]:
return self.parent_graph.solver.get_neighbors(self.i, self.j)
def routes_count(self) -> int:
if self._routes_count is None:
if self.is_edge:
self._routes_count = 1
else:
count = 0
for neighbor in self.neighbors:
if neighbor and not neighbor.is_wall and neighbor.distance < self.distance:
count += neighbor.routes_count
self._routes_count = count
return self._routes_count
def get_best_move(self) -> Optional[Tuple[int, int]]:
max_routes = -1
best_pos = None
neighbor_positions = self.neighbor_coords
for pos in neighbor_positions:
neighbor_block = self.parent_graph.get_block(pos[0], pos[1])
if neighbor_block and not neighbor_block.is_wall and neighbor_block.distance < self.distance:
if neighbor_block.routes_count > max_routes:
max_routes = neighbor_block.routes_count
best_pos = pos
return best_pos
class OptimizedCatAIGraph:
def __init__(self, solver_instance: 'CatchTheCatSolver', walls: Set[Tuple[int, int]]):
self.solver = solver_instance
self.width = solver_instance.width
self.height = solver_instance.height
self.walls = walls
self.distances = [[float('inf')] * self.height for _ in range(self.width)]
self.routes_cache = {}
self.calc_distances()
def get_block(self, i: int, j: int) -> Optional[CatAIBlock]:
if 0 <= i < self.width and 0 <= j < self.height:
return CatAIBlock(self, i, j, (i, j) in self.walls)
return None
def calc_distances(self):
from collections import deque
q = deque()
for i in range(self.width):
for j in range(self.height):
if (i == 0 or i == self.width - 1 or
j == 0 or j == self.height - 1) and (i, j) not in self.walls:
self.distances[i][j] = 0
q.append((i, j))
while q:
i, j = q.popleft()
current_dist = self.distances[i][j]
for neighbor in self.solver.get_neighbors(i, j):
ni, nj = neighbor
if (ni, nj) not in self.walls:
if self.distances[ni][nj] > current_dist + 1:
self.distances[ni][nj] = current_dist + 1
q.append((ni, nj))
def get_routes_count(self, i: int, j: int) -> int:
if (i, j) in self.routes_cache:
return self.routes_cache[(i, j)]
if (i, j) in self.walls:
self.routes_cache[(i, j)] = 0
return 0
if i == 0 or i == self.width - 1 or j == 0 or j == self.height - 1:
self.routes_cache[(i, j)] = 1
return 1
count = 0
current_dist = self.distances[i][j]
for neighbor in self.solver.get_neighbors(i, j):
ni, nj = neighbor
if (ni, nj) not in self.walls and self.distances[ni][nj] < current_dist:
count += self.get_routes_count(ni, nj)
self.routes_cache[(i, j)] = count
return count
class OptimizedCatchTheCatSolver:
def __init__(self, width=11, height=11):
self.width = width
self.height = height
self.cat_start = (width // 2, height // 2)
self.initial_walls = set()
self.cell_radius = 20
self.cell_spacing = 5
self.MAX_DEPTH = 12
self.MAX_CANDIDATES = 6
self.MAX_SOLUTIONS = 20
self.MAX_TOTAL_TIME = 30
self.computing = False
self.start_time = 0
self.move_cache = {}
self.evaluation_cache = {}
self.escape_path_cache = {}
self.step_labels = {}
self.neighbors_map = {}
self.game_mode = False
self.game_walls = set()
self.game_cat_pos = None
self.game_step = 0
self.show_solution = False
self.solution_on_board = []
self.wall_click_order = []
self.root = tk.Tk()
self.root.title("圈小猫")
self.root.geometry("850x680")
self.root.columnconfigure(0, weight=1)
self.root.rowconfigure(0, weight=1)
main_frame = ttk.Frame(self.root, padding="10")
main_frame.grid(row=0, column=0, sticky=(tk.W, tk.E, tk.N, tk.S))
main_frame.columnconfigure(0, weight=100)
main_frame.columnconfigure(1, weight=1)
main_frame.rowconfigure(0, weight=1)
left_frame = ttk.LabelFrame(main_frame, text="游戏区域", padding="10")
left_frame.grid(row=0, column=0, sticky=(tk.W, tk.E, tk.N, tk.S), padx=(0, 5))
right_frame = ttk.LabelFrame(main_frame, text="解决方案", padding="10")
right_frame.grid(row=0, column=1, sticky=(tk.N, tk.S), padx=(5, 0))
right_frame.rowconfigure(2, weight=1)
self.dx = 2 * self.cell_radius + self.cell_spacing
self.dy = (2 * self.cell_radius + self.cell_spacing) * 0.866
canvas_width = self.dx * self.width + self.cell_radius + 2 * self.cell_spacing
canvas_height = self.dy * self.height + self.cell_radius + 2 * self.cell_spacing
self.canvas = tk.Canvas(left_frame, width=canvas_width, height=canvas_height, bg='white')
self.canvas.grid(row=0, column=0, columnspan=5, pady=10)
button_frame = ttk.Frame(left_frame)
button_frame.grid(row=1, column=0, columnspan=5, sticky=(tk.W, tk.E), pady=5)
button_frame.columnconfigure(0, weight=1)
button_frame.columnconfigure(1, weight=1)
button_frame.columnconfigure(2, weight=1)
button_frame.columnconfigure(3, weight=1)
button_frame.columnconfigure(4, weight=1)
ttk.Button(button_frame, text="重置", command=self.reset).grid(row=0, column=0, sticky=(tk.W, tk.E), padx=3)
ttk.Button(button_frame, text="计算方案", command=self.start_generate_solutions).grid(row=0, column=1, sticky=(tk.W, tk.E), padx=3)
self.stop_button = ttk.Button(button_frame, text="停止计算", command=self.stop_computing, state='disabled')
self.stop_button.grid(row=0, column=2, sticky=(tk.W, tk.E), padx=3)
ttk.Button(button_frame, text="生成墙壁", command=self.generate_random_walls).grid(row=0, column=3, sticky=(tk.W, tk.E), padx=3)
self.start_game_button = ttk.Button(button_frame, text="开始游戏", command=self.start_game)
self.start_game_button.grid(row=0, column=4, sticky=(tk.W, tk.E), padx=3)
self.progress_var = tk.StringVar(value="就绪")
self.progress_label = ttk.Label(left_frame, textvariable=self.progress_var)
self.progress_label.grid(row=2, column=0, columnspan=5, pady=5)
self.progress_bar = ttk.Progressbar(left_frame, mode='indeterminate')
self.progress_bar.grid(row=3, column=0, columnspan=5, sticky=(tk.W, tk.E), pady=5)
info_frame = ttk.Frame(left_frame)
info_frame.grid(row=4, column=0, columnspan=5, pady=10)
self.info_label = ttk.Label(info_frame, text="Tips: 点击圆圈设置初始墙壁位置")
self.info_label.pack(side=tk.LEFT)
self.show_solution_var = tk.BooleanVar(value=False)
self.show_solution_check = ttk.Checkbutton(
info_frame,
text="作弊模式",
variable=self.show_solution_var,
command=self.toggle_show_solution,
state='disabled'
)
self.show_solution_check.pack(side=tk.RIGHT, padx=10)
control_frame = ttk.Frame(right_frame)
control_frame.grid(row=0, column=0, columnspan=2, sticky=tk.W, pady=(0, 10))
self.solution_stats_label = ttk.Label(control_frame, text="解决方案统计: 0 个")
self.solution_stats_label.grid(row=0, column=0, sticky=tk.W)
ttk.Label(control_frame, text="排序方式:").grid(row=1, column=0, sticky=tk.W, pady=(5, 0))
self.sort_var = tk.StringVar(value="steps")
sort_combo = ttk.Combobox(control_frame, textvariable=self.sort_var,
values=["steps", "efficiency"], state="readonly", width=10)
sort_combo.grid(row=1, column=1, sticky=tk.W, padx=(5, 0), pady=(5, 0))
sort_combo.bind('<<ComboboxSelected>>', self.on_sort_change)
self.stats_var = tk.StringVar(value="")
self.stats_label = ttk.Label(control_frame, textvariable=self.stats_var)
self.stats_label.grid(row=2, column=0, columnspan=2, sticky=tk.W, pady=(5, 0))
tree_frame = ttk.Frame(right_frame)
tree_frame.grid(row=2, column=0, columnspan=2, sticky=(tk.N, tk.S), pady=(10, 0))
tree_frame.rowconfigure(0, weight=1)
self.tree = ttk.Treeview(tree_frame, height=12, columns=('steps', 'efficiency'), show='tree headings')
self.tree.heading('#0', text='方案')
self.tree.heading('steps', text='步数')
self.tree.heading('efficiency', text='效率')
self.tree.column('#0', width=100, stretch=False)
self.tree.column('steps', width=50, stretch=False)
self.tree.column('efficiency', width=60, stretch=False)
self.tree.grid(row=0, column=0, sticky=(tk.N, tk.S))
scrollbar = ttk.Scrollbar(tree_frame, orient=tk.VERTICAL, command=self.tree.yview)
scrollbar.grid(row=0, column=1, sticky=(tk.N, tk.S))
self.tree.configure(yscrollcommand=scrollbar.set)
detail_frame = ttk.LabelFrame(right_frame, text="方案详情", padding="5")
detail_frame.grid(row=3, column=0, columnspan=2, sticky=(tk.N, tk.S), pady=(10, 0))
detail_frame.rowconfigure(0, weight=1)
self.detail_text = tk.Text(detail_frame, height=6, wrap=tk.WORD, width=25)
self.detail_text.grid(row=0, column=0, sticky=(tk.N, tk.S))
detail_scrollbar = ttk.Scrollbar(detail_frame, orient=tk.VERTICAL, command=self.detail_text.yview)
detail_scrollbar.grid(row=0, column=1, sticky=(tk.N, tk.S))
self.detail_text.configure(yscrollcommand=detail_scrollbar.set)
self.tree.bind('<<TreeviewSelect>>', self.on_solution_select)
self.solutions = []
self.current_solution_walls = set()
self.precompute_neighbors()
self.draw_board()
self.canvas.bind("<Button-1>", self.on_canvas_click)
def precompute_neighbors(self):
for j in range(self.height):
for i in range(self.width):
self.neighbors_map[(i, j)] = self._compute_neighbors(i, j)
def _compute_neighbors(self, i: int, j: int) -> List[Tuple[int, int]]:
if j % 2 == 0:
neighbors = [
(i-1, j),
(i-1, j-1),
(i, j-1),
(i+1, j),
(i, j+1),
(i-1, j+1),
]
else:
neighbors = [
(i-1, j),
(i, j-1),
(i+1, j-1),
(i+1, j),
(i+1, j+1),
(i, j+1),
]
return [(ni, nj) for ni, nj in neighbors
if 0 <= ni < self.width and 0 <= nj < self.height]
def get_neighbors(self, i: int, j: int) -> List[Tuple[int, int]]:
return self.neighbors_map[(i, j)]
def get_cell_center(self, i: int, j: int) -> Tuple[float, float]:
offset = self.cell_radius if j % 2 == 1 else 0
x = self.cell_radius + self.cell_spacing + i * self.dx + offset
y = self.cell_radius + self.cell_spacing + j * self.dy
return x, y
def draw_circle(self, x: float, y: float, color: str, outline: str = 'black', width: int = 2):
r = self.cell_radius * 0.85
return self.canvas.create_oval(
x - r, y - r, x + r, y + r,
fill=color,
outline=outline,
width=width
)
def draw_board(self):
self.canvas.delete("all")
self.cells = {}
self.step_labels.clear()
for j in range(self.height):
for i in range(self.width):
x, y = self.get_cell_center(i, j)
if self.game_mode:
if (i, j) == self.game_cat_pos:
color = '#FFB6C1'
elif (i, j) in self.game_walls:
color = '#333333'
else:
color = '#E0E0E0'
else:
if (i, j) == self.cat_start:
color = '#FFB6C1'
elif (i, j) in self.initial_walls:
color = '#333333'
elif (i, j) in self.current_solution_walls:
color = '#FF6B6B'
elif self.show_solution and (i, j) in self.solution_on_board:
color = '#90EE90'
else:
color = '#E0E0E0'
cell = self.draw_circle(x, y, color)
self.cells[(i, j)] = cell
if self.game_mode:
if (i, j) == self.game_cat_pos:
self.canvas.create_text(x, y, text="🐱", font=("Arial", 14))
else:
if (i, j) == self.cat_start:
self.canvas.create_text(x, y, text="🐱", font=("Arial", 14))
if self.show_solution and self.solution_on_board:
try:
step_idx = self.solution_on_board.index((i, j))
self.canvas.create_text(x, y, text=str(step_idx + 1),
font=("Arial", 10, "bold"),
fill='blue')
except ValueError:
pass
def display_solution_steps(self, solution):
for label in self.step_labels.values():
self.canvas.delete(label)
self.step_labels.clear()
for i, wall_pos in enumerate(solution):
x, y = self.get_cell_center(wall_pos[0], wall_pos[1])
bg = self.canvas.create_oval(x-10, y-10, x+10, y+10,
fill='white', outline='')
label = self.canvas.create_text(x, y, text=str(i+1),
font=("Arial", 12, "bold"),
fill='red')
self.step_labels[wall_pos] = (bg, label)
def on_canvas_click(self, event):
if self.computing:
messagebox.showinfo("提示", "正在计算中，请等待计算完成")
return
min_dist = float('inf')
closest_cell = None
for j in range(self.height):
for i in range(self.width):
x, y = self.get_cell_center(i, j)
dist = ((event.x - x) ** 2 + (event.y - y) ** 2) ** 0.5
if dist < min_dist and dist < self.cell_radius:
min_dist = dist
closest_cell = (i, j)
if not closest_cell:
return
if self.game_mode:
if closest_cell == self.game_cat_pos:
return
if closest_cell not in self.game_walls:
self.game_walls.add(closest_cell)
self.game_step += 1
self.draw_board()
if self.is_cat_completely_trapped(self.game_walls, self.game_cat_pos):
messagebox.showinfo("游戏胜利", f"恭喜！您在第{self.game_step}步成功困住了小猫！")
self.exit_game_mode()
return
next_cat_pos = self.get_cat_next_move(self.game_walls, self.game_cat_pos)
if next_cat_pos is None:
messagebox.showinfo("游戏胜利", f"恭喜！您在第{self.game_step}步成功困住了小猫！")
self.exit_game_mode()
elif self.is_cat_escaped(next_cat_pos):
messagebox.showinfo("游戏失败", f"小猫逃脱了！游戏结束。")
self.exit_game_mode()
else:
self.game_cat_pos = next_cat_pos
self.draw_board()
return
if closest_cell and closest_cell != self.cat_start:
if closest_cell in self.initial_walls:
self.initial_walls.remove(closest_cell)
if closest_cell in self.wall_click_order:
self.wall_click_order.remove(closest_cell)
self.draw_board()
else:
if len(self.initial_walls) >= 8:
messagebox.showinfo("提示", "最多只能设置 8 个墙壁！点击'开始游戏'按钮开始游戏。")
return
self.initial_walls.add(closest_cell)
if closest_cell not in self.wall_click_order:
self.wall_click_order.append(closest_cell)
self.draw_board()
def reset(self):
if self.computing:
messagebox.showinfo("提示", "正在计算中，请等待计算完成")
return
self.initial_walls.clear()
self.wall_click_order.clear()
self.current_solution_walls.clear()
self.solution_on_board.clear()
self.show_solution = False
self.solutions = []
self.draw_board()
self.tree.delete(*self.tree.get_children())
self.info_label.config(text="已重置")
self.solution_stats_label.config(text="解决方案统计：0 个")
self.detail_text.delete(1.0, tk.END)
self.stats_var.set("")
self.show_solution_check.config(state='disabled')
self.show_solution_var.set(False)
def generate_random_walls(self):
if self.computing:
messagebox.showinfo("提示", "正在计算中，请等待计算完成")
return
if self.game_mode:
messagebox.showinfo("提示", "请先退出游戏模式")
return
if len(self.wall_click_order) >= 8:
walls_to_keep = self.wall_click_order[:8]
self.initial_walls = set(walls_to_keep)
self.wall_click_order = walls_to_keep
self.info_label.config(text="已保留您点击的前 8 个墙壁")
else:
current_count = len(self.wall_click_order)
available_positions = []
for j in range(self.height):
for i in range(self.width):
if (i, j) != self.cat_start and (i, j) not in self.initial_walls:
available_positions.append((i, j))
need_count = 8 - current_count
if available_positions:
selected = random.sample(available_positions, min(need_count, len(available_positions)))
self.wall_click_order.extend(selected)
self.initial_walls = set(self.wall_click_order)
self.info_label.config(text=f"已生成 8 个随机墙壁（保留了{current_count}个您设置的墙壁）")
self.draw_board()
def start_game(self):
if self.computing:
messagebox.showinfo("提示", "正在计算中，请等待计算完成")
return
if not self.initial_walls:
messagebox.showinfo("提示", "请先设置一些初始墙壁（可以使用'生成随机墙壁'按钮）")
return
self.game_mode = True
self.game_walls = self.initial_walls.copy()
self.game_cat_pos = self.cat_start
self.game_step = 0
self.start_game_button.config(text="游戏中...")
self.info_label.config(text="游戏模式：点击圆圈放置墙壁，困住小猫！")
for widget in self.root.winfo_children():
self._disable_widgets_except_solution(widget)
if self.solutions:
self.show_solution_check.config(state='normal')
self.draw_board()
def _disable_widgets(self, widget):
try:
if isinstance(widget, ttk.Button):
widget.config(state='disabled')
elif isinstance(widget, ttk.Checkbutton):
if widget != self.show_solution_check:
widget.config(state='disabled')
except:
pass
for child in widget.winfo_children():
self._disable_widgets(child)
def _disable_widgets_except_solution(self, widget):
try:
if isinstance(widget, ttk.Button):
widget.config(state='disabled')
elif isinstance(widget, ttk.Checkbutton):
if widget != self.show_solution_check:
widget.config(state='disabled')
except:
pass
for child in widget.winfo_children():
self._disable_widgets_except_solution(child)
def _enable_widgets(self):
for widget in self.root.winfo_children():
self._enable_widgets_recursive(widget)
def _enable_widgets_recursive(self, widget):
try:
if isinstance(widget, ttk.Button):
widget.config(state='normal')
elif isinstance(widget, ttk.Checkbutton):
widget.config(state='normal')
except:
pass
for child in widget.winfo_children():
self._enable_widgets_recursive(child)
def exit_game_mode(self):
self.game_mode = False
self.game_walls.clear()
self.game_cat_pos = None
self.game_step = 0
self.start_game_button.config(text="开始游戏")
self._enable_widgets()
self.info_label.config(text="已退出游戏模式")
self.draw_board()
def toggle_show_solution(self):
self.show_solution = self.show_solution_var.get()
if self.show_solution:
selection = self.tree.selection()
if selection:
idx = int(self.tree.item(selection[0])['text'].split()[-1]) - 1
if 0 <= idx < len(self.solutions):
self.solution_on_board = list(self.solutions[idx])
self.info_label.config(text=f"作弊模式：共{len(self.solution_on_board)}步，点击圆圈查看步骤")
else:
self.solution_on_board = []
self.info_label.config(text="请先选择一个解决方案")
self.show_solution_var.set(False)
self.show_solution = False
else:
self.solution_on_board = []
self.info_label.config(text="请先选择一个解决方案")
self.show_solution_var.set(False)
self.show_solution = False
else:
self.solution_on_board = []
self.info_label.config(text="已关闭作弊模式")
self.draw_board()
def is_cat_escaped(self, cat_pos: Tuple[int, int]) -> bool:
i, j = cat_pos
return i == 0 or i == self.width - 1 or j == 0 or j == self.height - 1
def is_cat_completely_trapped(self, walls: Set[Tuple[int, int]], cat_pos: Tuple[int, int]) -> bool:
for neighbor in self.get_neighbors(cat_pos[0], cat_pos[1]):
ni, nj = neighbor
if (ni, nj) not in walls:
return False
return True
def get_cat_next_move(self, walls: Set[Tuple[int, int]], cat_pos: Tuple[int, int]) -> Optional[Tuple[int, int]]:
cache_key = (frozenset(walls), cat_pos)
if cache_key in self.move_cache:
return self.move_cache[cache_key]
graph = OptimizedCatAIGraph(self, walls)
if cat_pos[0] == 0 or cat_pos[0] == self.width - 1 or \
cat_pos[1] == 0 or cat_pos[1] == self.height - 1:
self.move_cache[cache_key] = None
return None
ci, cj = cat_pos
if graph.distances[ci][cj] == float('inf'):
self.move_cache[cache_key] = None
return None
best_move = None
best_routes = -1
current_dist = graph.distances[ci][cj]
for neighbor in self.get_neighbors(ci, cj):
ni, nj = neighbor
if (ni, nj) not in walls and graph.distances[ni][nj] < current_dist:
routes = graph.get_routes_count(ni, nj)
if routes > best_routes:
best_routes = routes
best_move = (ni, nj)
self.move_cache[cache_key] = best_move
return best_move
def get_heuristic_candidates(self, walls, cat_pos, limit=8):
candidates = []
strategic = self.get_strategic_wall_positions(walls, cat_pos)
for pos in strategic:
if pos in walls:
continue
score = self.quick_evaluate_position(walls, cat_pos, pos)
candidates.append((score, pos))
candidates.sort(key=lambda x: x[0], reverse=True)
return [pos for _, pos in candidates[:limit]]
def quick_evaluate_position(self, walls, cat_pos, wall_pos):
cache_key = (frozenset(walls), cat_pos, wall_pos)
if cache_key in self.evaluation_cache:
return self.evaluation_cache[cache_key]
score = 0
dist_to_cat = abs(wall_pos[0] - cat_pos[0]) + abs(wall_pos[1] - cat_pos[1])
if dist_to_cat == 1:
score += 30
elif dist_to_cat == 2:
score += 20
elif dist_to_cat <= 4:
score += 15 - dist_to_cat * 2
path = self.get_cat_escape_path_positions(walls, cat_pos)
if wall_pos in path[:3]:
score += 25
test_walls = walls.copy()
test_walls.add(wall_pos)
new_path = self.get_cat_escape_path_positions(test_walls, cat_pos)
if not new_path:
score += 50
elif path and new_path and len(new_path) > len(path):
score += (len(new_path) - len(path)) * 5
self.evaluation_cache[cache_key] = score
return score
def get_strategic_wall_positions(self, walls: Set[Tuple[int, int]], cat_pos: Tuple[int, int]) -> Set[Tuple[int, int]]:
strategic = set()
for neighbor in self.get_neighbors(cat_pos[0], cat_pos[1]):
if neighbor not in walls:
strategic.add(neighbor)
escape_path = self.get_cat_escape_path_positions(walls, cat_pos)
if escape_path:
for pos in escape_path[:3]:
strategic.add(pos)
for i in range(max(0, cat_pos[0] - 2), min(self.width, cat_pos[0] + 3)):
for j in range(max(0, cat_pos[1] - 2), min(self.height, cat_pos[1] + 3)):
if (i, j) not in walls and (i, j) != cat_pos:
dist = abs(i - cat_pos[0]) + abs(j - cat_pos[1])
if dist <= 3:
strategic.add((i, j))
return strategic
def get_cat_escape_path_positions(self, walls: Set[Tuple[int, int]], cat_pos: Tuple[int, int]) -> List[Tuple[int, int]]:
cache_key = (frozenset(walls), cat_pos)
if cache_key in self.escape_path_cache:
return self.escape_path_cache[cache_key]
open_set = []
heapq.heappush(open_set, (0, cat_pos))
came_from = {}
g_score = {cat_pos: 0}
f_score = {cat_pos: self.heuristic(cat_pos)}
while open_set:
current_f, current = heapq.heappop(open_set)
i, j = current
if i == 0 or i == self.width - 1 or j == 0 or j == self.height - 1:
path = self.reconstruct_path(came_from, current)
self.escape_path_cache[cache_key] = path
return path
for neighbor in self.get_neighbors(i, j):
if neighbor in walls:
continue
tentative_g = g_score[current] + 1
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 + self.heuristic(neighbor)
heapq.heappush(open_set, (f_score[neighbor], neighbor))
self.escape_path_cache[cache_key] = []
return []
def heuristic(self, pos: Tuple[int, int]) -> float:
i, j = pos
return min(i, self.width - 1 - i, j, self.height - 1 - j)
def reconstruct_path(self, came_from: Dict, current: Tuple[int, int]) -> List[Tuple[int, int]]:
path = []
while current in came_from:
path.append(current)
current = came_from[current]
path.reverse()
return path
def on_sort_change(self, event):
if not self.solutions:
return
sort_by = self.sort_var.get()
if sort_by == "steps":
self.solutions.sort(key=lambda x: (len(x), -self.calculate_solution_efficiency(x)))
elif sort_by == "efficiency":
self.solutions.sort(key=lambda x: (-self.calculate_solution_efficiency(x), len(x)))
self.update_solution_display()
def update_solution_display(self):
self.tree.delete(*self.tree.get_children())
for idx, solution in enumerate(self.solutions):
efficiency = self.calculate_solution_efficiency(solution)
self.tree.insert('', 'end',
text=f"方案 {idx + 1}",
values=(len(solution), f"{efficiency:.2f}"))
self.solution_stats_label.config(text=f"解决方案统计: {len(self.solutions)} 个")
def calculate_solution_efficiency(self, solution: List[Tuple[int, int]]) -> float:
if not solution:
return 0.0
return 1.0 / len(solution)
def start_generate_solutions(self):
if not self.initial_walls:
messagebox.showwarning("警告", "请先设置一些初始墙壁！")
return
if self.computing:
return
self.current_solution_walls.clear()
self.draw_board()
self.detail_text.delete(1.0, tk.END)
self.move_cache.clear()
self.evaluation_cache.clear()
self.escape_path_cache.clear()
self.computing = True
self.stop_button.config(state='normal')
self.progress_bar.start()
self.progress_var.set("正在计算...")
self.stats_var.set("")
threading.Thread(target=self.optimized_compute_thread, daemon=True).start()
def optimized_compute_thread(self):
try:
self.start_time = time.time()
if self.is_cat_completely_trapped(self.initial_walls, self.cat_start):
self.root.after(0, lambda: self.on_solutions_complete([]))
return
solutions = self.iterative_deepening_search()
elapsed = time.time() - self.start_time
print(f"计算完成，耗时: {elapsed:.2f}秒，找到 {len(solutions)} 个解决方案")
self.root.after(0, lambda: self.on_solutions_complete(solutions))
except Exception as e:
print(f"计算线程错误: {e}")
self.root.after(0, lambda: self.on_computation_error(str(e)))
def iterative_deepening_search(self):
all_solutions = []
for depth in range(6, self.MAX_DEPTH + 1, 2):
if not self.computing:
break
if time.time() - self.start_time > self.MAX_TOTAL_TIME:
self.root.after(0, lambda: self.update_progress("达到时间限制，停止搜索"))
break
self.root.after(0, lambda d=depth: self.update_progress(f"正在搜索深度 {d}..."))
solutions = self.depth_limited_search(depth)
all_solutions.extend(solutions)
if len(all_solutions) >= self.MAX_SOLUTIONS:
break
return self.deduplicate_solutions(all_solutions)
def depth_limited_search(self, max_depth):
solutions = []
initial_state = (0, self.initial_walls.copy(), self.cat_start, [])
states = [initial_state]
best_length = float('inf')
while states and self.computing and time.time() - self.start_time < self.MAX_TOTAL_TIME:
depth, walls, cat_pos, moves = heapq.heappop(states)
if depth >= best_length or depth >= max_depth:
continue
if self.is_cat_completely_trapped(walls, cat_pos):
solutions.append(moves)
if len(moves) < best_length:
best_length = len(moves)
continue
candidates = self.get_heuristic_candidates(walls, cat_pos, self.MAX_CANDIDATES)
for wall_pos in candidates:
if wall_pos in walls:
continue
new_walls = walls.copy()
new_walls.add(wall_pos)
new_moves = moves.copy()
new_moves.append(wall_pos)
next_cat_pos = self.get_cat_next_move(new_walls, cat_pos)
if next_cat_pos is None or self.is_cat_completely_trapped(new_walls, cat_pos):
solutions.append(new_moves)
if len(new_moves) < best_length:
best_length = len(new_moves)
elif not self.is_cat_escaped(next_cat_pos):
new_state = (len(new_moves), new_walls, next_cat_pos, new_moves)
heapq.heappush(states, new_state)
return solutions
def deduplicate_solutions(self, solutions):
unique = []
seen = set()
for solution in solutions:
key = frozenset(solution)
if key not in seen:
seen.add(key)
unique.append(solution)
unique.sort(key=len)
return unique[:self.MAX_SOLUTIONS]
def update_progress(self, message):
self.progress_var.set(message)
def on_solutions_complete(self, all_solutions):
self.computing = False
self.stop_button.config(state='disabled')
self.progress_bar.stop()
elapsed = time.time() - self.start_time
self.solutions = all_solutions
self.update_solution_display()
if self.solutions:
self.progress_var.set(f"计算完成！找到 {len(self.solutions)} 个解决方案")
self.info_label.config(text=f"找到 {len(self.solutions)} 个解决方案，点击'开始游戏'后可查看方案")
self.show_solution_check.config(state='disabled')
self.show_solution_var.set(False)
else:
self.progress_var.set("计算完成")
self.info_label.config(text="没有找到解决方案")
self.solution_stats_label.config(text="解决方案统计: 0 个")
self.stats_var.set(f"耗时: {elapsed:.2f}秒")
self.show_solution_check.config(state='disabled')
self.show_solution_var.set(False)
def on_computation_error(self, error_msg):
self.computing = False
self.stop_button.config(state='disabled')
self.progress_bar.stop()
self.progress_var.set("计算出错")
messagebox.showerror("错误", f"计算过程中出现错误：{error_msg}")
def stop_computing(self):
self.computing = False
self.stop_button.config(state='disabled')
self.progress_bar.stop()
self.progress_var.set("计算已停止")
self.info_label.config(text="计算已停止")
def on_solution_select(self, event):
selection = self.tree.selection()
if selection:
item = self.tree.item(selection[0])
idx = int(item['text'].split()[1]) - 1
if 0 <= idx < len(self.solutions):
solution = self.solutions[idx]
self.current_solution_walls = set(solution)
if self.show_solution:
self.solution_on_board = list(solution)
self.draw_board()
self.display_solution_steps(solution)
current_walls = self.initial_walls.copy()
current_cat_pos = self.cat_start
details = f"方案 {idx + 1} 详情:\n"
details += f"总步数: {len(solution)}\n"
details += f"{'='*40}\n\n"
details += f"初始状态:\n"
details += f" 猫的位置: {current_cat_pos}\n"
details += f" 初始墙壁: {list(self.initial_walls)}\n\n"
game_over = False
for i, wall_pos in enumerate(solution):
current_walls.add(wall_pos)
details += f"第 {i + 1} 步:\n"
details += f" 玩家在 {wall_pos} 放置墙壁\n"
if self.is_cat_completely_trapped(current_walls, current_cat_pos):
details += f" 猫被困在 {current_cat_pos}，游戏结束！\n\n"
game_over = True
break
else:
next_cat_pos = self.get_cat_next_move(current_walls, current_cat_pos)
if next_cat_pos:
details += f" 猫移动到 {next_cat_pos}\n"
current_cat_pos = next_cat_pos
if self.is_cat_escaped(current_cat_pos):
details += f" 猫逃脱了！\n\n"
break
else:
details += f" 猫无法移动，被困在 {current_cat_pos}！\n\n"
game_over = True
break
details += "\n"
if not game_over and not self.is_cat_escaped(current_cat_pos):
details += f"最终状态: 小猫被困在 {current_cat_pos}\n"
self.detail_text.delete(1.0, tk.END)
self.detail_text.insert(1.0, details)
def run(self):
self.root.mainloop()
if __name__ == "__main__":
solver = OptimizedCatchTheCatSolver()
solver.run()
[复制链接]
发表于 2026-4-20 09:07
分享到朋友圈
