Vuoi scontrarti velocemente con dei problemi di ottimizzazione anche nel più semplice gioco 2D senza effetti grafici? Basta provare ad implementare un algoritmo generico per far “trovare la strada” ai tuoi omini e poi mettere un po’ di omini o allargare il campo di gioco.
In queste settimane sto sperimentando diverse strategie di pathfinding per simulare il movimento di una folla in un ambiente bidimensionale visto dall’alto con ostacoli. Sto cercando di evitare di usare una griglia e per questa ragione la mia implementazione utilizza i raycast del motore fisico 2D di Unity.
I raycast son semplicemente dei raggi che partono ad esempio da un personaggio, e segnalano se e dove colpiscono un ostacolo: in questo modo si può cercare di tracciare una strada per muovere il personaggio dalla sua posizione alla sua destinazione.
Se gli ostacoli sono pochi e semplici basterà angolare i raggi e far muovere il personaggio fino a quando questo sarà in vista del suo obiettivo, ma se vogliamo far muovere i nostri personaggi all’interno di un sistema più complesso, tipo una serie di stanze ad un vero e proprio labirinto, allora abbiamo bisogno di un sistema generico.
L’algoritmo A* è un sistema generico di navigazione formulato nel lontano 1968, ma tutt’oggi ancora molto utilizzato per la sua versatilità.
Questo algoritmo funziona su una griglia di nodi: dalla partenza si controllano i nodi circostanti e si calcola quale è il più vicino alla destinazione e quanto è il costo per arrivare ad ogni singolo nodo; quindi si prende il nodo più vicino alla destinazione e si fa lo stesso; quindi ci si continua ad espandere per nodi adiacenti fino a quando si trova il nodo di destinazione.
A questo punto possiamo impostare l’algoritmo con pesi differenti in modo che dia priorità al nodo più vicino o alla destinazione, o se privilegiare il minor numero di passaggi. Se privilegiamo il nodo di destinazione cercheremo di avvicinarci il più possibile all’obiettivo, e questo può andar bene se non ci son diversi vicoli ciechi. Se diamo priorità al numero di passaggi invece l’espansione della ricerca sarà uniforme e quindi più lenta nella sua esecuzione se si tratta di girare attorno ad un semplice muro.
La prima soluzione quindi è più veloce con degli ostacoli semplici ma anche in questo caso non garantisce la strada più veloce, mentre la seconda è più veloce con veri e propri labirinti (ed un labirinto è in ogni caso più lento da risolvere).
Una volta trovata la soluzione naturalmente possiamo effettuare altri passaggi per migliorarla, e soprattutto per memorizzarla in modo che il programma possa evitare di risolvere più volte problemi simili.
L’A* è quindi una buona base per cominciare a pensare ad un algoritmo di pathfinding, ma naturalmente su questa base occorre implementare altre “scorciatoie” a seconda delle necessità, per ottimizzare il processo.
A questo punto dello sviluppo ho implementato il semplice A* e un algoritmo per tagliare i nodi intermedi, ma non ci sono ancora come prestazioni: inoltre questa implementazione non sfrutta a pieno il potenziale del raycast che è molto adatto a misurare distanze: per questo motivo nei prossimi giorni proverò a cambiare la costruzione della griglia dei nodi.
Probabilmente scriverò un altro articolo quando arriverò ad una soluzione accettabile.