Automatyczny_kelner/genetyczny.py

import pygame
import random
import time
import random
import copy

kuchnia_xy = 0
pozycja_startowa = 0
losuj_uklad = False  # Gdy True, losuje uklad stolikow oraz przeszkod

# ------------Ustawienia siatki
blockSize = 60
rows = 14
columns = 24


# -----------------------------Inicjacja klas
class Kelner:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.speed = 80  # od 0 do 100, preferowane 80
        self.stanPrzestrzeni = [0, 0, 0]
        self.stan = "stoi"  # Stan kelnera: stoi, odbiera lub wraca
        self.stolik_docelowy = None  # Stolik, do którego idzie kelner
        self.chodzi = True
        self.cel_x = x
        self.cel_y = y
        self.kierunek = 0  # 0 - północ, 1 - wschód, 2 - południe, 3 - zachód
        self.indexRuchu = 0

    def wklej(self):
        kelnerRotated = pygame.transform.rotate(kelnerImg, -90 * kelner.kierunek)
        screen.blit(kelnerRotated, (self.x * blockSize, self.y * blockSize))

    # def idz_do_stolika(self):
    #     self.cel_x, self.cel_y = self.stolik_docelowy.x, self.stolik_docelowy.y
    #     kelner.stan = "odbiera"

    def idz_do_kuchni(self):
        self.cel_x, self.cel_y = kuchnia_xy, kuchnia_xy
        self.stolik_docelowy = None
        kelner.stan = "wraca"

    def obrot_w_lewo(self):
        self.kierunek = (self.kierunek - 1) % 4
        self.stanPrzestrzeni[2] = (self.stanPrzestrzeni[2] - 1) % 4

    def obrot_w_prawo(self):
        self.kierunek = (self.kierunek + 1) % 4
        self.stanPrzestrzeni[2] = (self.stanPrzestrzeni[2] + 1) % 4

    def idz_do_przodu(self):
        if self.kierunek == 0:
            self.y -= 1
            self.stanPrzestrzeni[1] -= 1
        elif self.kierunek == 1:
            self.x += 1
            self.stanPrzestrzeni[0] += 1
        elif self.kierunek == 2:
            self.y += 1
            self.stanPrzestrzeni[1] += 1
        elif self.kierunek == 3:
            self.x -= 1
            self.stanPrzestrzeni[0] -= 1

    def wykonajAkcje(self, ruchy):
        if self.indexRuchu < len(ruchy):
            akcja = ruchy[self.indexRuchu]
            if akcja == 'F':
                self.idz_do_przodu()
            elif akcja == 'L':
                self.obrot_w_lewo()
            elif akcja == 'R':
                self.obrot_w_prawo()
            self.indexRuchu += 1
            if self.indexRuchu >= len(ruchy):  # Reset po zakończeniu wszystkich ruchów
                self.indexRuchu = 0


class Stolik:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.zamowione = False

    def wklej(self):
        screen.blit(stolikImg, (self.x * blockSize, self.y * blockSize))


class Przeszkoda:
    def __init__(self, x, y, typ):
        self.x = x
        self.y = y
        self.typ = typ

        # ocena kosztu przeszkody
        if self.typ == "sliska podloga":
            self.cena = 2

        elif self.typ == "dywan":
            self.cena = 4

    def wklej(self):
        if self.typ == "sliska podloga":
            screen.blit(sliskaPodlogaImg, (self.x * blockSize, self.y * blockSize))
        elif self.typ == "dywan":
            screen.blit(dywanImg, (self.x * blockSize, self.y * blockSize))


# -----------------Przeszukiwanie przestrzeni stanów

import heapq


