Esplorazione degli algoritmi di ricerca del percorso per Wall-E

Algoritmi di ricerca del percorso per Wall-E

La Storia Dietro

Alcuni anni fa, Yandex ha organizzato un concorso chiamato Robot Corrieri con un premio allettante: un biglietto per una conferenza chiusa sull’auto guida per professionisti. Il concorso assomigliava a un gioco, con i partecipanti incaricati di trovare percorsi ottimali sulla mappa e ottimizzare la consegna utilizzando corrieri robotici.

Mentre approfondivo l’argomento, ho scoperto che nonostante la ricerca di percorsi fosse un problema risolto, continuava ad essere di interesse per la comunità di sviluppatori di giochi professionisti. Tra il 2010 e il 2020, gli ingegneri hanno apportato significative ottimizzazioni all’algoritmo A*, particolarmente vantaggiose per i giochi AAA con mappe enormi. Leggere articoli e ricerche su queste ottimizzazioni è stata un’esperienza entusiasmante.

Inoltre, i requisiti del concorso erano progettati per consentire una valutazione facile degli output del programma da parte del sistema di test del concorso. Di conseguenza, c’era poca enfasi sulla visualizzazione.

Ho trovato affascinante esplorare questo campo e sviluppare una piccola applicazione che utilizza noti algoritmi grafici per trovare percorsi su una mappa a griglia. Per visualizzare i miei risultati, ho utilizzato la libreria grafica SFML.

Obiettivo

Questo progetto si basa su uno dei miei sforzi precedenti, in cui ho dimostrato che quattro noti algoritmi di ricerca di percorsi (BFS, DFS, Dijkstra e A*) non sono fondamentalmente diversi e possono essere implementati in modo universale. Tuttavia, è stato difficile mostrare differenze significative di prestazioni tra questi algoritmi in quel progetto.

In questo articolo, mi propongo di utilizzare dati di test migliorati e creare qualcosa di visivamente eccitante. Sebbene il compito del concorso Yandex menzionato in precedenza si allinei bene ai miei obiettivi, non risolverò qui il loro problema specifico poiché si basa pesantemente sul loro sistema di test, attualmente non disponibile.

Invece, estrarro idee generali per i parametri di input da quel concorso e creerò la mia implementazione.

Mondo Immaginario

Immagina una città tecnologicamente avanzata e innovativa in cui il futuro è arrivato da molto tempo. In questa città, la maggior parte degli ordini viene consegnata da robot corrieri ed è diventato raro che una persona consegni un ordine da un caffè. In questo compito, ti invitiamo a partecipare alla ricerca di percorsi ottimali per consegnare gli ordini in modo efficiente.

Immaginiamo la città come una mappa N × N. Per semplicità, assumiamo che ogni robot occupi esattamente una cella e ogni cella possa essere attraversata o meno dai robot. In un passo, un robot può muoversi in una delle quattro direzioni cardinali (su, giù, sinistra o destra) se la cella di destinazione è libera.

E ignoro il resto del mio compito originale: All’inizio del test, devi restituire il numero di robot che desideri utilizzare per consegnare gli ordini e le loro coordinate iniziali. La costruzione di ogni robot costerà Costc rubli.

Successivamente, verranno eseguite T iterazioni della simulazione. Un’iterazione rappresenta un minuto virtuale e consiste in 60 secondi. Ad ogni iterazione, il tuo programma riceverà il numero di nuovi ordini e in risposta, il programma dovrà indicarti le azioni che ogni robot compie (60 azioni per robot).

Per ogni ordine consegnato con successo, riceverai max(0, MaxTips – DeliveryTime) dollari di mancia, dove MaxTips è il numero massimo di mance per un ordine e DeliveryTime è il tempo dal momento in cui l’ordine è apparso alla sua consegna in secondi.

Il numero totale di punti che guadagni in un test viene calcolato secondo la formula TotalTips – R × Costc, dove TotalTips è il numero totale di mance guadagnate, R è il numero di robot utilizzati e Costc è il costo di costruzione di un robot. I valori di Costc e MaxTips vengono impostati in ogni test. Se guadagni meno mance di quelle che hai speso per fare i robot, i tuoi punti totali saranno 0. Riceverai anche 0 punti per il test se esegui qualsiasi azione errata.

Input

Il programma utilizza l’input standard per leggere i parametri. Questo approccio ci permette di specificare dati di test di varie complessità utilizzando file di input.

La prima riga di input contiene tre numeri naturali: N (la dimensione della mappa della città), MaxTips (il numero massimo di mance per ordine) e Costc (il costo di costruzione di un robot). Ignoro entrambi i parametri MaxTips e Costc per la mia prima implementazione e potrei considerarli in futuro.

