Un generador de laberintos y su IA (Sin optimisar)

from time import time
from sys import setrecursionlimit

from Laberinto import Generar, Imprimir


o='â–''#ocupado
l='.'#libre
e='@'#Entrada
s='#'#salida
k='+'#camino

posinicial=[0,0]
possalida=[0,0]

setrecursionlimit(999999) # fijar limite de recurcividad

print('Generando laberinto')
inicio=time()
laberinto = Generar(o, l, e, s)
print(time()-inicio)
Imprimir(laberinto)
print()
print('Buscando ruta')
inicio = time()
# laberinto = [
#     [o,o,e,o,o],
#     [o,l,l,l,o],
#     [o,l,l,o,o],
#     [o,l,l,l,o],
#     [o,l,l,s,o]
# ]
total = 1
dicc = {}
for ii,i in enumerate(laberinto):
    for pp,p in enumerate(i):
        if p == e:
            posinicial = [ii,pp]
            laberinto[ii][pp] = l
        if p == s:
            possalida = [ii,pp]
            laberinto[ii][pp] = l
        total +=1
total+=1
# print(posinicial,possalida)

for ii,i in enumerate(laberinto):
    for pp,p in enumerate(i):
        if p == l:
            dicc.update({str([ii,pp]):[[ii,pp],total,False,[0,0]]})
dicc.update({str(posinicial):[posinicial,0,False,[-1,-1]]})

recorrer = [posinicial]

for c in recorrer:
    v=dicc[str(c)]
    if not v[2]:
        if str([v[0][0],v[0][1]+1]) in dicc:
            if v[1]+1 < dicc[str([v[0][0],v[0][1]+1])][1]:
                # print(c ,[v[0][0],v[0][1]+1])
                dicc[str([v[0][0],v[0][1]+1])][1]=v[1]+1
                dicc[str([v[0][0],v[0][1]+1])][3]=v[0]
                recorrer.append([v[0][0],v[0][1]+1])


        if str([v[0][0],v[0][1]-1]) in dicc:
            if v[1]+1 < dicc[str([v[0][0],v[0][1]-1])][1]:
                # print(c,[v[0][0], v[0][1] - 1],'------',dicc[str(c)],'-----',dicc[str([v[0][0], v[0][1] - 1])])
                dicc[str([v[0][0],v[0][1]-1])][1]=v[1]+1
                dicc[str([v[0][0], v[0][1] - 1])][3]=v[0]
                recorrer.append([v[0][0],v[0][1]-1])


        if str([v[0][0]+1,v[0][1]]) in dicc:
            if v[1]+1 < dicc[str([v[0][0]+1,v[0][1]])][1]:
                # print(c, v[1] + 1, [v[0][0]+1, v[0][1]], dicc[str([v[0][0]+1, v[0][1]])][1])
                dicc[str([v[0][0]+1,v[0][1]])][1]=v[1]+1
                dicc[str([v[0][0] + 1, v[0][1]])][3]=v[0]
                recorrer.append([v[0][0]+1,v[0][1]])


        if str([v[0][0]-1,v[0][1]]) in dicc:
            if v[1]+1 < dicc[str([v[0][0]-1,v[0][1]])][1]:
                # print(c, v[1] + 1, [v[0][0]-1, v[0][1]], dicc[str([v[0][0]-1, v[0][1]])][1])
                dicc[str([v[0][0]-1,v[0][1]])][1]=v[1]+1
                dicc[str([v[0][0] - 1, v[0][1]])][3]=v[0]
                recorrer.append([v[0][0]-1,v[0][1]])


        dicc[str(v[0])][2]=True
del recorrer
rec = []
def camino(pos):
    if pos == [-1,-1]:
        return
    else:
        rec.append(dicc[str(pos)][0])
        camino(dicc[str(pos)][3])
camino(possalida)

#print(rec,len(rec))
# print(len(dicc))

laberinto[posinicial[0]][posinicial[1]]=e
laberinto[possalida[0]][possalida[1]]=s

for i in rec:
    laberinto[i[0]][i[1]] = k
laberinto[posinicial[0]][posinicial[1]]=e
laberinto[possalida[0]][possalida[1]]=s



print('\n', time()-inicio)
print("Mostrando ruta tomada")

from random import randint, choice
def Generar(o='â–"', l='â–'', e='@', s='#'):
    SizeX = SizeY = 78 # Tamaño del lavereinto
    Direcciones=[
        (-1,0),
        (0,-1),
        (1,0),
        (0,1)
    ]

    Laberinto = []
    for x in range(SizeX+1):
        Laberinto.append([' ']*(SizeY+1))
    Pos = [randint(1, SizeX-1), randint(1, SizeY-1)]
    Laberinto[Pos[0]][Pos[1]] = e

    Recorrido = [[[Pos[0], Pos[1]], Direcciones.copy()]]
    Lado=[]

    while Recorrido or Lado:
        sigiente=True
        if sigiente:
            Lado=Recorrido[-1]
            Pos[0]=Lado[0][0]
            Pos[1] = Lado[0][1]
            sigiente=False
        if not Lado[1]:
            Recorrido.remove(Lado)
            Lado=[]
            continue
        else:IrA = Lado[1].pop(randint(0, len(Lado[1]) - 1))

        if Pos[0]+IrA[0] == 0 or Pos[0]+IrA[0] == SizeX or Pos[1]+IrA[1] == 0 or Pos[1]+IrA[1] == SizeY:
            Laberinto[Pos[0]+IrA[0]][Pos[1]+IrA[1]] = o
        else:
            if Laberinto[Pos[0]+IrA[0]][Pos[1]+IrA[1]] == ' ':
                if Laberinto[Pos[0]+IrA[0]+IrA[0]][Pos[1]+IrA[1]+IrA[1]] == ' ':
                    if Pos[0] + IrA[0]+IrA[0] == 0 or Pos[0] + IrA[0]+IrA[0] == SizeX or Pos[1] + IrA[1]+IrA[1] == 0 or Pos[1] + IrA[1]+IrA[1] == SizeY:
                        Laberinto[Pos[0] + IrA[0]][Pos[1] + IrA[1]] = o
                    else:
                        Laberinto[Pos[0] + IrA[0]][Pos[1] + IrA[1]] = l
                        Laberinto[Pos[0] + IrA[0]+IrA[0]][Pos[1] + IrA[1]+IrA[1]] = l
                        Recorrido.append([[Pos[0]+IrA[0]+IrA[0], Pos[1]+IrA[1]+IrA[1]], Direcciones.copy()])
                        sigiente=True
                elif Laberinto[Pos[0]+IrA[0]+IrA[0]][Pos[1]+IrA[1]+IrA[1]] == l:
                    Laberinto[Pos[0] + IrA[0]][Pos[1] + IrA[1]] = o

    Laberinto[randint(1, SizeX-1)][randint(1, SizeY-1)] = s

    return Laberinto

o='â–''#ocupado
l='.'#libre
e='@'#Entrada
s='#'#salida

def Imprimir(laberinto):
    for i in laberinto:
        Filas= ''
        for y in i:
            if y == ' ':
                Filas += o
            else:
                Filas+=y
        print(Filas)
        #open('Laberintos.txt', 'ab').write(Filas.encode()+b'\n')