He estado trabajando en las últimas semanas en un juego HTML5 multijugador, usandonodejs ywebsockets.

He estado atrapado en este problema por un tiempo. Imagine que tengo este mapa de hoja de mosaico implementado con una matriz (Como se muestra abajo)

1 oazulejos marrones - hay un obstáculo en el camino y el jugador no puede pasarlo.

0 oazulejos verdes - son caminos libres donde el jugador puede moverse.

Acceda a cualquier mosaico en el mapa llamando:

 array[x][y]

Me gustaría crear el algoritmo más rápido posible para encontrar la ruta más corta (si hay una) entre dos puntos del mapa. ¿Cómo abordarías este problema? Sé que este es un problema común.

Ejemplo:

El jugador en la posición (1,7) dispara una bala con algo de IA que se dirigirá hacia el jugador enemigo en la posición (6,0). Bullet tiene que calcular la ruta más corta entre los 2 jugadores y, de no existir, explotaría contra una pared.

Pregunta:

¿Cómo encontrar eficientemente la ruta más corta entre dos puntos?