Pathfinding
Uitzoeken hoe een personage van A naar B komt zonder tegen muren op te lopen — in een fractie van een frame.
Het probleem heeft twee helften. Eerst moet de wereld als graaf worden beschreven: een raster van open en geblokkeerde cellen, een netwerk van met de hand geplaatste waypoints of een navmesh van begaanbare vlakken. Daarna wordt die graaf doorzocht, vrijwel altijd met A* — in 1968 gepubliceerd door Peter Hart, Nils Nilsson en Bertram Raphael voor de robot Shakey — oftewel Dijkstra plus een heuristiek die de zoektocht richting het doel trekt.
De rest van het vakgebied is optimalisatie en cosmetica. Hiërarchische pathfinding verdeelt grote kaarten in clusters, met flow fields delen duizend eenheden één zoekopdracht en padafvlakking voorkomt dat het resultaat zigzagt. Een pad dat wiskundig het kortst is maar er robotachtig uitziet, geldt nog steeds als bug.