Razón Artificial

La ciencia y el arte de crear videojuegos

IA en videojuegos – Persiguiendo y evadiendo II

Escrito por adrigm el 28 de octubre de 2010 en Desarrollo Videojuegos, Inteligencia Artificial, Programación | 4 Comentarios.

En la primera parte vimos un algoritmo de persecución y evasión bastante simple, pero efectivo. En este artículo vamos a ver otro que es algo mejor que el anterior.

Persiguiendo en la línea de visión

Este algoritmo consiste en que el depredador persigue a la presa en línea recta desde su posición hasta la presa. En teoría el movimiento en línea recta es el camino mas corto entre dos puntos, a menos que haya obstáculos o que la presa esté en movimiento. Si hay obstáculos no es tema de este artículo pues necesitamos combinarlo con un algoritmo de pathfinding, sin embargo, si la presa está en movimiento el algoritmo también es válido, solo que debemos calcular la línea recta en cada interacción del bucle, haciendo que aunque nos movamos en línea recta, al cambiar la dirección de la recta podamos trazar un camino curvo, esté algoritmo es más eficiente que el anterior.

En la imagen anterior supongamos que el círculo es el depredador y la presa es el cuadrado, que está quieta. Los diferentes círculos son las posiciones del depredador en diferentes periodos de tiempo, en los que calcula una nueva recta hacia la presa, como la presa está estática es siempre la misma recta la que debe seguir el depredador.

Vamos a ver dos versiones de este algoritmo una para juegos basados en tiles y otra para espacios continuos.

Línea de visión para juegos basados en tiles

Como dijimos en el articulo anterior los juegos basados en tiles se dividen en casillas. Esto crea una limitación de movimiento que no se aplica a los entornos continuos. En los entornos continuos, las posiciones por lo general se representan con variables en punto flotante. Esas posiciones se asignan a los píxeles de la pantalla más cercanos. Al cambiar de posición en un entorno continuo puedes saltarte algunos píxeles ya que suelen ser lo suficientemente pequeños como para que el movimiento sea fluido y no se noten los saltos de uno a otro.

En los juegos basados en tiles, sin embargo, el cambio de posiciones es más restrictivo. Por su propia naturaleza, el movimiento los movimientos son más dentados y cuadriculados. Si tenemos que nuestros tiles son cuadrados tendremos 8 posibles direcciones a las que movernos.

Como vemos en la imagen ninguna de las 8 direcciones está en línea recta entre el perseguidor y la presa matemáticamente hablando. Esto nos crea un dilema, como movernos en línea recta si no hay línea recta directa entre las casillas.

Lo que necesitamos es una manera de determinar a cuál de las ocho casillas adyacentes hay que trasladarse con el fin de que el depredador avance a la presa en línea recta.

Como mostramos anteriormente, podemos utilizar el algoritmo de persecución simple. Se calculará la ruta más corta posible para el depredador. Así que, ¿Cual es el problema? La estética, me explico. Cuando trabajamos con tiles el método de persecución simple si siempre produce una línea visual directa, veámoslo con una imagen.

Como podemos ver la primera imagen la produce un algoritmo de persecución simple que ya hemos visto. Va moviendo las coordenadas x e y de manera que se acercan a la presa. Cuando la coordenada x coincide con la de la presa pasa a moverse en la coordenada y solamente hasta que también coincide por lo que ha alcanzado a la presa. Sin embargo, podemos ver que no es el camino más directo, como podemos ver el camino de la imagen de la derecha es mucho más directo hacia el objetivo. Cabe destacar que la distancia recorrida es la misma, 8 tiles en este caso, pero el segundo es mucho más natural el movimiento.

Otro problema sería que si en vez de uno tenemos varios perseguidores, llegados a un punto puede que todos estén en la misma coordenada y avanzando en línea hacia la presa, lo que queda algo antiestético, mejor que todos desde su posición avancen en línea recta hacia el objetivo.

