Razón Artificial

La ciencia y el arte de crear videojuegos

IA en videojuegos – Persiguiendo y evadiendo I

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

En este artículo nos centraremos en el problema omnipresente de la persecución y la evasión. Ya sea que esté desarrollando un juego de acción espacial, una simulación, estrategia o un juego de rol, es probable que necesites que los personajes no jugadores de la IA tengan que perseguir o huir del jugador. En un juego arcade la situación podría implicar tener naves enemigas que deben perseguir o evadir al jugador o un misil guiado que debe acabar con nosotros. En cualquier caso, necesitas una cierta lógica que permite a los depredadores no jugadores cazar y a sus presas, correr.

El problema de perseguir/evadir consta de dos partes. La primera parte consiste en la decisión de iniciar una persecución o una evasión. La segunda parte consiste en efectuar la persecución o la evasión, es decir, ser depredador o presa. Se podría decir que el problema contiene un tercer elemento: Evitar obstáculos. Tener que evitar obstáculos mientras se persigue o se huye definitivamente complica mucho las cosas, por lo que los algoritmos serán más difíciles de programar. En este artículo no nos centraremos en evitar obstáculos, pero ya hemos visto en el blog varios artículos de pathfinding para evitar obstáculos y en próximos artículos veremos como combinarlos con la persecución y la huida. De la primera parte entra en la toma de decisiones que veremos en futuros artículos cuando tratemos las maquinas de estados finitos y las redes neuronales. Por tanto en este artículo nos centraremos en la parte central del problema que es la persecución o la huida en sí misma.

La forma más simple y el método más común de programar una persecución consiste en actualizar las coordenadas del perseguidor (lo llamaremos depredador) en cada bucle del juego tal que las coordenadas que separan a depredador y presa sean cada vez menores. Este algoritmo no presta atención ni a la velocidad ni a la dirección de la presa y el depredador. Este método es eficaz si el depredador se mueve constante y en la misma dirección y no hay obstáculos, pero tiene sus limitaciones, como veremos.

Este método como vemos es muy básico, hay otros métodos que seguramente te resulten más útiles que junto con un motor de física se pueden combinar para tener en cuenta distancia y velocidades de depredador y presa. En los que el depredador podría tratar de interceptar a su presa y no solo perseguirla. En este caso, la información de posición y velocidad relativa puede utilizarse como entrada para un algoritmo que determinará la actuación adecuada: la dirección de la fuerza, por ejemplo, para guiar al depredador a su destino.

En este artículo vamos a ver varios métodos de persecución y evasión empezando por los métodos más básicos.

Persecución y evasión básica

El método más básico consiste, como ya dijimos, en comprobar las coordenadas de la presa y en función de ella mover nuestras coordenadas, para la evasión es lo mismo, pero hacer justo lo contrario alejarnos lo más posible.

if depredador_x > presa_x:
    depredador_x -= 1
elif: depredador_x < presa_x:
    depredador_x += 1

if depredador_y > presa_y:
    depredador_x -= 1
elif: depredador_y < presa_y:
    depredador_y += 1

Como vemos en el código comprobamos si la coordenada x del depredador es mayor que la coordenada x de la presa en cuyo caso disminuimos la coordenada x del depredador con el fin de acercarlo a la presa, si por el contrario la coordenada x es menor a la de la presa lo que hacemos es aumentarla. Lo mismo se aplica a la coordenada y.

Para la evasión es lo mismo, pero si la coordenada x de la presa es mayor que la coordenada x del depredador pues lo que hacemos es seguir aumentándola con el fin de alejarnos.

if presa_x > depredador_x:
    presa_x += 1
elif: presa_x < depredador_x:
    presa_x -= 1

if presa_y > depredador_y:
    presa_y += 1
elif: presa_y < depredador_y:
    presa_y -= 1

Podemos ver que si las velocidades del depredador y la presa son las mismas y ambas se mueven en una unidad por ciclo de juego como en el ejemplo, la distancia entre ambas va a permanecer constante, el depredador deberá tener algo más de velocidad con este método si quiere alcanzar a la presa.