In seguito, ciascuna delle successive N righe contiene N caratteri che rappresentano la mappa della città. Ogni stringa può consistere in due tipi di caratteri:

  • ‘#’ – indica una cella occupata da un ostacolo.
  • ‘.’ – indica uno spazio libero.

Inoltre, ti verranno forniti due numeri naturali: T e D (T ≤ 100.000, D ≤ 10.000.000). T rappresenta il numero di iterazioni di interazione e D rappresenta il numero totale di ordini.

Output

Il tuo compito è visualizzare la mappa e le rotte ottimali utilizzando la libreria grafica SFML.

Modellazione delle mappe

Sono un fan delle mappe rappresentate come una griglia di celle. Pertanto, preferisco renderizzare tutti i risultati e mapparli come una griglia, cella per cella.

C’è anche la possibilità di eseguire la ricerca del percorso direttamente sulla griglia senza utilizzare alcuna struttura dati aggiuntiva (ho implementato questo anche per scopi di apprendimento: vedi nel codice).

Tuttavia, grazie alla griglia, è facile rappresentare una mappa come un grafo utilizzando un metodo o un altro. Preferisco utilizzare una lista di adiacenza delle celle per la maggior parte degli algoritmi come BFS, Dijkstra e A-Star. Per algoritmi come Bellman-Ford, potrebbe avere senso utilizzare una lista di archi invece di una lista di adiacenza. Ecco perché se esplori il codice sorgente, troverai tutte queste implementazioni, e tutte sono esempi funzionanti.

Per separare la logica e le responsabilità, ho un’entità chiamata Navigator che è responsabile dell’esecuzione della ricerca del percorso in base alle configurazioni di ordini e compiti specificate tramite il file di configurazione AppConfig e i file di mappa correlati.

La configurazione dell’applicazione (App Config) ha un aspetto del genere:

Nota che “map_”, “map__”, ecc. non sono realmente proprietà di configurazione. Vengono ignorate durante l’esecuzione dell’applicazione. Poiché non è possibile commentare una parte del file JSON, utilizzo il sottolineato nel nome della proprietà in modo che rimanga nel file di configurazione ma non venga utilizzata.

Il file della mappa ha un aspetto del genere:

25 50 150
#########################
#########################
#########################
###.......#####.......###
###.......#####.......###
###.......#####.......###
###...................###
###.......#####.......###
###.......#####.......###
...................###
######.###########.######
######.###########.######
######.###########.######
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
######.###########.######
#########################
#########################
#########################
#########################
2 4
2
6 6 4 20

Questo è uno degli esempi più semplici che contiene celle bloccate o non bloccate. Ho preparato molti esempi diversi di parametri di input e dati di test, partendo da parti molto piccole che ti permettono di eseguire il debug e imparare il codice, fino ad arrivare a una grande porzione di mappa (dalla città esistente nel mondo reale) che ci consente di misurare le prestazioni di un algoritmo di grafico.

Come disegniamo le mappe?

Quando una mappa contiene solo celle con uno stato binario (bloccate o non bloccate), questo significa fondamentalmente che ogni arco del grafo esiste o non esiste.

Per trovare un percorso nel grafo, dobbiamo rappresentarlo in modo efficiente. Come nel mio post precedente, ho utilizzato una lista di adiacenza con la relazione come Vector[NodeId]->punta a->Vector[Nodi adiacenti]:

Curiosamente, quando esploriamo le griglie, non è realmente necessario utilizzare i grafici. Siamo in grado di attraversare la griglia utilizzando gli algoritmi BFS/DFS cella per cella senza pensarci agli archi. Vedi il metodo _GetPathByBFSOnGrid.

Per prima cosa, il codice di inizializzazione legge il file e lo converte in una griglia riga per riga e colonna per colonna:

In seguito, viene creato un grafo effettivo come lista di adiacenza:

La rappresentazione della griglia è utile per disegnare sullo schermo utilizzando la libreria SFML. Possiamo disegnare creando oggetti geometrici (esattamente ciò che faccio per le mappe piccole):

O possiamo farlo in modo efficiente pixel per pixel per mappe più grandi:

Infine, vediamo come sarebbe una mappa definita dal file test_25_xmax.

In origine, il file definiva questo:

E una mappa renderizzata con SFML ha questo aspetto:

Poiché volevo che tutto ciò fosse controllato dall’utente con la tastiera, ho lasciato tutta la logica del comportamento utente nel main.cpp. Mi piace chiamarla logica del “Controller”.

La libreria SFML rende molto facile gestire gli eventi della tastiera:

