() translation by (you can also view the original English article)
Pathfinding es omnipresente en los juegos. Por lo tanto, es importante entender las implicaciones que están presentes al usar algoritmos como A *. En este tutorial vamos a cubrir un método relativamente nuevo para buscar mundos basados en grid: Jump Point Search, que puede acelerar A * en órdenes de magnitud.
Nota: Aunque este tutorial está escrito usando AS3 y Flash, debería ser capaz de utilizar las mismas técnicas y conceptos en casi cualquier entorno de desarrollo de juegos.
Esta implementación se basa en el documento original y el
artículo sobre JPS que se encuentran aquí: Jump Point Search. La
implementación basada en Lua, Jumper, se usó para ayudar con algunas
partes de la implementación.
Demostración de búsqueda Jump Point
Haga clic en el SWF para enfocarlo, luego mueva el mouse sobre áreas que no sean de bloqueo del mapa para que los NPC intenten acceder a él. Pulse Espacio para alternar entre A *, Búsqueda de punto de salto y ambos.
¿No flash? Mira el video de YouTube en su lugar:
Preparar
La implementación de demostración anterior usa AS3 y Flash con Starling Framework para la representación acelerada de GPU y la biblioteca de polygonal-ds para estructuras de datos.
Pathfinding
El pathfinding a menudo se usa en videojuegos y seguramente se encontrará con él en algún momento de su carrera de desarrollo de juegos. Su uso principal es dar un comportamiento de movimiento de aspecto inteligente a las entidades artificiales (NPC), para evitar chocar con las cosas (a menudo).
En algunos juegos, el avatar del jugador también está sujeto a pathfinding (juegos de estrategia, muchos juegos de rol en tercera persona y juegos de aventura). Entonces, puede suponer que el problema de la ruta está resuelto, pero desafortunadamente ese no es el caso; no hay una bala de plata que puedas usar y acaba de terminar con ella.
E incluso en los grandes juegos AAA, todavía encontrarás cosas divertidas como esta:
Puede que no haya una bala de plata, pero hay una bala: el algoritmo A * (Una estrella). En este tutorial vamos a ver una breve descripción general de A * y cómo acelerarlo utilizando otro algoritmo, Jump Point Search.
Primero, necesitamos una forma de representar nuestro mundo del juego de forma que un algoritmo de identificación de ruta pueda usarlo.
Representaciones mundiales
Una de las cosas más importantes a considerar cuando se piensa en la búsqueda de caminos para su juego es la representación mundial. ¿Cómo se organizan los datos de las áreas y obstáculos que se pueden pasar con las estructuras de programación en la memoria?
La representación más simple que puede usar es una estructura basada en cuadrículas, donde los nodos de ruta están organizados en una cuadrícula y pueden representarse mediante una matriz 2D. Vamos a usar esta representación en este tutorial. Específicamente será una representación de cuadrícula de ocho vías: permite el movimiento en direcciones rectas y diagonales.
Los píxeles negros en la imagen representan las celdas de bloqueo.
Sus requisitos pueden ser diferentes, por lo que esta estructura puede no ser adecuada para usted. Lo bueno es que con un poco de procesamiento (generalmente realizado fuera de línea) puede cambiar las representaciones de ruta a otros formatos. Las alternativas al enfoque basado en la red incluirían elementos como el polígono (obstáculos representados por polígonos) o las mallas de navegación (áreas de navegación representadas por polígonos); estos pueden representar los mismos datos con menos nodos.
Otra información que se puede almacenar en la representación del mapa son los costos: cuánto cuesta viajar de un nodo a otro. Esto se puede usar para que la IA determine la ruta que, por ejemplo, prefiere carreteras sobre un terreno regular (lo que hace que el costo de la carretera sea menor que el terreno).
Jump Point Search está específicamente diseñado para la representación de mapas en cuadrícula de ocho vías, así que lo usaremos. Además, en su forma vainilla, no admite mapas ponderados. (En la sección final, discutiré una posible forma de remediar esto).
A * Refrescador de ruta de acceso
Ahora tenemos una representación mundial echemos un vistazo rápido a la implementación de A *. Es un algoritmo de búsqueda de gráficos ponderado que utiliza heurística (pequeños "consejos") sobre cómo buscar mejor el área desde el nodo de inicio hasta el nodo final.
Le recomiendo que revise esta
visualización de algoritmos de pathfinding:
PathFinding.js - visual. Jugar con él puede aumentar tu intuición de lo que el algoritmo
realmente está haciendo, ¡además es divertido!
Para la identificación de ruta usando A * en cuadrículas rectangulares hacemos lo siguiente:
1 |
|
2 |
1. Find node closest to your position and declare it start node and put it on |
3 |
the open list. |
4 |
2. While there are nodes in the open list: |
5 |
3. Pick the node from the open list having the smallest F score. Put it on |
6 |
the closed list (you don't want to consider it again). |
7 |
4. For each neighbor (adjacent cell) which isn't in the closed list: |
8 |
5. Set its parent to current node. |
9 |
6. Calculate G score (distance from starting node to this neighbor) and |
10 |
add it to the open list |
11 |
7. Calculate F score by adding heuristics to the G value. |
La heurística consiste esencialmente en adivinar la posibilidad de que el nodo que se está evaluando conduzca a la meta. La heurística puede marcar una gran diferencia en la eficacia de los algoritmos de determinación de ruta ya que tienden a limitar la cantidad de nodos que deben visitarse. Vamos a usar la distancia de Manhattan para nuestros propósitos (lo que significa que los nodos más cercanos a la meta tendrán un número menor):
1 |
|
2 |
private function manhattanDistance(start:Node, end:Node):int { |
3 |
return Math.abs(end.x - start.x) + Math.abs(end.y - start.y); |
4 |
}
|
Esto es más o menos eso. Paramos el algoritmo cuando encontramos el nodo objetivo, y luego rastreamos usando la variable padre del nodo para construir la ruta.
Los algoritmos de búsqueda también se pueden usar para otras cosas. A * es un algoritmo de búsqueda de grafos general ponderado, y puede usarse en cualquier gráfico de este tipo. Esto puede abarcar otros campos en IA, como encontrar los pasos óptimos para lograr ciertos objetivos: lanzar una bomba o correr en busca de refugio y tratar de escabullirse detrás de un enemigo.
En el desarrollo del juego, necesitamos hacer las cosas rápido, al actualizar nuestros juegos a 60 cuadros por segundo cada milisegundo cuenta. Aunque A * funciona razonablemente bien para algunos usos, existe la necesidad de hacerlo más rápido o utilizar menos memoria.
Optimizaciones
Elegir la representación es lo primero que tendrá un impacto en el rendimiento de la ruta de acceso y la elección del algoritmo de determinación de ruta. El tamaño del gráfico que se busca tendrá una gran correlación en el rendimiento de su ruta (lo que tiene sentido, es más fácil encontrar su camino en su habitación que en una gran ciudad).
Luego consideraría optimizaciones de mayor nivel que generalmente implican agrupar los datos en regiones más pequeñas y luego buscarlas mientras refinan caminos en regiones más pequeñas recorridas. Por ejemplo, si quieres ir a un restaurante en una ciudad vecina, primero debes considerar cómo llegas de tu ciudad a esa, y una vez que estás en esa ciudad, limitas tu "búsqueda" al área donde se encuentra el restaurante. ignorando el resto. Esto incluiría cosas como pantanos, eliminación de callejones sin salida y HPA *.
En el nivel más bajo tienes que hacer la búsqueda. Usted eligió su representación de datos y posibles abstracciones y luego los conectó a un algoritmo que seleccionará los nodos, viajará aquí y allá en busca del objetivo. Estos algoritmos generalmente se basan en el algoritmo de búsqueda A * con posibles modificaciones. En casos más simples, puede salirse con la suya usando A * recta que le ofrece la simplicidad. Proporcioné una implementación basada en grid en la descarga de la fuente.
Jump Point Search
Dado que este tutorial trata sobre la implementación de Jump Point Search, el gráfico de pathfinding se representará con una grilla. Y específicamente debe ser una cuadrícula de ocho vías ya que el algoritmo la usa directamente.
Lo que Jump Point Search realmente hace es eliminar muchos nodos intermedios en cierto tipo de combinaciones de grillas. Se salta un montón de estos que agregaría a la lista abierta y lista cerrada, así como a otros cálculos, a favor de hacer un poco más de procesamiento al elegir el siguiente nodo.
Al igual que con A *, elegimos de la escena abierta el nodo con la puntuación F más baja. Pero aquí es donde las cosas comienzan a ponerse interesantes. En lugar de elegir nodos adyacentes, llamaremos a esta función para que lo haga por nosotros:
1 |
|
2 |
function identifySuccessors(current:Node, start:Node, end:Node):Vector.<Node> { |
3 |
var successors:Vector.<Node> = new Vector.<Node>(); |
4 |
var neighbours:Vector.<Node> = nodeNeighbours(current); |
5 |
|
6 |
for each (var neighbour:Node in neighbours) { |
7 |
// Direction from current node to neighbor:
|
8 |
var dX:int = clamp(neighbour.x - current.x, -1, 1); |
9 |
var dY:int = clamp(neighbour.y - current.y, -1, 1); |
10 |
|
11 |
|
12 |
// Try to find a node to jump to:
|
13 |
var jumpPoint:Node = jump(current.x, current.y, dX, dY, start, end); |
14 |
|
15 |
|
16 |
// If found add it to the list:
|
17 |
if (jumpPoint) successors.push(jumpPoint); |
18 |
}
|
19 |
|
20 |
return successors; |
21 |
}
|
Lo que hace es eliminar los nodos que no son interesantes para nuestro camino. Para esto usamos la dirección de parent como la guía principal. Aquí hay ejemplos de poda de los nodos que ignoraremos para direcciones horizontales y verticales:
Ejemplo de una de las situaciones de poda horizontal.
En el código, esto terminará como una serie de declaraciones if que
verifican estas situaciones. Puede ver el ejemplo aquí, que describe el
caso correcto de la imagen:
1 |
|
2 |
if(directionY == 0) { |
3 |
if (!_world.isBlocked(current.x + directionX, current.y)) { |
4 |
if (_world.isBlocked(current.x, current.y + 1)) { |
5 |
// create a node with the new position
|
6 |
neighbours.push( |
7 |
Node.pooledNode(current.x + directionX, current.y + 1)); |
8 |
}
|
9 |
}
|
10 |
}
|
Ejemplo de situaciones de poda diagonal.
Después de elegir el vecino, tratamos de encontrar un punto de salto, que es un nodo que se puede alcanzar desde el actual, pero no necesariamente de una sola manera. Para decirlo más formalmente, lo que JPS hace es eliminar la simetría entre las rutas: cada una tiene una permutación diferente de los mismos movimientos:
Ejemplo de simetría de ruta.
Entonces, para grandes espacios abiertos podemos tener grandes victorias. Así es como funciona el método de salto:
1 |
|
2 |
function jump(cX:int, cY:int, dX:int, dY:int, start:Node, end:Node):Node { |
3 |
// cX, cY - Current Node Position, dX, dY - Direction
|
4 |
|
5 |
// Position of new node we are going to consider:
|
6 |
var nextX:int = cX + dX; |
7 |
var nextY:int = cY + dY; |
8 |
|
9 |
// If it's blocked we can't jump here
|
10 |
if (_world.isBlocked(nextX, nextY)) return null; |
11 |
|
12 |
// If the node is the goal return it
|
13 |
if (nextX == end.x && nextY == end.y) return new Node(nextX, nextY); |
14 |
|
15 |
// Diagonal Case
|
16 |
if (dX != 0 && dY != 0) { |
17 |
if (/*... Diagonal Forced Neighbor Check ...*/) { |
18 |
return Node.pooledNode(nextX, nextY); |
19 |
}
|
20 |
|
21 |
// Check in horizontal and vertical directions for forced neighbors
|
22 |
// This is a special case for diagonal direction
|
23 |
if (jump(nextX, nextY, dX, 0, start, end) != null || |
24 |
jump(nextX, nextY, 0, dY, start, end) != null) |
25 |
{
|
26 |
return Node.pooledNode(nextX, nextY); |
27 |
}
|
28 |
} else { |
29 |
// Horizontal case
|
30 |
if (dX != 0) { |
31 |
if (/*... Horizontal Forced Neighbor Check ...*/) { |
32 |
return Node.pooledNode(nextX, nextY); |
33 |
}
|
34 |
/// Vertical case
|
35 |
} else { |
36 |
if (/*... Vertical Forced Neighbor Check ...*/) { |
37 |
return Node.pooledNode(nextX, nextY); |
38 |
}
|
39 |
}
|
40 |
}
|
41 |
|
42 |
/// If forced neighbor was not found try next jump point
|
43 |
return jump(nextX, nextY, dX, dY, start, end); |
44 |
}
|
Eliminé los controles de vecinos forzados de las declaraciones if porque son bastante grandes. Básicamente consisten en los controles que son similares a los que usamos cuando seleccionamos vecinos para un nuevo nodo (muchos controles para ver si las células están bloqueadas). Sirven para detectar cuándo se nos permite tener nuestras suposiciones sobre la simetría.
Ejemplo de comportamiento de la función de salto.
La caja diagonal es especial y debemos mirar no solo a los vecinos forzados en las direcciones diagonales, sino también en las direcciones horizontal y vertical, y si alguno falla, debemos colocar un nodo forzado como punto de salto. También tenemos que considerar un caso especial del nodo objetivo, donde el método de salto finaliza.
Cada vez que no encontramos un nodo de búsqueda llamamos a la función de salto recursivamente en la dirección especificada. En la demostración, he desarrollado esta llamada recursiva ya que se llamará mucho. (En mi prueba, esto mejoró el rendimiento en un factor de dos).
Esto es lo que hace JPS; el resultado final son nuevos nodos para A * verificar y procedemos con el algoritmo. Cuando se encuentra el nodo objetivo, reconstruimos el camino y lo devolvemos.
Propiedades
JPS puede omitir muchos nodos durante la búsqueda, lo que puede proporcionar mejoras de velocidad agradables (en mi proyecto es alrededor de 30 veces por encima de A *), pero tiene un costo.
Funciona mejor en una grilla uniforme, pero se puede hacer que funcione sin uniformes mediante ajustes adicionales, marcando a los vecinos como forzados donde hay una transición a un nodo de diferentes costos (mejor usar costos discretos).
En un juego en el que estoy trabajando, la parrilla es uniforme, excepto en el caso de las carreteras, que cuestan mucho menos que caminar en terrenos regulares. (Se ve mucho mejor cuando el personaje lo respeta). Al final he resuelto esto precomputando algunos valores de las posiciones de la carretera. Cuando se inicia la búsqueda de ruta, el algoritmo busca los puntos más cercanos a la ruta desde los nodos de inicio y objetivo, y luego busca un gráfico especial de carreteras de alto nivel (que está precalculado), y luego usa JPS para buscar áreas de terreno.
Depuración
Una nota rápida sobre la depuración. La depuración de este tipo de algoritmos puede ser muy difícil, y es casi seguro que la primera implementación tendrá algún error difícil de encontrar. Puedes hacerte un favor y construir algún tipo de visualización funcionalmente y dibujar lo que está sucediendo cuando se ejecuta el algoritmo.
Si obtiene un error, debe reducir el dominio (tamaño de la cuadrícula) al mínimo que le permita reproducir su problema y realizar la prueba desde allí. Como probablemente puedas adivinar, ¡mi primera implementación de JPS no funcionó de inmediato!
