Campos de flujo: compartir un destino sin compartir una ruta rígida

Compartir la consulta costosa del destino

Cuando muchas unidades tienen el mismo destino, un campo de flujo puede sustituir las búsquedas de ruta individuales repetidas por una guía compartida. Cada unidad muestrea una dirección cerca de su posición actual, de modo que el desplazamiento no exige construir otra ruta completa. Aun así, el resultado reutilizable pertenece a un destino y a un modelo de movimiento concretos. Emerson describe una implementación por teselas (tiles); Patel explica la búsqueda subyacente de todos los orígenes hacia una única meta. [1][2]

Separar el coste de travesía, la integración y la dirección

Mantén el coste de entrar en un terreno o atravesarlo separado del coste integrado de llegar a la meta. En un modelo de grafo discreto, define D(goal) = 0 y resuelve D(x) = min(c(x,y) + D(y)) sobre las aristas salientes válidas. Con pesos no negativos, una búsqueda de Dijkstra inversa puede construir estas distancias. Recorre las aristas invertidas, pero conservando sus costes originales en sentido directo.

Almacena de forma explícita un marcador de inalcanzable. Elige una dirección de salida válida con el mismo modelo de costes; limitarse a seguir al vecino con la menor distancia almacenada no basta cuando los costes de las aristas difieren.

Ejemplo resuelto: la ruta con menor distancia restante no siempre es la más barata

En una bifurcación, la ruta A cuesta primero 8 y después tiene un coste restante de 1. La ruta B cuesta primero 1 y después tiene un coste restante de 4. Sus totales son 8 + 1 = 9 y 1 + 4 = 5. El campo debe guiar a la unidad hacia B, aunque la distancia restante de A sea menor.

Supongamos que 200 unidades comparten este destino y esta clase de movimiento. Pueden compartir el mismo campo ya completado; eso no implica que su resolución de colisiones o su steering (control de dirección) se compartan ni que sean gratuitos. Estos costes y cantidades de unidades son ilustrativos: describen un diseño, no una aceleración medida.

Construir un campo que se pueda inspeccionar

Empieza con un mapa pequeño que contenga un muro, una franja costosa y una bolsa inalcanzable. Representa por separado los costes de travesía, los valores integrados y las direcciones elegidas. Sigue las flechas desde cada celda alcanzable y comprueba que se llega al destino sin ciclos. Verifica que la guía en diagonal respeta las mismas reglas de esquinas que se usaron para generar las distancias.

Identifica los campos en cache por meta, clase de movimiento y versión relevante del terreno. Reconstruye los datos afectados cuando desaparece un puente o cambia un permiso de travesía. Publica juntas las generaciones de campos completadas, de modo que las unidades nunca muestreen distancias y direcciones actualizadas solo a medias. Prueba las transiciones entre los límites de las teselas y las unidades que entran desde posiciones inesperadas.

Presupuestar por separado el reparto y la ejecución física

Muchas metas o clases de movimiento distintas reducen la reutilización y multiplican los datos en cache. Las celdas gruesas pueden ocultar pasos estrechos, y los vectores interpolados cerca de los muros pueden apuntar a través de obstáculos. Un campo ofrece guía de ruta; el espacio libre del cuerpo, la separación, el tráfico en cuellos de botella y la ocupación del destino siguen requiriendo un tratamiento explícito. Mide por separado la construcción del campo, la rotación de la cache, el muestreo y el movimiento local antes de decidir cuánto movimiento de multitudes ahorra realmente el campo compartido.

Fuentes

• [1] Crowd Pathfinding and Steering Using Flow Field Tiles — Elijah Emerson, Game AI Pro.
• [2] Flow Field Pathfinding for Tower Defense — Amit Patel, Red Blob Games.