Non capisco A * Pathfinding - algoritmo, path-finding, a-star

Da quello che ho capito:

Aggiungi il nodo corrente all'elenco chiuso.

Trova nodi adiacenti al nodo corrente e senon sono nodi non percorribili e non nell'elenco chiuso, aggiungono quel nodo all'elenco aperto con il padre come nodo corrente e calcolano i valori F, G e H. Se il nodo esiste già nell'elenco aperto, verificare se l'accesso a quel nodo attraverso il nodo corrente comporterà un valore G inferiore - in caso affermativo, rendere il nodo padre di quel nodo il nodo corrente.

Trova il nodo nell'elenco aperto con il valore F più alto e imposta quel nodo sul nodo corrente.

Ripeti fino a quando non arrivi a destinazione, quindi passa attraverso i genitori del nodo di destinazione e tornerai al nodo iniziale. Questo sarà il percorso migliore.

Quindi, questo ha senso per il mio cervello, ma quando in realtà lo provo su un diagramma, penso di non capirlo correttamente.

(Dalla foto sotto) Scendi dalcominciando dalla piastrella verde, quella con un valore F di 60. Questo è nell'elenco aperto e ha un valore F inferiore a 74 in basso a destra. Perché viene scelto il 74 anziché il 60?

risposte:

Secondo me, dovresti dare un'occhiata Amit "s A * Pages. Sono davvero fantastici per spiegare come funziona l'algoritmo e come farlo funzionare.

Per quanto riguarda il tuo caso, il diagramma mostra il punteggio G dal primo nodo nell'elenco aperto. Quando si guarda il sito Web, l'intero diagramma viene creato per primo per la valutazione del primo nodo e l'autore mostra che il primo nodo migliore è quello a destra. Quindi, andare avanti utilizza il punteggio G. basato sul punteggio del nodo corrente più il costo di spostamento di quello successivo, che non è mostrato nel diagramma.

Si dice sul sito Web però:

E l'ultimo quadrato, immediatamente a sinistra del quadrato corrente, viene controllato per vedere se il punteggio G è inferiore se attraversi la piazza corrente per arrivarci. Niente da fare.

Il punteggio G sarebbe effettivamente 24 (14 (costo attuale) + 10 (costo del movimento orizzontale)), proprio come il quadrato sottostante, se ricordo bene.

Il motivo per cui non ti sposti in piazzacon un valore F di 60 è perché è nella "lista chiusa". Dove come i quadrati con un valore F di 88 e 74 sono nella "lista aperta" e possono essere esaminati per la mossa successiva.