Pathfinding
Working out how a character gets from A to B without walking into walls — in a fraction of a frame.
The problem comes in two halves. First the world has to be described as a graph: a grid of open and blocked cells, a network of hand-placed waypoints, or a navmesh of walkable polygons. Then the graph gets searched, nearly always with A* — published in 1968 by Peter Hart, Nils Nilsson and Bertram Raphael for the Shakey robot — which is Dijkstra plus a heuristic that pulls the search toward the goal.
The rest of the field is optimisation and cosmetics. Hierarchical pathfinding splits large maps into clusters, flow fields let a thousand units share one search, and path smoothing stops the result from zigzagging. A path that's mathematically shortest but looks robotic still counts as a bug.