algorithm
A * Algoritmo Pathfinding

introduzione

Semplice esempio di A * Pathfinding: un labirinto senza ostacoli

Diciamo che abbiamo la seguente griglia 4 per 4:

Supponiamo che questo sia un labirinto . Non ci sono muri / ostacoli, però. Abbiamo solo un punto di partenza (il quadrato verde) e un punto finale (il quadrato rosso). Supponiamo anche che per passare dal verde al rosso, non possiamo spostarci in diagonale. Quindi, partendo dal quadrato verde, vediamo quali quadrati possiamo spostare e evidenziarli in blu:

Per scegliere quale quadrato spostare al prossimo, dobbiamo prendere in considerazione 2 euristiche:

1. Il valore "g" - Questo è quanto lontano questo nodo proviene dal quadrato verde.
2. Il valore "h" - Questo è quanto lontano questo nodo proviene dal quadrato rosso.
3. Il valore "f" - Questa è la somma del valore "g" e del valore "h". Questo è il numero finale che ci dice su quale nodo spostare.

Per calcolare queste euristiche, questa è la formula che useremo: distance = abs(from.x - to.x) + abs(from.y - to.y)

Questa è conosciuta come la formula "Manhattan Distance" .

Calcoliamo il valore "g" per il quadrato blu immediatamente a sinistra del quadrato verde: abs(3 - 2) + abs(2 - 2) = 1

Grande! Abbiamo il valore: 1. Ora proviamo a calcolare il valore "h": abs(2 - 0) + abs(2 - 0) = 4

Perfezionare. Ora, prendiamo il valore "f": 1 + 4 = 5

Quindi, il valore finale per questo nodo è "5".

Facciamo lo stesso per tutti gli altri quadrati blu. Il grande numero al centro di ogni quadrato è il valore "f", mentre il numero in alto a sinistra è il valore "g", e il numero in alto a destra è il valore "h":

Abbiamo calcolato i valori g, h e f per tutti i nodi blu. Ora, quale scegliere?

Qualunque abbia il valore f più basso.

Tuttavia, in questo caso, abbiamo 2 nodi con lo stesso valore f, 5. Come possiamo scegliere tra loro?

Semplicemente, scegli uno a caso o hai una priorità. Di solito preferisco avere una priorità in questo modo: "Destra> Su> Giù> Sinistra"

Uno dei nodi con il valore f di 5 ci porta nella direzione "Giù", e l'altro ci porta "Sinistra". Dal momento che Giù ha una priorità più alta di Sinistra, scegliamo il quadrato che ci porta "Giù".

Segnalo ora i nodi per i quali abbiamo calcolato l'euristica, ma non ci siamo mossi, come l'arancione, e il nodo che abbiamo scelto come ciano:

Bene, ora calcoliamo la stessa euristica per i nodi attorno al nodo ciano:

Di nuovo, scegliamo il nodo che scende dal nodo ciano, poiché tutte le opzioni hanno lo stesso valore f:

Calcoliamo l'euristica per l'unico vicino che il nodo ciano ha:

Bene, poiché seguiremo lo stesso schema seguito da noi:

Ancora una volta, calcoliamo l'euristica per il vicino del nodo:

Andiamo lì:

Infine, possiamo vedere che abbiamo una piazza vincente accanto a noi, quindi ci spostiamo lì e abbiamo finito.