objects.py

import pygame
from settings import *
import time
import math
from queue import PriorityQueue

class Cell():
    def __init__(self, x, y, tilesize):
        self.x = x * tilesize
        self.y = y * tilesize
        
        self.visited = False
        self.current = False
        self.start = False
        self.end = False
        self.searched = False
        self.path = False
        self.parent = None
        
        self.walls = [True, True, True, True]  # top, right, bottom, left
        self.neighbors = []
        
        self.top = 0
        self.right = 0
        self.bottom = 0
        self.left = 0
        self.next_cell = 0

    def removeWalls(self, next_cell, tilesize):
        x = int(self.x / tilesize) - int(next_cell.x / tilesize)
        y = int(self.y / tilesize) - int(next_cell.y / tilesize)
        if y == 1:  # top
            self.walls[0] = False
            next_cell.walls[2] = False
        elif x == -1:  # right
            self.walls[1] = False
            next_cell.walls[3] = False
        elif y == -1:  # bottom
            self.walls[2] = False
            next_cell.walls[0] = False
        elif x == 1:  # left
            self.walls[3] = False
            next_cell.walls[1] = False


    def addNeighbors(self, tilesize):
        if self.top and not self.walls[0] and not self.top.walls[2] and not self.top.searched:
            self.neighbors.append(self.top)
        if self.right and not self.walls[1] and not self.right.walls[3] and not self.right.searched:
            self.neighbors.append(self.right)
        if self.bottom and not self.walls[2] and not self.bottom.walls[0] and not self.bottom.searched:
            self.neighbors.append(self.bottom)
        if self.left and not self.walls[3] and not self.left.walls[1] and not self.left.searched:
            self.neighbors.append(self.left)
            
    def draw(self, tilesize):
        if self.end:
            pygame.draw.rect(screen, RED, (self.x, self.y, tilesize, tilesize))
        elif self.start or self.path:
            pygame.draw.rect(screen, GREEN, (self.x, self.y, tilesize, tilesize))
        elif self.searched:
            pygame.draw.rect(screen, SEARCHED, (self.x, self.y, tilesize, tilesize))
        elif self.current:
            pygame.draw.rect(screen, CURRENT, (self.x, self.y, tilesize, tilesize))
        elif self.visited:
            pygame.draw.rect(screen, WHITE, (self.x, self.y, tilesize, tilesize))
        
        if self.walls[0]:
            pygame.draw.line(screen, BLACK, (self.x, self.y), ((self.x + tilesize), self.y), 1)  # top
        if self.walls[1]:
            pygame.draw.line(screen, BLACK, ((self.x + tilesize), self.y), ((self.x + tilesize), (self.y + tilesize)), 1)  # right
        if self.walls[2]:
            pygame.draw.line(screen, BLACK, ((self.x + tilesize), (self.y + tilesize)), (self.x, (self.y + tilesize)), 1)  # bottom
        if self.walls[3]:
            pygame.draw.line(screen, BLACK, (self.x, (self.y + tilesize)), (self.x, self.y), 1)  # left