def a_star(start, cel, stoliki, przeszkody):
    queue = []  # Kolejka priorytetowa
    heapq.heappush(queue, (0, start))  # (koszt, stan)
    odwiedzone = set([start])
    poprzednicy = {start: (None, None, 0)}  # (poprzedni stan, ruch, koszt do tej pory)

    while queue:
        obecny_koszt, obecny = heapq.heappop(queue)  # pobranie stanu z najniższym kosztem

        if obecny[:2] == cel:
            return odtworz_ruchy(poprzednicy, obecny)

        for nastepnik, ruch, koszt_ruchu in generuj_nastepniki_i_ruchy(obecny, stoliki, przeszkody):
            nowy_koszt = poprzednicy[obecny][2] + koszt_ruchu  # Obliczanie nowego kosztu dojscia do nastepnika

            # nastepnik nie był odwiedzony lub znaleziono tansza sciezke do niego
            if nastepnik not in odwiedzone or nowy_koszt < poprzednicy.get(nastepnik, (None, None, float('inf')))[2]:
                heapq.heappush(queue, (nowy_koszt + heurystyka(nastepnik, cel), nastepnik))
                poprzednicy[nastepnik] = (obecny, ruch, nowy_koszt)
                odwiedzone.add(nastepnik)
    return []


def heurystyka(nastepnik, cel):
    # Oszacowanie sumy odleglosci w pionie i w poziomie
    return abs(nastepnik[0] - cel[0]) + abs(nastepnik[1] - cel[1])


# ----------Funkcja generowania następników dla poszczególnych stanów
def generuj_nastepniki_i_ruchy(stan, stoliki, przeszkody):
    x, y, kierunek = stan
    ruchy = []

    # Obrot w lewo
    nowy_kierunek = (kierunek - 1) % 4
    ruchy.append(((x, y, nowy_kierunek), 'L', 1))

    # Obrot w prawo
    nowy_kierunek = (kierunek + 1) % 4
    ruchy.append(((x, y, nowy_kierunek), 'R', 1))

    # Krok do przodu
    if kierunek == 0:
        nowy_x, nowy_y = x, y - 1
    elif kierunek == 1:
        nowy_x, nowy_y = x + 1, y
    elif kierunek == 2:
        nowy_x, nowy_y = x, y + 1
    elif kierunek == 3:
        nowy_x, nowy_y = x - 1, y

    # sprawdzamy, czy następny stan jest w granicach planszy
    if 0 <= nowy_x < columns and 0 <= nowy_y < rows:
        # sprawdzamy, czy następny stan nie wchodzi w stolik
        if not any(stolik.x == nowy_x and stolik.y == nowy_y for stolik in stoliki):
            koszt = next(
                (przeszkoda.cena for przeszkoda in przeszkody if przeszkoda.x == nowy_x and przeszkoda.y == nowy_y), 1)
            ruchy.append(((nowy_x, nowy_y, kierunek), 'F', koszt))

    return ruchy


# -----Funkcja tworząca listę kroków potrzebnych do uzyskania celu
def odtworz_ruchy(poprzednicy, cel):
    ruchy = []
    krok = cel
    while krok and poprzednicy[krok][0] is not None:
        ruchy.append(poprzednicy[krok][1])
        krok = poprzednicy[krok][0]
    ruchy.reverse()
    return ruchy


start = (0, 0, 0)  # Początkowy stan
cel = (0, 0)  # Docelowe współrzędne

# --------------Inicjacja obiektów
kelner = Kelner(pozycja_startowa, pozycja_startowa)

# -----------wspolrzedne stolikow
coords = ["8 4", "16 4", "0 7", "23 7", "12 9", "8 10", "16 10", "4 12", "12 12", "20 12"]

# -----------wspolrzedne sliskich podlog
coords2 = ["0 2", "0 3", "0 4", "0 5", "4 8", "4 9", "12 2", "12 3", "15 8", "16 8", "19 4", "20 4", "21 4"]

# -----------wspolrzedne dywanow
coords3 = ["6 0", "6 1", "2 2", "3 2", "4 2", "5 2", "1 5", "6 2", "8 6", "8 7", "20 2", "20 3", "19 9", "20 9", "21 9"]

