🗺️ Pathfinding A*

Greedy Best-First imposta g = 0 e usa solo h per classificare i nodi, precipitandosi sempre verso il nodo che sembra più vicino all'obiettivo. Questo è molto veloce in ambienti aperti, ma ignora il costo reale del percorso, quindi può essere attirata attraverso terreno costoso o attorno a ostacoli in un percorso più lungo. Nel caso peggiore trova un percorso arbitrariamente peggiore dell'ottimale.

Usa la distanza Manhattan quando il movimento è limitato a 4 direzioni (su, giù, sinistra, destra), poiché conta esattamente il numero minimo di passi. La distanza Euclidea è appropriata quando le mosse diagonali sono permesse e il costo diagonale è √2. La distanza Chebyshev (massimo tra |Δx|, |Δy|) è la scelta giusta quando tutte le 8 direzioni costano uguale, come è comune in molti giochi strategici.

Le celle pesate rappresentano terreno più difficile da attraversare — fango, acqua bassa o una strada dissestata. In questa simulazione una cella pesata costa 5 invece di 1 per essere attraversata, quindi A* spesso aggirerà diverse celle pesate invece di attraversarle. Dijkstra e A* gestiscono entrambi i pesi correttamente; Greedy Best-First ignora i costi e può attraversare terreno costoso in linea retta.

Nel caso peggiore A* ha complessità temporale e spaziale O(b^d), dove b è il fattore di ramificazione e d è la profondità della soluzione ottimale. Con un'euristica consistente (che soddisfa la disuguaglianza triangolare) ogni nodo è espanso al massimo una volta, dando O(V log V) su un grafo finito con V vertici — lo stesso limite asintotico di Dijkstra con uno heap binario.

Il generatore di labirinti crea un labirinto perfetto usando un algoritmo randomizzato che scava passaggi attraverso una griglia, garantendo esattamente un percorso tra due celle qualsiasi. I labirinti sono particolarmente impegnativi per gli algoritmi di ricerca perché i corridoi stretti eliminano il vantaggio euristico di A* — con un solo percorso valido, tutti gli algoritmi devono esplorare circa gli stessi nodi.

Il verde segna il nodo di partenza, il rosso l'obiettivo. Le celle blu formano la frontiera corrente (insieme aperto), il blu scuro segna i nodi visitati (chiusi), e il giallo evidenzia il nodo in fase di espansione. Le celle pesate appaiono marroni. Una volta trovato un percorso, viene tracciato in verde lime dalla partenza all'obiettivo, e puoi leggere il costo esatto nel pannello statistiche.

Sì — A* funziona su qualsiasi grafo dove i costi degli archi non sono negativi e si può fornire un'euristica ammissibile. Applicazioni reali includono la pianificazione del movimento di bracci robotici 3D (grafi dello spazio di configurazione), l'instradamento di rete (latenza come costo), e il parsing del linguaggio naturale (reticoli simili a Viterbi). La griglia qui è solo la rappresentazione visivamente più intuitiva dell'algoritmo generale.

Nodi espansi conta quante volte l'algoritmo ha estratto un nodo dalla frontiera e processato i suoi vicini — questa è la misura primaria dell'efficienza di A*. Un conteggio più basso significa che l'euristica sta guidando bene la ricerca. Su una griglia 30×30 (900 celle) una buona euristica può spesso trovare il percorso ottimale espandendo meno di 100 nodi, mentre Dijkstra può espandere ogni cella raggiungibile.