Yol bulma (pathfinding)
Bir karakterin A noktasından B noktasına duvarlara çarpmadan nasıl gideceğini, bir karenin çok küçük bir kesrinde hesaplamak.
Problem iki yarıdan oluşur. Önce dünyanın bir graf olarak tanımlanması gerekir: açık ve kapalı hücrelerden oluşan bir ızgara, elle yerleştirilmiş yol noktaları ağı ya da yürünebilir çokgenlerden oluşan bir navmesh. Sonra graf aranır; neredeyse her zaman A* ile. A*, 1968'de Peter Hart, Nils Nilsson ve Bertram Raphael tarafından Shakey robotu için yayımlandı ve Dijkstra'ya aramayı hedefe doğru çeken bir sezgisel işlev ekler.
Alanın geri kalanı optimizasyon ve kozmetiktir. Hiyerarşik yol bulma büyük haritaları kümelere böler, akış alanları bin birimin tek bir aramayı paylaşmasını sağlar, yol yumuşatma ise sonucun zikzak çizmesini önler. Matematiksel olarak en kısa ama robot gibi görünen bir yol yine de hata sayılır.