from state_space_search import graphsearch, generate_cost_map
import random

# Parametry algorytmu genetycznego
POPULATION_SIZE = 700
MUTATION_RATE = 0.01
NUM_GENERATIONS = 600

# Generowanie początkowej populacji
def generate_individual(animals):
    return random.sample(animals, len(animals))

def generate_population(animals, size):
    return [generate_individual(animals) for _ in range(size)]

# Obliczanie odległości między zwierzetami
def calculate_distance(animal1, animal2):
    x1, y1 = animal1
    x2, y2 = animal2
    return abs(x1 - x2) + abs(y1 - y2) # Odległość Manhattana

def calculate_total_distance(animals):
    total_distance = 0
    for i in range(len(animals) - 1):
        total_distance += calculate_distance(animals[i], animals[i+1])
    total_distance += calculate_distance(animals[-1], animals[0])  # Zamknięcie cyklu
    return total_distance

# Selekcja rodziców za pomocą metody ruletki
def select_parents(population, num_parents):
    fitness_scores = [1 / calculate_total_distance(individual) for individual in population]
    total_fitness = sum(fitness_scores)
    selection_probs = [fitness / total_fitness for fitness in fitness_scores]

    parents = random.choices(population, weights=selection_probs, k=num_parents)
    return parents

# Krzyżowanie rodziców (OX,Davis)
def crossover(parent1, parent2):
    child1 = [None] * len(parent1)
    child2 = [None] * len(parent1)
    start_index = random.randint(0, len(parent1) - 1)
    end_index = random.randint(start_index, len(parent1) - 1)
    child1[start_index:end_index+1] = parent1[start_index:end_index+1]
    child2[start_index:end_index+1] = parent2[start_index:end_index+1]

    # Uzupełnienie brakujących zwierząt z drugiego rodzica
    for i in range(len(parent1)):
        if parent2[i] not in child1:
            for j in range(len(parent2)):
                if child1[j] is None:
                    child1[j] = parent2[i]
                    break

    for i in range(len(parent1)):
        if parent1[i] not in child2:
            for j in range(len(parent1)):
                if child2[j] is None:
                    child2[j] = parent1[i]
                    break

    return child1, child2

# Mutacja: zamiana dwóch losowych zwierząt z prawdopodobieństwem MUTATION_RATE
def mutate(individual):
    if random.random() < MUTATION_RATE:
        index1, index2 = random.sample(range(len(individual)), 2)
        individual[index1], individual[index2] = individual[index2], individual[index1]

# Algorytm genetyczny
def genetic_algorithm(animals):
    population = generate_population(animals, POPULATION_SIZE)

    for generation in range(NUM_GENERATIONS):
        # Selekcja rodziców
        parents = select_parents(population, POPULATION_SIZE // 2)

        # Krzyżowanie i tworzenie nowej populacji
        next_generation = []
        for i in range(0, len(parents), 2):
            parent1 = parents[i]
            if i + 1 < len(parents):
                parent2 = parents[i + 1]
            else:
                parent2 = parents[0]
            child1, child2 = crossover(parent1, parent2)
            next_generation.extend([child1, child2])

        # Mutacja nowej populacji
        for individual in next_generation:
            mutate(individual)

        # Zastąpienie starej populacji nową
        population = next_generation

    # Znalezienie najlepszego osobnika
    best_individual = min(population, key=calculate_total_distance)

    return best_individual

# def calculate_distance(start, goal, max_x, max_y, obstacles, cost_map):
#     istate = (start[0], start[1], 'N')  # Zakładamy, że zaczynamy od kierunku północnego
#     actions, cost = graphsearch(istate, goal, max_x, max_y, obstacles, cost_map)
#     return cost

# def calculate_total_distance(animals, max_x, max_y, obstacles, cost_map):
#     total_distance = 0
#     for i in range(len(animals) - 1):
#         total_distance += calculate_distance(animals[i], animals[i+1], max_x, max_y, obstacles, cost_map)
#     total_distance += calculate_distance(animals[-1], animals[0], max_x, max_y, obstacles, cost_map)  # Zamknięcie cyklu
#     return total_distance

# # Selekcja rodziców za pomocą metody ruletki
# def select_parents(population, num_parents, max_x, max_y, obstacles, cost_map):
#     fitness_scores = [1 / calculate_total_distance(individual, max_x, max_y, obstacles, cost_map) for individual in population]
#     total_fitness = sum(fitness_scores)
#     selection_probs = [fitness / total_fitness for fitness in fitness_scores]

#     parents = random.choices(population, weights=selection_probs, k=num_parents)
#     return parents


# def genetic_algorithm(animals, max_x, max_y, obstacles, cost_map):
#     population = generate_population(animals, POPULATION_SIZE)

#     for generation in range(NUM_GENERATIONS):
#         # Selekcja rodziców
#         parents = select_parents(population, POPULATION_SIZE // 2, max_x, max_y, obstacles, cost_map)

#         # Krzyżowanie i tworzenie nowej populacji
#         next_generation = []
#         for i in range(0, len(parents), 2):
#             parent1 = parents[i]
#             parent2 = parents[i + 1]
#             child1, child2 = crossover(parent1, parent2)
#             next_generation.extend([child1, child2])

#         # Mutacja nowej populacji
#         for individual in next_generation:
#             mutate(individual)

#         # Zastąpienie starej populacji nową
#         population = next_generation

#     # Znalezienie najlepszego osobnika
#     best_individual = min(population, key=lambda individual: calculate_total_distance(individual, max_x, max_y, obstacles, cost_map))

#     return best_individual