A.I. che può navigare in una città 2D generata in modo casuale

Question

Sto scrivendo un gioco iOS (Utilizzo di UIView), che ha una città 2D generata casualmente. Ho bisogno di attaccare A.I., che prenderà un percorso intelligente per trovare il giocatore (senza scontrarsi con gli edifici). Qualcuno può indicarmi la giusta direzione su quale tipo di algoritmi utilizzerei per raggiungere questo obiettivo?

Modifica: Ho deciso di utilizzare A *. Creerò una griglia sulla mappa, testerò ogni punto di intersezione della griglia, se quel punto si trova all'interno di un edificio, annullerò il punto. L'attacco A.I. il giocatore si sposterà quindi dalla posizione corrente a un punto di griglia valido, più vicino al suo obiettivo (entro un certo raggio dalla sua posizione).

Answer 1

Stai cercando una classe di algoritmi chiamata pathfinding algorithms. Ci sono molti approcci che puoi usare.

Gli algoritmi classici qui sono Dijkstra's algorithm e A* search, che possono guidare un oggetto da una posizione all'altra lungo il percorso ottimale. Questi algoritmi funzionano modellando il mondo 2D come graph e quindi trovando il percorso più breve dalla posizione iniziale dell'oggetto alla posizione di destinazione in tale grafico. Questi due algoritmi sono ampiamente utilizzati in AI e pathfinding e suggerirei caldamente di investire il tempo per leggere di più su di essi. C'è uno solid tutorial on A* search disponibile online se lo desideri.

Se si dispone di molti oggetti diversi che devono spostarsi su un target senza interferire, è possibile esaminare i potenziali campi, che forniscono una struttura semplice e flessibile per far sì che più oggetti si avvicinino a un obiettivo. Questo approccio è stato utilizzato da the Berkeley "Overmind" StarCraft AI e viene spesso utilizzato nella pianificazione del movimento del robot. Intuitivamente, questo approccio funziona assegnando un valore "potenziale" a ciascuna posizione, quindi facendo in modo che gli oggetti continuino a passare dal potenziale elevato al potenziale basso fino a raggiungere il bersaglio. Questo approccio è un po 'più complicato per essere corretto, ma una volta che funziona tende a creare un'IA flessibile e personalizzabile che si comporti in modo intelligente.

Spero che questo aiuti!

Answer 2

Questa domanda qui: Pacman: how do the eyes find their way back to the monster hole? è una buona panoramica degli approcci alla navigazione AI di una griglia 2D casuale alla ricerca di un giocatore in movimento. Il consenso generale (e l'approccio utilizzato da Pacman) non è quello di preoccuparsi di cuocere algoritmi di PathFinding intelligenti nell'IA, ma di usare la mappa stessa per memorizzare le informazioni sulla posizione del giocatore. È una lettura affascinante, in particolare la seconda e la terza risposta (e i loro collegamenti esterni) di AmmoQ e Dan Vinton.

Questo collegamento qui Pacman scent antiobject pattern descrive un approccio economico ed efficace.