Escape del laberinto

667 days ago by jlbravo

Escape del Laberinto

En esta sesión vamos a ver cómo resolver un laberinto (y, si tenemos tiempo, cómo crearlo), usando el ordenador. Concretamente, usaremos Sage, que es un software matemático creado sobre Python, uno de los lenguajes de programación más utilizados.

 

 

De laberintos a grafos y vuelta

Vamos a considerar laberintos típicos de los que se dibujan en una hoja de papel a cuadros, como el siguiente:

# Cargamos un laberinto M=Matrix(load(DATA+'M')) color='gray' # Todas las opciones de color en: http://matplotlib.org/examples/color/colormaps_reference.html GM=matrix_plot(M,frame=false,cmap=color,origin='lower',ymin=0,ymax=M.dimensions()[0]) GM 
       

Un laberinto es un objeto con el que no es sencillo trabajar. Así que vamos a transformarlo en algo más simple: Un grafo.

Un grafo es un objeto matemático, que podemos visualizar como un conjunto de vértices unidos con algunas aristas entre ellos. Más detalles en "Grafo" en la Wikipedia.

Para ello, consideramos que en cada cuadradito en blanco hay un vértice y dibujamos una arista (un segmento) uniendo dos vértices contiguos (es decir, dos cuadrados blancos que estén "pegados" en el laberinto). Así tenemos un grafo.

%hide %auto def laberinto_a_grafo(M): # Definimos las dimensiones m,n=M.dimensions() # Creamos un grafo vacío g=Graph({}) # Recorremos el laberinto for j in range(1,m-1,2): # para cada fila for i in range(1,n-1,2): # para cada columna # Si es un hueco, añadimos un vértice if M[j,i]==1: g.add_vertex((j,i)) # Si hay un hueco en la posición superior, los unimos con una arista if j>1 and M[j,i]*M[j-1,i]==1: g.add_edge([(j-2,i),(j,i)]) # Si hay un hueco a la izquierda, los unimos con una arista if i>1 and M[j,i]*M[j,i-1]==1: g.add_edge([(j,i),(j,i-2)]) # La siguiente línea dos dice dónde pintar los circulitos (en el hueco asociado) g.set_pos({k:(k[1],k[0]) for k in g.vertices()}) return g 
       

Ya tenemos nuestra función de Sage, que nos pasa un laberinto a un grafo. Vamos a pintarlos juntos, para ver que lo hemos hecho bien:

g=laberinto_a_grafo(M) GM+g.plot(vertex_labels=false,vertex_size=150) 
       

Creación "manual" de laberintos

La ventaja de tener nuestro laberinto como un grafo, es que ahora es muy sencillo trabajar con él porque el ordenador dispone de muchos métodos para trabajar con grafos.

Vamos a crearnos un laberinto (como un grafo). Partimos de una cuadrícula:

n=5 # Comenzamos por uno pequeñito m=8 g=graphs.Grid2dGraph(n,m) # Por una cuestión técnica con el editor de grafos, hay que cambiar los nombres de los vértices ov={lk:k for k,lk in zip(range(n*m),g.vertices())} # Guardamos las etiquetas que queremos que tengan después (creando espacio para los huecos) nv={k:(1+2*lk[0],1+2*lk[1]) for k,lk in zip(range(n*m),g.vertices())} g.relabel(ov) g.plot(vertex_labels=false) 
       

El grafo anterior se corresponde con un laberinto sin paredes: desde cada posición puedes ir a todas las vecinas sin impedimento.

 

Elimina las aristas que desees haciendo click en los dos vértices que las determinan. Cuando hayas terminado de crear un laberinto, pulsa "save".
graph_editor(g); 
       

Una vez guardado, volvemos a etiquetarlo y colocamos los vértices

# Volvemos a nuestras etiquetas originales g.relabel(nv) # Y recolocamos los vértices (por si los hemos movido) g.set_pos({k:(k[1],k[0]) for k in g.vertices()}) g.plot(vertex_labels=false) 
       

