A* pathfinding algoritması nasıl çalışır? Heuristic seçimi neyi etkiler?

A*, bir başlangıçtan hedefe en kısa yolu bulan, Dijkstra'nın heuristic ile yönlendirilmiş hâlidir. Her düğüm için:

• g(n): başlangıçtan bu düğüme gerçek maliyet
• h(n): bu düğümden hedefe tahmini maliyet (heuristic)
• f(n) = g(n) + h(n): öncelik değeri

Algoritma her adımda open set'teki en düşük f değerli düğümü seçer.

List<Node> FindPath(Node start, Node goal)
{
    var open = new PriorityQueue<Node, float>();
    var cameFrom = new Dictionary<Node, Node>();
    var g = new Dictionary<Node, float> { [start] = 0 };
    open.Enqueue(start, Heuristic(start, goal));

    while (open.Count > 0)
    {
        Node current = open.Dequeue();
        if (current == goal) return Reconstruct(cameFrom, current);

        foreach (Node n in current.Neighbors)
        {
            if (!n.Walkable) continue;
            float tentative = g[current] + Cost(current, n);
            if (!g.TryGetValue(n, out float old) || tentative < old)
            {
                cameFrom[n] = current;
                g[n] = tentative;
                open.Enqueue(n, tentative + Heuristic(n, goal));
            }
        }
    }
    return null; // yol yok
}

Heuristic seçimi

• Heuristic admissible ise (gerçek maliyeti asla abartmıyorsa) A* en kısa yolu garanti eder.
• h = 0 olursa A* Dijkstra'ya dönüşür: doğru ama yavaş.
• Heuristic abartılırsa (weighted A*) daha az düğüm gezilir, daha hızlı olur ama yol optimal olmayabilir. Oyunlarda bu takas sık yapılır.

Pratik notlar

• Oyunlarda çoğunlukla grid yerine NavMesh (Unity'de NavMeshAgent) üzerinde çalışılır.
• Çok sayıda ajan için yol hesaplamayı birkaç kareye yaymak, sonuçları önbelleğe almak veya flow field kullanmak gerekir.
• Bulunan yol köşeli olabilir; path smoothing (string pulling) uygulanır.