Ho un gioco in cui devi muoverti intorno a una mapparaccogliere l'oro e poi spostarsi verso l'uscita. Attualmente sto cercando di scrivere un'IA che giocherà questo gioco, ma voglio sapere quale algoritmo dovrei usare per trovare l'istanza più vicina di un oggetto. Ad esempio, il pezzo d'oro più vicino o il quadrato di mappa sconosciuto più vicino. Il problema è che ci sono muri che il giocatore non può attraversare, quindi piuttosto che trovare l'oggetto più vicino ho bisogno di trovare quello a cui c'è la via più breve. C'è un algoritmo che può farlo?
risposte:
5 per risposta № 1L'algoritmo che stai cercando si chiama A *Algoritmo di ricerca. Si tratta di un algoritmo di ricerca best-first che funziona partendo dal punto di partenza e creando una serie di possibili percorsi (escludendo attraversando ostacoli dal momento che non sono possibili percorsi), quindi segnando quei percorsi per trovare il meno costoso. Nel tuo caso hai bisogno di personalizzare il punteggio diminuendo il costo basato sugli oggetti lungo il percorso e aumentando il costo per distanza.
Ci sono alcune informazioni che ti aiuteranno con questo qui:
C'è una bella demo interattiva qui (codice anche su github): http://qiao.github.io/PathFinding.js/visual/
Altre risorse:
- https://harablog.wordpress.com/2011/09/01/rectangular-symmetry-reduction/
- https://en.wikipedia.org/wiki/A*_search_algorithm
- Cos'è un buon algoritmo di individuazione dei percorsi basato sulla griglia 2D?