A*

#!/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

#Calcula la distancia manhattan
def manhattan(a,b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

#busca la posicion de X en el laberinto
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()

# Toma un archivo con el laberinto en ASCII, imprime el inicio, el final y busca el mejor camino.
# Por ultimo escribe un archivo con formato solucion_archivo.txt en donde escribe el mejor camino encontrado.
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()