L’idea principale è che i trigger dell’utente (premendo il tasto SPAZIO) leggano il file della mappa e renderizzino la mappa, e quindi un secondo trigger (seconda pressione del tasto SPAZIO) carichi il compito di instradamento e calcoli il percorso più breve tra due punti sulla mappa:

Dobbiamo Andare Più in Profondità

Volevo giocare con più algoritmi di grafi, e tutti hanno le loro limitazioni, quindi ho deciso di implementare anche mappe multicolori che possono essere rappresentate da grafi multi-pesati.

Ogni cella è colorata, e il colore significa che l’arco non solo esiste ma applica anche un certo peso (o tassa, o multa, come preferisci). Quindi, l’arco potrebbe essere bloccato, parzialmente bloccato, non bloccato…capisci l’idea.

Così, ho implementato mappe multicolori che sembrano più allegre e pronte per il gioco (esempio dal file test_31_multi_weight_graph_map):

Alcuni dei file di configurazione contengono mappe più complesse di città realmente esistenti, come test_29_yandex_weighten_real_map:

Come sfida, ora dovremmo gestire mappe con configurazioni molto flessibili. RectangularMap.cpp contiene essenzialmente molta logica interna, inclusi tutti gli algoritmi di grafi e anche più di quanto necessario (perché mi piace giocare con le cose, anche se non sono particolarmente utili al momento).

Ho implementato gli algoritmi BFS#Linea 598, Dijkstra#Linea 299, A-Star#Linea 356, Bellman-Ford#Linea 428, e una serie di algoritmi “utility” aggiuntivi come Topological Sort, Single Source Path, che non sono utili per lo stato attuale dell’applicazione (perché funzionano su Grafi Direttamente Aciclici, che non sono il tipo di Grafi che utilizzo attualmente), ma ho alcune idee per utilizzarli in futuri miglioramenti.

Non ho rifinito tutto il codice e non l’ho reso abbastanza ideale, ma mi permette (e spero che permetta anche a te) di giocare con il codice e confrontare le metriche di performance.

Scusa per alcune righe commentate qua e là, forse del codice sporco…è tutto un modo per imparare :). Per capire l’idea di cosa c’è dentro, ti consiglio di dare un’occhiata a RectangularMap.h.

Ci sono anche alcune funzionalità divertenti, come una funzionalità di Focus che consente di visualizzare solo una parte specifica di una mappa. Cambia il focus rirenderizzando la parte necessaria utilizzando il pattern Observer quando l’utente preme i tasti PgDown o PgUp. È abbastanza facile migliorare questa funzionalità e implementare la funzionalità di “Zoom”. Prendilo come compito, se ti piace.

Funzionalità di Focus con il file della mappa test_29_yandex_weighten_real_map in funzione:

Il diagramma delle classi è così:

Esegui e Gioca

Credo che la parte più divertente sia semplicemente eseguire questa piccola applicazione, giocando con le variazioni della sua configurazione e degli algoritmi. Puoi fare molti esperimenti utilizzando vari file di mappa come parametri di input con dati di test diversi e modificando la logica nel codice.

Dopo l’avvio, devi premere SPAZIO. L’applicazione renderizzerà una mappa in base al file di configurazione, e ha molto senso iniziare l’esplorazione dai casi di test più semplici passando ai più complessi.

Premendo SPAZIO ancora una volta, gli algoritmi di routing verranno eseguiti e troveranno il percorso tra l’inizio e l’ordine più vicino. A proposito, non è ancora fatto, ma è facile implementare la lettura di tutti gli altri ordini disponibili nei file di configurazione della mappa ed eseguire la ricerca del percorso per tutti loro.

Ecco il percorso trovato sulla mappa definita dal file test_18_yandex_super_high_res:

È in grado anche di trovare percorsi nelle mappe che simulano città esistenti, come test_29_yandex_weighten_real_map:

Trovare percorsi efficienti tra due coordinate diventa una sfida per algoritmi come BFS ma può essere facilmente fatto da A-star.

In base alle celle trovate nei file di configurazione della mappa, l’applicazione tratterà la mappa come un grafo pesato o non pesato e selezionerà l’algoritmo giusto per esso (e puoi facilmente cambiarlo anche tu). È facile vedere la differenza tra le performance di BFS e A-Star:

Parole Finali

Con questo, voglio lasciarti solo e permetterti di giocare con questi esempi di codice. Spero che lo troverai affascinante e che imparerai molto da esso.

Resta sintonizzato!

  1. Implementazione universale di BFS, DFS, Dijkstra e algoritmi A-Star
  2. JPS+: Oltre 100 volte più veloce di A* di Steve Rabin
  3. Ottimizzazioni e Miglioramenti di A* di Lucho Suaya