javascript - Cálculo de la ruta más corta entre dos puntos.

node.js algorithm

Question

He estado trabajando en las últimas semanas en un juego multijugador de HTML5, utilizando nodejs y websockets .

He estado atrapado en este problema por un tiempo. Imagine que tengo este mapa de hojas de mosaico implementado con una matriz ( como se muestra a continuación ).

1 o azulejos marrones : hay un obstáculo en el camino y el jugador no puede atravesarlo.

0 o azulejos verdes : son caminos libres donde el jugador puede moverse.

Accede a cualquier ficha del mapa llamando al:

 array[x][y]

Me gustaría crear el algoritmo más rápido posible para descubrir la ruta más corta (si existe 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 alguna 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 si no hay alguna, simplemente explotará contra una pared.

Pregunta :

¿Cómo encontrar de manera eficiente la ruta más corta entre dos puntos?

Answer 1

Aquí no hay ninguna condición para calcular el costo de la ruta porque todo el costo de la ruta es 1. Por lo tanto, puede ejecutar aquí el algoritmo BFS 2D normal y la complejidad será O (V + E) (vértice y borde).

Aquí cada nodo tiene dos propiedades. Uno es fila y otro es columna. Así que u puede crear un par para denotar el valor de una celda. Aquí está el código y la explicación de c ++:

#define pii pair<int,int>
int fx[]={1,-1,0,0}; //Direction array for moving one cell to another cell horizontaly
int fy[]={0,0,1,-1}; //Direction array for moving one cell to another cell verticaly
int cell[100][100]; //cell[x][y] if this cell is -1 then it is block (Here it is your brown cell)
int d[100][100],vis[100][100]; //d means destination from source. 
int row,col;
void bfs(int sx,int sy) //Source node is in [sx][sy] cell.
{
    memset(vis,0,sizeof vis);
    vis[sx][sy]=1;
    queue<pii>q; //A queue containing STL pairs
    q.push(pii(sx,sy));
    while(!q.empty())
    {       
        pii top=q.front(); q.pop();
        for(int k=0;k<4;k++)
        {
            int tx=top.uu+fx[k];
            int ty=top.vv+fy[k]; //Neighbor cell [tx][ty]
            if(tx>=0 and tx<row and ty>=0 and ty<col and cell[tx][ty]!=-1 and vis[tx][ty]==0) //Check if the neighbor is valid and not visited before.
            {               
                vis[tx][ty]=1;
                d[tx][ty]=d[top.uu][top.vv]+1; 
                q.push(pii(tx,ty)); //Pushing a new pair in the queue
            }
        }
    }
}

Ahora puede encontrar fácilmente su ruta más corta desde la celda d [x] [y].

Answer 2

Este es un algoritmo común de problemas de la teoría de grafos.

En la teoría de gráficos, el problema de la ruta más corta es el problema de encontrar una ruta entre dos vértices (o nodos) en un gráfico de tal manera que se minimice la suma de los pesos de sus bordes constituyentes.

El problema de encontrar la ruta más corta entre dos intersecciones en un mapa de ruta (los vértices del gráfico corresponden a las intersecciones y los bordes corresponden a segmentos de carretera, cada uno ponderado por la longitud de su segmento de carretera) puede ser modelado por un caso especial de la ruta más corta Problema en los gráficos.

Por ahora existen muchas implementaciones de este algoritmo. Más simple en la implementación es un en.wikipedia.org/wiki/Dijkstra%27s_algorithm con el peor desempeño de caso como O(|E|+|V|log|V|) donde

• | V | es el numero de nodos
• | E | es el numero de aristas

Ilustración de trabajo de algoritmo.

Definición del algoritmo del camino más corto de Dijkstra

• nodo inicial - el nodo en el que estamos empezando.
• distancia del nodo Y - es la distancia desde el nodo inicial hasta Y.

El algoritmo asignará algunos valores de distancia iniciales e intentará mejorarlos paso a paso:

1. Asigne a cada nodo un valor de distancia tentativa: configúrelo en 0 para nuestro nodo inicial y en ∞ para todos los demás nodos.

2. Establecer el nodo inicial como actual. Marque todos los demás nodos no visitados . Cree un conjunto de todos los nodos no visitados denominado conjunto no visitado .

3. Para el nodo actual, considere a todos sus vecinos no visitados y calcule sus distancias tentativas. Compare la distancia tentativa recién calculada con el valor asignado actual y asigne el menor.

4. Cuando hayamos terminado de considerar a todos los vecinos del nodo actual, marque el nodo actual como visitado y elimínelo del conjunto no visitado . Un nodo visitado nunca será verificado de nuevo.

5. Si el nodo de destino se ha marcado como visitado (al planificar una ruta entre dos nodos específicos) o si la distancia tentativa más pequeña entre los nodos en el conjunto no visitado es (cuando se planifica un recorrido completo; ocurre cuando no hay conexión entre el nodo inicial y permanecen nodos no visitados), luego se detienen. El algoritmo ha terminado .

6. De lo contrario, seleccione el nodo no visitado que está marcado con la distancia tentativa más pequeña, configúrelo como el nuevo "nodo actual" y vuelva al paso 3.

Más implementaciones del algoritmo Dijkstra se pueden encontrar en el repositorio mburst/dijkstras-algorithm .

Por ejemplo aquí está la implementación de JavaScript.

Answer 3

Si bien el algoritmo dijkstra definitivamente funciona, en su caso, el gráfico es un gráfico no ponderado, por lo que un simple BFS debería ser suficiente.

Pseudo código:

queue = [startingposition]
prev = [-1, -1, -1 ...] (array of n elements, all -1)
while (queue not empty) 
   u <- pop(queue)
   if u = targetposition then DONE! trace the *prev* array for path
   for (v in every unvisited points adjacent to u):
      prev[v] = u
      push v to queue
   end for
end while

La matriz anterior también se puede usar para verificar si se visita un punto.