A* sobre NavMesh poligonal: triángulos, portales y funnel

0. Introducción

Hasta ahora todos los algoritmos asumen un grid uniforme: cada celda es un nodo, los vecinos son las 4 u 8 celdas adyacentes. Eso es perfecto para juegos tactical, roguelike, top-down con celdas.

Para juegos 3D modernos — Witcher 3, GTA, cualquier shooter, casi todo Unity de mundo abierto — el grid no escala. ¿Cuántos nodos tiene un mundo de 1km × 1km a 0.5m de precisión? 4 millones. ¿Y si el suelo es irregular, con escaleras, rampas, plataformas a distintas alturas? Imposible.

La solución estándar es el NavMesh (navigation mesh): el espacio walkable se representa como un conjunto de polígonos (típicamente triángulos). A* corre sobre los polígonos. Un mapa de varios km² puede tener solo unos pocos miles de polígonos — un par de órdenes de magnitud menos que el grid equivalente.

Unity trae un sistema de NavMesh integrado (NavMeshAgent, NavMeshSurface). Saber cómo funciona por dentro te permite usarlo bien y, si hace falta, escribir el tuyo.

Lo que vamos a cubrir

1. Cómo se construye el navmesh: triangulación del espacio walkable, con obstáculos como restricciones.
2. Cómo corre A* sobre triángulos: el grafo es de polígonos, las aristas son los portales (segmentos compartidos).
3. Funnel algorithm: el path naïve zigzaguea entre centroides; funnel produce el path geodésico real.

1. Construcción del navmesh

El navmesh divide el espacio walkable en triángulos (o polígonos convexos). Triángulos vecinos comparten una arista — esa arista es un portal. Activar el obstáculo regenera la triangulación: zonas inalcanzables desaparecen, zonas nuevas se subdividen.

añadir obstáculo en habitación B

Figura 1 — Dos habitaciones conectadas por un pasillo, trianguladas. Cuando añades un obstáculo, la habitación derecha se subdivide en triángulos que rodean al obstáculo. Las celdas no walkable simplemente no aparecen en el mesh.

1.1 Las dos formas de obtener un navmesh

• Manual — un artista lo dibuja (en un editor de meshes). Caro, pero útil para mapas pequeños y específicos.
• Automático — un algoritmo lo genera a partir de la geometría de la escena. Es lo que hace Unity con NavMeshSurface.BuildNavMesh().

El algoritmo automático canónico es Recast (Mikko Mononen, 2009), usado por Unity y por casi todos los engines:

1. Voxelización: la escena se convierte a voxels.
2. Filtrado: se detectan voxels caminables (suelo plano, pendientes razonables, sin techo bajo).
3. Particionado: los voxels caminables se agrupan en regiones convexas.
4. Triangulación: cada región se triangula. El resultado es el navmesh.

La parte difícil es el particionado en regiones convexas. Para tutorial vale con saber: el resultado son polígonos convexos (a menudo triángulos por simplicidad) que cubren el espacio caminable.

1.2 Por qué triángulos

• Convexidad garantizada — un triángulo siempre es convexo, así que cualquier dos puntos dentro de él son alcanzables en línea recta.
• Conectividad simple — dos triángulos son vecinos si comparten exactamente una arista (que se vuelve un portal).
• Algoritmos clásicos — Delaunay, ear-clipping y similar producen triangulaciones de calidad.

Los engines AAA usan polígonos convexos genéricos (no solo triángulos) porque reducen el número de nodos. Pero la teoría es la misma.

2. A* sobre triángulos

El navmesh es un grafo. Cada nodo es un triángulo, cada arista es un portal (segmento compartido entre dos triángulos vecinos). A* corre sobre ese grafo igual que sobre un grid.

Arrastra los nodos S y G dentro del mesh. A* corre sobre la conectividad de triángulos: nodos = triángulos, aristas = portales (los segmentos naranjas son los portales atravesados). El path verde une centroides — fíjate cómo zigzaguea. Eso lo arregla el funnel (siguiente viz).

Figura 2 — Arrastra S y G dentro del mesh. A* encuentra la secuencia de triángulos a recorrer (verde claro) y los portales que cruza (líneas naranja). El path verde “literal” une centroides de triángulos consecutivos — y zigzaguea innecesariamente.