# Tworzenie listy stolikow i przeszkod
stoliki = []
przeszkody = []
if not losuj_uklad:
    for coord in coords:
        x, y = map(int, coord.split())
        stoliki.append(Stolik(x, y))
    for coord in coords2:
        x, y = map(int, coord.split())
        przeszkody.append(Przeszkoda(x, y, "sliska podloga"))
    for coord in coords3:
        x, y = map(int, coord.split())
        przeszkody.append(Przeszkoda(x, y, "dywan"))
else:
    juzbyly = []
    for j in range(1, rows):
        for i in range(columns):
            if (random.randrange(7) == 0) and ((i, j - 1) not in juzbyly) and (
                    ((i - 1, j - 1) not in juzbyly) or ((i + 1, j - 1) not in juzbyly)):
                stoliki.append(Stolik(i, j))
                juzbyly.append((i, j))
            elif random.randrange(9) == 0:
                przeszkody.append(Przeszkoda(i, j, "sliska podloga"))
            elif random.randrange(12) == 0:
                przeszkody.append(Przeszkoda(i, j, "dywan"))

# stoliki = []
# for i in range(rows)

pygame.init()
pygame.display.set_caption("Automatyczny kelner")

# ----------------wymiary okna
width = columns * blockSize
height = rows * blockSize

screen = pygame.display.set_mode((width, height))

kelnerImg = pygame.image.load("kelner.png")
kelnerImg = pygame.transform.scale(kelnerImg, (blockSize, blockSize))
stolikImg = pygame.image.load("stolik.png")
stolikImg = pygame.transform.scale(stolikImg, (blockSize, blockSize))
menuImg = pygame.image.load("menu.png")
menuImg = pygame.transform.scale(menuImg, (blockSize / 2, blockSize / 2))
kitchenImg = pygame.image.load("kitchen.png")
kitchenImg = pygame.transform.scale(kitchenImg, (blockSize * 2, blockSize * 2))
sliskaPodlogaImg = pygame.image.load("plama.png")
sliskaPodlogaImg = pygame.transform.scale(sliskaPodlogaImg, (blockSize, blockSize))
dywanImg = pygame.image.load("dywan.png")
dywanImg = pygame.transform.scale(dywanImg, (blockSize, blockSize))


def kuchnia(x, y):
    screen.blit(kitchenImg, (x * blockSize, y * blockSize))


def menu(x, y):
    screen.blit(menuImg, (x * blockSize, y * blockSize))


def wypiszOkno():
    screen.fill((0, 0, 0))
    for x in range(0, width, blockSize):
        for y in range(0, height, blockSize):
            rect = pygame.Rect(x, y, blockSize, blockSize)
            pygame.draw.rect(screen, (200, 200, 200), rect, 1)  # -------------Wypisz kratę -TA
            # pygame.draw.rect(screen, (0, 0, 0), rect, 1) #-------------Wypisz kratę -TA


pop_size = 100
klient = []
mutacje = 1


def Zamiana(populacja_pref, pokolenie_pref):#---------------------------------------------------------------------------------
    nowe_pokolenie = []
    for i in range(len(pokolenie_pref)):
        if populacja_pref[i][-1] < pokolenie_pref[i][-1]:
            nowe_pokolenie.append(pokolenie_pref[i][0:-1])
        elif populacja_pref[i][-1] >= pokolenie_pref[i][-1]:
            nowe_pokolenie.append(populacja_pref[i][0:-1])
    return nowe_pokolenie
def Mutacje(dzieci):
    nowe_pokolenie = []
    nowe_pokolenie1 = []
    x = 0
    ryba = []
    ryba.append("nic")
    mieso = []
    mieso.append("nic")
    deser = []
    deser.append("nic")
    napoj = []
    napoj.append("nic")
    for x in range(len(klient)):
        if klient[x]["typ"] == "ryba":
            ryba.append(klient[x]["nazwa"])
        elif klient[x]["typ"] == "mieso":
            mieso.append(klient[x]["nazwa"])
        elif klient[x]["typ"] == "deser":
            deser.append(klient[x]["nazwa"])
        elif klient[x]["typ"] == "napoj":
            napoj.append(klient[x]["nazwa"])

    for a in dzieci:
        for b in range(len(a)):
            if random.randrange(0, 10) < mutacje:
                if b == 0:
                    a[b] = random.choice(ryba)
                if b == 1:
                    a[b] = random.choice(mieso)
                if b == 2:
                    a[b] = random.choice(deser)
                if b == 3:
                    a[b] = random.choice(napoj)
        nowe_pokolenie.append(a)
    return nowe_pokolenie

