Cómo generar un Navmesh 2D?

Métodos de búsqueda de caminos

Existen varios métodos para resolver el problema clásico de path finding o búsqueda de caminos, algunos, más rudimentarios, y otros más sofisticados. Antes de analizar un método, debemos tener en claro si el entorno en el que realizaremos las búsquedas será estático, es decir que las zonas caminables y los obstáculos no cambiarán, y no habrá obstáculos móviles. O si por otro lado, el escenario se modificará de alguna forma y/o tendremos obstáculos móviles, como por ejemplo otros personajes. Esto afectar nuestra selección del método de búsqueda, ya que deberíamos tener en cuenta que la estructura cambie, o bien tendremos que agregar una etapa que solucione el problema de los obstáculos móviles. Podemos clasificar los métodos de búsqueda de caminos por la estructura de datos sobre la cual se realizan las búsquedas. Las estructuras más comunes son:

• Grillas
• Son nodos equi-espaciados en el espacio, que forman una red sobre la cual se desplazarán los personajes. Los personajes pueden moverse desde un nodo hacia otro nodo, siempre y cuando éstos sean adyacentes. Los obstáculos serán secciones donde no habrán nodos ni conexiones.
• Navgraph o waypoints
• Se forman por nodos que se distribuyen en el espacio, pero a diferencia de las grillas, estos nodos no necesitan estar equi-espaciados, ni dispuesto de ninguna forma estructurada. A su vez, las conexiones o aristas entre los nodos que determinan los caminos navegables entre los nodos, y deben ser dispuestos manualmente. Al igual que las grillas, en este método los personajes se moverán entre nodos, tan solo pudiendo cruzar entre dos nodos si existe una arista que los une. Los obstáculos se determinaran por la ausencia de aristas entre nodos.
• Navmesh
• Es una estructura más compleja que las dos anteriores, y se representa por polígonos. Estos polígonos pueden ser convexos o cóncavos, y se unen a través de aristas de los polígonos. Es decir, que en vez de tener simples puntos espaciales (o nodos en los que se mueven los personajes), tenemos polígonos por los que circulan, pudiendo pasar entre dos polígonos si son adyacentes. El método se basa en la hipótesis de que dentro de estos polígonos el personaje se puede mover libremente, ya que no hay obstáculos. Por lo que los personajes pueden recorrer el camino dentro de estos polígonos que más les convenga. Los obstáculos los determinaremos con la ausencia de polígonos.

Una vez elegido el método sobre el que se realizara la búsqueda, se debe optar por un algoritmo de búsqueda de caminos para encontrar el camino que deberá seguir el personaje para llegar desde un punto de origen A a un punto de destino B. En particular, en el caso de las grillas y navgraphs será un camino entre dos nodos, y en el caso de navmeshes serán dos puntos que se encuentren dentro de polígonos. En esta entrada no hablaremos de algoritmos de búsqueda de caminos, sino que solo nos centraremos en la creación de la estructura de datos sobre la que realizar la búsqueda de caminos, en particular sobre como crear un mesh de navegación o Navmesh 2D.

Implementación

Y que vamos a hacer exactamente?

Vamos a implementar una biblioteca para generar la estructura de un Navmesh a partir de un conjunto de polígonos de zonas caminables y un conjunto de polígonos de zonas de obstáculos. Además, utilizaremos esta biblioteca para implementar una aplicación (muy simple) que nos permita definir un nivel para un juego, y poder visualizar como quedaría el Navmesh resultante. En el gráfico de abajo se ve la aplicación llamada NavMeshEditor, en color azul, que utiliza la biblioteca que crearemos, llamada NavMeshGenerator, en color verde. A su vez, la biblioteca que crearemos depende de las bibliotecas polypartition y Clipper, de las que hablaremos en la próxima sección.

La prioridad es que el código sea entendible, no eficiente. Por lo que en la implementación se realizan muchos cálculos redundantes, no se cachean resultados y se implementa en algunos casos las cosas como NO HAY QUE IMPLEMENTAR.

Una captura del editor. Donde se pueden ver polígonos verdes que representan las regiones caminables, y polígonos rojos que representan las regiones de obstáculos.



Una captura del editor. Donde se ve el Navmesh generado con los datos de la captura anterior. En líneas amarillas oscuras se ven los bordes de cada uno de los mesh del grafo de navegación, y las líneas azules representan las conexiones entre los mesh.

Que vamos a utilizar?

El código lo realizaremos en lenguaje C++, y se incluye en el archivo descargable scripts de CMake para crear proyectos para varios IDEs. No obstante, para simplificar las cosas para la mayoría, ya hay un proyecto de VisualStudio 2012. Para poder compilar el proyecto, se debe utilizar un compilador que soporte el estandar C++11, o al menos la característica de lambda functions (si no sabes lo que es, no te preocupes, no se usa para nada clave). Además, se incluye en el archivo las bibliotecas que se utilizaron, y se detallan a continuación (a excepción de OpenGL).

