125 lines
3.5 KiB
Python
125 lines
3.5 KiB
Python
from enum import Enum
|
|
|
|
from typing import Tuple, Dict
|
|
|
|
class GridCellType(Enum):
|
|
FREE = 0
|
|
REGAL = 1
|
|
# dodać oznaczenie na miejsce dla paczek
|
|
|
|
class SearchSpace:
|
|
grid: Dict[Tuple[int, int], GridCellType] = {}
|
|
|
|
def __init__(self) -> None:
|
|
self._init_grid()
|
|
|
|
def _init_grid(self) -> None:
|
|
for i in range (0,10):
|
|
for j in range(0,10):
|
|
self.grid[(i, j)] = GridCellType.FREE
|
|
for r, c in [(2,2), (2,3), (3,2), (3,3), (8,2), (8,3), (9,2), (9,3),
|
|
(2,8), (2,9), (3,8), (3,9), (8,8), (8,9), (9,8), (9,9)]:
|
|
self.grid[(r,c)] = GridCellType.REGAL
|
|
|
|
class Stan:
|
|
def __init__(self, x, y, kierunek):
|
|
self.x = x
|
|
self.y = y
|
|
self.kierunek = kierunek
|
|
|
|
|
|
class Wezel:
|
|
def __init__(self, stan: Stan, akcja = None, parent = None):
|
|
self.stan = stan
|
|
self.akcja = akcja
|
|
self.parent = parent
|
|
|
|
class Search:
|
|
def __init__(self, search_grid: SearchSpace):
|
|
self.search_grid = search_grid
|
|
|
|
def wyszukiwanie_bfs(self, stan_poczatkowy: Stan, stan_docelowy: Stan):
|
|
pierwszy_wezel = Wezel(stan_poczatkowy)
|
|
fringe = [pierwszy_wezel]
|
|
|
|
odwiedzone = []
|
|
|
|
while fringe:
|
|
wezel = fringe.pop(0)
|
|
|
|
if self.goal_test(state = wezel.stan, goal_state = stan_docelowy):
|
|
return self.get_actions(wezel)
|
|
|
|
odwiedzone.append(wezel.stan)
|
|
|
|
for akcja, stan in self.nastepnik(wezel):
|
|
if wezel not in fringe and stan not in odwiedzone:
|
|
x_node = Wezel(stan, akcja, wezel)
|
|
fringe.append(x_node)
|
|
return False
|
|
|
|
def goal_test(self, state: Stan, goal_state: Stan):
|
|
if state.x == goal_state.x and state.y == goal_state.y:
|
|
return True
|
|
else:
|
|
return False
|
|
|
|
def nastepnik(self, wezel: Wezel):
|
|
# gora -> prawo -> dol -> lewo | obrot w prawo
|
|
# gora -> lewo -> dol -> prawo | obrot w lewo
|
|
# 0 gora 1 prawo 2 dol 3 lewo
|
|
state = wezel.stan
|
|
|
|
stan_prawego = Stan(state.x, state.y,(state.kierunek + 1) % 4)
|
|
ruch_w_prawo = ["Prawo", stan_prawego]
|
|
|
|
stan_lewego = Stan(state.x, state.y, 3 if state.kierunek == 0 else state.kierunek - 1)
|
|
ruch_w_lewo = ["Lewo", stan_lewego]
|
|
|
|
nodes = [ruch_w_prawo, ruch_w_lewo]
|
|
|
|
y = state.x
|
|
x = state.y
|
|
|
|
if wezel.stan.kierunek == 0:
|
|
y -= 1
|
|
elif wezel.stan.kierunek == 1:
|
|
x += 1
|
|
elif wezel.stan.kierunek == 2:
|
|
y += 1
|
|
elif wezel.stan.kierunek == 3:
|
|
x -= 1
|
|
|
|
place = None
|
|
|
|
if 0 <= y < 98 and 0 <= x < 98:
|
|
place = self.search_grid.grid[(x,y)]
|
|
|
|
if place is not None and place is GridCellType.FREE:
|
|
stan_w_przod = Stan(y, x, wezel.stan.kierunek)
|
|
ruch_w_przod = ["Do przodu", stan_w_przod]
|
|
nodes.append(ruch_w_przod)
|
|
|
|
return nodes
|
|
|
|
def get_actions(self, wezel: Wezel):
|
|
akcje = []
|
|
moves_forward = 0
|
|
turns = 0
|
|
parent = wezel
|
|
while True:
|
|
akcja = parent.akcja
|
|
parent = parent.parent
|
|
|
|
if akcja is None:
|
|
break
|
|
|
|
if akcja == "Forward":
|
|
moves_forward = moves_forward + 1
|
|
else:
|
|
turns = turns + 1
|
|
|
|
akcje.append(akcja)
|
|
akcje.reverse()
|
|
|
|
return akcje |