Un algoritmo de movimiento básico en videojuegos

Una gran cantidad de videojuegos se basan en que los personajes, partiendo de un punto de origen, sean capaces de llegar a un destino. Dicho destino puede ser estático o en movimiento, en cuyo caso estaríamos hablando de llevar a cabo una persecución entre personajes. Por la parte del jugador, todo esto recae en la programación de los controles, y hacerlo con más o menos gracia ya es cosa suya. Pero cuando la tarea la deben de llevar a cabo los personajes que controla el ordenador, llega el momento de aplicar algún tipo de estrategia. Esta parte es muy importante, ya que de ella depende una experiencia satisfactoria. Sin embargo, a veces puede ser complejo ver a simple vista cual sería la mejor táctica para llevar a cabo la tarea de manera simple y sin demasiados cálculos.

Si empezamos por el principio, el primer problema que hemos de resolver es simplemente el expuesto al inicio. ¿Qué recorrido he de trazar para llegar de A a B de manera automatizada? La aproximación más simple, y quizá la primera que nos viene a la cabeza, sería, cada vez que el personaje se ha de mover, calcular la diferencia entre coordenadas X e Y de origen y destino e ir aumentado o disminuyendo paulatinamente cada una hasta alcanzar la meta.

A nivel de pseudocódigo, sólo para transmitir el concepto, podría ser el siguiente. Las variables x e y indicarían directamente las coordenadas del personaje en movimiento, y obj_Target englobaría los datos del objetivo:

if (x < obj_Target.x) {
    x = x + 1;
} else if (x > obj_Target.x) {
    x = x - 1;
}

if (y < obj_Target.y) {
    y = y + 1;
} else if (y > obj_Target.y) {
    y = y - 1;
}

A continuación se puede ver una demostración de su ejecución. Para simplificar y que se vean bien las transiciones, usamos un esquema de juego en cuadrícula, similar al de los juegos de Pokémon, los primeros Final Fantasy, o los Fire Emblem:

Ejemplo del algoritmo más simple para calcular trayectorias.

Sin embargo, esta aproximación tiene un pequeño problema, fruto de su suma simplicidad. El movimiento del personaje siempre será en diagonal, hasta que coincida con el eje “x” o “y” con mayor diferencia hasta el objetivo. Y a continuación, se desplazará en línea recta hacia él. Este tipo de movimiento no es muy natural, ya que lo más lógico sería trazar una línea directa al destino.

Un algoritmo relativamente simple, pero no tanto como el recién expuesto, que nos puede ayudar es el de Bresenham. Este algoritmo sirve para trazar líneas en diagonal, y normalmente se suele usar en motores gráficos. Sin embargo, también resulta útil como una primera aproximación a implementar inteligencia artificial a un personaje para que su movimiento sea más natural. Su ventaja respecto otros algoritmos similares es su eficiencia. Además, debemos tener presente que, en realidad, estamos trazando un recorrido, no una línea que se ha de mostrar en pantalla y deber quedar bonita (por ejemplo, suavizando el aspecto de sierra). Estas características lo puede hacer preferible a otros como el de Wu.

Para usar dicho algoritmo, la estrategia varía un poco respecto al anterior, ya que normalmente lo que haremos ahora es calcular primero la trayectoria hacia el objetivo, y posteriormente ejecutar el seguimiento de dicha trayectoria. Existen diferentes implementaciones más o menos intuitivas, según como desglosan el número de casos posibles según los puntos cardinales. Una versión muy resumida en número de líneas podría ser la siguiente:

//Crear ruta de “hero” a “target”

//1. Calcular diferencias entre coordenadas
dx = abs(target_x - hero_x);
dy = abs(target_y - hero_y);
error = dx - dy;

//2. Calcular puntos de la trayectoria
steps_len = max(dx, dy);

//3. Calcular los tipos de incremento necesarios por
//eje de coordenadas
if (hero_x < target_x) { sx = 1; } else { sx = -1; }
if (hero_y < target_y) { sy = 1; } else { sy = -1; }

//4. Calcular trayectoria
for (i = 0; i < steps_len; i++) {

  e2 = 2*error;
  if (e2 > -dy) {
    error = error - dy;
    hero_x = hero_x + sx;
  }
  if (e2 < dx) {
    error = error + dx;
    hero_y = hero_y + sy;
  }

  //5. Guardamos el punto resultante. La variable
  // “steps” contendrá la trayectoria.
  //Cada posición és un punto del recorrido.
  //Las “x” en el subíndice 0, y las “y” en el 1.
  steps[i,0] = hero_x;
  steps[i,1] = hero_y;
}

La idea es calcular qué eje de coordenadas tiene mayor distancia entre el origen y el destino, en valor absoluto. Este eje será el que llevará la voz cantante. A partir de este valor, se van ubicando los incrementos en el eje con menor distancia de manera que se repartan equitativamente a lo largo desplazamiento del eje con mayor diferencia. En el caso del ejemplo, la variable error es la que controla que se mantenga dicha proporción y e2 sirve de tope.

Para ejecutar el movimiento, solo hay que consultar la trayectoria pregenerada e irse desplazando hacia cada punto, paulatinamente, de acuerdo a la rapidez que queremos que tenga el personaje. Al tratarse de puntos adyacentes, podemos usar el algoritmo inicial, solo que en este caso el valor a comparar con la posición actual en cada transición no es la meta final, sino el siguiente punto de la trayectoria. La pega está, no todo puede ser perfecto, en que si el objetivo se mueve, hay que recalcular la trayectoria.

A continuación se puede ver una demostración de su ejecución, en la que se puede apreciar, en según que combinaciones, la diferencia respecto al algoritmo simple.

Ejemplo de ejecución del algoritmo de Bresenham.

A partir de aquí, ya podemos empezar a complicar la cosa, especialmente con la inclusión de obstáculos. De hecho, los propios algoritmos de trazado de lineas nos pueden servir también para establecer, antes de mover a un personaje, si el objetivo está realmente en su campo de visión o no (y evitar “hacer trampas”). Pero esto lo lo dejo para otro día 🙂

Nota: Los proyectos con el código fuente de ambos ejemplos, en formato GameMaker (disponible en versión gratuita) lo podéis descargar a continuación: Pathfinding.gmx.zip y Bresenham.gmx.zip.

Joan Arnedo es profesor de los estudios de Informática, Multimedia y Telecomunicaciones en la UOC. Director académico del Postgrado de Diseño y Programación de Videojuegos e investigador en el campo de la ludificación y los juegos serios en el eLearn Center. Su experiencia se remonta a cuando los ordenadores MSX poblaban la Tierra…