¿Qué ruta será la más segura, dónde están más enemigos y dónde está el botiquín de primeros auxilios más cercano? Todos estos problemas de relaciones espaciales que se encuentran con frecuencia se pueden resolver de manera efectiva utilizando particiones matemáticas llamadas "diagramas de Voronoi". A partir de esta publicación, aprenderá cómo analizar las tarjetas de juego y recibir información que garantice el realismo y el éxito de la inteligencia artificial.
Relación espacial
Una relación espacial es cualquier información que describe cómo un objeto en el espacio está relacionado con otro. Ejemplos: la distancia entre ellos, el área cubierta por cada uno de ellos espacio y la intersección de estas áreas, el número de tales objetos ubicados en un área.
Dichas relaciones se usan constantemente en los videojuegos y pueden proporcionar información de IA muy útil, así como para el propio jugador.
Voronoi tiene una respuesta
El diagrama de Voronoi describe la relación espacial entre puntos muy cercanos o sus vecinos más cercanos. Este es un conjunto de polígonos conectados obtenidos de puntos o ubicaciones. Cada línea del "área" de Voronoi se encuentra en el medio entre dos puntos.
Para entender, mira la imagen:
Como puede ver, cada línea está exactamente en el medio entre dos puntos, y todos están conectados en el centro. Agregue algunos puntos más a la escena y vea qué sucede:
¡La imagen se ha vuelto más interesante! Ya tenemos áreas reales.
¿Qué nos dice cada una de las áreas? Sabemos que estar en el área tiene la garantía de estar ubicado más cerca de un punto, que también está en el área. Esto nos dice mucho sobre lo que hay cerca; Tal es la relación espacial fundamental en los diagramas de Voronoi.
Voronoi al revés: triangulación de Delaunay
El sistema opuesto al diagrama de Voronoi se llama triangulación de Delaunay. Este diagrama consiste en líneas desde cada punto hasta sus vecinos más cercanos, y cada línea es perpendicular al borde de Voronoi que intersecta. Así es como se ve:
El blanco marca la línea Delaunay. Cada línea de Delaunay corresponde a uno y solo un borde Voronoi. Al principio parece que algunos de ellos cruzan varios bordes, pero mirando de cerca, se dará cuenta de que esto no es así.
En la figura, la línea verde de Delaunay corresponde a la costilla rosa de Voronoi. Solo imagina que la costilla rosa va más allá y ves que se cruzan.
Gracias a la triangulación de Delaunay, vemos que en lugar de polígonos ahora tenemos muchos triángulos. Esto es increíblemente útil porque dividimos el área en triángulos que se pueden representar. Esta técnica se puede utilizar para la teselación o triangulación de figuras. Genial
Además, esta es una excelente manera de crear un gráfico a partir de múltiples puntos en caso de que queramos movernos de un punto a otro. Por ejemplo, los puntos pueden indicar ciudades.
Estructura de datos Voronoi
Ya sabemos cómo se ve el diagrama de Voronoi; Ahora veamos cómo se verá su estructura de datos. Primero necesitamos guardar los puntos que son la base del diagrama de Voronoi:
class VoronoiPoint { float x float y VoronoiRegion* region }
Cada
VoronoiPoint tiene una ubicación
(x, y) y un enlace al área en la que está ubicado.
A continuación, debemos describir
VoronoiRegion :
class VoronoiRegion { VoronoiPoint* point Edge *edges[]
El área almacena un enlace a su
VoronoiPoint , así como una lista de los bordes de
VoronoiEdges .
Veamos cómo se ve
VoronoiEdges :
class VoronoiEdge { VoronoiPoint* pointA VoronoiPoint* pointB float distance
El borde conoce dos puntos que lo definen, así como la distancia entre ellos. Para la visualización, así como para construir la forma de la región poligonal, necesitamos almacenar los puntos de inicio y finalización del borde.
Y eso es todo. Con esta información, podemos construir fácilmente un diagrama de Voronoi. A continuación aprenderemos cómo se genera el diagrama de Voronoi. Pero por ahora, veamos un par de ejemplos de cómo se pueden usar estos datos.
Encuentra tu botiquín más cercano
Nuevamente, mira el diagrama de Voronoi para ver los puntos.
Si cada punto indica un botiquín de primeros auxilios, entonces podemos determinar rápidamente dónde está el más cercano a nosotros, pero primero debemos determinar el área en la que estamos. Los diagramas de Voronoi no proporcionan una forma efectiva de definir una región, sin embargo, para acelerar la búsqueda, podemos almacenar un enlace a cada región en el
árbol del
cuadrante o en el
árbol R. Y habiendo aprendido la región, podremos reconocer a sus vecinos y a los vecinos de sus vecinos.
Por ejemplo, si no hay más botiquines de primeros auxilios en su área, entonces necesita encontrar un camino hacia otro más cercano. A partir de la estructura de datos y el pseudocódigo que se muestra arriba, podemos entender que conociendo la región, podemos reconocer sus bordes. Y con la ayuda de estas costillas podemos conseguir vecinos. Tomaremos al vecino más cercano y veremos si hay un botiquín de primeros auxilios.
También puede aplicar la triangulación de Delaunay aquí. Consiste en líneas entre los botiquines de primeros auxilios. Luego puede sortearlo utilizando el algoritmo de búsqueda de ruta A * para encontrar el botiquín de primeros auxilios más cercano.
Busca una ruta segura
Reemplaza todos los botiquines de primeros auxilios con torres de vigilancia enemigas. Debe encontrar la ruta más segura entre ellos para no ser atrapado. La forma estándar de atravesar gráficos en videojuegos es usar
el algoritmo A * . Como el diagrama de Voronoi es un gráfico, es muy fácil implementar una búsqueda. Solo necesitamos el algoritmo A *, que admite estructuras de gráficos generales; planifique con anticipación y lo ayudará en el futuro.
Una vez preparado el gráfico, debe asignar peso a cada borde. Para nosotros, el valor del peso será la distancia a estas torres de vigilancia, y puede obtenerlo directamente de la estructura de datos: cada
VoronoiEdge ya conoce su distancia entre dos puntos. Por lo general, cuanto menor es el valor en el borde A *, mejor, pero en nuestro caso, mayor es el valor, ya que indica la distancia a la torre.
Así es como se ve el gráfico inicial si queremos movernos del punto A al punto B:
Aplicando peso a cada borde, veremos qué ruta es mejor elegir:
Costillas rojas indican los contactos más cercanos con las torres. El naranja indica los más largos; amarillo aún más distante y, finalmente, verde, el más seguro. Después de ejecutar A * con estos pesos, obtenemos la siguiente ruta:
Con este uso de la balanza, no se elegirá la forma
más rápida , sino
la más segura , que necesitamos. ¡La IA debería adherirse a este camino y no desviarse de él!
Puede dar otro paso para
garantizar un camino seguro: elimine todos los bordes que estén más cerca de la distancia mínima segura. Por ejemplo, si cada torre de vigilancia tiene un radio de visibilidad de 30 unidades, entonces todos los bordes, la distancia a la cual los puntos son más cortos, pueden eliminarse del gráfico y no omitirse.
También puede usar este método para encontrar la ruta más amplia para unidades grandes que no pueden pasar por cuellos de botella. Cada borde tiene una distancia entre dos puntos, por lo que sabemos si pueden pasar en este espacio.
También puede realizar la operación opuesta: use el diagrama de triangulación de Delaunay y obtenga las líneas que provienen de cada torre de vigilancia. La IA de los guardias podrá determinar rápidamente qué otras torres están cerca y, si es necesario, acudir en su ayuda.
Busque un conjunto de artículos bien embalado
Supongamos que necesitamos dejar caer un paquete de hierba gatera desde un avión para un montón de focas sentadas en el suelo. ¿Dónde está la mejor manera de soltarlo para que la mayor cantidad de gatos pueda usarlo? Esto puede ser extremadamente costoso. Pero, afortunadamente, podemos hacer una suposición razonable utilizando la triangulación de Delaunay.
Sugerencia: no olvide que la triangulación de Delaunay es solo la inversa del diagrama de Voronoi. Se forma conectando cada punto de Voronoi con puntos vecinos obtenidos de la lista de bordes.
Con esta colección de triángulos, puede explorar el área cubierta por cada uno de los triángulos. Si encontramos el triángulo con el área más pequeña, entonces tenemos tres puntos más cercanos, o gatos. Puede que no sea el grupo promedio más denso en la superficie, pero será una buena suposición. Si pudiéramos descartar algunas parcelas con menta, simplemente marcaríamos los triángulos ya seleccionados y pasaríamos a los siguientes en tamaño creciente.
La designación de tales áreas también se denomina
círculos circunscritos de la triangulación de Delaunay. Cada círculo es el círculo más grande que puede caber en los puntos del triángulo. Aquí hay una imagen de los círculos circunscritos para el diagrama de Voronoi:
Puede usar el centro exacto de los círculos para determinar el centro del área donde se envía la hierba gatera. De hecho, el radio del círculo es una forma más adecuada de determinar el mejor triángulo para doblar en lugar del área del triángulo, especialmente si los dos puntos del triángulo están muy cerca el uno del otro y el tercero está lejos; entonces obtenemos un triángulo muy afilado con un área pequeña, pero los puntos que lo definen están realmente muy separados.
Implementación de diagramas de Voronoi
Hay varias formas de generar diagramas de Voronoi, y la elección del método utilizado depende del momento en que recibamos los datos.
Algoritmo de fortuna
La forma más rápida se llama
algoritmo de Fortune . Se ejecuta en
O(n log(n)) y requiere que todos los puntos utilizados para generar el gráfico sean conocidos en el momento en que comienza la generación. Si agrega nuevos puntos más tarde, tendrá que regenerar todo el gráfico. Si hay pocos puntos, entonces esto puede no causar problemas, pero si tiene 100 mil de ellos, ¡esto puede llevar mucho tiempo!
La implementación de este algoritmo no es trivial. Parábolas cruzadas y casos especiales. Sin embargo, este es el método más rápido. Afortunadamente, hay muchas implementaciones de este algoritmo de código abierto que puede usar, y he proporcionado enlaces a ellas a continuación.
Veamos como funciona.
El algoritmo consiste en deslizar una línea (vertical u horizontal) sobre un área con puntos. Cuando encuentra un punto, comienza a dibujar una parábola, que continúa con una línea de barrido. Aquí está la animación de este proceso:
Las parábolas de intersección forman las costillas de Voronoi. ¿Pero por qué parábolas?
Para entender esto, imagine que cada punto contiene un globo inflable que se hincha hasta que choca con otra bola. Puede transferir esta idea a círculos que se expanden en un plano 2D. Haremos otra bola hacia adelante y colocaremos en cada punto un cono invertido con un ángulo de inclinación de 45 grados, aumentando hasta el infinito. Luego imagine una línea de barrido en forma de línea, también a 45 grados, que se desliza hasta que choca con los conos. Dado que el plano y los conos están ubicados en el mismo ángulo, cuando se cruzan, forman parábolas.
Al crecer, los conos tarde o temprano se cruzan con uno o más conos. Si observamos la intersección de los conos o círculos, obtenemos líneas rectas de los bordes de Voronoi. En la figura, la línea roja indica la intersección de los conos. Si los conos crecen aún más (verticalmente hasta el infinito), la línea roja continuará extendiéndose.
Cuando el avión se desliza y se produce el primer contacto con el cono, la línea resultante será así:
Con un mayor movimiento del avión a lo largo de los conos, veremos cómo se forman las parábolas:
El avión continúa moviéndose por la escena. Para cada punto que encuentra, examina los puntos vecinos en la línea de barrido que ya tienen parábolas y comienza una nueva parábola en ese punto. Ella continúa avanzando y creciendo hasta que esta nueva parábola comienza a superponerse no con la que se superpuso anteriormente. Entonces esta parábola anterior se cierra. Este es el punto en el que las líneas de tres puntos de Voronoi se encuentran.
Como se indicó anteriormente, esto es bastante difícil de entender, así que aquí hay enlaces a implementaciones de código abierto que puede usar y aprender:
Inserción de triángulo incremental
Otro método es insertar gradualmente un punto a la vez, comenzando con un triángulo base de tres puntos fuera del área posible de todos los demás puntos. Este método funciona con
O(n^2) y no requiere todos los puntos en el momento de la generación.
Cuando inserta un nuevo punto, define el área existente en la que cae. Esta área se subdivide y se crean nuevas áreas.
Aquí hay un ejemplo de código abierto para usar y aprender:
Conclusión
Ahora tienes que imaginar lo que los diagramas de Voronoi pueden darle a tu juego y su IA. Si tiene un gráfico de nodos y bordes adecuadamente estructurado, puede solicitar información importante para que todos obtengan sus botiquines de primeros auxilios, la hierba gatera y pasen por las torres enemigas.