Implementación genérica de A estrella
El otro día estaba buscando una implementación del algoritmo de búsqueda A* para el game engine que estoy desarrollando en C++. Sin embargo, lo que me encontré es que casi todas las implementaciones dependían del problema en específico que estaban solucionando. Y en las que no, se necesitaba derivar de una clase y no me parecía de lo más cómodo o eficiente. Por eso dije:
Necesitaba el algoritmo para lo típico de pathfinding en un mapa de tiles bidimensional. Pero además, hay entidades que pueden bloquear el camino, así que debía de incorporar esa información de alguna forma. Dado que A* también es una técnica utilizada para inteligencia artificial, también tengo pensado usarlo para la IA de los enemigos. Por todo ello decidí que la interfaz sería una sola función genérica que recibe lambdas como argumentos con la semántica especifica del problema a resolver. Además, he hecho que sea capaz de automáticamente almacenar las estructuras que crea en su operación sin destruirlas al acabar la búsqueda, de forma que sucesivas llamadas a la función pueden ser más rápidas. Esto es especialmente importante dado que se usa cientos o miles de veces dentro de un game loop. Además, es thread-safe. Las cosas thread-safe están bien. El código está público en mi github con ejemplos de uso para un mapa 2D, el problema del caballo del ajedrez y el 8 puzzle.