IT 
English
Українська
Deutsch
Español
Français
Polski🎮 Ricercatore di Percorsi per NPC — Ricerca A* dal Vivo
Osserva il vero algoritmo di ricerca A* espandere dal vivo i nodi di una mappa di gioco simulata secondo un genuino costo f=g+h, trovando percorsi NPC dimostrabilmente più brevi attorno agli ostacoli, più velocemente del semplice Dijkstra.
Informazioni sulla simulazione Ricerca A* dal Vivo
I motori di gioco si pongono costantemente la stessa domanda: qual è il percorso percorribile più breve da un NPC al suo obiettivo attraverso una mappa piena di muri, terreno e altri ostacoli? La ricerca A* (Hart, Nilsson e Raphael, 1968) è la risposta di riferimento — una ricerca su grafo best-first che mantiene una vera coda a priorità ordinata per f(n) = g(n) + h(n), dove g(n) è il vero costo accumulato dalla partenza e h(n) è una stima euristica ammissibile della distanza rimanente. Questa simulazione esegue l'algoritmo reale — vero insieme aperto, vero insieme chiuso, veri puntatori genitore — su una mappa di gioco a griglia che puoi modificare, ed esegue contemporaneamente il semplice algoritmo di Dijkstra (A* con h(n) = 0) sulla mappa identica, così puoi osservare, nodo per nodo, esattamente quanto lavoro risparmia l'euristica.
🔬 Cosa mostra
Due griglie affiancate che condividono una mappa di ostacoli: la griglia di sinistra esegue il vero A* con un'euristica a distanza ottile, la griglia di destra esegue Dijkstra con l'euristica forzata a zero. Le celle ciano sono nell'insieme aperto (scoperte, in coda, non ancora espanse), le celle ambra sono nell'insieme chiuso (espanse, finalizzate), e il percorso colorato in accento è il percorso più breve ricostruito tramite i puntatori genitore una volta estratto il nodo obiettivo. I contatori dal vivo totalizzano il numero reale di nodi che ciascuna coda a priorità ha effettivamente estratto.
🎮 Come si usa
Scegli una modalità — Muro, Partenza o Obiettivo — poi clicca su qualsiasi cella di entrambe le griglie per modificare la mappa condivisa; entrambe le ricerche si rieseguono all'istante. Usa Labirinto casuale per generare un nuovo schema di ostacoli, Cancella muri per ripartire da un campo aperto, e il cursore della velocità di espansione per rallentare la rivelazione a scopo didattico o accelerarla per vedere subito il percorso finale. Replay riavvia l'animazione nodo per nodo senza ricalcolare la ricerca.
💡 Lo sapevi?
Poiché l'algoritmo di Dijkstra è matematicamente identico ad A* con h(n)=0, i due pannelli eseguono esattamente lo stesso percorso di codice con un numero cambiato — motivo per cui questo è un confronto equo, a parità di condizioni, anziché due implementazioni scorrelate. Su mappe aperte A* spesso espande meno della metà dei nodi di Dijkstra; su mappe dove un muro costringe entrambi gli algoritmi a una lunga deviazione, il divario si riduce perché nessuno dei due può scavalcare la geometria che l'euristica non riesce a vedere attraverso.
Domande frequenti
Che cos'è la ricerca A* e in cosa differisce dall'algoritmo di Dijkstra?
Entrambe sono ricerche su grafo best-first che estraggono a ogni passo il nodo a costo più basso da una coda a priorità (l'insieme aperto). L'algoritmo di Dijkstra ordina quella coda puramente per g(n), il costo effettivo accumulato dal nodo di partenza, quindi esplora verso l'esterno in tutte le direzioni allo stesso modo, come le onde su uno stagno. A* ordina la stessa coda per f(n) = g(n) + h(n), aggiungendo una stima euristica ammissibile h(n) della distanza rimanente verso l'obiettivo. Quel termine extra orienta l'espansione verso l'obiettivo, quindi A* tipicamente chiude molti meno nodi di Dijkstra pur garantendo di restituire lo stesso percorso a costo minimo, perché un'esecuzione di Dijkstra è matematicamente identica a un'esecuzione di A* con h(n) = 0 per ogni nodo — esattamente come questa simulazione implementa il confronto su una mappa condivisa.
Cosa rende ammissibile un'euristica, e perché ciò garantisce che A* trovi il percorso più breve?
Un'euristica h(n) è ammissibile se non sovrastima mai il vero costo rimanente dal nodo n all'obiettivo — può sottostimare o essere esattamente corretta, ma mai troppo ottimistica nella direzione sbagliata. Su una griglia dove i passi diagonali costano √2 e quelli ortogonali costano 1, la distanza in linea retta (ottile) verso l'obiettivo è sempre minore o uguale al vero costo del percorso rimanente attorno agli ostacoli, quindi è ammissibile. Con un'euristica ammissibile, A* è garantito non finalizzare mai un nodo con un valore g subottimale: qualsiasi percorso che riporta come più breve lo è davvero, motivo per cui la simulazione può affermare che A* e Dijkstra approdano sempre allo stesso costo di percorso, non solo a uno simile.
Che cos'è la distanza ottile e perché viene usata su mappe a griglia che consentono il movimento diagonale?
La distanza ottile è l'euristica per griglie a 8 direzioni: date |dx| e |dy| celle di separazione orizzontale e verticale, il percorso più breve possibile (ignorando gli ostacoli) si muove diagonalmente min(|dx|,|dy|) volte a costo √2 ciascuna, poi copre le rimanenti |dx|-|dy| celle ortogonalmente a costo 1 ciascuna. La formula (|dx|+|dy|) + (√2-2)·min(|dx|,|dy|) calcola esattamente questo. La semplice distanza euclidea o di Manhattan sovrastimerebbe (rompendo l'ammissibilità su una griglia a movimento diagonale) oppure sottostimerebbe troppo, quindi la distanza ottile è la scelta stretta e ammissibile che questa simulazione usa per l'h(n) di A*.
Perché A* di solito espande meno nodi di Dijkstra?
Dijkstra non ha alcuna nozione di dove si trovi l'obiettivo, quindi il suo fronte di espansione cresce come un fronte d'onda approssimativamente circolare centrato sulla partenza, toccando ogni nodo entro un dato raggio di costo prima di raggiungere l'obiettivo. L'ordinamento f = g + h di A* mantiene i nodi che puntano verso l'obiettivo vicino alla testa della coda a priorità, quindi il suo fronte si allunga in una forma elongata e orientata all'obiettivo, saltando ampie regioni sul lato opposto della mappa che Dijkstra dovrebbe comunque visitare. I contatori dal vivo in questa simulazione totalizzano il numero reale di nodi che ciascun algoritmo ha effettivamente estratto e chiuso dalla propria coda a priorità sulla stessa mappa di ostacoli, quindi il divario che vedi è una differenza genuina e misurata, non presunta — e su mappe dove la linea retta verso l'obiettivo è bloccata da un grande ostacolo, il divario può ridursi o addirittura svanire, cosa che la simulazione mostrerà onestamente.
Qual è la differenza tra l'insieme aperto e l'insieme chiuso?
L'insieme aperto è il fronte: nodi che sono stati scoperti (raggiunti da qualche vicino) e inseriti nella coda a priorità, ma non ancora espansi. L'insieme chiuso sono i nodi già estratti dalla coda e di cui sono stati esaminati tutti i vicini — il loro costo g più breve dalla partenza è finalizzato e non cambierà più. Nella visualizzazione, le celle ciano sono nell'insieme aperto (candidati ancora in considerazione) e le celle ambra sono nell'insieme chiuso (completamente elaborate); una volta che l'obiettivo viene estratto dall'insieme chiuso, l'algoritmo si ferma e ricostruisce il percorso percorrendo i puntatori genitore all'indietro dall'obiettivo alla partenza.
A* può mai non riuscire a trovare il percorso più breve, o non trovare affatto un percorso?
A* è garantito trovare il percorso più breve ogni volta che ne esiste uno e la sua euristica è ammissibile — l'euristica a distanza ottile di questa simulazione soddisfa quella condizione su ogni mappa che costruisci. Ciò che A* non può fare è trovare un percorso che non esiste: se muri completamente l'obiettivo, sia A* che Dijkstra esauriranno i loro insiemi aperti e segnaleranno che non è stato trovato alcun percorso, cosa che il pannello statistiche mostrerà esplicitamente anziché visualizzare silenziosamente un percorso obsoleto.
Una coda a priorità a heap binario espande i nodi in vero ordine best-first secondo f(n)=g(n)+h(n) sulla griglia sinistra e f(n)=g(n) su quella destra; entrambe ricostruiscono il percorso più breve tramite veri puntatori genitore una volta estratto l'obiettivo dall'insieme chiuso.
3D · renderer Three.js / WebGL · target 60 FPS · funziona interamente lato client, senza installazione