En juegos basados en tiles el mapa esta dividido en celdas que pueden ser cuadrados, hexágonos, etc. y la posición del jugador está limitada a una de estas celdas. El moviento de jugador está limitado a estos tiles, normalmente a los tiles adyacentes. En un entorno continuo viene dado por un punto con coordenadas x e y normalmente en coma flotante y puede moverse en cualquier dirección.

El enfoque anterior es válido tanto para un método como para otro, pues en vez de coordenadas x e y usaremos filas y columnas. Veamos un ejemplo.

if depredador_col > presa_col:
    depredador_col -= 1
elif: depredador_col < presa_col:
    depredador_col += 1

if depredador_fil > presa_fil:
    depredador_col -= 1
elif: depredador_fil < presa_fil:
    depredador_fil += 1

Podemos ver como solo necesitamos cambiar las referencias a las coordenadas del punto por las filas y columnas y el algoritmo es perfectamente válido.

En la imagen podemos ver como sería la persecución en un mapa basado en tiles.

Cuidado con los movimientos diagonales en juegos basados en tiles, pongamos que tenemos tiles de 32×32 píxeles, el movimiento de un tile a otro en horizontal o vertical sería de exactamente 32 píxeles, pero el movimiento en diagonal seria: sqrt(25²+25²) Es decir, la raiz cuadrada de los lados al cuadrado, que es la diagonal de un tile que nos daría aproximadamente 35.35 por tanto el movimiento en diagonal debería penalizarse más.

En la segunda parte veremos métodos más avanzados, de momento esto nos sirve como introducción al tema.

4 Comentarios en "IA en videojuegos – Persiguiendo y evadiendo I"

  1. seniorH dice:

    En juegos basados en tiles de extintas consolas como el SNES (ejemplo Final Fantasy V) no se permitía el movimiento en diagonal, una solución que tendría un impacto más negativo hoy por hoy que en aquel entonces pero que sigue cumpliendo su propósito. También noten que tener el mapa en tiles no significa que no te puedas mover en punto flotante e incluso descansar ocupando varios tiles (ejemplo, otra ves el SNES, Chrono Trigger).

    Otra cosa que quiero agregar, en el primer bloque de código, a partir de la línea 6:
    if depredador_y > presa_y:
    depredador_x -= 1
    elif: depredador_y presa_y:
    depredador_y -= 1
    elif: depredador_y < presa_y:
    depredador_y += 1

    En el original reducimos el valor de x cuando debería ser de y.

  2. mariano299 dice:

    Por favor,¿alguien podria explicarme mejor esto?
    es que no lo entendi :/

    “Cuidado con los movimientos diagonales en juegos basados en tiles, pongamos que tenemos tiles de 32×32 píxeles, el movimiento de un tile a otro en horizontal o vertical sería de exactamente 32 píxeles, pero el movimiento en diagonal seria: sqrt(25²+25²) Es decir, la raiz cuadrada de los lados al cuadrado, que es la diagonal de un tile que nos daría aproximadamente 35.35 por tanto el movimiento en diagonal debería penalizarse más.”

    • Fucken dice:

      mariano299, yo lo entiendo así:
      Imagina que te paras en una baldosa cuadrada de 32×32 unidades cuadradas de longitud (cm^2, dm^2, etc). Si te mueves a la baldosa de al lado, atrás, o en frente, darás un paso de 32 unidades, pero si haces un movimiento a una baldosa diagonal, el traslado será la longitud diagonal (la hipotenusa), lo que es igual a la raíz cuadrada de la suma de cada lado al cuadrado, es decir: sqrt(32^2 + 32^2) [No sé por qué colocaron 25^2].
      sqrt(32^2 + 32^2) = 35,36 (aproximado a dos cifras decimales). Por lo que, si permites un “paso” diagonal, estarías permitiendo un paso más largo.

  3. Fucken dice:

    ¿Cómo podría validar el movimiento en un espacio limitado?
    Según el algoritmo que presentas, cuando la presa llegue al borde del mapa/espacio/área, esta no sería capaz de retroceder o cambiar de ruta, seguirá tratando de alejarse hacia un solo lado, el opuesto al cazador, pero como está en el límite, no podrá avanzar, por lo que el cazador la acorralaría fácilmente.

Deja un comentario