HwStories#00: Stagisti, il pathfinding e LabY

Luca Cicchinelli/ novembre 25, 2017/ +/ 0 comments

Da sempre i labirinti appassionano orde di sviluppatori.
Sì, me compreso.

L’ultimo anno di Tecnico Industriale ho avuto l’opportunità di fare uno stage presso Eidos – un’azienda di Roma che sviluppa software.
Tra tutti i vari stage a cui ho partecipato è stato decisamente il più fico.

“Sì, ma che c’entra con i labirinti? E soprattutto, perché è stato il più fico?”
Tra poco ci arriviamo.

© EIDOS S.R.L.

Solitamente, gli stage che vengono proposti agli studenti di Informatica spaziano dalle ricerche di mercato allo sviluppo di siti in WordPress.

Uno stage scolastico dovrebbe sfruttare capacità già apprese dagli studenti oppure permettergli di acquisire nuove competenze? Sia chiaro che stiamo parlando di stage non retribuiti e obbligatori per lo svolgimento dell’esame di stato.

Eidos ha proposto agli studenti uno stage fine a sé stesso, senza lo scopo di monetizzare le prestazioni degli studenti o di sfruttare le loro conoscenze per la realizzazione di prodotti – per cui sarebbe necessario pagare un’azienda o un professionista.

Il Contest

Chi mi conosce da decisamente troppo tempo sa bene quanto mi piacciano le competizioni.
La competizione è ispirazione pura.

Eidos aveva progettato un labirinto in C# e il nostro scopo era ovviamente risolverlo. C’erano però delle condizioni particolari.

Eravamo 12 stagisti, divisi a coppie di 2.
Avevamo una settimana di tempo, dopodiché avremmo dovuto sfidarci in un Tutti contro Tutti degno di Mw2.

Ognuna delle coppie doveva sviluppare una .dll diversa che poi sarebbe stata utilizzata, insieme a tutte le altre, nella sfida finale.
Chi raggiunge per primo l’uscita vince.

Come funziona?

Si doveva semplicemente instanziare l’oggetto player e utilizzare i metodi messi a disposizione dalla libreria.

Il labirinto aveva una dimensione di circa 50×50. Ogni volta che si iniziava un match variava il posizionamento dell’entrata e dell’uscita. Dopodichè player veniva inizializzato sopra la partenza. Variavano anche le celle su cui erano posizionati i muri.

Una particolarità di player era la visione della mappa limitata ad un’area 10×10.
Le direzioni possibili erano 8, i movimenti obliqui erano risultati ottimi per sorpassare i muri e velocizzare l’arrivo a destinazione.

Durante la sfida finale, ogni player avrebbe compiuto un movimento alla volta per poi aspettare i movimenti di tutti gli altri.
Così via, ciclicamente, fino a quando qualcuno non avesse raggiunto l’uscita.

Una lavagna e qualche neurone

Anziché investire del tempo nella comprensione di algoritmi che ci avrebbero permesso di implementare il pathfinding, abbiamo deciso di approcciarci al problema utilizzando i nostri neuroni.
La verità è che non sapevamo neanche cosa fosse un algoritmo di pathfinding. 

E comunque qualsiasi algoritmo preesistente sarebbe dovuto essere modificato affinché l’avessimo potuto utilizzare in un labirinto con delle condizioni simili.
Per cui abbiamo optato per la via più complessa: pennarello, lavagna e caffeina.

Tra un movimento e l’altro ricostruivamo la mappa in un array bidimensionale [50][50] su cui poi effettuavamo un’infinità di controlli.
Dopo quattro giorni dall’inizio del contest, avevamo dato forma ad un algoritmo che ci permettesse di calcolare il percorso più breve, utilizzando le parti di mappa ormai elaborate.

L’algoritmo era ricorsivo, poiché non avevamo trovato una soluzione migliore.
Ovviamente andava in loop. Non funzionava.

Scontenti ma soddisfatti, implementammo un algoritmo più semplice che si limitava a scegliere se far tendere i movimenti sempre a destra o sempre a sinistra, basandosi sulla posizione iniziale di player.
Aggiungemmo poi qualche funzionalità in più per ottimizzare i movimenti in caso di spazi chiusi e muri invalicabili.

La sfida finale

Senza accorgersene neanche, ci siamo ritrovati a venerdì – il giorno della sfida finale.
Dopo aver pranzato continuammo a cercare spasmodicamente eventuali bug e ad effettuare milioni di test.

La sfida finale era strutturata in modo tale che quando uno dei player riusciva ad uscire, chi era più distante dall’uscita veniva eliminato.
In questo modo ci sarebbero stati tanti round quanti player.

Passammo il primo turno, il secondo ed anche il terzo.
Erano rimaste soltanto tre DLL in gioco, tra cui la nostra.

Sorpassammo anche il turno successivo, trovando l’uscita per primi.
Chi avrebbe vinto l’ultimo round si sarebbe aggiudicato una Cam IP.

Il labirinto dell’ultimo round viene generato. Ho gli occhi rossi e le mani sudate.
Le coppie ormai eliminate facevano il tifo.

. . .

Poi il nostro algoritmo decise di andare nella direzione opposta a quella dell’uscita.
Ebbene sì, ci siamo classificati in seconda posizione.

LabY

LabY

Rosicai un po’ ma non per la sconfitta, bensì per non esser riuscito ad elaborare un algoritmo di pathfinding funzionante.

Studiai i vari approcci possibili e scoprii che i nostri ragionamenti erano molto affini ai metodi più conosciuti, soprattutto alle varie implementazioni della ricerca in ampiezza.

Implementai il tutto in Java, con l’intenzione di scrivere poi un articolo sull’argomento.
Chi ci segue da abbastanza tempo si ricorderà il video seguente, postato sulla nostra Pagina Facebook.

Per farla breve, tra una formattazione e l’altra: persi il source.

A distanza di mesi, ho deciso di voler creare un Maze Generator che potesse essere utile durante un’eventuale spiegazione degli algoritmi di pathfinding – che verrà pubblicata prossimamente.

Volevo però che fosse utilizzabile su qualsiasi dispositivo, perciò ho messo da parte il Java ed ho optato per una soluzione basata su JQuery e i miei beneamati Flexbox.

LabY è in fase di sviluppo ma è già utilizzabile: http://bit.ly/HoworksLabY
Attualmente è privo di controlli e non è stato implementato nessun algoritmo di pathfinding. Verrà ovviamente aggiornato nel tempo, perciò la precedente affermazione potrebbe non essere più vera.

Nel mentre che aspettate, vi lascio il link al Maze Generator più fico dell’intero Internet: https://qiao.github.io/PathFinding.js/visual/

Facci sapere cosa ne pensi con un commento!