Por supuesto, podemos volver a transformar un grafo (como el anterior) en un laberinto:

%hide %auto def grafo_a_laberinto(g): # Buscamos las dimensiones n=max([i for i,j in g.vertices()])+2 # Comenzamos por 0 m=max([j for i,j in g.vertices()])+2 # Creamos la matriz con todas las posiciones en negro M=[[0 for i in range(m)] for j in range(n)] # Recorremos los vértices y los marcamos en "blanco" for v in g.vertex_iterator(): M[v[0]][v[1]]=1 # También marcamos en blanco los píxeles que están sobre cada arista for e in g.edge_iterator(): M[(e[0][0]+e[1][0])/2][(e[0][1]+e[1][1])/2]=1 # Marcamos la entrada y la salida M[1][0]=M[0][0]=M[0][1]=M[n-2][m-1]=M[n-1][m-2]=M[n-1][m-1]=1 return Matrix(M) 
       
M_nuevo=grafo_a_laberinto(g) GMn=matrix_plot(M_nuevo,frame=false,cmap=color,ymin=0,ymax=M_nuevo.dimensions()[0]) GMn+g.plot(vertex_labels=false,vertex_size=150) 
       

Resolución de laberintos

Ya sabemos crear laberintos con el ordenador. Ahora que ya sabemos que podemos transformar un laberinto en un grafo, vamos a tratar de que el ordenador nos resuelva el laberinto usando teoría de grafos.

Vamos a ver primero cómo resolverlo "a mano". En primer lugar, veremos cómo movernos por el laberinto. En cada momento guardaremos la información de la posición en la que estamos (pos)  y de la dirección (direccion). Las direcciones serán 0 para arriba, 1 para la derecha, 2 para abajo y 3 para la izquierda.

Vamos a decirle al ordenador qué es girar (a la izquierda y a la derecha):

def gira_izquierda(direccion): return (direccion-1)%4 def gira_derecha(direccion): return (direccion+1)%4 
       

Ahora vamos a "avanzar". En primer lugar, tenemos que decirle cuáles son las posiciones a las que queremos avanzar en función de nuestra dirección. Eso lo haremos mediante una lista en la que guardaremos lo que hay que sumar a la posición actual para avanzar en cada dirección.

direcciones=[vector(k) for k in [(2,0),(0,2),(-2,0),(0,-2)]] 
       

Para avanzar, primero definimos una función que nos dice si hay camino a la siguiente posición y después otra que avanza:

def delanteLibre(g,pos,direccion): return g.has_edge( (tuple(pos),tuple(pos+direcciones[direccion])) ) def avanza(pos,direccion): return pos+direcciones[direccion] 
       
Ejecuta la celda siguiente (dale a "evaluar"). Mueve el cursor pulsando en los botones hasta llegar a la posición superior derecha del laberinto.
# Buscamos las dimensiones del laberinto n=max([i for i,j in g.vertices()]); m=max([j for i,j in g.vertices()]) # Establecemos la posición y la dirección inicial y la meta pos=vector((1,1));direccion=1;meta=(n,m); # Para dibujar el cursor, tendremos que permutar las coordenadas def permuta(pos): return (pos[1],pos[0]) # La siguiente función crea el "juego" color='gray' @interact def _(action=selector(['izquierda','avanza','derecha'],buttons=True)): global g,pos, direccion, direcciones if action=='izquierda': direccion=gira_izquierda(direccion) if action=='derecha': direccion=gira_derecha(direccion) if action=='avanza': if delanteLibre(g,pos,direccion): pos=avanza(pos,direccion) if pos[0]==meta[0] and pos[1]==meta[1]: print u'¡MUY BIEN!' activo = {(0,0,1):pos} # Esto es para pintar lab = matrix_plot(M_nuevo,frame=false,cmap=color,ymin=0,ymax=M_nuevo.dimensions()[0]) graf = g.plot(vertex_labels=false,vertex_size=150) cursor = circle(permuta(pos),0.4,fill=True,axes=False) cursor += circle(permuta(meta),0.4,fill=True,color='red',axes=False) cursor += arrow(permuta(pos),permuta(pos+direcciones[direccion]*0.7)) show(lab+graf+cursor) 
       

