import sys import heapq import math from PyQt5.QtWidgets import (QApplication, QMainWindow, QWidget, QVBoxLayout, QHBoxLayout, QPushButton, QLabel, QSpinBox, QComboBox, QMessageBox, QFrame) from PyQt5.QtCore import Qt, QTimer, pyqtSignal from PyQt5.QtGui import QPainter, QColor, QPen, QFont class Node: def __init__(self, x, y, walkable=True): self.x = x self.y = y self.walkable = walkable self.g = 0 # Cost from start to this node self.h = 0 # Heuristic cost to end self.f = 0 # Total cost (g + h) self.parent = None def __lt__(self, other): return self.f < other.f class AStarGame(QMainWindow): def __init__(self): super().__init__() self.grid_size = 20 self.cell_size = 30 self.grid = [] self.start_node = None self.end_node = None self.path = [] self.open_set = [] self.closed_set = set() self.is_running = False self.is_paused = False self.speed = 100 # ms self.timer = QTimer() self.timer.timeout.connect(self.step_algorithm) self.current_mode = "start" # start, end, obstacle, erase self.init_ui() self.init_grid() def init_ui(self): self.setWindowTitle("A* Pathfinding Algorithm Game") self.setFixedSize(self.grid_size * self.cell_size + 250, self.grid_size * self.cell_size + 50) # Central widget central_widget = QWidget() self.setCentralWidget(central_widget) # Main layout main_layout = QHBoxLayout() central_widget.setLayout(main_layout) # Grid widget self.grid_widget = GridWidget(self) main_layout.addWidget(self.grid_widget) # Control panel control_panel = QFrame() control_panel.setFrameStyle(QFrame.Box) control_panel.setFixedWidth(200) control_layout = QVBoxLayout() control_panel.setLayout(control_layout) # Mode selection mode_label = QLabel("Mode:") mode_label.setFont(QFont("Arial", 12, QFont.Bold)) control_layout.addWidget(mode_label) self.mode_combo = QComboBox() self.mode_combo.addItems(["Start Point", "End Point", "Obstacles", "Erase"]) self.mode_combo.currentIndexChanged.connect(self.change_mode) control_layout.addWidget(self.mode_combo) # Algorithm controls control_layout.addSpacing(20) algo_label = QLabel("Algorithm Controls:") algo_label.setFont(QFont("Arial", 12, QFont.Bold)) control_layout.addWidget(algo_label) self.start_button = QPushButton("Start") self.start_button.clicked.connect(self.start_algorithm) control_layout.addWidget(self.start_button) self.pause_button = QPushButton("Pause") self.pause_button.clicked.connect(self.pause_algorithm) self.pause_button.setEnabled(False) control_layout.addWidget(self.pause_button) self.reset_button = QPushButton("Reset") self.reset_button.clicked.connect(self.reset_grid) control_layout.addWidget(self.reset_button) self.clear_button = QPushButton("Clear All") self.clear_button.clicked.connect(self.clear_all) control_layout.addWidget(self.clear_button) # Speed control control_layout.addSpacing(20) speed_label = QLabel("Speed:") speed_label.setFont(QFont("Arial", 12, QFont.Bold)) control_layout.addWidget(speed_label) speed_layout = QHBoxLayout() self.speed_spin = QSpinBox() self.speed_spin.setRange(10, 500) self.speed_spin.setValue(self.speed) self.speed_spin.valueChanged.connect(self.change_speed) speed_layout.addWidget(self.speed_spin) speed_layout.addWidget(QLabel("ms")) control_layout.addLayout(speed_layout) # Instructions control_layout.addSpacing(20) instructions_label = QLabel("Instructions:") instructions_label.setFont(QFont("Arial", 12, QFont.Bold)) control_layout.addWidget(instructions_label) instructions = QLabel( "1. Set start and end points\n" "2. Add obstacles\n" "3. Click Start to find path\n" "4. Watch the algorithm work!" ) instructions.setWordWrap(True) control_layout.addWidget(instructions) # Status control_layout.addSpacing(20) self.status_label = QLabel("Status: Ready") self.status_label.setFont(QFont("Arial", 10)) control_layout.addWidget(self.status_label) control_layout.addStretch() main_layout.addWidget(control_panel) def init_grid(self): self.grid = [] for y in range(self.grid_size): row = [] for x in range(self.grid_size): row.append(Node(x, y)) self.grid.append(row) # Set default start and end self.start_node = self.grid[2][2] self.end_node = self.grid[self.grid_size-3][self.grid_size-3] self.update() def change_mode(self, index): modes = ["start", "end", "obstacle", "erase"] self.current_mode = modes[index] def change_speed(self, value): self.speed = value if self.timer.isActive(): self.timer.setInterval(self.speed) def start_algorithm(self): if not self.start_node or not self.end_node: QMessageBox.warning(self, "Warning", "Please set both start and end points.") return self.is_running = True self.is_paused = False self.path = [] self.open_set = [] self.closed_set = set() # Initialize start node self.start_node.g = 0 self.start_node.h = self.heuristic(self.start_node, self.end_node) self.start_node.f = self.start_node.g + self.start_node.h heapq.heappush(self.open_set, (self.start_node.f, self.start_node)) self.start_button.setEnabled(False) self.pause_button.setEnabled(True) self.reset_button.setEnabled(False) self.status_label.setText("Status: Running") self.timer.start(self.speed) def pause_algorithm(self): if self.is_running: if self.is_paused: self.timer.start(self.speed) self.pause_button.setText("Pause") self.status_label.setText("Status: Running") else: self.timer.stop() self.pause_button.setText("Resume") self.status_label.setText("Status: Paused") self.is_paused = not self.is_paused def reset_grid(self): self.timer.stop() self.is_running = False self.is_paused = False for row in self.grid: for node in row: node.g = 0 node.h = 0 node.f = 0 node.parent = None self.path = [] self.open_set = [] self.closed_set = set() self.start_button.setEnabled(True) self.pause_button.setEnabled(False) self.reset_button.setEnabled(True) self.pause_button.setText("Pause") self.status_label.setText("Status: Ready") self.update() def clear_all(self): self.reset_grid() self.init_grid() def step_algorithm(self): if not self.open_set: self.timer.stop() self.is_running = False self.status_label.setText("Status: No path found!") self.start_button.setEnabled(True) self.pause_button.setEnabled(False) self.reset_button.setEnabled(True) return # Get node with lowest f score current = heapq.heappop(self.open_set)[1] # Check if we reached the end if current == self.end_node: self.timer.stop() self.is_running = False self.reconstruct_path(current) self.status_label.setText("Status: Path found!") self.start_button.setEnabled(True) self.pause_button.setEnabled(False) self.reset_button.setEnabled(True) return self.closed_set.add(current) # Check neighbors for neighbor in self.get_neighbors(current): if neighbor in self.closed_set or not neighbor.walkable: continue tentative_g = current.g + self.distance(current, neighbor) if tentative_g < neighbor.g or neighbor not in [n[1] for n in self.open_set]: neighbor.parent = current neighbor.g = tentative_g neighbor.h = self.heuristic(neighbor, self.end_node) neighbor.f = neighbor.g + neighbor.h if neighbor not in [n[1] for n in self.open_set]: heapq.heappush(self.open_set, (neighbor.f, neighbor)) self.update() def get_neighbors(self, node): neighbors = [] for dx, dy in [(0, -1), (1, 0), (0, 1), (-1, 0), (-1, -1), (1, -1), (-1, 1), (1, 1)]: x, y = node.x + dx, node.y + dy if 0 <= x < self.grid_size and 0 <= y < self.grid_size: neighbors.append(self.grid[y][x]) return neighbors def distance(self, node_a, node_b): # Euclidean distance dx = node_a.x - node_b.x dy = node_a.y - node_b.y return math.sqrt(dx*dx + dy*dy) def heuristic(self, node_a, node_b): # Manhattan distance return abs(node_a.x - node_b.x) + abs(node_a.y - node_b.y) def reconstruct_path(self, current): self.path = [] while current: self.path.append(current) current = current.parent self.path.reverse() def handle_click(self, x, y): if self.is_running: return node = self.grid[y][x] if self.current_mode == "start": if node != self.end_node and node.walkable: self.start_node = node elif self.current_mode == "end": if node != self.start_node and node.walkable: self.end_node = node elif self.current_mode == "obstacle": if node != self.start_node and node != self.end_node: node.walkable = False elif self.current_mode == "erase": node.walkable = True if node == self.start_node: self.start_node = None elif node == self.end_node: self.end_node = None self.update() class GridWidget(QWidget): def __init__(self, game): super().__init__() self.game = game self.setMouseTracking(True) def mousePressEvent(self, event): if event.button() == Qt.LeftButton: x = event.x() // self.game.cell_size y = event.y() // self.game.cell_size if 0 <= x < self.game.grid_size and 0 <= y < self.game.grid_size: self.game.handle_click(x, y) def paintEvent(self, event): painter = QPainter(self) painter.setRenderHint(QPainter.Antialiasing) # Draw grid for y in range(self.game.grid_size): for x in range(self.game.grid_size): node = self.game.grid[y][x] rect = (x * self.game.cell_size, y * self.game.cell_size, self.game.cell_size, self.game.cell_size) # Background if node == self.game.start_node: painter.fillRect(*rect, QColor(0, 200, 0)) # Green for start elif node == self.game.end_node: painter.fillRect(*rect, QColor(200, 0, 0)) # Red for end elif not node.walkable: painter.fillRect(*rect, QColor(100, 100, 100)) # Gray for obstacles elif node in self.game.path: painter.fillRect(*rect, QColor(0, 0, 200)) # Blue for path elif node in [n[1] for n in self.game.open_set]: painter.fillRect(*rect, QColor(200, 200, 100)) # Yellow for open set elif node in self.game.closed_set: painter.fillRect(*rect, QColor(200, 150, 150)) # Light red for closed set else: painter.fillRect(*rect, QColor(255, 255, 255)) # White for empty # Grid lines painter.setPen(QPen(QColor(200, 200, 200), 1)) painter.drawRect(*rect) # Display cost values if algorithm is running if self.game.is_running and node.g > 0: painter.setPen(QPen(QColor(0, 0, 0), 1)) painter.setFont(QFont("Arial", 8)) painter.drawText(rect[0] + 2, rect[1] + 12, f"g:{node.g:.1f}") painter.drawText(rect[0] + 2, rect[1] + 24, f"h:{node.h:.1f}") def main(): app = QApplication(sys.argv) game = AStarGame() game.show() sys.exit(app.exec_()) if __name__ == "__main__": main()