Pathfinding nei Videogiochi: Tecniche Classiche e Nuove Frontiere

La tesi fornisce una ricognizione critica e integrata delle tecniche di pathfinding impiegate nell'intelligenza artificiale dei videogiochi. Dopo aver inquadrato il problema della navigazione degli NPC e le principali strutture dati (griglie, Waypoint, NavMesh), il lavoro analizza i classici algoritmi di ricerca del percorso, da BFS/DFS a Dijkstra e A*, e le loro varianti ottimizzate (Jump Point Search, HPA*, Flow Field), valutandone complessità, scalabilità e qualità dei percorsi. Successivamente esplora l’evoluzione verso approcci guidati dall’IA avanzata: Behaviour Trees per l’orchestrazione decisionale, modelli di Machine Learning e Deep Reinforcement Learning per adattare i costi euristici e generare strategie in ambienti dinamici, fino alle prime applicazioni di modelli generativi che promettono NPC più credibili e diversificati. L’implementazione prototipale sviluppata in Unity dimostra, con scenari interattivi, i vantaggi pratici delle diverse metodologie: gli algoritmi classici garantiscono prestazioni deterministiche e facilmente controllabili; le tecniche ML ottengono invece maggiore adattività, riducendo ricalcoli in tempo reale e migliorando il realismo collettivo di grandi insiemi di agenti. I test quantitativi confermano che le varianti gerarchiche e Jump Point Search dimezzano, nei casi studio, il tempo di calcolo rispetto ad A*, mentre il Flow Field scala efficientemente a centinaia di unità concorrenti. Il confronto finale evidenzia che la soluzione ottimale non risiede in una singola tecnica, bensì in architetture ibride capaci di combinare la solidità degli algoritmi classici con la flessibilità del learning. La tesi conclude delineando linee di ricerca sul co-design fra NavMesh dinamiche e reti neurali differenziabili, aprendo la strada a sistemi di pathfinding che non solo trovano percorsi brevi, ma apprendono a farlo in modo contestuale al gameplay.