def Krzyzowanie(populacja, top):
    dzieci = []
    for i in range(len(populacja)):
        r1 = random.choice(top)
        r2 = random.choice(populacja)
        rodzic1 = r1[0:-1]
        rodzic2 = r2[0:-1]
        crossover_point = random.randint(1, len(populacja[0])-2)
        dziecko = rodzic1[:crossover_point] + rodzic2[crossover_point:]
        if dziecko not in dzieci:
            dzieci.append(dziecko)
    nowe_pokolenie = Mutacje(dzieci)
    return nowe_pokolenie

def LiczZadowolenie(klient, populacja):
    preferencje = []
    for x in populacja:
        satysfakcja = 0
        for y in x:
            for a in range(len(klient)):
                if klient[a]["nazwa"] == y:
                    satysfakcja = satysfakcja + klient[a]["popularnosc"]
        d2 = copy.deepcopy(x)
        d2.append(satysfakcja)
        preferencje.append(d2)
    return preferencje

def UsunZleChromosomy(klient, chromosomy, budzet):
    populacja = []
    for chromosom in chromosomy:
        suma = 0
        cena = 0
        for y in chromosom:
            for a in range(len(klient)):
                if klient[a]["nazwa"] == y:
                    cena = klient[a]["cena"]
                    suma = suma + cena
                elif y == "nic":
                    cena = 0
                    suma = suma + cena
        if(suma<=budzet):
            populacja.append(chromosom)
    return populacja

def UtworzPopulacje(klient, budzet):
    ryba = []
    ryba.append("nic")
    mieso = []
    mieso.append("nic")
    deser = []
    deser.append("nic")
    napoj = []
    napoj.append("nic")
    x = 0
    for x in range(len(klient)):
        if klient[x]["typ"] == "ryba":
            ryba.append(klient[x]["nazwa"])
        elif klient[x]["typ"] == "mieso":
            mieso.append(klient[x]["nazwa"])
        elif klient[x]["typ"] == "deser":
            deser.append(klient[x]["nazwa"])
        elif klient[x]["typ"] == "napoj":
            napoj.append(klient[x]["nazwa"])
    chromosomy = []
    for i in range(pop_size):
        chromosom = []
        chromosom.append(ryba[random.randint(0, len(ryba)-1)])
        chromosom.append(mieso[random.randint(0, len(mieso)-1)])
        chromosom.append(deser[random.randint(0, len(deser)-1)])
        chromosom.append(napoj[random.randint(0, len(napoj)-1)])
        if chromosom not in chromosomy:
            chromosomy.append(chromosom)
    populacja = UsunZleChromosomy(klient, chromosomy, budzet)
    print("Budzet klienta: " + str(budzet))
    return populacja

def Algorytm_genetyczny(populacja, budzet, gen, klient):
    populacja_pref = LiczZadowolenie(klient, populacja)
    top = []
    for x in populacja_pref:
        d2 = copy.deepcopy(x)
        top.append(d2)
    top.sort(key=lambda x: x[4], reverse = True)
    for i in range (int(len(top)/2)):
        top.pop()
    pokolenie = Krzyzowanie(populacja_pref, top)
    pokolenie1 = UsunZleChromosomy(klient, pokolenie, budzet)
    pokolenie_pref = LiczZadowolenie(klient, pokolenie1)
    nowe_pokolenie = Zamiana(populacja_pref, pokolenie_pref)
    if gen == 3:
        print("Najlepsze dopasowanie: " + str(top[0]))
    return nowe_pokolenie

