Pathfinding
Calcolare come un personaggio arrivi da A a B senza sbattere contro i muri, in una frazione di frame.
Il problema ha due metà. Prima il mondo va descritto come un grafo: una griglia di celle libere e bloccate, una rete di punti di passaggio posizionati a mano o una navmesh di poligoni percorribili. Poi il grafo viene esplorato, quasi sempre con A*, pubblicato nel 1968 da Peter Hart, Nils Nilsson e Bertram Raphael per il robot Shakey: è Dijkstra con un'euristica che orienta la ricerca verso l'obiettivo.
Il resto del campo è ottimizzazione ed estetica. Il pathfinding gerarchico divide le mappe grandi in cluster, i flow field permettono a mille unità di condividere un'unica ricerca e lo smoothing del percorso evita che il risultato proceda a zigzag. Un percorso matematicamente il più breve ma dall'aspetto robotico conta comunque come un bug.