Introducción
El algoritmo A* (A estrella) es uno de los algoritmos de búsqueda de caminos más utilizados en videojuegos debido a su eficiencia y precisión. Combina las ventajas de los algoritmos de búsqueda de costo uniforme y búsqueda heurística, permitiendo encontrar el camino más corto de manera óptima.
Conceptos Clave
Antes de sumergirnos en la implementación, es importante entender algunos conceptos clave:
- Nodo: Representa un punto en el espacio de búsqueda.
- G(n): El costo desde el nodo inicial hasta el nodo n.
- H(n): La estimación heurística del costo desde el nodo n hasta el nodo objetivo.
- F(n): La suma de G(n) y H(n), utilizada para determinar el orden de exploración de los nodos.
Algoritmo A* Paso a Paso
-
Inicialización:
- Añadir el nodo inicial a la lista abierta (open list).
- Establecer G(n) del nodo inicial a 0 y calcular H(n) (usualmente utilizando la distancia Manhattan o Euclidiana).
-
Bucle Principal:
- Mientras la lista abierta no esté vacía:
- Seleccionar el nodo con el menor F(n) de la lista abierta.
- Si el nodo seleccionado es el nodo objetivo, reconstruir el camino y terminar.
- Mover el nodo seleccionado de la lista abierta a la lista cerrada (closed list).
- Para cada vecino del nodo seleccionado:
- Si el vecino está en la lista cerrada, ignorarlo.
- Si el vecino no está en la lista abierta, añadirlo y calcular sus valores G(n), H(n) y F(n).
- Si el vecino ya está en la lista abierta, comprobar si el nuevo camino a este vecino es mejor (menor G(n)). Si es así, actualizar los valores y el nodo padre.
- Mientras la lista abierta no esté vacía:
-
Reconstrucción del Camino:
- Una vez que se alcanza el nodo objetivo, reconstruir el camino desde el nodo objetivo hasta el nodo inicial utilizando los nodos padres.
Implementación en Python
A continuación, se presenta una implementación básica del algoritmo A* en Python:
import heapq
class Nodo:
def __init__(self, posicion, g=0, h=0, padre=None):
self.posicion = posicion
self.g = g
self.h = h
self.f = g + h
self.padre = padre
def __lt__(self, otro):
return self.f < otro.f
def heuristica(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def a_estrella(inicio, objetivo, grid):
lista_abierta = []
lista_cerrada = set()
nodo_inicio = Nodo(inicio, 0, heuristica(inicio, objetivo))
heapq.heappush(lista_abierta, nodo_inicio)
while lista_abierta:
nodo_actual = heapq.heappop(lista_abierta)
lista_cerrada.add(nodo_actual.posicion)
if nodo_actual.posicion == objetivo:
camino = []
while nodo_actual:
camino.append(nodo_actual.posicion)
nodo_actual = nodo_actual.padre
return camino[::-1]
vecinos = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for desplazamiento in vecinos:
vecino_pos = (nodo_actual.posicion[0] + desplazamiento[0], nodo_actual.posicion[1] + desplazamiento[1])
if (0 <= vecino_pos[0] < len(grid) and 0 <= vecino_pos[1] < len(grid[0]) and grid[vecino_pos[0]][vecino_pos[1]] == 0):
if vecino_pos in lista_cerrada:
continue
g_nuevo = nodo_actual.g + 1
h_nuevo = heuristica(vecino_pos, objetivo)
vecino_nodo = Nodo(vecino_pos, g_nuevo, h_nuevo, nodo_actual)
if vecino_nodo not in lista_abierta:
heapq.heappush(lista_abierta, vecino_nodo)
else:
for nodo in lista_abierta:
if nodo.posicion == vecino_pos and g_nuevo < nodo.g:
nodo.g = g_nuevo
nodo.f = g_nuevo + nodo.h
nodo.padre = nodo_actual
heapq.heapify(lista_abierta)
break
return None
# Ejemplo de uso
grid = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 1, 0]
]
inicio = (0, 0)
objetivo = (4, 4)
camino = a_estrella(inicio, objetivo, grid)
print("Camino encontrado:", camino)Explicación del Código
-
Clase Nodo:
- Representa cada nodo en el espacio de búsqueda.
- Contiene la posición del nodo, los costos G, H y F, y una referencia al nodo padre.
-
Función heurística:
- Calcula la distancia Manhattan entre dos puntos, utilizada como estimación heurística H(n).
-
Función a_estrella:
- Implementa el algoritmo A*.
- Utiliza una lista abierta (open list) implementada como una cola de prioridad (heapq) y una lista cerrada (closed list) implementada como un conjunto.
- Explora los vecinos del nodo actual y actualiza los costos y nodos padres según sea necesario.
- Reconstruye el camino una vez que se alcanza el nodo objetivo.
Ejercicio Práctico
Ejercicio 1: Modificar la Heurística
Modifica la función heuristica para utilizar la distancia Euclidiana en lugar de la distancia Manhattan. Implementa y prueba el nuevo algoritmo.
Solución:
import math
def heuristica_euclidiana(a, b):
return math.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2)
def a_estrella_euclidiana(inicio, objetivo, grid):
lista_abierta = []
lista_cerrada = set()
nodo_inicio = Nodo(inicio, 0, heuristica_euclidiana(inicio, objetivo))
heapq.heappush(lista_abierta, nodo_inicio)
while lista_abierta:
nodo_actual = heapq.heappop(lista_abierta)
lista_cerrada.add(nodo_actual.posicion)
if nodo_actual.posicion == objetivo:
camino = []
while nodo_actual:
camino.append(nodo_actual.posicion)
nodo_actual = nodo_actual.padre
return camino[::-1]
vecinos = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for desplazamiento in vecinos:
vecino_pos = (nodo_actual.posicion[0] + desplazamiento[0], nodo_actual.posicion[1] + desplazamiento[1])
if (0 <= vecino_pos[0] < len(grid) and 0 <= vecino_pos[1] < len(grid[0]) and grid[vecino_pos[0]][vecino_pos[1]] == 0):
if vecino_pos in lista_cerrada:
continue
g_nuevo = nodo_actual.g + 1
h_nuevo = heuristica_euclidiana(vecino_pos, objetivo)
vecino_nodo = Nodo(vecino_pos, g_nuevo, h_nuevo, nodo_actual)
if vecino_nodo not in lista_abierta:
heapq.heappush(lista_abierta, vecino_nodo)
else:
for nodo in lista_abierta:
if nodo.posicion == vecino_pos and g_nuevo < nodo.g:
nodo.g = g_nuevo
nodo.f = g_nuevo + nodo.h
nodo.padre = nodo_actual
heapq.heapify(lista_abierta)
break
return None
# Ejemplo de uso
camino_euclidiano = a_estrella_euclidiana(inicio, objetivo, grid)
print("Camino encontrado con heurística euclidiana:", camino_euclidiano)Ejercicio 2: Implementar Diagonales
Modifica el algoritmo para permitir movimientos diagonales. Asegúrate de ajustar los costos G(n) y la heurística en consecuencia.
Solución:
def a_estrella_diagonal(inicio, objetivo, grid):
lista_abierta = []
lista_cerrada = set()
nodo_inicio = Nodo(inicio, 0, heuristica(inicio, objetivo))
heapq.heappush(lista_abierta, nodo_inicio)
while lista_abierta:
nodo_actual = heapq.heappop(lista_abierta)
lista_cerrada.add(nodo_actual.posicion)
if nodo_actual.posicion == objetivo:
camino = []
while nodo_actual:
camino.append(nodo_actual.posicion)
nodo_actual = nodo_actual.padre
return camino[::-1]
vecinos = [(0, 1), (1, 0), (0, -1), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
for desplazamiento in vecinos:
vecino_pos = (nodo_actual.posicion[0] + desplazamiento[0], nodo_actual.posicion[1] + desplazamiento[1])
if (0 <= vecino_pos[0] < len(grid) and 0 <= vecino_pos[1] < len(grid[0]) and grid[vecino_pos[0]][vecino_pos[1]] == 0):
if vecino_pos in lista_cerrada:
continue
g_nuevo = nodo_actual.g + (1 if desplazamiento[0] == 0 or desplazamiento[1] == 0 else 1.414)
h_nuevo = heuristica(vecino_pos, objetivo)
vecino_nodo = Nodo(vecino_pos, g_nuevo, h_nuevo, nodo_actual)
if vecino_nodo not in lista_abierta:
heapq.heappush(lista_abierta, vecino_nodo)
else:
for nodo in lista_abierta:
if nodo.posicion == vecino_pos and g_nuevo < nodo.g:
nodo.g = g_nuevo
nodo.f = g_nuevo + nodo.h
nodo.padre = nodo_actual
heapq.heapify(lista_abierta)
break
return None
# Ejemplo de uso
camino_diagonal = a_estrella_diagonal(inicio, objetivo, grid)
print("Camino encontrado con movimientos diagonales:", camino_diagonal)Conclusión
En esta sección, hemos cubierto la implementación del algoritmo A* para la búsqueda de caminos en videojuegos. Hemos aprendido los conceptos clave, el flujo del algoritmo y cómo implementarlo en Python. Además, hemos explorado ejercicios prácticos para modificar la heurística y permitir movimientos diagonales, reforzando así nuestra comprensión del algoritmo.
En el siguiente módulo, exploraremos la navegación con NavMesh, una técnica avanzada para la navegación en entornos tridimensionales.
IA para Videojuegos
Módulo 1: Introducción a la IA en Videojuegos
- Historia y Evolución de la IA en Videojuegos
- Conceptos Básicos de IA
- Herramientas y Lenguajes de Programación
Módulo 2: Navegación en Videojuegos
- Algoritmos de Búsqueda de Caminos
- Implementación de A*
- Navegación con NavMesh
- Evitación de Obstáculos
Módulo 3: Toma de Decisiones
Módulo 4: Aprendizaje Automático
- Introducción al Aprendizaje Automático
- Redes Neuronales en Videojuegos
- Aprendizaje por Refuerzo
- Implementación de un Agente de Aprendizaje
Módulo 5: Integración y Optimización
Módulo 6: Proyectos Prácticos
- Proyecto 1: Implementación de Navegación Básica
- Proyecto 2: Creación de un NPC con Toma de Decisiones
- Proyecto 3: Desarrollo de un Agente con Aprendizaje Automático