def najlepszeDopasowanie():
    pop_size = 100
    klient = []
    dania = [
        {"nazwa": "Losos", "typ": "ryba", "cena": 50, "popularnosc": 45},
        {"nazwa": "Sledz", "typ": "ryba", "cena": 28, "popularnosc": 28},
        {"nazwa": "Karp", "typ": "ryba", "cena": 43, "popularnosc": 45},
        {"nazwa": "Tunczyk", "typ": "ryba", "cena": 53, "popularnosc": 46},
        {"nazwa": "Dorsz", "typ": "ryba", "cena": 42, "popularnosc": 45},
        {"nazwa": "Pstrag", "typ": "ryba", "cena": 34, "popularnosc": 38},
        {"nazwa": "Makrela", "typ": "ryba", "cena": 40, "popularnosc": 44},
        {"nazwa": "Kaczka", "typ": "mieso", "cena": 32, "popularnosc": 30},
        {"nazwa": "Kurczak", "typ": "mieso", "cena": 27, "popularnosc": 29},
        {"nazwa": "Indyk", "typ": "mieso", "cena": 31, "popularnosc": 32},
        {"nazwa": "Wieprzowina", "typ": "mieso", "cena": 20, "popularnosc": 25},
        {"nazwa": "Wolowina", "typ": "mieso", "cena": 25, "popularnosc": 28},
        {"nazwa": "Krolik", "typ": "mieso", "cena": 36, "popularnosc": 33},
        {"nazwa": "Stek", "typ": "mieso", "cena": 37, "popularnosc": 35},
        {"nazwa": "Tiramisu", "typ": "deser", "cena": 27, "popularnosc": 40},
        {"nazwa": "Ciasto", "typ": "deser", "cena": 24, "popularnosc": 33},
        {"nazwa": "Gofry", "typ": "deser", "cena": 23, "popularnosc": 35},
        {"nazwa": "Sernik", "typ": "deser", "cena": 19, "popularnosc": 30},
        {"nazwa": "Churros", "typ": "deser", "cena": 35, "popularnosc": 50},
        {"nazwa": "Pudding", "typ": "deser", "cena": 29, "popularnosc": 42},
        {"nazwa": "Lody", "typ": "deser", "cena": 20, "popularnosc": 33},
        {"nazwa": "Herbata", "typ": "napoj", "cena": 15, "popularnosc": 25},
        {"nazwa": "Sok", "typ": "napoj", "cena": 18, "popularnosc": 30},
        {"nazwa": "Kawa", "typ": "napoj", "cena": 20, "popularnosc": 30},
        {"nazwa": "Lemoniada", "typ": "napoj", "cena": 16, "popularnosc": 29},
        {"nazwa": "Mirinda", "typ": "napoj", "cena": 14, "popularnosc": 27},
        {"nazwa": "Woda", "typ": "napoj", "cena": 8, "popularnosc": 14},
        {"nazwa": "Pepsi", "typ": "napoj", "cena": 16, "popularnosc": 28}
    ]

    mnoznik_ryba = random.randint(1, 8) * 0.25  # -----------------------preferencje klienta
    mnoznik_mieso = random.randint(1, 8) * 0.25
    mnoznik_deser = random.randint(1, 8) * 0.25
    mnoznik_napoj = random.randint(1, 8) * 0.25
    budzet = random.randint(100, 200)

    pop_size = 100  # --------------------------------------------liczba chromosomow w populacji
    mutacje = 1  # ------------------------------------------------od 0 do 10
    print("Preferencje klienta: Ryba: " + str(mnoznik_ryba) + "; Mieso: " + str(mnoznik_mieso) + "; Deser: " + str(
        mnoznik_deser) + "; Napoj: " + str(mnoznik_napoj))

    for x in dania:
        d2 = copy.deepcopy(x)
        klient.append(d2)

    for i in range(len(dania)):
        if klient[i]["typ"] == "ryba":
            klient[i]["popularnosc"] = klient[i]["popularnosc"] * mnoznik_ryba
        if klient[i]["typ"] == "mieso":
            klient[i]["popularnosc"] = klient[i]["popularnosc"] * mnoznik_mieso
        if klient[i]["typ"] == "deser":
            klient[i]["popularnosc"] = klient[i]["popularnosc"] * mnoznik_deser
        if klient[i]["typ"] == "napoj":
            klient[i]["popularnosc"] = klient[i]["popularnosc"] * mnoznik_napoj

    populacja = UtworzPopulacje(klient, budzet)
    gen = 0
    for i in range(3):
        gen = gen + 1
        populacja_pom = Algorytm_genetyczny(populacja, budzet, gen, klient)
        populacja = populacja_pom