El enfoque que vamos a tomar para resolver el problema consiste en utilizar un algoritmo para generar una línea entre los dos puntos que normalmente se utiliza en entornos de píxeles. Así que vamos a tratar nuestro mapa como si los diferentes tiles fueran píxeles gigantes y los cuadros que pasen por esa línea será la ruta que tomara nuestro depredador.

Por tanto el modo de hacer es trazar una línea entre el punto de origen (posición del depredador) y el punto destino (posición de la presa). Luego calculamos los puntos por los que pasa la recta y ya tendríamos los cuadros, por los que pasaría nuestro personaje, pero hay algo más. Hay varias maneras de calcular los puntos por los que pasa una recta, nosotros vamos a usar el algoritmo de Bresenham. Este algoritmo es uno de los más eficientes para dibujar líneas en entornos basados en píxeles. Este algoritmo es ideal porque a diferencia de otros algoritmos no dibuja dos puntos adyacentes en el eje más corto. Veámos.

A la derecha podemos ver los puntos que dibujarían otros algoritmos, es decir, todos los cuadros por los que pasa la recta. Sin embargo como vemos, ese camino no es el más corto ni el más eficiente. Sin embargo a la derecha podemos ver los puntos por los puntos que dibujaría en algoritmo Bresenham. Como vemos no dibuja dos puntos adyacentes en el eje más corto (en este caso el eje x) Obteniendo así un camino directo y optimizado. Creo que se puede ver claramente como el camino de la izquierda es mucho más corto que el de la derecha.

El algoritmo de Bresenham no es nada complicado, pero puede ser lioso porque hay que detectar cual es el punto más a la izquierda y cual más a la derecha. En este artículo podéis ver la explicación del algoritmo, y una implementación en C, tiene la explicación del algoritmo, pero da por supuesto que el eje corto es el x y no el y. Sin embargo en este otro artículo al final del mismo encontré una implementación generalizada para dos puntos cuales quieras. He hecho una traducción a Python del programa.

class Punto:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y
        
    def __str__(self):
        return "(" + str(self.x) + ", " + str(self.y) + ")"
        

def linea(p1, p2):
    puntos = []
    dx = (p2.x - p1.x)
    dy = (p2.y - p1.y)
    
    # Determinar que punto usar para empezar y cual para terminar.
    if dy < 0:
        dy = -dy
        stepy = -1
    else:
        stepy = 1
    if dx < 0:
        dx = -dx
        stepx = -1
    else:
        stepx = 1
    x = p1.x
    y = p1.y
    
    # Bucle hasta llegar al otro extremo de la linea.
    if dx > dy:
        p = 2*dy-dx
        while x != p2.x:
            x += stepx
            if p < 0:
                p += 2*dy
            else:
                y += stepy
                p += 2*(dy-dx)
            puntos.append(Punto(x, y))
    else:
        p = 2*dx-dy
        while y != p2.y:
            y = y + stepy
            if p < 0:
                p += 2*dx
            else:
                x += stepx
                p += 2*(dx-dy)
            puntos.append(Punto(x, y))
    return puntos
            

p = Punto(2, 3)
q = Punto(9, 6)
puntos = linea(p, q)
for i in range(len(puntos)):
    print puntos[i]

Esto es un programa de prueba que lo implementa, imprimiendo en pantalla los puntos por los que pasaría. He creado una clase punto para manejarlos más fácil, pero el algoritmo en sí está en la función línea que devuelve la lista de puntos que tendría que tomar el depredador.

Ojo, si la presa se mueve de su posición habría que calcular de nuevo las posiciones a moverse, por lo que si la presa está en movimiento hay que calcular en cada bucle la nueva línea, si sabes que la presa se va a mover sí o sí en la siguiente interacción optimizar el algoritmo para que no calcule toda la lista y solo calcule la siguiente posición.

El resultado sería como el siguiente.

Como vemos es un camino mucho más natural y estético, haciendo que las persecuciones sean más inteligentes y realistas. En el próximo artículo veremos el problema en juegos sin tiles, es decir, de espacios continuos con coordenadas en coma flotante.

Deja un comentario