Click to the left again to hide and once more to show the dynamic interactive window

Siguiendo la pared de la derecha

Un método para resolver los laberintos de este tipo (tales que la entrada y la salida se situan en el borde exterior del laberinto) es "seguir la pared de la derecha". Piensa que estás en la entrada del laberinto, extiendes la mano derecha hasta tocar la pared y tratas de seguir sin dejar en ningún momento de tocar la pared de la derecha. Vamos a hacerlo primero sobre papel y luego veremos cómo se hace con el ordenador.

 

Coge uno de los laberintos impresos y busca la salida siguiendo la pared de la derecha. También puedes hacerlo con la izquierda, pero no mezcles las dos maneras.

 

A continuación tenemos el código que nos lo hace. Los pasos que hemos dado (los vértices visitados) se dibujan en azul al final.

# Buscamos las dimensiones del laberinto n=max([i for i,j in g.vertices()]); m=max([j for i,j in g.vertices()]) # Establecemos la posición y la dirección inicial y la meta pos=vector((1,1));direccion=0;meta=(n,m); # Guardaremos las posiciones que visitamos en una lista posiciones=[tuple(pos)] contador=0 # Para no quedarnos atascados while pos[0]!=meta[0] or pos[1]!=meta[1]: # Hasta llegar al final direccion=gira_derecha(direccion) # Giramos a la derecha while not(delanteLibre(g,pos,direccion)): # Mientras no podamos avanzar direccion=gira_izquierda(direccion) # Giramos a la izquierda pos=avanza(pos,direccion) # Avanzamos # Guardamos la nueva posición posiciones+=[tuple(pos)] contador+=1 if contador>n*m or (pos[0]==1 and pos[1]==1 and direccion==0): # Si no llegamos a ninguna parte print u'¡No encuentro el camino!' break # Marcamos el camino en azul camino = {(0,0,1):posiciones} color='gray' lab = matrix_plot(M_nuevo,frame=false,cmap=color,ymin=0,ymax=M_nuevo.dimensions()[0]) graf = g.plot(vertex_labels=false,vertex_size=150,vertex_colors=camino) lab+graf 
       

Esta estrategia nos permite también encontrar el camino "sin vueltas". En el papel es sencillo, porque basta mirar el camino recorrido y tomar su parte "izquierda". Con el ordenador es un poco más difícil programar lo de "la parte izquierda de un camino"; lo que vamos a hacer es que, cada vez que volvemos a un vértice que ya hemos visitado, borramos todo el tramo intermedio (porque no necesitamos recorrerlo para llegar al final).

def cortar(posiciones): n=len(posiciones) for i in range(n): for j in range(i+1,n): if posiciones[i]==posiciones[j]: return cortar(posiciones[:i]+posiciones[j:]) return posiciones posiciones=cortar(posiciones) camino = {(0,0,1):posiciones} lab = matrix_plot(M_nuevo,frame=false,cmap=color,ymin=0,ymax=M_nuevo.dimensions()[0]) graf = g.plot(vertex_labels=false,vertex_size=150,vertex_colors=camino) lab+graf 
       

Hilo de Ariadna

En la mitología griega, Ariadna entregó a Teseo una espada y un ovillo de hilo para que pudiese derrotar al minotauro y salir del laberinto. Teseo ató una punta del ovillo en la entrada y así pudo regresar. Algunas fuentes dicen que el propio Dédalo, creador del laberinto, fue quién proporcionó el hilo a Ariadna. Pero, ¿tanta complicación sólo para salir del laberinto, una vez muerto el minotauro? ¿Dédalo tuvo que explicarles cómo salir del laberinto usando un hilo?

