AntAlgorithm.py

from Algorithm import Algorithm
from Labyrinth import LABYRINTH_SIZE
from WinStatistics import Statistics

import numpy as np
import random
import math
import time
#należy napisać algorytm by był przystosowany do wywołania konstruktora i nextStep
#klasa window ma pola:  labyrinth.board[y][x], gdzie 1 - ściana, 0 - pole
#                       labyrinth.exit, które ma pola exit.x i exit.y
#                       exit defaultowo znajduje się w prawym-górnym rogu czyli (LABYRINTH_SIZE-1, 0) LABYRINTH_SIZE znajduje się w Labyrinth.py
#                       start defaultowo uznaje się za (0, LABYRINTH_SIZE-1)
#                       labirynt wyświetalny w oknie jest wczytywany zawsze z "save.txt" można to sparametryzować później

class Ant:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.recent_tiles = [(x, y)]
        self.visited = set(self.recent_tiles)
        self.visited_counter =0

    def move(self, next_tile):
        self.x, self.y = next_tile
        self.recent_tiles.append(next_tile)

        visited_length = len(self.visited)
        self.visited.add(next_tile)
        if len(self.visited) == visited_length:
            self.visited_counter += 1
            if self.visited_counter > 15:
                self.x = 0
                self.y = LABYRINTH_SIZE - 1
                self.visited.clear()
                self.visited_counter = 0
                self.recent_tiles.clear()

        

        # if len(self.recent_tiles) > 10:
        #     self.recent_tiles.pop(0)

