Razón Artificial

La ciencia y el arte de crear videojuegos

Pathfinding A* en Python. Parte II

Escrito por adrigm el 1 de abril de 2010 en Inteligencia Artificial, Noticias, Programación | 11 Comentarios.

En el anterior artículo creamos un mapa y lo convertimos en una array. En este artículo crearemos la parte del código que encuentra el camino más corto entre los dos puntos.

La clase Nodo

Lo primero que necesitamos siguiendo la teoría es tener la forma de crear un nodo. Cada nodo debe de contener la siguiente información.

  • Posición – Coordenadas del nodo.
  • Padre. Almacena el nodo padre.
  • Valor de H. Distancia con el punto objetico.
  • Valor de G. Distancia recorrida hasta ese nodo.
  • Valor de F. Suma de G más H.

Eso son los datos que contiene un nodo, por lo que la mejor manera de almacenarlos en Python en creando una clase que cree esos datos automáticamente.

class Nodo:
	def __init__(self, pos=[0, 0], padre=None):
		self.pos = pos
		self.padre = padre
		self.h = distancia(self.pos, pos_f)

		if self.padre == None:
			self.g = 0
		else:
			self.g = self.padre.g + 1
		self.f = self.g + self.h

Como vemos recibe dos parámetros la posición y el nodo padre. A partir de ellos obtiene la G que si no tiene padre valdrá 0 y sino le añadirá 1 a la G de su padre. La F la obtiene de la suma de G y H. Dejo la H para el final porque para calcularla usa la siguiente función:

# Distancia entre dos puntos.
def distancia(a, b):
	return abs(a[0] - b[0]) + abs(a[1] - b[1]) #Valor absoluto.

Como ves usa matemáticas básicas para obtener la distancia entre dos puntos, ojo al dato de que la devuelve en valor absoluto, las distancias negativas no existen. Cabe destacar que el punto b (pos_f) es la posición final y es una variable declarada global.

La calcula usando la siguiente función:

def buscarPos(x, mapa):
	for f in range(mapa.fil):
		for c in range(mapa.col):
			if mapa.mapa[f]1 == x:
				return [f, c]
	return 0

La Clase AEstrella

Aquí viene la chicha del algoritmo, la clase que dará nuestro camino a seguir, la dejo entera y la comentamos.

class AEstrella:
	def __init__(self, mapa):
		self.mapa = mapa

		# Nodos de inicio y fin.
		self.inicio = Nodo(buscarPos(2, mapa))
		self.fin = Nodo(buscarPos(3, mapa))

		# Crea las listas abierta y cerrada.
		self.abierta = []
		self.cerrada = []

		# Añade el nodo inicial a la lista cerrada.
		self.cerrada.append(self.inicio)

		# Añade vecinos a la lista abierta
		self.abierta += self.vecinos(self.inicio)

		# Buscar mientras objetivo no este en la lista cerrada.
		while self.objetivo():
			self.buscar()

		self.camino = self.camino()

	# Devuelve una lista con los nodos vecinos transitables.
	def vecinos(self, nodo):
		vecinos = []
		if self.mapa.mapa[nodo.pos[0]+1][nodo.pos[1]] != 1:
			vecinos.append(Nodo([nodo.pos[0]+1, nodo.pos[1]], nodo))
		if self.mapa.mapa[nodo.pos[0]-1][nodo.pos[1]] != 1:
			vecinos.append(Nodo([nodo.pos[0]-1, nodo.pos[1]], nodo))
		if self.mapa.mapa[nodo.pos[0]][nodo.pos[1]-1] != 1:
			vecinos.append(Nodo([nodo.pos[0], nodo.pos[1]-1], nodo))
		if self.mapa.mapa[nodo.pos[0]][nodo.pos[1]+1] != 1:
			vecinos.append(Nodo([nodo.pos[0], nodo.pos[1]+1], nodo))
		return vecinos

	# Pasa el elemento de f menor de la lista abierta a la cerrada.
	def f_menor(self):
		a = self.abierta[0]
		n = 0
		for i in range(1, len(self.abierta)):
			if self.abierta[i].f < a.f:
				a = self.abierta[i]
				n = i
		self.cerrada.append(self.abierta[n])
		del self.abierta[n]

	# Comprueba si un nodo está en una lista.
	def en_lista(self, nodo, lista):
		for i in range(len(lista)):
			if nodo.pos == lista[i].pos:
				return 1
		return 0

	# Gestiona los vecinos del nodo seleccionado.
	def ruta(self):
		for i in range(len(self.nodos)):
			if self.en_lista(self.nodos[i], self.cerrada):
				continue
			elif not self.en_lista(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].pos == self.abierta[j].pos:
							del self.abierta[j]
							self.abierta.append(self.nodos[i])
							break

	# Analiza el último elemento de la lista cerrada.
	def buscar(self):
		self.f_menor()
		self.select = self.cerrada[-1]
		self.nodos = self.vecinos(self.select)
		self.ruta()

	# Comprueba si el objetivo objetivo está en la lista abierta.
	def objetivo(self):
		for i in range(len(self.abierta)):
			if self.fin.pos == self.abierta[i].pos:
				return 0
		return 1

	# Retorna una lista con las posiciones del camino a seguir.
	def camino(self):
		for i in range(len(self.abierta)):
			if self.fin.pos == self.abierta[i].pos:
				objetivo = self.abierta[i]

		camino = []
		while objetivo.padre != None:
			camino.append(objetivo.pos)
			objetivo = objetivo.padre
		camino.reverse()
		return camino

