Kursy Online

Grafy w Pythonie – Labirynt

# Tak można zdefiniować graf (pierwsza linia jest nieco przesunieta..)
maze_txt =  '''█████ ████
█     █  █
█ ██████ █
█        █
████ █████'''
start = 44
end = 5
print(maze_txt)

# a to troche większy labirynt

maze_txt =  '''██████████████ █████
█              █   █
█████ ███ ████████ █
█     █ █          █
█ █████ ██████████ █
█        █    █    █
████████ ██ █ █ ██ █
█        █  █ █  █ █
█ ██████ ██ █ ██ █ █
█           █    █ █
█████████ ██████████'''
start = 209
end = 14
print(maze_txt)



# policz wysokosc i szerokosc grafu - 
maze_lines = maze_txt.split("\n")
h=len(maze_lines)
w=len(maze_lines[0])
print(h, w, h*w)

# zbuduj jeden dlugi tekst, ktory zawiera w sobie tylko znaki grafu
# po tym tekscie bedzie mozna przemieszczac sie korzystajac z indeksow
# usuwam entery zeby text odpowiadal numeracji wezlow
maze_txt = maze_txt.replace('\n','')

# proces budowy struktury grafu
graph = [ [] for i in range(len(maze_txt))]

# tu odbywa sie przeksztalcenie graficznej reprezentacji labiryntu
# do postaci grafu
#     wierzcholki to pola labiryntu - droga lub sciana
#     krawedz, to mozliwosc przejscia do innego pola

for i in range(len(maze_txt)):
    # Jesli przez to pole prowadzi droga
    if maze_txt[i] == ' ':
        # dla kazdego wezla musze ustalic co jest po lewej/prawej/wyzej/w dol    
        on_left  = None if i % w == 0     else i-1
        on_right = None if (i+1) % w == 0 else i+1
        on_up    = None if i < w          else i-w
        on_down  = None if i + w > h * w  else i+w
        # sprawdzic czy jest to droga i jesli tak, to dodac info do definicji grafu
        if on_left and maze_txt[on_left] == ' ':
            graph[i].append(on_left)
        if on_right and maze_txt[on_right] == ' ':
            graph[i].append(on_right)
        if on_up and maze_txt[on_up] == ' ':
            graph[i].append(on_up)
        if on_down and maze_txt[on_down] == ' ':
            graph[i].append(on_down)



# funkcja do wyszukiwania najkrótszej drogi

def is_path_between(V, source, dest):

    list_to_check = [[source]]
    list_visited = []

    while list_to_check:

        current_path = list_to_check.pop(0)
        current_node = current_path[-1]
        if current_node == dest:
            return current_path
        else:
            if current_node not in list_visited:
                list_visited.append(current_node)
                for n in V[current_node]:
                    new_path = current_path.copy()
                    new_path.append(n)
                    list_to_check.append(new_path)
    
    return []



# find shortest path between start and end
path = is_path_between(graph, start, end)

# narysuj graf, oznaczając znalezioną ścieżkę znakiem *
for i in range(h):
    line = ''
    for j in range(w):
        if (i*w+j) in path:
            line+='*'
        else:
            line+=maze_txt[i*w+j]
    print(line)