class Grid():
    def __init__(self, rows, cols, algo):
        self.grid = [[Cell(x, y, WIDTH // rows) for x in range(cols)] for y in range(rows)]
        self.bfs_cost = 0
        self.dfs_cost = 0
        self.a_star_cost = 0
        self.algo = algo

    def reset_grid(self, tilesize):
        self.dfs_cost = 0
        self.a_star_cost = 0
        self.bfs_cost = 0
        for i in self.grid:
            for j in i:
                j.searched = False
                j.current = False
                j.parent = None
                j.neighbors = []
                j.draw(tilesize)

    def draw_path_line(self, path, tilesize):
        if len(path) < 2:
            return

        for i in range(len(path) - 1):
            cell1 = path[i]
            cell2 = path[i + 1]
            x1 = cell1.x + tilesize // 2
            y1 = cell1.y + tilesize // 2
            x2 = cell2.x + tilesize // 2
            y2 = cell2.y + tilesize // 2
            pygame.draw.line(screen, (0, 255, 0), (x1, y1), (x2, y2), tilesize // 10)
            pygame.display.update()
            time.sleep(0.02)

    def heuristic(self, a, b):
        return abs(a.x - b.x) + abs(a.y - b.y)

    def a_star(self, current, solution, tilesize):
        g_score = {current: 0}

        pq = PriorityQueue()
        pq.put((0, random.random(), current))
        solution = []

        while not pq.empty():
            node = pq.get()[2]
            node.addNeighbors(tilesize)
            neighbors = node.neighbors
            node.searched = True
            node.draw(tilesize)
            self.a_star_cost += 1
            time.sleep(0.04)
            pygame.display.update()

            if node.end:
                while node:
                    solution.append(node)
                    node = node.parent

                break

            for neighbor in neighbors:
                tentative_g = g_score[node] + 1
                if tentative_g < g_score.get(neighbor, float('inf')):
                    g_score[neighbor] = tentative_g
                    neighbor.parent = node
                    f_score = tentative_g + self.heuristic(neighbor, self.grid[len(self.grid) - 1][len(self.grid[0]) - 1])
                    pq.put((f_score, random.random(), neighbor))

        return solution, self.a_star_cost


    def iterative_bfs(self, current, solution, tilesize):
        solution = []
        queue = [current]
        visited = [current]

        while queue:
            self.bfs_cost += 1
            time.sleep(0.04)
            node = queue.pop(0)

            node.searched = True
            node.draw(tilesize)
            pygame.display.update()
            node.addNeighbors(tilesize)
            
            if node.end:
                solution.append(node)
                while node:
                    solution.append(node)
                    node = node.parent
                break

            for neighbour in node.neighbors:
                if neighbour not in visited:
                    neighbour.parent = node
                    queue.append(neighbour)
                    visited.append(neighbour)

        return solution, self.bfs_cost

    def recursive_dfs(self, current, solution, tilesize):
        self.dfs_cost += 1
        time.sleep(0.04)
        current.searched = True
        current.draw(tilesize)
        current.addNeighbors(tilesize)

        pygame.display.update()

        if current.end:
            return solution, self.dfs_cost

        for neighbor in current.neighbors:
            result = self.recursive_dfs(neighbor, solution + [neighbor], tilesize)
            if result:
                return result
        
        return None
    
    def checkNeighbors(self, current_cell, tilesize, rows, cols):
        if int(current_cell.y / tilesize) - 1 >= 0:
            current_cell.top = self.grid[int(current_cell.y / tilesize) - 1][int(current_cell.x / tilesize)]
        if int(current_cell.x / tilesize) + 1 <= cols - 1:
            current_cell.right = self.grid[int(current_cell.y / tilesize)][int(current_cell.x / tilesize) + 1]
        if int(current_cell.y / tilesize) + 1 <= rows - 1:
            current_cell.bottom = self.grid[int(current_cell.y / tilesize) + 1][int(current_cell.x / tilesize)]
        if int(current_cell.x / tilesize) - 1 >= 0:
            current_cell.left = self.grid[int(current_cell.y / tilesize)][int(current_cell.x / tilesize) - 1]
        
        if current_cell.top and not current_cell.top.visited:
            current_cell.neighbors.append(current_cell.top)
        if current_cell.right and not current_cell.right.visited:
            current_cell.neighbors.append(current_cell.right)
        if current_cell.bottom and not current_cell.bottom.visited:
            current_cell.neighbors.append(current_cell.bottom)
        if current_cell.left and not current_cell.left.visited:
            current_cell.neighbors.append(current_cell.left)
        
        if current_cell.neighbors:
            current_cell.next_cell = random.choice(current_cell.neighbors)
            return current_cell.next_cell
        
        return False