Búsqueda de ruta

La búsqueda de ruta en el contexto de los videojuegos se refiere a la forma en que una entidad en movimiento encuentra un camino alrededor de un obstáculo; el contexto más frecuente se encuentra en los videojuegos de estrategia en tiempo real (en el que el jugador orienta las unidades en torno a un área de juego que contiene los obstáculos), pero esta modalidad se encuentra en los videojuegos más modernos. La importancia de la búsqueda de rutas ha crecido tanto en importancia como los entornos de los juegos se han vuelto cada vez más complejos, y como resultado, varios paquetes de software de IA ya han desarrollado los algoritmos para resolver el problema.

Los videojuegos de estrategia en tiempo real generalmente contienen grandes áreas de terreno abierto que suele ser relativamente fácil de atravesar, en el que es muy común que más de una unidad esté viajando a la vez; esto crea una necesidad diferente, y a menudo son necesarios algoritmos más complejos para evitar un atasco de tráfico en los puntos más circulados del mapa o terreno, o cuando las unidades están en contacto unas con otras. En los juegos de estrategia los mapas normalmente están divididos en tiles, que actúan como nodos en el algoritmo de pathfinding.

Géneros estructurados más abiertos, tales como los videojuegos de disparo en primera persona que a menudo tienen más áreas cerradas (o una mezcla entre abierta y cerrada) que no están tan simplemente divididos en nodos, ha dado lugar al uso de mallas de navegación. Estos son construidos por la colocación de nodos en el mundo del juego, que almacenan detalles de qué nodos son accesibles desde el mismo.