Hace algún tiempo, para el trabajo, empecé a hacer un port a ActionScript3 de la librería opensource poly2tri.
La idea era usarla para búsqueda de caminos en flash.
La búsqueda poligonal de caminos consta de tres partes:

  1. Triangulación (en este caso mediante la librería poly2tri)
  2. Búsqueda del camino más corto en nodos. (Usando A). En este caso no ha hecho falta dividir la búsqueda en varios nivels. Es un A sencillito con un nodo para cada triángulo que puede acceder a los triángulos contiguos.
  3. Algoritmo del embudo (Funnel algorithm). Implementación Simple Stupid Funnel Algorithm (De la cual también hice un port en Javascript).

Los pasos 2 y 3 son suficientemente rápidos como para hacerlos en tiempo real, al menos con escenas sencillitas. El paso uno posiblemente también, pero en este caso no hace falta.

Se puede acceder al código fuente de mercurial desde aquí.

Aquí una demo en funcionamiento (tras el salto):

(Requiere Flash Player) {

}

La implementación en javascript del algoritmo del embudo, se puede encontrar aquí.