Razón Artificial

La ciencia y el arte de crear videojuegos

Pathfinding A* en Python. Parte I

Escrito por adrigm el 31 de marzo de 2010 en Inteligencia Artificial, Noticias, Programación | 3 Comentarios.

Voy a explicar como implementar un algoritmo de búsqueda del camino mas corto en Python, el Pathfinding es muy usado y es una de las técnicas básicas de la inteligencia artificial. Consiste en encontrar el camino más corto entre dos puntos superando obstáculos. Remarco lo de superando obstáculos porque obviamente el camino más corto entre dos puntos es la línea recta.

Esta técnica es muy usada en videojuegos de estrategia y en general en todos los videojuegos en donde se trata que la inteligencia artificial encuentre el camino más corto entre dos puntos. También es aplicable a la robótica para controlar los movimientos de un robot y que este supere obstáculos.

Antes de empezar es impresindible leer el artículo A* Pathfinding. Camino óptimo y entenderlo donde se explica el algoritmo, en este artículo usaré esas ideas para implementarlo en Python. He dividido el artículo en tres partes esta primera tratará de la creación de un entorno donde aplicar el algoritmo, la segunda parte es la creación del pathfinding en sí, el buscador del camino óptimo y por último en la tercera parte haré una interfaz gráfica en Pygame donde aplicarlo.

Creando un Mapa

Lo primero que necesitamos es un mapa donde probarlo. Para no complicarnos la vida usaremos un archivo de texto plano, un txt. A continuación un ejemplo:

# # # # # # # # # # # # # # # # #
# T . . . . . . . . . # . # . . #
# # # # # . # # # . . . . # . # #
# . . . . . . . . . # . . . . . #
# . # # # . # . # . # . # . # . #
# . # . # . # . # . # . # . # . #
# . # . # . # . # . . # # . # . #
# . # . . . # . # # . # . # . . #
# . . . # # # . . # . . . . . # #
# . . . . . . . # # . # # . . . #
# # # # . # . . . # . # . . # . #
# . . . . # . # . . . # # . # . #
# . # # . # . # . # . . . . . . #
# # # # # # # # # # # # # # # S #

He usado caracteres que faciliten visualmente el diseño del mapa, en este sencillo ejemplo hay 4 tipos de datos:

  • Las almohadillas(#) – Representan los muros, son las zonas no atravesables.
  • Los puntos(.) – Son los caminos, la zonas transitables por las que nos podemos mover.
  • La T – Representa la posición inicial del jugador.
  • La S – Representa el destino, el punto al que ha de llegar.

Con esto ya tenemos un mapa base en el que poder probar nuestro algorimo, lo guardamos en un archivo con el nombre mapa.txt y lo ponemos en el directorio de trabajo. Es hora de empezar con el código.

Leyendo el Mapa

Creamos el archivo principal del proyecto yo lo he llamado buscador.py, puedes llamorlo como quiera y he cargado mi plantilla base.

Lo primero que necesitamos es un método de leer el txt y convertirlo en algo que podamos manejar con Python. Yo lo he convertido en una lista bidimensional que contiene las filas y columnas del mapa y a cada tipo de carácter/bloque le he asignado un valor. Las siguientes tres funciones Hacen todo esto.

# Quita el ultimo caracter de una lista.
def quitarUltimo(lista):
	for i in range(len(lista)):
		lista[i] = lista[i][:-1]
	return lista

# Covierte una cadena en una lista.
def listarCadena(cadena):
	lista = []
	for i in range(len(cadena)):
		if cadena[i] == ".":
			lista.append(0)
		if cadena[i] == "#":
			lista.append(1)
		if cadena[i] == "T":
			lista.append(2)
		if cadena[i] == "S":
			lista.append(3)
	return lista

# Lee un archivo de texto y lo convierte en una lista.
def leerMapa(archivo):
	mapa = open(archivo, "r")
	mapa = mapa.readlines()
	mapa = quitarUltimo(mapa)
	for i in range(len(mapa)):
		mapa[i] = listarCadena(mapa[i])
	return mapa

Como puedes ver he asignado diferentes valores según el carácter quedando la relación así:

  • Caminos – 0
  • Paredes – 1
  • Jugador – 2
  • Salida – 3

La clase Mapa:

A continuación creamos una clase que represente el mapa, en principio solo va a tener dos métodos, el constructor y el str que nos servirá para probar que funciona correctamente, la clase es la siguiente:

class Mapa:
	def __init__(self, archivo="mapa.txt"):
		self.mapa = leerMapa(archivo)
		self.fil = len(self.mapa)
		self.col = len(self.mapa[0])

	def __str__(self):
		salida = ""
		for f in range(self.fil):
			for c in range(self.col):
				if self.mapa[f]1 == 0:
					salida += "."
				if self.mapa[f]1 == 1:
					salida += "# "
				if self.mapa[f]1 == 2:
					salida += "T "
				if self.mapa[f]1 == 3:
					salida += "S "
			salida += "\n"
		return salida

Como ves el constructor llama a la funcion leerMapa() que hicimos antes y también almacena el tamaño del mapa en filas y columnas. El método __str__ nos sirve para sustituir a print y ver una representación del mapa.

Por último creamos un mapa dentro de la función main() y lo imprimimos a ver como queda:

def main():
	mapa = Mapa()
	print mapa
	return 0

Con esto ya tenemos todo listo para aplicar el algoritmo pathfinding A* y encontrar el camino más corto entre T y S que veremos en el siguiente artículo.

Si algo no funciona o quieres probarlo directamente puedes descargarlo aquí.

3 Comentarios en "Pathfinding A* en Python. Parte I"

    • me dice lo siguiente:
      Traceback (most recent call last):
      File “C:/Users/Alumno/Desktop/LogicaLaberinto.py”, line 1, in
      from ClasesLaberinto import *
      File “C:/Users/Alumno/Desktop\ClasesLaberinto.py”, line 11
      if self.mapa[f]1 == 0:
      ^
      SyntaxError: invalid syntax

  1. arreglé el error que me arrojaba antes pero no me imprime nada, ¿que version de python usaron?

Deja un comentario