2021-05-31 17:10:14 +02:00
import cart
2021-04-10 11:08:17 +02:00
import copy
2021-06-18 12:16:19 +02:00
class Istate : # stan początkowy wózka (strona, w którą patrzy, miejsce, w którym się on znajduje)
2021-04-10 18:24:13 +02:00
def __init__ ( self , direction , x , y ) :
2021-04-09 22:49:58 +02:00
self . direction = direction
self . x = x
self . y = y
2021-06-18 12:16:19 +02:00
2021-04-09 22:49:58 +02:00
def get_direction ( self ) :
return self . direction
2021-06-18 12:16:19 +02:00
2021-04-09 22:49:58 +02:00
def set_direction ( self , direction ) :
self . direction = direction
2021-06-18 12:16:19 +02:00
2021-04-09 22:49:58 +02:00
def get_x ( self ) :
return self . x
2021-06-18 12:16:19 +02:00
2021-04-09 22:49:58 +02:00
def set_x ( self , x ) :
self . x = x
2021-06-18 12:16:19 +02:00
2021-04-09 22:49:58 +02:00
def get_y ( self ) :
return self . y
2021-06-18 12:16:19 +02:00
2021-04-09 22:49:58 +02:00
def set_y ( self , y ) :
self . y = y
2021-06-18 12:16:19 +02:00
class Node : # wierzchołek grafu
2021-04-10 18:24:13 +02:00
def __init__ ( self , action , direction , parent , x , y ) :
2021-06-18 12:16:19 +02:00
self . action = action # akcja jaką ma wykonać (obróc się w lewo, obróć się w prawo, ruch do przodu)
2021-04-09 22:49:58 +02:00
self . direction = direction
2021-06-18 12:16:19 +02:00
self . parent = parent # ojciec wierzchołka
2021-04-09 22:49:58 +02:00
self . x = x
self . y = y
2021-06-18 12:16:19 +02:00
2021-04-10 18:24:13 +02:00
def get_action ( self ) :
return self . action
2021-06-18 12:16:19 +02:00
2021-04-10 18:24:13 +02:00
def set_action ( self , action ) :
self . action = action
2021-06-18 12:16:19 +02:00
2021-04-09 22:49:58 +02:00
def get_direction ( self ) :
return self . direction
2021-06-18 12:16:19 +02:00
2021-04-09 22:49:58 +02:00
def set_direction ( self , direction ) :
self . direction = direction
2021-06-18 12:16:19 +02:00
2021-04-10 18:24:13 +02:00
def get_parent ( self ) :
return self . parent
2021-06-18 12:16:19 +02:00
2021-04-10 18:24:13 +02:00
def set_parent ( self , parent ) :
self . parent = parent
2021-06-18 12:16:19 +02:00
2021-04-09 22:49:58 +02:00
def get_x ( self ) :
return self . x
2021-06-18 12:16:19 +02:00
2021-04-09 22:49:58 +02:00
def set_x ( self , x ) :
self . x = x
2021-06-18 12:16:19 +02:00
2021-04-09 22:49:58 +02:00
def get_y ( self ) :
return self . y
2021-06-18 12:16:19 +02:00
2021-04-09 22:49:58 +02:00
def set_y ( self , y ) :
self . y = y
2021-06-18 12:16:19 +02:00
def goal_test ( goaltest ,
elem ) : # funkcja sprawdzająca czy położenie wózka równa się położeniu punktu docelowego, jeśli tak zwraca prawdę, w przeciwnym wypadku fałsz
2021-04-10 18:24:13 +02:00
if elem . get_x ( ) == goaltest [ 0 ] and elem . get_y ( ) == goaltest [ 1 ] :
2021-04-09 22:49:58 +02:00
return True
else :
return False
2021-06-18 12:16:19 +02:00
def graphsearch ( explored , fringe , goaltest , istate , succ ) : # przeszukiwanie grafu wszerz
node = Node ( None , istate . get_direction ( ) , None , istate . get_x ( ) ,
istate . get_y ( ) ) # wierzchołek początkowy, stworzony ze stanu początkowego wózka
fringe . append ( node ) # wierzchołki do odwiedzenia
2021-05-31 17:10:14 +02:00
while True :
if not fringe :
return False
2021-06-18 12:16:19 +02:00
elem = fringe . pop ( 0 ) # zdejmujemy wierzchołek z kolejki fringe i rozpatrujemy go
2021-05-31 17:10:14 +02:00
temp = copy . copy ( elem )
2021-06-18 12:16:19 +02:00
if goal_test ( goaltest ,
elem ) is True : # jeżeli osiągniemy cel w trakcie przeszukiwania grafu wszerz (wjedziemy na pole docelowe) : zwracamy listę ruchów, po których wykonaniu dotrzemy na miejsce
2021-05-31 17:10:14 +02:00
return print_moves ( elem )
2021-06-18 12:16:19 +02:00
explored . append ( elem ) # dodajemy wierzchołek do listy wierzchołków odwiedzonych
for ( action , state ) in succ (
temp ) : # iterujemy po wszystkich możliwych akcjach i stanach otrzymanych dla danego wierzchołka grafu
2021-05-31 17:10:14 +02:00
fringe_tuple = [ ]
explored_tuple = [ ]
for x in fringe :
fringe_tuple . append ( ( x . get_direction ( ) , x . get_x ( ) , x . get_y ( ) ) )
for x in explored :
explored_tuple . append ( ( x . get_direction ( ) , x . get_x ( ) , x . get_y ( ) ) )
2021-06-18 12:16:19 +02:00
if state not in fringe_tuple and state not in explored_tuple : # jeżeli stan nie znajduje się na fringe oraz nie znajduje się w liście wierzchołków odwiedzonych
x = Node ( action , state [ 0 ] , elem , state [ 1 ] ,
state [ 2 ] ) # stworzenie nowego wierzchołka, którego rodzicem jest elem
fringe . append ( x ) # dodanie wierzchołka na fringe
def print_moves ( elem ) : # zwraca listę ruchów jakie należy wykonać by dotrzeć do punktu docelowego
2021-04-10 13:42:32 +02:00
moves_list = [ ]
while ( elem . get_parent ( ) != None ) :
moves_list . append ( elem . get_action ( ) )
elem = elem . get_parent ( )
moves_list . reverse ( )
return moves_list
2021-06-18 12:16:19 +02:00
def succ (
elem ) : # funkcja następnika, przypisuje jakie akcje są możliwe do wykonania na danym polu oraz jaki będzie stan (kierunek, położenie) po wykonaniu tej akcji
2021-04-09 22:49:58 +02:00
actions_list = [ ]
2021-04-10 11:08:17 +02:00
temp = copy . copy ( elem . get_direction ( ) )
if temp == 1 :
temp = 4
else :
temp = temp - 1
actions_list . append ( ( " rotate_left " , ( temp , elem . get_x ( ) , elem . get_y ( ) ) ) )
temp = copy . copy ( elem . get_direction ( ) )
if temp == 4 :
temp = 1
else :
temp = temp + 1
actions_list . append ( ( " rotate_right " , ( temp , elem . get_x ( ) , elem . get_y ( ) ) ) )
2021-04-10 13:42:32 +02:00
temp_move_south = elem . get_y ( ) + 1
temp_move_west = elem . get_x ( ) - 1
temp_move_east = elem . get_x ( ) + 1
temp_move_north = elem . get_y ( ) - 1
2021-05-31 17:10:14 +02:00
if cart . Cart . is_move_allowed_succ ( elem ) == " x + 1 " :
2021-04-10 13:42:32 +02:00
actions_list . append ( ( " move " , ( elem . get_direction ( ) , temp_move_east , elem . get_y ( ) ) ) )
2021-05-31 17:10:14 +02:00
elif cart . Cart . is_move_allowed_succ ( elem ) == " y - 1 " :
2021-04-10 13:42:32 +02:00
actions_list . append ( ( " move " , ( elem . get_direction ( ) , elem . get_x ( ) , temp_move_north ) ) )
2021-05-31 17:10:14 +02:00
elif cart . Cart . is_move_allowed_succ ( elem ) == " y + 1 " :
2021-04-10 13:42:32 +02:00
actions_list . append ( ( " move " , ( elem . get_direction ( ) , elem . get_x ( ) , temp_move_south ) ) )
2021-05-31 17:10:14 +02:00
elif cart . Cart . is_move_allowed_succ ( elem ) == " x - 1 " :
2021-04-10 13:42:32 +02:00
actions_list . append ( ( " move " , ( elem . get_direction ( ) , temp_move_west , elem . get_y ( ) ) ) )
2021-06-18 12:16:19 +02:00
return actions_list