2.1 El bucle es idéntico al de A* sobre grid

function astarNavmesh(mesh, start, goal)
    startTri = findTriangle(start)
    goalTri = findTriangle(goal)
    return astar(graph = mesh.triangleAdjacency,
                 start = startTri,
                 goal = goalTri,
                 cost(a, b) = distance(centroid(a), centroid(b)),
                 heuristic(a, goal) = distance(centroid(a), centroid(goal)))

Solo cambian dos cosas:

• Costos: ya no son “1 por celda”; son la distancia entre centroides (o cualquier métrica razonable entre triángulos).
• Heurística: distancia euclidiana entre centroides al goal. Admisible siempre.

El resultado del A* es una secuencia de triángulos y los portales que los conectan.

2.2 El problema con el path naïve

Si conectas centroides directamente, el agente zigzaguea: entra a un triángulo, va al centro, sale por el portal, va al centro del siguiente, etc. No es óptimo en distancia real. El path real más corto solo cambia de dirección cuando un portal lo obliga.

Para conseguir ese path real, hace falta el funnel algorithm.

3. Funnel algorithm — del zigzag al geodésico

El path naïve (verde punteado) une centroides de triángulos: zigzaguea sin razón. El funnel algorithm toma esa secuencia de portales (líneas naranja) y produce el path geodésico óptimo (rojo): solo cambia de dirección cuando un portal lo obliga. El resultado es lo que el agente realmente recorrería.

mostrar zigzag (centroides)

Figura 3 — Verde punteado es el path naïve por centroides; rojo es el path después de aplicar funnel. El funnel solo cambia de dirección cuando un portal lo obliga: el agente puede ir directo entre waypoints.

3.1 La intuición del funnel

Imagina que vas por un pasillo curvo. Estás parado en un punto (el apex del funnel) y miras hacia el siguiente portal. El portal tiene un borde izquierdo (left) y un borde derecho (right). Tu visión está limitada a ese rango angular: un cono.

Avanzas al siguiente portal. El nuevo left puede:

• Estar más a la derecha que el viejo (el cono se cierra por la izquierda) → actualiza left.
• Estar fuera del cono actual por la derecha (el cono se cerró completamente) → emite un waypoint en el right viejo, y arranca un cono nuevo desde ahí.

Lo mismo simétricamente para right.

function funnel(start, goal, portals)
    apex = start
    left = portals[0].left
    right = portals[0].right
    path = [start]

    for i = 1 to portals.length - 1
        nextLeft = portals[i].left
        nextRight = portals[i].right

        # ¿el nuevo right cierra el cono?
        if cross(apex, right, nextRight) <= 0
            if cross(apex, left, nextRight) > 0
                right = nextRight
            else
                # el cono se cerró: emite waypoint en left
                path.push(left)
                apex = left
                # reinicia el funnel desde el portal del left

        # mismo simétrico para left

    path.push(goal)
    return path

La implementación correcta tiene unos detalles delicados (orientación de portales, casos degenerados), pero la idea es: mantén el cono lo más abierto posible; emite waypoints solo cuando el cono colapsa.

3.2 Por qué el resultado es óptimo en distancia

El funnel es equivalente a “estirar una cuerda” entre start y goal, dejándola tensar contra los bordes de los portales. Esa cuerda, en geometría plana, es el camino geodésico — el más corto. Demostrado.

3.3 Lo que hace Unity por dentro

NavMeshAgent.SetDestination(target) internamente:

1. Encuentra los triángulos del navmesh para transform.position y target.
2. Corre A* sobre los triángulos.
3. Aplica funnel sobre la secuencia de portales resultante.
4. Devuelve corners[] — exactamente los waypoints del funnel.

El agente luego se mueve entre corners[i] y corners[i+1] con MoveTowards o tu controlador favorito. Lo que ves como movimiento “fluido” del NPC es funnel actuando.

4. Pseudocódigo completo

class Navmesh
    triangles: List<Triangle>
    adjacency: Map<Triangle, List<{neighbor, portal}>>