Vamos a utilizar algunas bibliotecas para renderizar la estructura y manejo de ventanas e input del usuario. Para esas tareas vamos a utilizar SFML (http://www.sfml-dev.org/) y OpenGL. En la implementación (que pueden descargar al final de la entrada) se utilizó SFML 2.1, y en cuanto a OpenGL no se utilizó ninguna característica "fancy" así que no debería dar problemas.

Adicionalmente, necesitaremos realizar operaciones de conjuntos sobre polígonos, es decir realizar operaciones como la unión de dos o más polígonos. Para ahorrarnos el dolor de cabeza de implementar estos algoritmos, utilizaremos una biblioteca llamada Clipper (http://www.angusj.com/delphi/clipper.php). Una alternativa hubiera sido el paquete Boost Geometry de la biblioteca Boost, pero se eligió Clipper por simpleza, ya que solo es un archivo fuente que hay que incluir, y porque según los desarrolladores "venden" es tanto o más rápido/bueno que la biblioteca de Boost.

Por otro lado, necesitaremos tesselar polígonos, es decir poder "partir" un polígono complejo en muchos polígonos más simples (como triángulos o polígonos cóncavos). Para realizar esto se utilizó una biblioteca llamada polypartition (http://code.google.com/p/polypartition/). En este caso, una alternativa hubiera sido utilizar el paquete 2D Polygon Partitioning de la biblioteca CGAL, pero se eligió esta biblioteca, una vez más, por simpleza, ya que también al igual que Clipper sólo es un archivo fuente.

Algo que faltaría sería utilizar algún framework para crear una GUI para el editor de escenarios (en vez de como se optó por realizar todo el control de la aplicación por teclado). Esto se lo evitó para no darle mayor complejidad al proyecto. No obstante, se incluye una versión del código que utiliza un sistema de GUI (hecho en MFC así que no lo van a poder correr desde Linux :/).

Sobre polígonos

Convexos y cóncavo

Podemos clasificar a cualquier polígono en dos categorías:

• Polígono convexos: Son polígonos en los cuales si definimos dos puntos cualquiera dentro suyo y los unimos por un segmento, el segmento jamás cortará ninguna arista del polígono. Es decir, es un polígono que no tiene "protuberancias" hacia afuera o hacia dentro. Estos polígonos, en general, son más sencillos de trabajar, ya que en general los cálculos sobre ellos requieren de algoritmos más simples. En el gráfico de abajo se ve un ejemplo de un polígono convexo.

• Polígonos cóncavo: Son polígonos en los cuales si definimos dos puntos cualquiera dentro de él y los unimos por un segmento, para algún par de puntos el segmento cortará algunas aristas del polígono. Estos polígonos, en general, son más difíciles de tratar. En el gráfico de abajo se ve un ejemplo de un polígono cóncavo.

 

En nuestro programa tendremos que trabajar con los dos tipos de polígonos, ya que de esta forma, por un lado le damos más libertad al usuario para definir las formas de las áreas caminables y las áreas de obstáculos, y por otro lado, luego de procesar la área del Navmesh, antes de tesselarla, es casi seguro que el/los polígonos sean cóncavo o mucho peores, que sean polígonos complejos que pueden tener huecos en su interior. Por ultimo, una vez que tesselemos el navmesh lo haremos en polígonos convexos para lograr un tesselado con menor cantidad de polígonos.

Filling rule

El tema de los polígonos complejos, que se habló en la sección anterior, nos trae un problema técnico. Como representamos un hueco en un polígono? Bueno, una forma para hacer esto es definiendo un polígono que determine el hueco, y que este dentro de otro polígono más grande que determinara el polígono en sí mismo. Como se ve en el gráfico siguiente, el polígono A determina el hueco ya que está dentro del polígono B que determina el polígono.

Ahora, podríamos generalizar aun más la representación de un polígono complejo. Supongamos que tenemos el ejemplo de arriba, donde el polígono A esta dentro del polígono B. Luego, si desde cualquier punto del interior del polígono A tiramos un rayo en cualquier dirección (por ejemplo dirección +x) y contamos cada vez que el rayo atraviese cualquier línea de los polígonos A y B. Entonces, si el rayo atraviesa una línea que gira en el sentido de winding que determinamos como el del polígono sumamos 1, y si el rayo atraviese una línea que gira en sentido contrario al sentido de winding del polígono restamos 1. Por ejemplo, en el gráfico siguiente los dos polígonos A y B tienen sentido CCW que definimos como el del polígono complejo formado por los dos, por lo que el rayo con origen en el interior de A, y por lo tanto el polígono A, tiene asignado el numero 2 ya que atraviesa dos líneas en sentido CCW. Por otro lado, el rayo con origen dentro de B atraviesa sólo una línea en sentido CCW, por lo que tiene asignado el número 1. La numeración queda como se ve en el gráfico debajo.

Ahora podríamos interpretar los huecos de diferentes formas:

• Even-Odd rule: Las áreas con número impar son el interior del polígono, y las áreas con número par son huecos en el polígono. Esta es la regla se podría usar para lograr el resultado del primer enfoque donde el hueco era el polígono interior, pero es más general y nos permitiría tener polígonos dentro de los huecos.

• Non-Zero rule: Todas las áreas con número distinto a cero son el interior del polígono, y las áreas con número cero son huecos.

• Positive rule: Todas las áreas con números positivos son el interior del polígono, y las áreas con números negativos son huecos.

• Negative rule: Todas las áreas con números negativos son el interior del polígono, y las áreas con números positivos son huevos.

Estas últimas tres reglas nos servirían en casos donde definamos polígonos con distinto winding. Por ejemplo, si definimos el polígono A con orden CW y utilizamos la regla de relleno Non-Zero, entonces tendríamos el siguiente polígono que sería un resultado equivalente al ejemplo anterior.



Estos formatos son importantes ya que serán los que utilizaremos para representar polígonos complejos en nuestro programa.

Además, basándose en este método de numerar cada una de las secciones de un polígono, nos permite además, implementar un algoritmo de peeking que nos diga si un punto determinado del espacio está dentro del polígono o no. Si el polígono fuese convexo habría formas más simples de resolver este problema, pero como el polígono puede ser cóncavo o complejo, entonces esta es una buena alternativa.

Como utilizar Clipper

Como dijimos anteriormente, la biblioteca Clipper nos dará funcionalidades para realizar operaciones similares a las de conjuntos sobre los polígonos. Antes de avanzar definamos algunas características de Clipper:

• Representa los polígonos complejos usando una filling rule como las que vimos anteriormente. El sentido de winding de los vértices de los polígonos puede ser CW o CCW. En sentido CW suma uno al atravesar el rayo, y en sentido CCW resta uno al atravesar el rayo.
• Se pueden utilizar polígonos que se autointersecten.

Estas características serán importantes, ya que utilizaremos primero la biblioteca Clipper por lo que deberemos transformar desde nuestro formato de los polígonos complejos al formato de Clipper.

En Clipper tenemos dos conjuntos de polígonos complejos:

1. Subjects
2. Clip

La idea es que los Subjects son el primer operando de la operación de conjuntos que realicemos, y los Clips son el segundo operando. Como los Subjects y los Clips pueden ser muchos polígonos, se los toma como si fuera un sólo gran polígono el de Subjects y Clips para operar.

Entonces para comenzar, deberemos crear un objeto de tipo Clipper que es la representación de una operación entre polígonos (aunque lo podemos reutilizar para realizar todas las operaciones que queramos). Al objeto de tipo Clipper le asignamos los dos conjuntos de polígonos que comentamos anteriormente como se ve en el siguiente código:

Luego con los conjuntos sobre los cuales operaremos definidos podemos llamar al método Execute para realizar una operación como se ve en el siguiente ejemplo:

Para ver la documentación de cada parámetro de las funciones se puede ver la documentación de la biblioteca que va adjunta en el archivo descargable.

Para comprender el algoritmo pueden ver la publicación "A generic solution to polygon clipping", Communications of the ACM, Vol 35, Issue 7 (July 1992) pp 56-63. Tal vez, en un post futuro, haga un tutorial del algoritmo.

Como utilizar polypartition

La biblioteca polypartition nos calculara una tesselacion del polígono complejo que obtengamos luego de operar las regiones caminables y los obstáculos para así tener un conjunto de polígonos más simples con los que formaremos el Navmesh. Antes de hablar de cualquier cosa definamos algunas características de la biblioteca:

• Representa los polígonos complejos asignando sentidos de winding a los vértices de los polígonos del interior con sentido CCW y sentido CW para los huecos.
• No se pueden utilizar polígonos que se autointersecten.

Estas características serán importantes ya que utilizaremos esta biblioteca luego de utilizar Clipper, por lo que deberemos transformar desde el formato de Clipper de los polígonos complejos al formato de polypartition. Además, luego la salida de los polígonos resultantes de la tesselación, deberemos transformarlos del formato de polypartition (aunque ahora serán solo polígonos convexos sin huecos) a la estructura que utilicemos para nuestro Navmesh.

Para tesselar nuestro polígono lo primero que deberemos hacer es crear un objeto de tipo TPPLPartition que representa un proceso de tesselación. La biblioteca implementa varios métodos de tesselación, pero en general podemos realizar la tesselación en:

• Triángulos
• Polígonos convexos

De estos dos preferimos tesselar en polígonos convexos, ya que eso hará que en el Navmesh tengamos menor cantidad de polígonos en general, lo cual siempre es conveniente. Además, podremos elegir entre un algoritmo que nos generara una solución no óptima, y la solución óptima de menor cantidad de polígonos convexos. Por supuesto, la solución óptima es más cara computacionalmente hablando pero nos da un mejor resultado para luego utilizar el Navmesh. Como la tesselación la producimos en la generación del escenario, y el usuario del juego no la deberá calcular, es preferible ir por la opción óptima, no obstante la solución no óptima da un buen resultado también. A continuación se puede ver un ejemplo de un proceso de tesselación:

Al igual que Clipper tal vez en el futuro realice un tutorial sobre algún método de tesselación. No conozco ninguna referencia que trate todos los métodos juntos pero si les interesa alguno de los algoritmos que implementa la biblioteca pueden googlerlo por el nombre.

Pasos en la creación del Navmesh

Para generar el Navmesh crearemos una clase llamada NavMesh que será responsable de crear el mesh de navegación a partir de dos conjuntos de polígonos: uno de las áreas caminables y otro de las áreas de obstáculos. Además, la clase creara la estructura que utilizaremos para representar el Navmesh. A continuación se muestra el código (que fue ligeramente simplificado) del método que  recibe las áreas y genera el mesh:

A continuación veremos las implementaciones de los métodos _processWalkableObstacleRegions que genera el polígono resultado de mezclar las áreas pasadas por parámetro y el método _processNavigationConvexTesselation que realiza la tesselación del polígono del mesh. Por otro lado, la clase GeneralPolygon es una clase auxiliar que se utilizó a lo largo del código para representar un polígono complejo y que proveyó las funcionalidades de renderizado del polígono, mantener la información de transformación del polígono, peek para comprobar selección del polígono y conversión a entre los formatos de Clipper y polypartition. Esta última funcionalidad es por la cual se utiliza en este método.

Unión de polígonos caminables y substracción de polígonos obstáculos

El método  _processWalkableObstacleRegions es muy simple y lo que hace es a la unión de las regiones caminables les resta la unión de las regiones de obstáculos para así quedarse con un conjunto de polígonos complejos que solo contiene las regiones caminables definitivas.

Por otro lado el método _processNavigationConvexTesselation solo realiza una tesselación en polígonos convexos sobre los polígonos que se dan como entrada de forma que la salida serán los polígonos que formaran el Navmesh. Es de notar, que no estamos calculando la tesselación óptima sino que utilizamos una versión con heurística que nos da una buena solución pero no la óptima.

Creación de estructura de datos del Navmesh

Una vez que tenemos el conjunto de polígonos convexos que formaran el Navmesh, sólo nos resta formar la estructura de este. Lo más importante que nos queda, es calcular las conexiones del mesh de navegación para así saber que polígonos están conectados. Para hacer esto simplemente calcularemos que polígonos tienen aristas adyacentes. Almacenamos las adyacencias en un arreglo formado por la siguiente estructura: 

Luego calculamos las conexiones en un arreglo manteniendo dos veces las conexiones ya que si un polígono A es adyacente a través de la arista x a otro polígono B, y luego lo inverso también será cierto. Básicamente realizaremos el cálculo de la siguiente forma:

Vemos que toda la magia la está haciendo la función _getConexions. A continuación veamos como implementamos esta función:

Sólo quedaría definir las funciones auxiliares que utilizamos en el código. Estas funciones hacen exactamente lo que dice su nombre, y su implementación se puede ver en el código del proyecto.

Conclusión

Creo que como conclusión podemos decir que no es tan difícil implementar un editor simple para generar un mesh de navegación para un juego. Si bien la mayoría de los motores de juegos tienen alguna funcionalidad para resolver el problema de path finding, y de no tenerlo suele haber middlewares o bibliotecas que se pueden utilizar. Aunque este no es siempre el caso, por lo que nunca está de más saber cómo se podría improvisar un editor. El próximo paso lógico sería implementar algunos algoritmos de búsqueda de caminos y probar el Navmesh que generamos con estos. Posiblemente más adelante haya otra entrada con esta temática.

Licencia

GNU Lesser General Public License (LGPLv3)

Descargas

GitHub: https://github.com/erojasfredini/NavMesh

Descarga directa de primer versión - http://sdrv.ms/IfgEqv