run = True

# czcionka = pygame.font.SysFont('Arial',50)

licznik = 0
ruchy = []
cel2 = []

while run:
    cel2 = list(cel)

    # print(f"{kelner.stanPrzestrzeni}, {cel2}, {kelner.indexRuchu} {kelner.stan}")
    wypiszOkno()
    kuchnia(kuchnia_xy, kuchnia_xy)

    for stolik in stoliki:
        stolik.wklej()

    for przeszkoda in przeszkody:
        przeszkoda.wklej()

    kelner.wklej()

    if kelner.stan == "wraca":
        menu(kelner.x, kelner.y)

    licznik += 1

    # ------------weź zamowienie
    for stolik in stoliki:
        if stolik.zamowione == True:
            menu(stolik.x, stolik.y)
            if kelner.stan == "stoi":
                kelner.stolik_docelowy = stolik
                kelner.cel_x, kelner.cel_y = kelner.stolik_docelowy.x, kelner.stolik_docelowy.y - 1
                cel = (kelner.cel_x, kelner.cel_y)
                print("Szukam ścieżki do stolika...")
                ruchy = a_star(tuple(kelner.stanPrzestrzeni), cel, stoliki, przeszkody)
                kelner.stan = "odbiera"
                if ruchy:
                    print("Znaleziono ścieżkę ruchów: ", ruchy)
                    najlepszeDopasowanie()
                else:
                    print("Nie znaleziono ścieżki do celu.")

    # ----------Losuje stoliki, które dokonają zamówienia
    if kelner.stan == "stoi":
        for stolik in stoliki:
            if stolik.zamowione == True:
                break
        for i in range(len(stoliki)):
            if random.randrange(2) == 1:
                stoliki[i].zamowione = True

    # print(kelner.stan)--------------------------Wypisuje stan kelnera
    # print(f"{kelner.x} {kelner.y}")-------------Wypisuje wspolrzedne kelnera

    # ----------------Zmiana pozycji kelnera
    if kelner.chodzi == True and licznik % (101 - kelner.speed) == 0 and kelner.stanPrzestrzeni[
                                                                         :2] != cel2:  # ograniczenie prędkości
        kelner.wykonajAkcje(ruchy)

    if kelner.stanPrzestrzeni[:2] == cel2:
        if kelner.stan == "odbiera" and kelner.x == kelner.stolik_docelowy.x and kelner.y == kelner.stolik_docelowy.y - 1:
            kelner.stolik_docelowy.zamowione = False
            kelner.idz_do_kuchni()
            cel = (kelner.cel_x, kelner.cel_y)
            print("Szukam ścieżki do kuchni...")
            ruchy = a_star(tuple(kelner.stanPrzestrzeni), cel, stoliki, przeszkody)
            if ruchy:
                print("Znaleziono ścieżkę ruchów: ", ruchy)
            else:
                print("Nie znaleziono ścieżki do celu.")
        elif kelner.stan == "wraca" and kelner.x == kuchnia_xy and kelner.y == kuchnia_xy:
            kelner.stan = "stoi"

    time.sleep(0.001)

    key = pygame.key.get_pressed()
    pygame.display.update()
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            run = False
pygame.quit()