Labyrinth in Python

0

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() 
    
asked by Alonso Bustillos 05.11.2018 в 01:38
source

0 answers