Vamos a ver que un hilo es algo de gran utilidad para la resolución de un laberinto, aunque no lo hayamos atado a la salida. Pero en primer lugar, tenemos que pensar por qué no funciona siempre el método de "seguir el camino de la derecha".

Modifica el laberinto (la forma, la posición de entrada o la posición de salida) para el que falle el método de "seguir el camino de la derecha".
# Buscamos las dimensiones del laberinto n=max([i for i,j in g.vertices()]); m=max([j for i,j in g.vertices()]) # Establecemos la posición y la dirección inicial y la meta pos=vector((1,1));direccion=0;meta=(n,m); # Guardaremos las posiciones que visitamos en una lista posiciones=[tuple(pos)] contador=0 # Para no quedarnos atascados while pos[0]!=meta[0] or pos[1]!=meta[1]: # Hasta llegar al final direccion=gira_derecha(direccion) # Giramos a la derecha while not(delanteLibre(g,pos,direccion)): # Mientras no podamos avanzar direccion=gira_izquierda(direccion) pos=avanza(pos,direccion) # Avanzamos # Guardamos la nueva posición posiciones+=[tuple(pos)] contador+=1 if contador>n*m or (pos[0]==1 and pos[1]==1 and direccion==0): # Si no llegamos a ninguna parte print u'¡No encuentro el camino!' break # Marcamos el camino en azul camino = {(0,0,1):posiciones} color='gray' lab = matrix_plot(M_nuevo,frame=false,cmap=color,ymin=0,ymax=M_nuevo.dimensions()[0]) graf = g.plot(vertex_labels=true,vertex_size=900,vertex_colors=camino) lab+graf 
       

Modificaremos la función para que nos encuentre el camino. Para eso tenemos que evitar caer en un ciclo cuando estamos explorando. En realidad, basta comprobar si la posición a la que nos vamos a mover la hemos visitado o no (está en el camino que llevamos hecho). La única excepción es cuando estamos volviendo, pero la posición de "volver" es la penúltima, así que podemos comprobar que no está en nuestro camino, salvo en las dos últimas posiciones. Por último, hemos modificado el método para que cuando estamos volviendo vaya borrando las posiciones que dejamos (es decir, si estamos retrocediendo vamos "recogiendo el hilo"). De ese modo en cada momento sólo guardamos el camino desde la entrada hasta la posición actual, es decir, el hilo de Ariadna.

# Buscamos las dimensiones del laberinto n=max([i for i,j in g.vertices()]); m=max([j for i,j in g.vertices()]) # Establecemos la posición y la dirección inicial y la meta pos=vector((1,1));direccion=0;meta=(n,m); # Guardaremos las posiciones que visitamos en una lista posiciones=[tuple(pos)] contador=0 # Para no quedarnos atascados while pos[0]!=meta[0] or pos[1]!=meta[1]: # Hasta llegar al final direccion=gira_derecha(direccion) # Giramos a la derecha # Vamos girando a la izquierda hasta encontrar una dirección para avanzar en la que no esté el hilo while not(delanteLibre(g,pos,direccion) and not(tuple(avanza(pos,direccion)) in posiciones[:-2])): direccion=gira_izquierda(direccion) pos=avanza(pos,direccion) # Si la posición a la que llegamos ya la habíamos visitado, la borramos del camino if len(posiciones)>1 and posiciones[-2][0]==pos[0] and posiciones[-2][1]==pos[1]: posiciones.pop() else: posiciones+=[tuple(pos)] contador+=1 if contador>2*n*m or (pos[0]==1 and pos[1]==1 and direccion==0): # Si no llegamos a ninguna parte print u'¡No encuentro el camino!' break # Marcamos el camino en azul camino = {(0,0,1):posiciones} color='gray' lab = matrix_plot(M_nuevo,frame=false,cmap=color,ymin=0,ymax=M_nuevo.dimensions()[0]) graf = g.plot(vertex_labels=false,vertex_size=150,vertex_colors=camino) show(lab+graf) 
       