function findPath(navmesh, start: Vec2, goal: Vec2) -> List<Vec2>
    startTri = findTriangleContaining(navmesh, start)
    goalTri  = findTriangleContaining(navmesh, goal)

    triPath = astar(navmesh.adjacency, startTri, goalTri,
                    cost = (a, b) -> dist(centroid(a), centroid(b)),
                    h    = (a, b) -> dist(centroid(a), centroid(b)))

    portals = []
    for i = 0 to triPath.length - 2
        portals.push(navmesh.adjacency[triPath[i]][triPath[i+1]].portal)

    return funnel(start, goal, portals)


function funnel(start, goal, portals) -> List<Vec2>
    # como se describió arriba
    ...

5. Implementación en Unity / C#

En Unity casi nunca escribes el navmesh manual: usas NavMeshSurface (paquete AI Navigation) y dejas que el motor lo genere. El A* y el funnel los hace NavMeshAgent. Lo que escribes es gameplay sobre eso.

using UnityEngine;
using UnityEngine.AI;

[RequireComponent(typeof(NavMeshAgent))]
public class SimpleAgent : MonoBehaviour {
    NavMeshAgent agent;
    public Transform target;

    void Awake() => agent = GetComponent<NavMeshAgent>();

    void Update() {
        if (target != null) agent.SetDestination(target.position);
    }

    // Para acceder al path resuelto y dibujarlo:
    void OnDrawGizmosSelected() {
        if (agent == null || agent.path == null) return;
        var corners = agent.path.corners;
        for (int i = 0; i < corners.Length - 1; i++) {
            Gizmos.color = Color.green;
            Gizmos.DrawLine(corners[i], corners[i + 1]);
        }
    }
}

Si necesitas escribir tu propio funnel (porque tienes un sistema de pathfinding custom o quieres modificar el comportamiento), Unity expone NavMeshPath con corners[] ya post-funnel. Para hacer funnel desde cero sobre tu propio mesh, el snippet del pseudocódigo se traduce directo.

6. En otros engines

• Godot: trae NavigationServer y NavigationRegion3D que generan navmesh automático. La API es similar a Unity.
• Unreal: NavMeshBoundsVolume define las áreas; RecastNavMesh lo construye con el algoritmo Recast. AAIController.MoveToLocation() es el equivalente de SetDestination.
• JavaScript / TypeScript: librerías como recast-navigation-js (port de Recast) traen navmesh y funnel completos para Three.js.

7. Quiz

Pon a prueba lo que entendiste

Responde una por una. La explicación aparece al elegir, correcta o no.

1. ¿Por qué un navmesh escala mejor que un grid uniforme para mundos 3D?

   • AEl navmesh representa solo el espacio caminable con polígonos grandes (típicamente cientos o miles de triángulos por mapa). Un grid equivalente tendría millones de celdas.
   • BEs más fácil de implementar.
   • CPermite paths más cortos.

2. Implementaste A* sobre navmesh y el agente zigzaguea entre triángulos. ¿Qué falta?

   • AEl funnel algorithm. A* te da la secuencia de triángulos y portales; el funnel produce el path geodésico real entre ellos.
   • BLa heurística no es admisible.
   • CFaltan más triángulos en el mesh.

3. Tu unidad humana está sobre un navmesh con un puente angosto. ¿Cómo asegurás que el path lo cruce limpio (sin pegarse al borde)?

   • AInflar los obstáculos por el radio del agente antes de generar el navmesh, así el espacio walkable ya tiene margen del ancho del agente. Recast hace esto con su parámetro 'agent radius'.
   • BHaciendo el agente más chico.
   • CAplicar funnel con un offset de 0.5 metros.

4. ¿Cuál es la salida de NavMeshAgent.SetDestination(target) por dentro?

   • A(1) A* sobre los triángulos del NavMesh entre el agente y el target. (2) Funnel sobre la secuencia de portales. (3) Devuelve corners[], los waypoints geodésicos.
   • BDijkstra sobre todos los triángulos del mapa.
   • CBFS sobre las celdas del navmesh.

5. Querés que tu agente prefiera caminos pavimentados (cost 1) sobre césped (cost 2). ¿Cómo lo modelás en navmesh?

   • AAsignás 'áreas' (NavMeshAreas en Unity) a cada triángulo del navmesh con su costo. A* las usa al sumar costos en vez de solo distancia entre centroides.
   • BGenerás dos navmeshes distintos y elegís en runtime.
   • CEliminás los triángulos de césped del navmesh.

8. Siguientes pasos