I want to study a labyrinth program with a star algorithm search, what happens is that I found one but it says pycharm that the version I have does not support certain lines and I was wondering if they could help me see where I can run this program successfully. note my python version is 3.7.1 I am new to python: $
#!/usr/bin/python
import sys
#####################################################################
#####################CLASE AESTRELLA#################################
class AEstrella:
"""
laberinto : laberinto en ASCII
pos_final : punto objetivo
inicio : Nodo que contiene el punto inicial
fin : Nodo que contiene el punto final
abierta : lista con caminos abiertos
cerrada : lista con caminos cerrados o inutiles
"""
def __init__(self,laberinto):
self.laberinto = laberinto
self.pos_final = buscarPosicion('F',self.laberinto)
self.inicio = Nodo(self.pos_final,buscarPosicion('I',laberinto),None)
self.fin = Nodo(self.pos_final,self.pos_final,None)
self.abierta = []
self.cerrada = []
self.cerrada.append(self.inicio)
self.abierta += self.vecinos(self.inicio)
while self.objetivo():
self.buscar()
self.camino = self.camino()
#Devuelve una lista con vecinos transitables
def vecinos(self,nodo):
vecinos = []
try:
if self.laberinto[nodo.posicion[0]+1][nodo.posicion[1]] != '0':
vecinos.append(Nodo(self.pos_final,[nodo.posicion[0]+1, nodo.posicion[1]],nodo))
except IndexError,e:
pass
try:
if self.laberinto[nodo.posicion[0]-1][nodo.posicion[1]] != '0':
vecinos.append( Nodo(self.pos_final,[nodo.posicion[0]-1, nodo.posicion[1]],nodo))
except IndexError,e:
pass
try:
if self.laberinto[nodo.posicion[0]][nodo.posicion[1]-1] != '0':
vecinos.append(Nodo(self.pos_final,[nodo.posicion[0], nodo.posicion[1]-1],nodo))
except IndexError,e:
pass
try:
if self.laberinto[nodo.posicion[0]][nodo.posicion[1]+1] != '0':
vecinos.append( Nodo(self.pos_final,[nodo.posicion[0], nodo.posicion[1]+1],nodo))
except IndexError, e:
pass
return vecinos
#Pasa el vecino con menor costo (G+H) a la lista cerrada
def f_menor(self):
actual = self.abierta[0]
n = 0
for i in range(1, len(self.abierta)):
if self.abierta[i].f < actual.f:
actual = self.abierta[i]
n = i
self.cerrada.append(self.abierta[n])
del self.abierta[n]
#comprueba la existencia de un nodo en una lista
def exists(self,nodo,lista):
for i in range(len(lista)):
if nodo.posicion == lista[i].posicion:
return True
return False
#Se evaluan los movimientos buscando que los nodos esten en lista cerrada o abierta
#Si un nodo mejora el valor G del padre se comprueba en la lista abierta y el padre se manda a la cerrada.
#Despues el nodo que contenia un mejor valor se manda a la lista abierta
def ruta(self):
for i in range(len(self.nodos)):
if self.exists(self.nodos[i], self.cerrada):
continue
elif not self.exists(self.nodos[i], self.abierta):
self.abierta.append(self.nodos[i])
else:
if self.select.g+1 < self.nodos[i].g:
for j in range(len(self.abierta)):
if self.nodos[i].posicion == self.abierta[j].posicion:
del self.abierta[j]
self.abierta.append(self.nodos[i])
break
# Analiza el elemento que recien se agrego a la lista cerrada es decir el nodo padre.
def buscar(self):
self.f_menor()
self.select = self.cerrada[-1]
self.nodos = self.vecinos(self.select)
self.ruta()
#Comprueba si el objetivo esta en la lista abierta para terminar de buscar.
def objetivo(self):
for i in range(len(self.abierta)):
if self.fin.posicion == self.abierta[i].posicion:
return False
return True
#Retorna una lista con las posiciones del mejor camino a seguir
def camino(self):
print len(self.abierta)
for i in range(len(self.abierta)):
if self.fin.posicion == self.abierta[i].posicion:
objetivo = self.abierta[i]
camino = []
while objetivo.padre != None:
camino.append(objetivo.posicion)
objetivo = objetivo.padre
camino.reverse()
return camino
#####################################################################
#####################################################################
#####################CLASE Nodo######################################
class Nodo:
"""
pos_final : punto objetivo
posicion : localizacion x,y del nodo
padre : Nodo padre
h : valor Heuristico, costo desde el nodo actual hasta el objetivo
g : valor g, costo desde el nodo inicial hasta el nodo actual
"""
def __init__(self,pos_final,posicion=[0,0],padre=None):
self.posicion = posicion
self.padre = padre
self.h = manhattan(self.posicion,pos_final)
if self.padre == None:
self.g = 0
else:
self.g = self.padre.g + 1
self.f = self.g + self.h
Calculate the distance manhattan
def manhattan(a,b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
looks for the position of X in the labyrinth
def buscarPosicion(x,laberinto):
for fila in range(len(laberinto)):
for columna in range(len(laberinto[0])):
if laberinto[fila][columna] == x:
return [fila,columna]
#Para leer un archivo y crear el laberinto
def leerArchivo(name):
archivo = open(name,'r')
laberinto = [linea.split() for linea in archivo.readlines()]
archivo.close()
return laberinto
#Escribe una ruta con caracteres ASCII en un archivo
def escribirSolucion(camino,laberinto,name):
sname = "solucion_"+name
solucion = open(sname,'w')
for posicion in camino:
laberinto[ posicion[0]][ posicion[1]] = 'R'
for i in range(len(laberinto)):
linea = ""
for j in range(len(laberinto[0])):
linea = linea + laberinto[i][j] + " "
solucion.write(linea+"\n")
solucion.close()
Take a file with the labyrinth in ASCII, print the beginning, end and look for the best path.
Finally, write a file with the format solucion_archivo.txt where you write the best path found.
def main():
name = sys.argv[1]
laberinto = leerArchivo(name)
print "inicio %s " % buscarPosicion('I',laberinto)
print "final %s " % buscarPosicion('F',laberinto)
algoritmo = AEstrella(laberinto)
escribirSolucion(algoritmo.camino,laberinto,name)
main()