Creación de laberintos

El método que hemos visto antes es demasiado artesanal y bastante lento, así que vamos a intentar que lo haga otro por nosotros (el ordenador). Volvermos a crear una rejilla.

n=14 m=20 g=graphs.Grid2dGraph(n,m) # Tenemos que "crear huecos" para los caminos nv={lk:(1+2*lk[0],1+2*lk[1]) for lk in g.vertices()} g.relabel(nv) g.set_pos({k:(k[1],k[0]) for k in g.vertices()}) g.plot(vertex_labels=false) 
       

Para el método que vamos a aplicar, primero asignamos un peso a cada una de las aristas. Los valores no importan en este caso; lo hacemos aleatoriamente con enteros positivos (podrían haber sido números reales). A modo de ejemplo lo vemos en una esquina del grafo anterior.

for e in g.edge_iterator(): g.add_edge([e[0],e[1],randint(1,10)]) # en vez de random() o de round(random(),ndigits=4) g.subgraph(vertices=[(i,j) for i in [1,3,5] for j in [1,3,5]]).plot(vertex_labels=false,edge_labels=true,figsize=5) 
       

Lo que vamos a hacer es general un "árbol recubridor minimal". Un árbol es un grafo tal que entre cada dos vértices existe un único camino, es decir, que no hay ciclos (no puedes salir de un sitio y llegar al mismo sin retroceder). Es algo interesante para un laberinto que sea así.

Que sea minimal es una condición técnica: quiere decir que entre todos los árboles que contengan los vértices tomamos aquel en el que la suma de los pesos de las aristas sea mínima. Como hemos elegido pesos aleatorios nos saldrá un árbol que no podremos predecir.

laberinto=Graph(g.min_spanning_tree(weight_function = lambda e: e[2])) laberinto.set_pos(g.get_pos()) laberinto.plot(vertex_labels=false) 
       

Por último, lo convertimos en una imagen de un laberinto como hemos hecho antes.

M_nuevo=grafo_a_laberinto(laberinto) color='gray' GMn=matrix_plot(M_nuevo,frame=false,cmap=color,ymin=0,ymax=M_nuevo.dimensions()[0]) GMn+laberinto.plot(vertex_labels=false,vertex_size=100) 
       

Juntándolo todo, podemos crear laberintos muy grandes.

n=20;m=30 #n=65;m=90; #n=130;m=180; #n=200;m=300; g=graphs.Grid2dGraph(n,m) nv={lk:(1+2*lk[0],1+2*lk[1]) for lk in g.vertices()} g.relabel(nv) g.set_pos({k:(k[1],k[0]) for k in g.vertices()}) for e in g.edge_iterator(): g.add_edge([e[0],e[1],random()]) laberinto=Graph(g.min_spanning_tree(weight_function = lambda e: e[2])) laberinto.set_pos(g.get_pos()) M_nuevo=grafo_a_laberinto(laberinto) matrix_plot(M_nuevo,frame=false,dpi=400).save('lab.pdf')# Para laberintos grandes, la pantalla es pequeña 
       

Podemos crear una imagen más compacta guardando directamente la matriz como imagen

# Para guardarlo en una imagen 1-1 from PIL import Image import numpy as np h, w = M_nuevo.dimensions() data = np.zeros((h, w, 3), dtype=np.uint8) for i in range(h): for j in range(w): data[i,j]=[M_nuevo[i,j]*255,M_nuevo[i,j]*255,M_nuevo[i,j]*255] #data[256, 256] = [255, 0, 0] img = Image.fromarray(data, 'RGB') img.save('my.png') img.show() 
       
 
       