Si la estudias un poco puedes ver que sigue las directrices de la teoría, se crean las listas abierta y cerrada, se mete la posición inicial en la lista cerrada y sus vecinos a la abierta. A partir de aquí empieza un bucle que irá haciendo esto con cada uno de los vecinos, eligiendo siempre al de menor coste hasta que el Nodo objetivo sea añadido a la lista abierta, en este momento sale del bucle y llama al método camino. Que a partir del nodo objetivo añadido a la lista puede ir sacando su nodo padre hasta el que no tenga nodo padre que es el nodo inicial. Con esto tenemos un camino inverso entre el nodo objetivo y el nodo inicial.

Ahora si queréis probarlo basta con crear un objeto AEstrella pasandole nuestro mapa como parámetro e invocar a objeto.camino que es la variable que contiene la array con el camino. Si te resulta lioso no te preocupes te dejo el programa entero como va hasta ahora con algunas modificaciones para que muestre el camino a seguir.

Cualquier duda tienes los comentarios para preguntar, en el proximo tutorial haremos una interfaz gráfica en pygame que use el algoritmo.

11 Comentarios en "Pathfinding A* en Python. Parte II"

  1. Jose dice:

    Muy guapo el algoritmo, ademas de sencillo. Una sola cosa, no seria mejor una PriorityQueue para obtener directamente la entrada abierta de menor peso? En principio sería más optimo, pero tal y como esta ahora parece que funciona perfectamente.

  2. admin dice:

    Jose, No he tocado mucho el tema de colas, por eso no me he arriesgado y he preferido hacerlo así. Pero si quieres intentar hacer una versión con colas pues te animo a ellos y estaré en cantado de publicarla.

  3. j dice:

    Podrias explicarme brevemente esta parte es que me he liado un poco

    def ruta(self):
    		for i in range(len(self.nodos)):
    			if self.en_lista(self.nodos[i], self.cerrada):
    				continue
    			elif not self.en_lista(self.nodos[i], self.abierta):
    				self.abierta.append(self.nodos[i])
    			else:
    				if self.select.g+1 &lt; self.nodos[i].g:
    					for j in range(len(self.abierta)):
    						if self.nodos[i].pos == self.abierta[j].pos:
    							del self.abierta[j]
    							self.abierta.append(self.nodos[i])
    							break
    

    muchas gracias

  4. adrigm dice:

    A ver te explico, ese método lleva a cabo la asignación de los vecinos a una de las listas.

    Primero recorre la lista de vecinos del nodo seleccionado y luego va comprobando.

    Primero comprueba si ya está en la lista cerrada, en cuyo caso no hace nada. Luego comprueba si NO está en la lista abierta y si no está lo añade.

    Por último comprueba si ya está en la lista abierta, pero la g del nodo seleccionado más 1 es menor que la del nodo vecino que estamos comprobando. Si se cumple simplemente recorre la lista abierta buscando ese nodo en la lista y lo sustituye por el nuevo con los nuevos cálculos hechos.

    Para entenderlo supongo que primero te habrás mirado bien el artículo de la teoría, cualquier duda pregunta.

  5. nax dice:

    aun ando aprendiendo esto pero, habría que tener en cuenta los limites de la matriz en la funcion vecinos cierto?

  6. Rodrigo dice:

    Gracias por estos tutoriales. Estoy creando un juego de estrategia en python y la verdad esto del pathfinding es un dolor de cabeza.

  7. Etrk dice:

    se basa en si se puede mover y es menor distancia no? tanto para eso?

  8. david dice:

    Buenas, llego un poco tarde creo xD
    Pero me gustaria saber en la funcion vecinos. Acaso no tendria que tener en cuenta tambien aquellos que se encuentran en las diagonales? segun entiendo solo tienen en cuenta los vecinos de los lados. Saludos.

  9. Beto dice:

    Esta genial, gracias me interesa saber como implementaste la parte gráfica, saludos
    podrías enviarme la parte gráfica que desarrollaste, te lo agradecería mucho.

  10. john paul george dice:

    Estimado, cuando agrego una columna y/o fila a la matriz que ingresas en el txt. me arroja una secuencia de errores me podrías explicar donde declaras el numero de columnas y filas para tu matriz porfavor.

Deja un comentario