Calcolo del percorso più breve tra due punti

Ho lavorato nelle ultime settimane su un gioco HTML5 multiplayer, usando nodejs e websockets .

Sono rimasto bloccato in questo problema per un po ‘. Immagina di avere questa mappa del tilesheet implementata con un array ( come mostrato sotto ).

1 o tessere marroni – c’è un ostacolo nel modo in cui il giocatore non può attraversarlo.

0 o tessere verdi : sono percorsi liberi in cui il giocatore può muoversi.

Accedi a qualsiasi tessera sulla mappa chiamando:

  array[x][y] 

tileheet map - calcola il percorso più breve

Vorrei creare l’algoritmo più veloce ansible per scoprire il percorso più breve (se ce n’è uno) tra due punti della mappa. Come affronteresti questo problema? So che questo è un problema comune.

Esempio :

Il giocatore in posizione (1,7) spara un proiettile con una IA che raggiungerà il giocatore nemico nella posizione (6,0). Bullet deve calcolare il percorso più breve tra i 2 giocatori e se non ce ne sono che sarebbe semplicemente esplodere contro un muro.

Domanda :

Come trovare in modo efficiente il percorso più breve tra due punti?

Questo è un algoritmo di problemi di teoria del grafico comune

Nella teoria dei grafi, il problema del percorso più breve è il problema di trovare un percorso tra due vertici (o nodes) in un grafico tale che la sum dei pesi dei suoi bordi costitutivi sia minimizzata.

Il problema di trovare il percorso più breve tra due intersezioni su una mappa stradale (i vertici del grafico corrispondono alle intersezioni e i bordi corrispondono ai segmenti stradali, ciascuno ponderato per la lunghezza del suo segmento stradale) può essere modellato da un caso speciale del percorso più breve problema nei grafici.

Per ora esiste molte implementazioni di questo algoritmo. Più semplice nell’implementazione è un algoritmo di Dijkstra con le peggiori prestazioni in termini di O(|E|+|V|log|V|) dove

  • | V | è il numero di nodes
  • | E | è il numero di bordi

Illustrazione del lavoro dell’algoritmo

inserisci la descrizione dell'immagine qui

Definizione dell’algoritmo del percorso più breve di Dijkstra

  • nodo iniziale – il nodo al quale stiamo iniziando.
  • distanza del nodo Y – essere la distanza dal nodo iniziale a Y.

Algoritmo assegnerà alcuni valori iniziali di distanza e proverà a migliorarli passo dopo passo:

  1. Assegna a ogni nodo un valore di distanza provvisorio: impostalo su 0 per il nostro nodo iniziale e su ∞ per tutti gli altri nodes.

  2. Imposta il nodo iniziale come corrente. Contrassegna tutti gli altri nodes non visitati . Crea un set di tutti i nodes non visitati chiamato set non visitato .

  3. Per il nodo corrente, considera tutti i suoi vicini non visitati e calcola le loro distanze provvisorie. Confrontare la distanza provvisoria appena calcasting con il valore assegnato corrente e assegnare quella più piccola.

  4. Quando abbiamo finito di considerare tutti i vicini del nodo corrente, contrassegna il nodo corrente come visitato e rimuovilo dal set non visitato . Un nodo visitato non verrà mai più controllato.

  5. Se il nodo di destinazione è stato contrassegnato come visitato (quando si pianifica un percorso tra due nodes specifici) o se la minima distanza provvisoria tra i nodes nell’insieme non visitato è ∞ (quando si pianifica un attraversamento completo, si verifica quando non vi è alcuna connessione tra il nodo iniziale e rimanendo nodes non visitati), quindi fermarsi. L’algoritmo è finito .

  6. Altrimenti, selezionare il nodo non visitato contrassegnato con la distanza tentativa più piccola, impostarlo come nuovo “nodo corrente” e tornare al punto 3.

Altre implementazioni dell’algoritmo Dijkstra che puoi trovare su github repository mburst / dijkstras-algorithm .

Ad esempio, ecco l’ implementazione di JavaScript

Mentre l’algoritmo dijkstra funziona sicuramente, nel tuo caso il grafico è un grafico non ponderato, quindi un semplice BFS dovrebbe essere sufficiente.

Pseudo codice:

 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 

L'array prev può anche essere usato per verificare se un punto è visitato.

Qui non esiste alcuna condizione per calcolare il costo del percorso perché tutto il costo del percorso è 1. Quindi è ansible eseguire qui l’algoritmo 2D BFS normale e la complessità sarà O (V + E) (vertice e spigolo).

Qui ogni nodo ha due proprietà. Uno è fila e l’altro è colonna. Quindi puoi creare una coppia per denotare il valore di una cella. Ecco il codice c ++ e la spiegazione:

 #define pii pair 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; queueq; //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=0 and ty 

Ora puoi facilmente trovare il tuo percorso più breve dalla cella d [x] [y].