app.py

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()