Y también sabemos resolverlos.

camino=laberinto.shortest_path((1,1),(2*n-1,2*m-1)) M=Matrix(RDF,M_nuevo) va=camino[0] for v in camino: M[v[0],v[1]]=M[(v[0]+va[0])/2,(v[1]+va[1])/2]=1/2 va=copy(v) matrix_plot(M,frame=false,dpi=400).save('lab_sol.pdf')# Para laberintos grandes, la pantalla es pequeña 
       

Un minijuego

Vamos a poner en práctica lo aprendido. Intentaremos resolver un laberinto "sin verlo", para que sea un poco más realista.

 

Mueve el cursor pulsando en los botones hasta llegar a la posición superior derecha del laberinto. Para aumentar la dificultad y ponerte a prueba, cambia la visibilidad en el desplegable.
n=10;m=10 # Cambia estos números para cambiar la dificultad # Volvemos a cargar las funciones de antes. def gira_izquierda(direccion): return (direccion-1)%4 def gira_derecha(direccion): return (direccion+1)%4 direcciones=[vector(k) for k in [(2,0),(0,2),(-2,0),(0,-2)]] def delanteLibre(g,pos,direccion): return g.has_edge( (tuple(pos),tuple(pos+direcciones[direccion])) ) def avanza(pos,direccion): return pos+direcciones[direccion] #Creamos el laberinto g=graphs.Grid2dGraph(n,m) g.relabel({lk:(1+2*lk[0],1+2*lk[1]) for lk in g.vertices()}) g.set_pos({k:(k[1],k[0]) for k in g.vertices()}) for e in g.edge_iterator(): g.add_edge([e[0],e[1],randint(1,1)]) laberinto=Graph(g.min_spanning_tree(weight_function = lambda e: e[2])) laberinto.set_pos(g.get_pos()) g=copy(laberinto) M_nuevo=grafo_a_laberinto(laberinto) # Establecemos las condiciones iniciales pos=vector((1,1)) direccion=1 n=n*2-1;m=m*2-1 def permuta(pos): return (pos[1],pos[0]) # Ya tenemos nuestro juego meta=(n,m) M_vis=ones_matrix(*M_nuevo.dimensions())/2 color='gray' @interact def _(action=selector(['izquierda','avanza','derecha'],buttons=True),visibilidad = selector([(1,'Explorador'),(2,'Teseo'),(3,'Antorcha')])): global g,pos, direccion, direcciones, M_vis if action=='izquierda': direccion=gira_izquierda(direccion) if action=='derecha': direccion=gira_derecha(direccion) if action=='avanza': if delanteLibre(g,pos,direccion): pos_ant=pos pos=avanza(pos,direccion) if visibilidad==2: if M_vis[pos[0],pos[1]]==1: M_vis[pos_ant[0]-1:pos_ant[0]+2,pos_ant[1]-1:pos_ant[1]+2]=ones_matrix(3,3)/2 if pos[0]==meta[0] and pos[1]==meta[1]: print u'¡MUY BIEN!' activo = {(0,0,1):pos} if visibilidad==3: M_vis=ones_matrix(*M_nuevo.dimensions())/2; M_vis[pos[0]-1:pos[0]+2,pos[1]-1:pos[1]+2]=M_nuevo[pos[0]-1:pos[0]+2,pos[1]-1:pos[1]+2] lab = matrix_plot(M_vis,frame=false,cmap=color,ymin=0,ymax=M_nuevo.dimensions()[0]) cursor = circle(permuta(pos),0.4,fill=True,axes=False) cursor += circle(permuta(meta),0.4,fill=True,color='red',axes=False) cursor += arrow(permuta(pos),permuta(pos+direcciones[direccion]*0.8)) show(lab+cursor) 
       

Click to the left again to hide and once more to show the dynamic interactive window