class AntAlgorithm(Algorithm):
    def __init__(self, window):
        super().__init__(window)
        print("Hello from Ant file")
        self.adj_list = self.board_to_adjecency_list()
        self.color = (100, 100, 0)

        self.pheromone = self.initialize_pheromone()
        self.alpha = 1.0
        self.beta = 5.0
        self.evaporation_rate = 0.02
        self.pheromone_deposit = 100
        self.winning_paths = []

        self.ant_count = 10
        self.ants = []
        for i in range(self.ant_count):
            ant_x = 0
            ant_y = LABYRINTH_SIZE - 1
            self.ants.append(Ant(ant_x, ant_y))
            self.window.updateBoard(ant_x, ant_y, color="#57D457")

        self.stats = Statistics(self.window.labyrinth.board)

    def initialize_pheromone(self):
        pheromone = {}
        for y in range(LABYRINTH_SIZE):
            for x in range(LABYRINTH_SIZE):
                if self.window.labyrinth.board[y][x] == 0:
                    pheromone[(x, y)] = 2.0
        return pheromone
    
    def choose_next_tile(self, tile, ant_index):
        neighbors = self.adj_list[tile]
        if neighbors is None:
            return None        
        
        # print(len(self.ants[ant_index].visited))
        unvisited_neighbors = [n for n in neighbors if n not in self.ants[ant_index].visited]
        if unvisited_neighbors:
            neighbors = unvisited_neighbors
        
        probabilities = []
        pheromone_level = 0
        heuristic = 0
        for neighbor in neighbors:
            pheromone_level = self.pheromone[neighbor]
            diagonal_distance = abs(neighbor[0] - neighbor[1])
            heuristic = 1 / ((abs(neighbor[0] - self.window.labyrinth.exit.x) + abs(neighbor[1] - self.window.labyrinth.exit.y)) ** 2 + diagonal_distance**2 + 1)

            if neighbor in self.ants[ant_index].recent_tiles:
                pheromone_level *= 0.6

            probabilities.append((pheromone_level ** self.alpha) + (heuristic ** self.beta))

        total = sum(probabilities)
        probabilities = [p / total for p in probabilities]

        if random.random() < 0.15:
            return random.choice(neighbors)

        return random.choices(neighbors, weights=probabilities, k=1)[0]
    
    def update_pheromone(self, path):
        for tile in path:
            dist = math.sqrt((tile[0] - self.window.labyrinth.exit.x) ** 2 + (tile[1] - self.window.labyrinth.exit.y) ** 2)
            if dist == 0:
                dist = 1
            self.pheromone[tile] += self.pheromone_deposit / dist

    def evaporate_pheromones(self):
        for tile in self.pheromone:
            dist = math.sqrt((tile[0] - self.window.labyrinth.exit.x) ** 2 + (tile[1] - self.window.labyrinth.exit.y) ** 2)
            self.pheromone[tile] = self.pheromone[tile] * (1 - self.evaporation_rate) / (dist + 1)
        
    # 0, 0 is in the top left corner
    def board_to_adjecency_list(self):
        adj_list = {}
        for y in range(LABYRINTH_SIZE):
            for x in range(LABYRINTH_SIZE):
                adj_list[(x, y)] = []
                if self.window.labyrinth.board[y][x] == 1:
                    adj_list[(x, y)] = None
                else:
                    if x > 0 and self.window.labyrinth.board[y][x-1] == 0:
                        adj_list[(x, y)].append((x-1, y))
                    if x < LABYRINTH_SIZE - 1 and self.window.labyrinth.board[y][x+1] == 0:
                        adj_list[(x, y)].append((x+1, y))
                    if y > 0 and self.window.labyrinth.board[y-1][x] == 0:
                        adj_list[(x, y)].append((x, y-1))
                    if y < LABYRINTH_SIZE - 1 and self.window.labyrinth.board[y+1][x] == 0:
                        adj_list[(x, y)].append((x, y+1))
        return adj_list

    def nextStep(self, ant_index=0, run=False, iteration=0):
        if iteration > 50:
            return
        current_tile = (self.ants[ant_index].x, self.ants[ant_index].y)

        if current_tile == (self.window.labyrinth.exit.x, self.window.labyrinth.exit.y):
            self.window.updateLogs1(f"Ant {ant_index - 1} already reached the exit!")
            return

        next_tile = self.choose_next_tile(current_tile, ant_index)
        if not next_tile:
            self.window.updateLogs1("No valid moves available, algorithm failed.")
            return

        self.ants[ant_index].move(next_tile)
        if not run:
            self.window.updateBoard(current_tile[0], current_tile[1], color="#DFFFDC")
            self.window.updateBoard(next_tile[0], next_tile[1], color="#57D457")

            #self.window.updateLogs2(f"Ant {ant_index} moved to {next_tile}")
        
        self.update_pheromone(self.ants[ant_index].recent_tiles)
        self.evaporate_pheromones()
        if not run:
            self.window.root.after(30, self.nextStep, ant_index, False, iteration + 1)

        else:
            self.nextStep(ant_index=ant_index, iteration=iteration+1, run=True)

    def run(self):
        self.winning_paths = []
        running = True
        while running:
            for ant_index in range(self.ant_count):
                self.nextStep(ant_index, run=True, iteration=50)
                ant = self.ants[ant_index]
                if (ant.x, ant.y) == (self.window.labyrinth.exit.x, self.window.labyrinth.exit.y):
                    self.window.updateLogs1(f"Ant {ant_index} reached the exit!")
                    print(f"Ant {ant_index} reached the exit!")
                    
                    # Record the winning path for heatmap
                    self.winning_paths.append(list(ant.recent_tiles))
                    
                    # Draw the path
                    #for (x, y) in ant.recent_tiles:
                    #    self.window.updateBoard(x, y, color="#46901E")
                    
                    running = self.stats.record_win(ant.recent_tiles)

                    path_len = len(ant.recent_tiles)
                    for tile in ant.recent_tiles:
                        self.pheromone[tile] += self.pheromone_deposit / (path_len ** 3) * 200

                    ant.visited.clear()
                    ant.visited_counter = 0
                    ant.recent_tiles.clear()
                    ant.move((0, LABYRINTH_SIZE - 1))
        self.display_heatmap_on_board()

    def generate_heatmap(self):
        import numpy as np
        heatmap = np.zeros((LABYRINTH_SIZE, LABYRINTH_SIZE), dtype=int)
        
        for path in self.winning_paths:
            for (x, y) in path:
                heatmap[y, x] += 1  # increment heatmap cell counts
                
        return heatmap
    def display_heatmap_on_board(self):

        heatmap = self.generate_heatmap()
        max_heat = np.max(heatmap)
        if max_heat == 0:
            max_heat = 1  # avoid division by zero

        for y in range(LABYRINTH_SIZE):
            for x in range(LABYRINTH_SIZE):
                if self.window.labyrinth.board[y][x] == 0:  # only paths, skip walls
                    intensity = heatmap[y, x] / max_heat  # normalize 0..1
                    if intensity == 0:
                        color = "#FFFFFF"  # white for never used paths
                    else:
                        # Map intensity to green color brightness (lighter to darker green)
                        green_val = int(50 + 205 * intensity)  # from 50 to 255
                        color = f"#{0:02X}{green_val:02X}{0:02X}"  # RGB, red=0, green varies, blue=0
                    self.window.updateBoard(x, y, color=color)