Vägsökning (pathfinding)
Att räkna ut hur en spelfigur tar sig från A till B utan att gå in i väggar — och utan att det tar mer än en bråkdel av en bildruta.
Problemet har två halvor. Först måste världen beskrivas som en graf: ett rutnät av fria och blockerade celler, ett nät av handplacerade vägpunkter eller en navmesh av gångbara polygoner. Sedan söks grafen, nästan alltid med A* — Peter Hart, Nils Nilsson och Bertram Raphael publicerade den 1968 för roboten Shakey — som är Dijkstra med en heuristik som drar sökningen mot målet.
Resten av fältet är optimering och kosmetika. Hierarkisk vägsökning delar stora kartor i kluster, flödesfält låter tusen enheter dela en sökning, och vägutjämning ser till att resultatet inte zickzackar. En väg som är matematiskt kortast men ser robotaktig ut räknas fortfarande som ett fel.