11.1 Pathfinding (A*, Navmesh)

บทนี้ตอบคำถามที่เจาะจงมากข้อหนึ่ง: ตัวละครยืนอยู่ที่จุด A ต้องเดินไปยังจุด B โดยไม่เดินทะลุกำแพง และไม่ให้การเดินดูแข็งทื่อเหมือนหุ่นยนต์ บทก่อนหน้าให้วัตถุดิบสำหรับเรื่องนี้มาแล้ว — graph (กลุ่มของ node ที่เชื่อมกันด้วย edge), breadth-first search (BFS) และ priority queue ที่คุณสร้างเองสำหรับ Dijkstra's algorithm บทนี้จะเอาทั้งสามอย่างมาใช้งานจริงเพื่อสร้าง A* (อ่านว่า "A-star") ซึ่งเป็น pathfinding algorithm ที่เกมแทบทุกเกมใช้ แล้วค่อยแสดงให้เห็นว่าไอเดียเดียวกันนี้ขยายจาก grid เล็ก ๆ ไปถึงระบบ NavMesh ของ Unity ที่ใช้ในโลก 3D เต็มรูปแบบได้อย่างไร

ทุก section ด้านล่างจะมีรูปแบบเดียวกัน คือโค้ด C# เล็ก ๆ ที่รันได้จริง ผลลัพธ์จริงของมัน (หรือ trace แบบไล่ทีละขั้นในกรณีที่ไม่มี console ให้ print) แล้วตามด้วยคำอธิบายง่าย ๆ ว่าเกิดอะไรขึ้นและทำไม

1. The problem: getting from A to B without walking into walls

Pathfinding คืองานหาเส้นทางผ่าน level ของเกมจากตำแหน่งเริ่มต้นไปยังตำแหน่งเป้าหมาย โดยไม่ผ่านสิ่งกีดขวางที่ทึบตัน และให้เสีย cost น้อยที่สุดเท่าที่จะทำได้ (ระยะทางสั้นที่สุด เวลาน้อยที่สุด หรือ "ความอันตราย" ต่ำที่สุด — แล้วแต่ว่าเกมคุณสนใจอะไร) มันโผล่มาแทบทุกที่ ไม่ว่าจะเป็นศัตรูเดินเข้าหาผู้เล่น ตัวละครที่ตามคุณเข้าไปใน dungeon ฝูง NPC ที่เดินข้ามลานเมือง หรือ unit ในเกมวางแผนที่เดินไปยัง tile ที่ถูกคลิก

นี่คือห้องมุมสูงเล็ก ๆ S คือจุดเริ่ม G คือเป้าหมาย และ # คือกำแพง

ถ้าลากเส้นตรงจาก S ไป G เส้นนั้นจะทะลุกำแพงพอดี — ทำแบบนั้นไม่ได้ ตัวละครต้องหาเส้นทางที่ผ่านเฉพาะช่อง (.) ที่เปิดอยู่เท่านั้น ฟังดูง่ายสำหรับมนุษย์ที่มองภาพนี้อยู่ แต่คอมพิวเตอร์ไม่เห็น "รูปทรง" อะไรเลย มันเห็นแค่ก้อนตัวเลขก้อนใหญ่ ๆ ก้อนหนึ่ง การแปลง "รูปทรงของ level" ให้กลายเป็นสิ่งที่ algorithm ค้นหาได้คือปัญหาแรกจริง ๆ และมันคือปัญหาการแทน graph จากบทเรื่อง data structures นั่นเอง เพียงแต่เอามาใช้กับพื้นที่แทนที่จะเป็น social network หรือแผนที่เมือง

มีสองเรื่องที่ฟังดูคล้ายกันแต่จริง ๆ ไม่เหมือนกัน คุ้มค่าที่จะแยกให้ชัด: pathfinding คือการวางแผนแบบ global — คิดล่วงหน้าทั้งเส้นทางข้าม level โดยใช้แผนที่ของโลกทั้งหมด ส่วน obstacle avoidance (หรือ local steering) คือการตอบสนองแบบ reactive — หลบกำแพงหรือตัวละครอื่นที่กำลังจะชนอยู่ตรงหน้า โดยใช้แค่สิ่งที่อยู่ตรงหน้าเท่านั้น ไม่มีแผนที่เลย ตัวละครเกมที่ดีต้องมีทั้งสองอย่าง คือ pathfinding เพื่อเลือกเส้นทางรวมที่สมเหตุสมผล และ steering เพื่อตอบสนองสิ่งที่ไม่ได้อยู่ในแผนที่ (ตัวละครอื่นที่กำลังเคลื่อนที่ ถังที่เพิ่งมีคนเตะล้ม) บทนี้พูดถึงเรื่องแรกทั้งหมด ส่วน NavMeshAgent ของ Unity ที่จะพูดถึงทีหลัง จริง ๆ แล้วทำทั้งสองอย่างให้เราเลยนิดหน่อย

2. Representing the world as a graph: the grid

algorithm pathfinding ทุกตัวที่คุณรู้จักอยู่แล้ว — BFS, Dijkstra — ทำงานบน graph: กลุ่มของ node ที่เชื่อมกันด้วย edge เพื่อจะใช้มันตรงนี้ เราต้องแปลง level ให้กลายเป็น graph ก่อน วิธีที่ง่ายและใช้กันบ่อยที่สุดคือ grid: หั่นพื้นที่ที่เดินได้ออกเป็นช่องสี่เหลี่ยมขนาดเท่ากัน ให้แต่ละช่องที่เปิดอยู่เป็น node หนึ่ง แล้วเชื่อมแต่ละช่องเข้ากับช่องข้าง ๆ ด้วย edge

การเลือกระหว่างการเดิน 4 ทิศทางกับ 8 ทิศทางเปลี่ยนรูปทรงของ path ทุกเส้น: path แบบ 4 ทิศทางจะออกมาเป็นขั้นบันไดเสมอ ส่วน path แบบ 8 ทิศทางเดินทแยงมุมได้ ดูเป็นธรรมชาติกว่า แต่ต้องใช้ edge cost ที่ต่างกัน (การเดินทแยงมุมครอบคลุมระยะทางจริงมากกว่าการเดินตรง) และต้องมีกฎเรื่องมุม (ดู tip ด้านล่าง) บทนี้จะสร้างกรณี 4 ทิศทางก่อน เพราะทำให้ตัวเลขไล่ตามด้วยมือได้ง่าย ส่วน Exercise 2 จะให้คุณขยายไปเป็น 8 ทิศทาง

ในโค้ด grid แบบง่ายที่สุดคือ 2D array ของ boolean หนึ่งค่าต่อหนึ่งช่อง บอกว่าช่องนั้นเดินได้หรือไม่

public class GridMap
{
    public readonly bool[,] Walkable;
    public readonly int Width, Height;

    public GridMap(bool[,] walkable)
    {
        Walkable = walkable;
        Width = walkable.GetLength(0);
        Height = walkable.GetLength(1);
    }

    public bool IsWalkable(int x, int y)
    {
        if (x < 0 || y < 0 || x >= Width || y >= Height) return false;
        return Walkable[x, y];
    }
}

มีเรื่องหนึ่งที่ควรพูดให้ชัดตั้งแต่ตอนนี้ ก่อนที่จะสร้างความสับสนทีหลัง: (x, y) ตรงนี้คือ grid coordinate — index ของ column และ row ใน array — ไม่ใช่ตำแหน่ง world-space ของ Unity ใน diagram ของบทนี้ y = 0 คือแถวบนสุด และ y เพิ่มขึ้นเมื่อลงล่าง เพียงเพราะมันอ่านง่ายกว่าบนหน้ากระดาษ การแปลงช่อง grid ให้เป็นตำแหน่ง 3D จริงใน scene (คูณด้วยขนาดช่อง บวกจุดกำเนิดของ grid) เป็นโค้ดชิ้นเล็ก ๆ แยกต่างหากที่คุณเขียนครั้งเดียวตอนวาง tile — มันไม่ใช่ส่วนหนึ่งของตัว search algorithm เอง

มาสร้างห้องจาก Section 1 เป็น GridMap แล้วตรวจสอบบางช่องกัน

bool[,] walkable = new bool[7, 5];
for (int x = 0; x < 7; x++)
    for (int y = 0; y < 5; y++)
        walkable[x, y] = true;

// carve the wall: column x = 3, rows y = 0..3 (row 4 is left open as a gap)
walkable[3, 0] = false;
walkable[3, 1] = false;
walkable[3, 2] = false;
walkable[3, 3] = false;

var map = new GridMap(walkable);

Console.WriteLine("IsWalkable(3, 2) -> " + map.IsWalkable(3, 2));
Console.WriteLine("IsWalkable(3, 4) -> " + map.IsWalkable(3, 4));
Console.WriteLine("IsWalkable(6, 2) -> " + map.IsWalkable(6, 2));
Console.WriteLine("IsWalkable(-1, 2) -> " + map.IsWalkable(-1, 2));

Output:

IsWalkable(3, 2) -> False
IsWalkable(3, 4) -> True
IsWalkable(6, 2) -> True
IsWalkable(-1, 2) -> False

ช่อง (3, 2) อยู่ในกำแพง เลยเดินไม่ได้ ช่อง (3, 4) คือช่องว่างเดียวที่เราปล่อยให้เปิดอยู่ในกำแพง — นี่เป็นที่เดียวที่ path สามารถข้ามจากฝั่งซ้ายของห้องไปฝั่งขวาได้ และมันจะสำคัญมากในอีกไม่กี่ section ข้างหน้า (-1, 2) อยู่นอก array ไปเลย ดังนั้น IsWalkable คืนค่า false แทนที่จะ crash — ต้อง bounds-check ก่อน index เสมอ เหมือนที่บท array เตือนไว้

3. Recap: BFS finds the shortest path when every step costs the same

ทบทวนเร็ว ๆ จากบท data structures: BFS (breadth-first search) สำรวจ graph ทีละ "วง" — สำรวจทุก node ที่ห่างจากจุดเริ่มต้นหนึ่งก้าวก่อน แล้วค่อยสองก้าว ไปเรื่อย ๆ โดยใช้ FIFO queue ธรรมดา เพราะมันสำรวจวงหนึ่งจนครบก่อนจะเริ่มวงถัดไปเสมอ ครั้งแรกที่มันไปถึง node ไหนก็ตาม การันตีได้ว่าเป็นเส้นทางที่ใช้จำนวน edge (hop) น้อยที่สุดที่เป็นไปได้ การันตีนี้จะเป็นจริงก็ต่อเมื่อทุก edge มีค่าเท่ากันหมด — BFS ไม่มีทางรู้เลยว่า edge หนึ่งอาจ "แย่กว่า" อีก edge เพราะ graph ธรรมดาไม่มีแนวคิดเรื่อง edge weight อยู่แล้ว

นี่คือ BFS พร้อมกับ helper เล็ก ๆ สองตัวที่เราจะใช้ซ้ำตลอดบทนี้ เขียนแบบ generic บน grid coordinate

static IEnumerable<(int x, int y)> Neighbors((int x, int y) cell, bool[,] walkable)
{
    (int dx, int dy)[] dirs = { (1, 0), (-1, 0), (0, 1), (0, -1) };
    foreach (var (dx, dy) in dirs)
    {
        int nx = cell.x + dx, ny = cell.y + dy;
        if (nx >= 0 && ny >= 0 && nx < walkable.GetLength(0) && ny < walkable.GetLength(1) && walkable[nx, ny])
            yield return (nx, ny);
    }
}

static List<(int x, int y)> ReconstructPath(Dictionary<(int x, int y), (int x, int y)> cameFrom,
                                             (int x, int y) start, (int x, int y) goal)
{
    var path = new List<(int x, int y)> { goal };
    var current = goal;
    while (current != start)
    {
        current = cameFrom[current];
        path.Add(current);
    }
    path.Reverse();
    return path;
}

static List<(int x, int y)> BFS((int x, int y) start, (int x, int y) goal, bool[,] walkable)
{
    var queue = new Queue<(int x, int y)>();
    var cameFrom = new Dictionary<(int x, int y), (int x, int y)>();
    var visited = new HashSet<(int x, int y)> { start };
    queue.Enqueue(start);

    while (queue.Count > 0)
    {
        var current = queue.Dequeue();
        if (current.Equals(goal)) break;

        foreach (var next in Neighbors(current, walkable))
        {
            if (visited.Contains(next)) continue;
            visited.Add(next);
            cameFrom[next] = current;
            queue.Enqueue(next);
        }
    }
    return ReconstructPath(cameFrom, start, goal);
}

ทีนี้ลองใช้พื้นดินเล็ก ๆ ขนาด 3x2 ที่มีช่องแย่อยู่หนึ่งช่อง — ~ คือโคลน ที่เหลือคือพื้นดินปกติ

bool[,] walkable = { { true, true }, { true, true }, { true, true } }; // 3 columns x 2 rows, all walkable

var path = BFS((0, 0), (2, 0), walkable);
Console.WriteLine(string.Join(" -> ", path));

Output:

(0, 0) -> (1, 0) -> (2, 0)

BFS เดินเส้นตรงผ่านโคลนไปเลย เพราะนั่นคือ path ที่มีจำนวน hop น้อยที่สุด (2 hop) และ hop คือสิ่งเดียวที่ BFS มองเห็น ถ้าเราลองบวก cost จริง ของเส้นทางนั้นด้วยมือ — cost ของการเข้าแต่ละช่องหลังจุดเริ่มต้น — จะได้ 5 (โคลน) + 1 (goal) = 6 BFS ไม่มีทางรู้เรื่องนี้ และไม่มีทางเลือก route ที่ยาวกว่าแต่ถูกกว่าได้เลย นี่แหละคือช่องว่างที่ Dijkstra's algorithm มาเติมเต็มพอดี

4. Recap: Dijkstra's algorithm and the priority queue

Dijkstra's algorithm แก้ปัญหาเวอร์ชันที่ BFS แก้ไม่ได้: หา total cost ที่ถูกที่สุด เมื่อ edge แต่ละอันมี cost ต่างกันได้ การเปลี่ยนแปลงจาก BFS นั้นเล็กแต่สำคัญมาก คือสลับ FIFO queue เป็น priority queue (queue ที่คืนของที่มีค่า priority น้อยที่สุดให้ก่อนเสมอ แทนที่จะคืนของที่รออยู่นานที่สุด — คุณสร้างตัวนี้ด้วย binary heap ไปแล้วในบท data structures) แล้วใช้ total cost ที่ดีที่สุดเท่าที่รู้ของแต่ละ node เป็น priority

นี่คือ priority queue ตัวเดิม เขียนเป็น binary min-heap แบบกระชับ — รูปแบบเดียวกับที่คุณสร้างไปก่อนหน้านี้ พร้อมนำมาใช้ซ้ำตลอดบทนี้

public class PriorityQueue<TItem>
{
    private readonly List<(TItem item, float priority)> heap = new List<(TItem item, float priority)>();

    public int Count => heap.Count;

    public void Enqueue(TItem item, float priority)
    {
        heap.Add((item, priority));
        int i = heap.Count - 1;
        while (i > 0)
        {
            int parent = (i - 1) / 2;
            if (heap[parent].priority <= heap[i].priority) break;
            (heap[parent], heap[i]) = (heap[i], heap[parent]); // swap
            i = parent;
        }
    }

    public TItem Dequeue()
    {
        TItem best = heap[0].item;
        int last = heap.Count - 1;
        heap[0] = heap[last];
        heap.RemoveAt(last);

        int i = 0;
        while (true)
        {
            int left = i * 2 + 1;
            int right = i * 2 + 2;
            int smallest = i;
            if (left < heap.Count && heap[left].priority < heap[smallest].priority) smallest = left;
            if (right < heap.Count && heap[right].priority < heap[smallest].priority) smallest = right;
            if (smallest == i) break;
            (heap[smallest], heap[i]) = (heap[i], heap[smallest]); // swap
            i = smallest;
        }
        return best;
    }
}

static List<(int x, int y)> Dijkstra((int x, int y) start, (int x, int y) goal, bool[,] walkable, int[,] cost)
{
    var open = new PriorityQueue<(int x, int y)>();
    var cameFrom = new Dictionary<(int x, int y), (int x, int y)>();
    var bestCost = new Dictionary<(int x, int y), int> { [start] = 0 };
    open.Enqueue(start, 0);

    while (open.Count > 0)
    {
        var current = open.Dequeue();
        if (current.Equals(goal)) break;

        foreach (var next in Neighbors(current, walkable))
        {
            int newCost = bestCost[current] + cost[next.x, next.y];
            if (!bestCost.ContainsKey(next) || newCost < bestCost[next])
            {
                bestCost[next] = newCost;
                cameFrom[next] = current;
                open.Enqueue(next, newCost);
            }
        }
    }
    return ReconstructPath(cameFrom, start, goal);
}

รันบนพื้นโคลนแปลงเดิม ไล่ trace ด้วยมือทีละขั้น (pop node ที่ถูกที่สุด ดู neighbor ของมัน)

pop (0,0) cost 0   -> push (1,0) cost 5, push (0,1) cost 1
pop (0,1) cost 1   -> push (1,1) cost 2
pop (1,1) cost 2   -> push (2,1) cost 3
pop (2,1) cost 3   -> push (2,0) cost 4
pop (2,0) cost 4   -> this is the goal, stop

path: (0,0) -> (0,1) -> (1,1) -> (2,1) -> (2,0), total cost 4

Dijkstra หา route ที่ใช้ 4 hop แทนที่จะเป็น 2 hop แบบ BFS — แต่ cost จริงของมันคือ 4 ถูกกว่า route ผ่านโคลนที่มี cost 6 สังเกตว่าช่องโคลน (1, 0) ถูก push เข้า open set ไปตั้งแต่แรก (ด้วย cost 5) แล้วก็นั่งอยู่เฉย ๆ ไม่เคยถูก pop เลย เพราะมีอะไรที่ถูกกว่าโผล่มาก่อนตลอด นี่คือแก่นของ Dijkstra: ขยาย option ที่ถูกที่สุดเท่าที่รู้ตอนนี้เสมอ แล้วคุณจะไม่มีทางถูกหลอกให้ finalize node ที่แพงกว่าก่อน node ที่ถูกกว่าได้เลย

Dijkstra หา path ที่ถูกที่สุดได้เสมอ และนั่นคือการันตีที่เราต้องการสำหรับ pathfinding พอดี จุดอ่อนจริง ๆ ของมันคือมันไม่รู้เลยว่าเป้าหมายอยู่ตรงไหน มันขยาย node ที่ยังไม่ได้สำรวจซึ่งถูกที่สุด ในทุกทิศทางเท่า ๆ กัน แม้แต่ทิศตรงข้ามกับเป้าหมายเลยก็ตาม จนกว่าจะบังเอิญไปถึง บน level ใหญ่ ๆ นั่นคืองานที่เสียเปล่าไปเยอะมาก และความสูญเปล่านั้นแหละคือสิ่งที่ A* มาแก้

5. A* = Dijkstra guided by a heuristic

Dijkstra จัดอันดับ node ใน open set ด้วย g ล้วน ๆ — cost จริงที่รู้แล้วจากจุดเริ่มต้นไปยัง node นั้น A* จัดอันดับด้วย g บวก ค่าประมาณว่า node นั้นยังห่างจากเป้าหมายอีกแค่ไหน เรียกว่า heuristic เขียนแทนด้วย h ค่าที่ A* ใช้เรียงลำดับจริง ๆ คือ

node ที่มี g ต่ำแต่ h สูงมาก (ไปถึงง่ายแต่ชี้ไปไกลจากเป้าหมาย) จะถูกดันไปท้าย queue ส่วน node ที่มี g สูงกว่านิดหน่อยแต่ h ต่ำ (มุ่งตรงไปหาเป้าหมาย) จะถูกลองก่อน การค้นหายังคง track cost จริงเหมือน Dijkstra ทุกอย่าง — ความถูกต้องไม่เปลี่ยนเลย — แต่ ลำดับ ที่มันสำรวจ node จะถูกโน้มเข้าหาเป้าหมาย

ไอเดียเดียวนี้ — ใช้ Dijkstra เหมือนเดิมทุกอย่าง เพียงแต่เรียง open set ด้วย g + h แทนที่จะเป็น g อย่างเดียว — คือกลเม็ดทั้งหมดที่อยู่เบื้องหลัง A* ส่วนที่เหลือในบทนี้ก็แค่ "จะเลือก h ที่ดียังไง" หรือ "จะใช้ A* กับอย่างอื่นที่ไม่ใช่ grid ยังไง"

6. Heuristics: Manhattan, Euclidean, and admissibility

heuristic ก็แค่ function ตัวหนึ่ง ให้ node กับเป้าหมายเข้าไป ได้ระยะทางที่เดาออกมากลับมา สองแบบที่ใช้กันบ่อย

public static float ManhattanDistance(Vector2Int a, Vector2Int b)
{
    return Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);
}

public static float EuclideanDistance(Vector2Int a, Vector2Int b)
{
    float dx = a.x - b.x;
    float dy = a.y - b.y;
    return Mathf.Sqrt(dx * dx + dy * dy);
}

Vector2Int a = new Vector2Int(0, 0);
Vector2Int b = new Vector2Int(3, 4);
Debug.Log(ManhattanDistance(a, b));
Debug.Log(EuclideanDistance(a, b));

Output:

7
5

Manhattan distance (|dx| + |dy|) คือระยะทางถ้าคุณเดินตามแกน grid ได้อย่างเดียว — ชื่อนี้มาจากการเดินตาม block ของเมือง ที่คุณตัดทแยงผ่านตึกไม่ได้ Euclidean distance (เส้นตรง ตาม Pythagorean) คือระยะทาง "แบบนกบิน" Euclidean จะไม่มีวันมากกว่า Manhattan สำหรับจุดสองจุดเดียวกัน — เส้นตรงคือทางที่สั้นที่สุดในการเชื่อมสองจุดเสมอ

การเลือก heuristic ไม่ใช่แค่เรื่องสไตล์ มันต้องตรงกับวิธีที่ agent คุณเดินได้ เพราะมีคุณสมบัติชื่อ admissibility: heuristic จะ admissible ก็ต่อเมื่อมันไม่เคย ประเมินสูงเกินจริง (overestimate) cost ที่เหลือจริง สำหรับทุก node เรื่องนี้สำคัญเพราะการันตีความ optimal ของ A* (ที่ว่ามันจะหา path ถูกที่สุดได้ เหมือน Dijkstra เป๊ะ) ขึ้นอยู่กับมัน

บน grid แบบ 4 ทิศทาง (ไม่มีทแยงมุม) Manhattan distance เป็น admissible เสมอ: มันเท่ากับ cost จริงเป๊ะเมื่อไม่มีอะไรขวางทาง และกำแพงมีแต่จะทำให้ path จริงยาวขึ้นเท่านั้น ไม่มีวันสั้นลง — ดังนั้นค่าที่เดาจึงไม่มีวัน overestimate แต่ถ้าคุณเปลี่ยนไปใช้การเดิน 8 ทิศทาง Manhattan distance จะกลาย เป็น inadmissible: การเดินทแยงมุมครอบคลุม dx หนึ่งหน่วยกับ dy หนึ่งหน่วยในก้าวเดียว ดังนั้น path ที่ถูกที่สุดจริง ๆ จะดีกว่าที่ Manhattan ทำนายได้ และค่าที่เดาก็ overestimate ได้ ในกรณีนั้น Euclidean (หรือ distance ที่รู้จักทแยงมุม) คือตัวเลือกที่ถูกต้องกว่า

7. The A* algorithm step by step

A* เก็บข้อมูลไว้สี่ส่วนระหว่างค้นหา

• open set — priority queue ของ node ที่ยังรอถูกตรวจสอบ เรียงตาม f = g + h เริ่มต้นมีแค่ node เริ่มต้นตัวเดียว
• gScore — dictionary ของ cost จริงที่ดีที่สุดเท่าที่รู้จากจุดเริ่มต้นไปยังแต่ละ node ที่เจอมาแล้ว
• cameFrom — dictionary ที่บันทึกไว้ว่า แต่ละ node มาจาก neighbor ตัวไหนด้วย cost ถูกที่สุด นี่คือสิ่งที่ทำให้เราสร้าง path จริง ๆ กลับคืนมาได้ในตอนท้าย
• closed set — node ที่เราขยายจนครบแล้ว จะได้ไม่เสียเวลาประมวลผลซ้ำ

บรรทัดสำคัญที่ต้องสังเกตคือขั้นตอน update neighbor: A* ไม่ได้ push ทุก neighbor เข้าไปมั่ว ๆ มัน update cameFrom กับ gScore ของ neighbor ก็ต่อเมื่อ เจอทางที่ถูกกว่า ไปถึงมันเทียบกับทางที่เจอมาก่อนหน้านี้เท่านั้น node หนึ่งอาจถูก push เข้า open set ได้มากกว่าหนึ่งครั้ง ด้วย priority ต่างกัน ถ้าเจอ route ที่ถูกกว่าทีหลัง — closed set คือตัวที่หยุดไม่ให้เราขยาย node ที่ route ถูกที่สุดของมันถูกยืนยันไปแล้วซ้ำอย่างเสียเปล่า

8. C# implementation: A* on a grid

ถึงเวลาเขียนของจริง แบบที่มันจะเป็นในโปรเจกต์ Unity โดยใช้ Vector2Int แทน tuple

using System.Collections.Generic;
using UnityEngine;

public class AStarPathfinder
{
    private readonly GridMap map;

    private static readonly Vector2Int[] Directions =
    {
        new Vector2Int(0, -1), // up a row  (toward y = 0)
        new Vector2Int(0, 1),  // down a row
        new Vector2Int(-1, 0), // left a column
        new Vector2Int(1, 0),  // right a column
    };

    public AStarPathfinder(GridMap map)
    {
        this.map = map;
    }

    public List<Vector2Int> FindPath(Vector2Int start, Vector2Int goal)
    {
        var open = new PriorityQueue<Vector2Int>();
        var cameFrom = new Dictionary<Vector2Int, Vector2Int>();
        var gScore = new Dictionary<Vector2Int, float> { [start] = 0f };
        var closed = new HashSet<Vector2Int>();

        open.Enqueue(start, Heuristic(start, goal));

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

            if (!closed.Add(current)) continue; // already fully expanded, skip

            foreach (var (neighbor, moveCost) in GetNeighbors(current))
            {
                float tentativeG = gScore[current] + moveCost;
                if (!gScore.ContainsKey(neighbor) || tentativeG < gScore[neighbor])
                {
                    cameFrom[neighbor] = current;
                    gScore[neighbor] = tentativeG;
                    float f = tentativeG + Heuristic(neighbor, goal);
                    open.Enqueue(neighbor, f);
                }
            }
        }
        return null; // open set emptied without reaching the goal: no path exists
    }

    private float Heuristic(Vector2Int a, Vector2Int b)
    {
        return Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y); // Manhattan: matches 4-directional movement
    }

    private IEnumerable<(Vector2Int, float)> GetNeighbors(Vector2Int cell)
    {
        foreach (var d in Directions)
        {
            Vector2Int next = cell + d;
            if (map.IsWalkable(next.x, next.y))
                yield return (next, 1f);
        }
    }

    private List<Vector2Int> ReconstructPath(Dictionary<Vector2Int, Vector2Int> cameFrom, Vector2Int current)
    {
        var path = new List<Vector2Int> { current };
        while (cameFrom.TryGetValue(current, out var prev))
        {
            current = prev;
            path.Add(current);
        }
        path.Reverse();
        return path;
    }
}

รันบนห้องจาก Section 1

bool[,] walkable = new bool[7, 5];
for (int x = 0; x < 7; x++)
    for (int y = 0; y < 5; y++)
        walkable[x, y] = true;

walkable[3, 0] = false;
walkable[3, 1] = false;
walkable[3, 2] = false;
walkable[3, 3] = false;

var map = new GridMap(walkable);
var pathfinder = new AStarPathfinder(map);
List<Vector2Int> path = pathfinder.FindPath(new Vector2Int(0, 2), new Vector2Int(6, 2));

Debug.Log("length: " + (path.Count - 1) + " steps");
Debug.Log(string.Join(" -> ", path));

Output:

length: 10 steps
(0, 2) -> (1, 2) -> (2, 2) -> (2, 3) -> (2, 4) -> (3, 4) -> (4, 4) -> (4, 3) -> (4, 2) -> (5, 2) -> (6, 2)

สิบ step ผ่านช่องว่างเดียวในกำแพงที่ (3, 4) (รายการช่องที่ได้อาจต่างกันนิดหน่อยขึ้นอยู่กับลำดับที่ GetNeighbors เช็คทิศทาง ถ้าบังเอิญมี route ที่สั้นเท่ากันหลายเส้น — แต่ ความยาว ที่ 10 นั้นการันตีว่าเป็นค่าต่ำสุดจริง ๆ และเราจะเช็คด้วยมือใน section ถัดไป)

9. Tracing A*: why it expands fewer nodes than Dijkstra

มาเช็คกันว่า 10 คือค่าต่ำสุดจริงไหม แล้วดูว่า heuristic ของ A* ช่วยอะไรเราได้บ้างจริง ๆ ก่อนอื่น cost จริงในการไปถึง ทุก ช่องที่เปิดในห้องจาก S — นี่คือ g ตัวเลขเดียวกับที่ Dijkstra (หรือ BFS ธรรมดา เพราะทุก edge cost 1 ที่นี่) จะคำนวณได้สำหรับแต่ละช่องถ้ามันสำรวจทั้ง map

cost จริงของเป้าหมายคือ 10 — ตรงกับความยาว path ที่ A* คืนมาพอดี ทีนี้เพิ่ม heuristic เข้าไป: f = g + h โดย h คือ Manhattan distance ไปยัง (6, 2)

นี่คือจุดสำคัญ Dijkstra เรียงลำดับด้วย g ล้วน ๆ ดังนั้นก่อนจะ แน่ใจ ได้ว่าถึงเป้าหมายที่ cost 10 แล้ว มันต้อง settle ทุกช่องที่ g <= 10 ให้ครบก่อน — นั่นคือ 28 จาก 31 ช่องที่เปิดอยู่ แทบทั้งห้อง รวมถึงช่องอย่าง (4, 0) (g = 10) กับ (4, 1) (g = 9) — มุมตันทางมุมบนขวาที่ไม่ได้อยู่บน shortest path เลยสักนิด แต่ Dijkstra ไม่มีทางรู้เรื่องนั้น เลยสำรวจตรงนั้นไปด้วย

A* ไม่แตะมุมตันนั้นเลย ลองดูค่า f ของมัน: (4, 0) มี f = 14 และ (4, 1) มี f = 12 — ทั้งคู่แย่กว่า f = 10 ของเป้าหมาย เพราะ priority queue ของ A* พยายามลองค่า f น้อยที่สุดก่อนเสมอ เป้าหมายจะถูก pop ก่อนที่ช่องทั้งสองนั้นจะมีโอกาสถูก pop เลย heuristic ระบุได้ถูกต้องว่าช่องเหล่านั้น "ไกลจากเป้าหมาย" แม้ว่ามันจะบังเอิญไปถึงง่ายจากจุดเริ่มต้นก็ตาม และ A* ก็ข้ามมันไปเลย

นั่นคือข้อโต้แย้งเรื่อง performance ทั้งหมดของ A* ในตัวอย่างเดียว: การันตีว่าหา path ถูกที่สุดได้เหมือน Dijkstra แต่ heuristic เงียบ ๆ ตัด region ทั้งหมดของการค้นหาที่ไม่มีทางนำไปสู่คำตอบที่ดีกว่าออกไป

10. Path smoothing: string-pulling so agents don't zigzag

path 10 step ที่ A* หาเจอนั้นถูกต้อง แต่พอเคลื่อนไหวจริงมันดูแย่มาก: มันเป็นขั้นบันไดของ grid step ทีละก้าว เพราะการเดิน 4 ทิศทางเดินได้แค่ตรงหรือเลี้ยว 90 องศาเท่านั้น

Path smoothing หรือเรียกอีกชื่อว่า string-pulling แก้ปัญหานี้ทีหลัง: ให้จินตนาการว่าคุณดึงเชือกเส้นหนึ่งให้ตึงระหว่างจุดเริ่มต้นกับเป้าหมาย ร้อยผ่านช่อง grid ที่ path เดินผ่าน — เชือกจะเป็นเส้นตรงเองตรงไหนที่ไม่มีอะไรขวาง และจะหักมุมเฉพาะตรงมุมที่มันต้องอ้อมจริง ๆ เท่านั้น algorithm คือ: เริ่มจาก waypoint แรก มองไปข้างหน้าให้ไกลที่สุดเท่าที่จะเจอ waypoint ทีหลังที่มองเห็นเป็นเส้นตรงไม่มีอะไรบัง กระโดดตรงไปที่จุดไกลที่สุดที่มองเห็นได้ ทำซ้ำจากจุดนั้น

public static List<Vector2Int> SmoothPath(GridMap map, List<Vector2Int> path)
{
    if (path.Count < 3) return path;

    var smoothed = new List<Vector2Int> { path[0] };
    int current = 0;

    while (current < path.Count - 1)
    {
        int farthest = current + 1;
        for (int test = current + 2; test < path.Count; test++)
        {
            if (HasLineOfSight(map, path[current], path[test]))
                farthest = test;
        }
        smoothed.Add(path[farthest]);
        current = farthest;
    }
    return smoothed;
}

private static bool HasLineOfSight(GridMap map, Vector2Int a, Vector2Int b)
{
    int steps = Mathf.Max(Mathf.Abs(b.x - a.x), Mathf.Abs(b.y - a.y)) * 4;
    for (int i = 0; i <= steps; i++)
    {
        float t = (float)i / steps;
        int x = Mathf.RoundToInt(Mathf.Lerp(a.x, b.x, t));
        int y = Mathf.RoundToInt(Mathf.Lerp(a.y, b.y, t));
        if (!map.IsWalkable(x, y)) return false;
    }
    return true;
}

HasLineOfSight สุ่มตัวอย่างจุดตามเส้นตรงจาก a ไป b แล้วเช็คว่าทุกช่องที่สุ่มมาเดินได้ — เป็นตัวแทนง่าย ๆ ของ raycast จริง ๆ ลอง trace บน path 10 step ของเรา: จาก S = (0, 2) เส้นตรงไป (4, 4) ตัดผ่านช่องกำแพง (3, 3) โดยตรง (มองเห็นได้ใน diagram ด้านบน — เส้นนั้นจะตัดมุมกำแพงพอดี) ดังนั้น line of sight ตรงนั้นถูกบล็อก แต่เส้นไป (3, 4) — ช่องว่างที่เปิดอยู่ — ยังคงโล่งตลอดทาง เพราะมันแตะ column x = 3 แค่ตอนสุดท้ายเท่านั้น ตรงพอดีกับช่องว่างที่เปิดอยู่ ดังนั้นจุดที่มองเห็นได้ไกลสุดจาก S จึงกลายเป็น (3, 4)

จาก (3, 4) ทุก waypoint ที่เหลือก็อยู่ฝั่งตรงข้ามของกำแพงไปแล้ว และไม่มีอะไรขวางห้องอีก ดังนั้นเส้นตรงตลอดทางไป G = (6, 2) จึงโล่งสนิท

Output:

Before smoothing: 11 waypoints
After smoothing:  3 waypoints -> (0, 2), (3, 4), (6, 2)

สิบเอ็ด waypoint ยุบเหลือสาม และ agent ที่เดินตาม path ใหม่นี้จะเดินแค่สองเส้นตรงแทนที่จะเป็นขั้นบันไดสิบก้าวเล็ก ๆ นี่คือเหตุผลว่าทำไมแทบไม่มีเกมไหนที่วางขายจริงเคลื่อนตัวละครตาม output ดิบของ grid search ตรง ๆ เลย smoothing (หรือ search ที่ไม่สร้าง path แบบติด grid ตั้งแต่แรก ซึ่งก็คือสิ่งที่ navmesh ให้เรา จะพูดถึงต่อไป) คือสิ่งที่ทำให้การเคลื่อนไหวดูมีจุดหมาย ไม่ใช่แข็งทื่อเหมือนหุ่นยนต์

11. Navmesh: walkable polygons for big 3D worlds

grid ใช้ได้ดีกับเกมอย่าง roguelike หรือเกมวางแผนแบบ tile-based แต่มันมีปัญหากับโลก 3D ที่เปิดกว้างและต่อเนื่อง มีสามเหตุผล

• เรื่องหน่วยความจำและขนาดการค้นหา grid ที่ละเอียดพอจะดูเนียนบน map open-world ขนาดใหญ่อาจหมายถึงหลายล้านช่อง ส่วนใหญ่นั่งอยู่กลางพื้นที่โล่งกว้าง ๆ ไม่มีอะไรเลยที่ไม่จำเป็นต้องถูกแบ่งย่อยขนาดนั้นเลย
• เรื่องรูปทรง geometry ของ level จริงมีทางลาด กำแพงโค้ง และห้องที่เอียงมุมแปลก ๆ grid บังคับให้ทุกอย่างเป็นช่องสี่เหลี่ยมที่จัดตามแกนคงที่ ไม่ว่ากำแพงจริงจะเอียงมุมไหนก็ตาม
• ความละเอียดที่ไม่จำเป็นตรงที่หนึ่ง และไม่พอตรงอีกที่หนึ่ง ขนาดช่อง grid เดียวจะหยาบเกินไปสำหรับประตูแคบ ๆ หรือละเอียดเกินความจำเป็นสำหรับพื้นที่โล่ง — grid หยาบตรงหนึ่งแล้วละเอียดอีกตรงหนึ่งพร้อมกันไม่ได้ง่าย ๆ

ทางเลือกที่เกม 3D สมัยใหม่แทบทุกเกมใช้คือ navmesh (navigation mesh): แทนที่จะคลุม level ด้วยช่องสี่เหลี่ยมสม่ำเสมอ ให้คลุมเฉพาะพื้นผิวที่เดินได้ — พื้น ทางลาด สะพาน — ด้วย mesh ของ polygon ที่เชื่อมกัน ปกติเป็นรูปนูน (convex) ห้องใหญ่โล่ง ๆ ห้องเดียวอาจเป็นแค่ polygon ใหญ่สองสามอัน ประตูแคบ ๆ ก็ได้ polygon เล็ก ๆ ของตัวเองอยู่ระหว่างกลาง mesh ปรับตามรูปทรงของ level แทนที่จะบังคับ level ให้เข้ากับ grid ตายตัว

ประเด็นสำคัญคือ: A* ไม่สนใจเลยว่า node ของมันเป็นช่อง grid หรือ polygon ของ navmesh มันต้องการแค่สามอย่างจาก graph เท่านั้น — วิธี list neighbor ของ node, cost ของแต่ละ edge, และ heuristic ไปยังเป้าหมาย บน navmesh node คือ polygon (หรือจุดศูนย์กลางของมัน) และ edge มีอยู่ระหว่าง polygon สองอันที่มีขอบร่วมกัน (ปกติเรียกว่า portal) โดย cost ประมาณระยะห่างระหว่างจุดศูนย์กลางของทั้งสอง สลับ graph นั้นเข้าไปแทน แล้วทุกบรรทัดของ A* algorithm จาก Section 7 ก็รันได้เหมือนเดิมทุกอย่างโดยไม่ต้องแก้อะไรเลย

เมื่อ A* หาลำดับ polygon ได้แล้ว การเดินตรงผ่านจุดศูนย์กลางของแต่ละ polygon ก็ยังจะซิกแซกอยู่ดี เวอร์ชันที่แม่นยำทางเรขาคณิตของไอเดีย string-pulling จาก Section 10 — เรียกว่า funnel algorithm — ดึง path ที่ตึงและแม่นยำผ่านขอบ portal ที่ใช้ร่วมกันของลำดับ polygon นั้น โดยไม่ต้องประมาณด้วยการสุ่มตัวอย่างแบบที่ grid version ของเราต้องใช้ เพราะรู้ขอบที่แน่นอนของแต่ละ polygon อยู่แล้ว

มีสองชื่อที่โผล่มาบ่อยมากในวงการนี้: Recast เป็น library แบบ open-source ที่รับ raw 3D collision geometry ของ level มา voxelize (แบ่งเป็น 3D grid ชั่วคราว คล้ายกับ grid ใน Section 2 แค่เป็นขั้นตอนกลาง) แล้วสร้าง navmesh ที่เดินได้ให้อัตโนมัติ — หาว่าพื้นผิวไหนราบและกว้างพอจะเดินได้ ควรอยู่ห่างจากขอบเหวและทางลาดชันแค่ไหน และอื่น ๆ Detour คือ runtime library คู่กันที่ตอบคำถาม pathfinding (A* บวก funnel algorithm) กับ navmesh ที่ Recast สร้างไว้แล้ว ระบบ navigation ของ Unity เองก็สร้างขึ้นบนไอเดียเดียวกันนี้

ใน Unity คุณแทบไม่ต้องแตะ Recast หรือ Detour โดยตรงเลย แทนที่จะทำแบบนั้น

• คุณ mark level geometry (พื้น ทางลาด กำแพง) เป็น Navigation Static แล้ว bake navmesh สำหรับ scene (Window > AI > Navigation หรือ component NavMeshSurface) — นี่คือ Unity รัน Recast-like generation ให้คุณ แบบ offline ครั้งเดียว
• คุณติด component NavMeshAgent เข้ากับตัวละครไหนก็ตามที่ควรเคลื่อนที่ตาม navmesh

using UnityEngine;
using UnityEngine.AI;

public class EnemyChaser : MonoBehaviour
{
    public Transform target;
    private NavMeshAgent agent;

    void Awake()
    {
        agent = GetComponent<NavMeshAgent>();
    }

    void Update()
    {
        agent.SetDestination(target.position);
    }
}

call เดียวนั้น SetDestination ซ่อนบทนี้ทั้งบทอยู่ข้างหลังมัน: Unity รัน A* บน navmesh ที่ bake ไว้ รัน funnel algorithm เพื่อให้ได้ corridor ที่ตึงและเนียน แล้วขยับ agent ไปตามนั้นทีละเฟรม พร้อมกับทำ local steering นิดหน่อยด้วย (obstacle avoidance อีกแบบจาก Section 1) เพื่อให้ agent ที่ติด NavMeshAgent หลบกันเบา ๆ แทนที่จะเดินทะลุกันไปเลย ทุกอย่างก่อนหน้านี้ในบทนี้คือสิ่งที่บรรทัดเดียวนั้นทำอยู่ข้างใต้จริง ๆ

12. Hierarchical pathfinding for huge maps

A* บน navmesh เร็วก็จริง แต่ "เร็ว" ก็ยังมีขีดจำกัด: map open-world ขนาดใหญ่อาจมี polygon เป็นหมื่น ๆ อัน และเกมวางแผนเรียลไทม์อาจต้องการ path ใหม่สำหรับ unit หลายร้อยตัวทุกเฟรม การรัน A* เต็มรูปแบบทั่วทั้ง map สำหรับทุก request แบบนั้นมันแพงมาก

ทางแก้สะท้อนสิ่งที่คุณอาจเคยเห็นที่อื่นมาแล้ว: แก้ปัญหาแบบหยาบ ๆ ก่อน แล้วค่อยลงรายละเอียดเฉพาะตรงที่จำเป็น Hierarchical pathfinding จัดกลุ่ม map เป็น cluster (กลุ่มก้อนของ node ที่อยู่ใกล้กัน) แล้วสร้าง abstract graph เล็ก ๆ แยกต่างหาก ที่แต่ละ cluster เป็นแค่ node เดียว เชื่อมกับ cluster ข้างเคียงที่มีจุดข้ามที่ใช้ได้ร่วมกัน

นี่คือไอเดียเดียวกับการเลือก route บนแผนที่ทางหลวงก่อนจะมากังวลว่าจะเลี้ยวถนนเส้นไหนตรงจุดไหน — คุณตัดสินใจลำดับเมืองก่อน บนแผนที่ที่แทบไม่มีรายละเอียดอะไรเลย แล้วค่อยโหลดแผนที่ถนนละเอียดเฉพาะเมืองที่คุณจะผ่านจริง ๆ abstract graph เล็กมากเทียบกับ map เต็ม ดังนั้น step 1 แทบไม่เสีย cost อะไรเลย และ step 2 ก็รัน detailed search แค่ในไม่กี่ cluster เล็ก ๆ แทนที่จะเป็นทั้ง level

เพราะ level geometry ปกติเป็นแบบ static การเชื่อมต่อระหว่าง cluster (ว่า cluster คู่ไหนแตะกัน และแตะตรงไหน) สามารถคำนวณล่วงหน้าได้ครั้งเดียว แบบ offline เหมือนกับการ bake navmesh มีแค่ path request จริงของแต่ละ agent เท่านั้นที่ต้องเกิดตอน runtime และตอนนี้มันถูกพอที่จะรันสำหรับ unit หลายร้อยตัวโดยไม่ทำให้เฟรมตกแล้ว นี่คือวิธีมาตรฐานที่อยู่เบื้องหลัง pathfinding ในเกม RTS ขนาดใหญ่และฝูงชนใน open-world — มันไม่ใช่ algorithm ใหม่เลย แต่เป็นการรัน A* ที่คุณรู้จักอยู่แล้วในสอง zoom level ที่ต่างกัน

13. Greedy best-first search: fast, but it can walk you the long way

ทุกอย่างมาถึงตรงนี้เป็น C# ที่คุณเอาไปใส่ในโปรเจกต์ Unity ได้ตรง ๆ อีกหลาย section ต่อไปจะเจาะลึกเข้าไปในตัว algorithm เอง และสำหรับเรื่องนั้นมันช่วยได้มากถ้ามีโปรแกรมที่ compile แล้วรันได้ในไม่กี่วินาทีด้วย C++ compiler เปล่า ๆ — ไม่ต้องมี engine ไม่ต้องมี scene ดังนั้น demo ข้างล่างจึงเป็น C++ แบบ self-contained (clang++ -std=c++17 file.cpp && ./a.out) logic เหมือนกับ C# ที่คุณเห็นมาแล้วเป๊ะ ต่างกันแค่ syntax ผิวเผินเท่านั้น

Section 4 เรียง open set ด้วย g (Dijkstra); Section 5 เรียงด้วย g + h (A*) มีตัวเลือกที่สามที่ชัดเจนนั่งอยู่ตรงกลางระหว่างสองอันนั้นพอดี: เรียงด้วย h อย่างเดียว algorithm นั้นเรียกว่า greedy best-first search และมันคุ้มที่จะสร้างสักครั้ง เพราะการได้เห็นว่ามันพังยังไงเป๊ะ ๆ คือวิธีที่ชัดที่สุดในการเข้าใจว่าเทอม g ใน A* กำลังปกป้องคุณจากอะไรจริง ๆ

Greedy best-first จะขยาย node ใน open set ตัวที่ ดูเหมือน ใกล้เป้าหมายที่สุดเสมอ โดยไม่สนใจเลยว่ากว่าจะมาถึงตรงนั้นเสีย cost ไปเท่าไหร่ นั่นทำให้มันเร็ว — มันพุ่งตรงไปหาเป้าหมาย — แต่มันไม่มีทางรู้เลยเมื่อ "พุ่งตรงไปหาเป้าหมาย" พามันเข้าทางอ้อมที่ยาว นี่คือทั้งสามตัวบน level เล็ก ๆ อันเดียว นับทั้งความยาว path และจำนวนช่องที่แต่ละตัวขยาย

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
using namespace std;

// A small level. '#' is a wall, '.' is open, S start, G goal.
vector<string> level = {
    "S.......",
    "####....",
    "........",
    "...##..#",
    ".#.##.#.",
    "..#....G",
};

int W, H;
bool Walkable(int x, int y) {
    if (x < 0 || y < 0 || x >= W || y >= H) return false;
    return level[y][x] != '#';
}
int Manhattan(int ax, int ay, int bx, int by) {
    return abs(ax - bx) + abs(ay - by);
}

enum Mode { DIJKSTRA, GREEDY, ASTAR };

// Returns the path length in steps; writes the number of expanded cells to *expanded.
int Search(Mode mode, int sx, int sy, int gx, int gy, int *expanded) {
    auto id = [&](int x, int y) { return y * W + x; };
    // priority queue of (priority, insertionOrder, cellId), smallest priority first
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> open;
    unordered_map<int,int> gScore, cameFrom;
    unordered_set<int> closed;
    int order = 0;
    *expanded = 0;

    gScore[id(sx,sy)] = 0;
    int startPriority = (mode == DIJKSTRA) ? 0 : Manhattan(sx, sy, gx, gy);
    open.push({startPriority, order++, id(sx,sy)});

    int dx[4] = {1,-1,0,0}, dy[4] = {0,0,1,-1};
    while (!open.empty()) {
        auto [pri, ord, k] = open.top(); open.pop();
        int cx = k % W, cy = k / W;
        if (cx == gx && cy == gy) {           // reached the goal
            int len = 0, c = k;
            while (c != id(sx,sy)) { c = cameFrom[c]; len++; }
            return len;
        }
        if (closed.count(k)) continue;
        closed.insert(k);
        (*expanded)++;
        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i], ny = cy + dy[i];
            if (!Walkable(nx, ny)) continue;
            int nk = id(nx, ny), ng = gScore[k] + 1;
            // GREEDY commits to the first route it discovers to each cell;
            // DIJKSTRA / ASTAR keep the cheapest g and may relax it later.
            if (mode == GREEDY) {
                if (gScore.count(nk)) continue;      // already discovered: keep first cameFrom
                gScore[nk] = ng; cameFrom[nk] = k;
                open.push({Manhattan(nx,ny,gx,gy), order++, nk});
            } else {
                if (!gScore.count(nk) || ng < gScore[nk]) {
                    gScore[nk] = ng; cameFrom[nk] = k;
                    int h = Manhattan(nx, ny, gx, gy);
                    int f = (mode == DIJKSTRA) ? ng : ng + h;
                    open.push({f, order++, nk});
                }
            }
        }
    }
    return -1;
}

int main() {
    H = level.size(); W = level[0].size();
    int sx=0, sy=0, gx=0, gy=0;
    for (int y = 0; y < H; y++)
        for (int x = 0; x < W; x++) {
            if (level[y][x] == 'S') { sx = x; sy = y; }
            if (level[y][x] == 'G') { gx = x; gy = y; }
        }
    const char* names[3] = {"Dijkstra (g only) ", "Greedy   (h only) ", "A*       (g + h)  "};
    Mode modes[3] = {DIJKSTRA, GREEDY, ASTAR};
    for (int m = 0; m < 3; m++) {
        int expanded;
        int len = Search(modes[m], sx, sy, gx, gy, &expanded);
        printf("%s  path = %2d steps   cells expanded = %d\n", names[m], len, expanded);
    }
    return 0;
}

Output:

Dijkstra (g only)   path = 12 steps   cells expanded = 30
Greedy   (h only)   path = 16 steps   cells expanded = 16
A*       (g + h)    path = 12 steps   cells expanded = 21

อ่านสามบรรทัดนั้นให้ดี ๆ เพราะตัวเลขแต่ละคู่เล่าเรื่องคนละครึ่ง Dijkstra กับ A* คืน path สั้นที่สุดจริงเหมือนกัน 12 step — แต่ A* ไปถึงตรงนั้นโดยขยายแค่ 21 ช่องเทียบกับ 30 ของ Dijkstra เพราะ heuristic ดึงมันเข้าหาเป้าหมายแทนที่จะกระจายออกเท่า ๆ กันทุกทิศ ส่วน Greedy ขยายช่อง น้อยที่สุด ในบรรดาทั้งหมด แค่ 16 ช่อง — มันเป็นการ search ที่ถูกที่สุดจริง ๆ — แต่ path ที่มันคืนคือ 16 step ยาวกว่าที่จำเป็นหนึ่งในสาม มันพุ่งเข้าหาเป้าหมาย ยึดติดกับ corridor ที่กลายเป็นทางอ้อม และเพราะมันไม่เคยดู g เลย มันจึงไม่มีทางรู้ว่ากำลังทำให้ทริปยาวขึ้น

นั่นคืองานทั้งหมดของเทอม g ใน f = g + h: มันทำให้ search ซื่อสัตย์เรื่องระยะที่เดินไปแล้ว ดังนั้น A* จึงทิ้ง route ที่ดูมีอนาคตแต่กำลังกลายเป็นแพงได้ ตัด g ออกแล้วคุณจะได้ความเร็วโดยแลกกับความถูกต้อง — นั่นคือ greedy best-first ในประโยคเดียว

14. Consistency: the property beyond admissibility

Section 6 บอกว่า heuristic ที่ admissible (ตัวที่ไม่เคย overestimate) คือสิ่งที่ A* ต้องการเพื่อคืน path ถูกที่สุด นั่นจริงสำหรับ A* เวอร์ชัน ตำรา — ตัวที่ยอมกลับไปพิจารณา node ที่ตัดสินไปแล้วใหม่ แต่ลองดู implementation จริงใน Section 8 อีกที: พอ node ออกจาก open set มันจะเข้าไปใน closed และบรรทัดถัดไปเลย if (!closed.Add(current)) continue; คือตัวที่ทำให้มันไม่ถูกขยายอีก การ optimize นั้นคือสิ่งที่ทำให้ A* เร็ว และมันปลอดภัยก็ต่อเมื่อมีคุณสมบัติที่ แข็งกว่า admissibility เรียกว่า consistency (หรือ monotonicity)

Consistency คือ triangle inequality ที่เอามาใช้กับ heuristic ของคุณ: การก้าวจาก n ไป neighbor n' อาจลดค่าประมาณระยะที่เหลือได้ อย่างมากที่สุด เท่ากับ cost ของก้าวนั้น ถ้าก้าวเดียวทำให้ h ตกลงได้มากกว่า cost ของก้าวจริง ๆ แสดงว่า heuristic นั้น inconsistent ทุก heuristic ที่ consistent จะ admissible โดยอัตโนมัติ แต่ไม่ใช่ในทางกลับกัน — และช่องว่างตรงนั้นแหละคือจุดที่การ optimize ด้วย closed set กัดเอาได้

นี่คือเหตุผลว่าทำไมมันสำคัญ ในข้อเท็จจริงเดียว: ด้วย heuristic ที่ consistent ครั้งแรกที่ A* pop node ออกมา ค่า g ของมันคือค่าที่ถูกที่สุดที่เป็นไปได้อยู่แล้ว ดังนั้นการปิดตายมันจึงปลอดภัย และทุก node ถูกขยายมากที่สุดแค่ครั้งเดียว ด้วย heuristic ที่แค่ admissible แต่ inconsistent การันตีนั้นหายไป — A* อาจ pop node ปิดมัน แล้ว ค่อย ค้นพบทางที่ถูกกว่าไปถึงมันทีหลัง ซึ่ง code ใน Section 8 จะปฏิเสธที่จะส่งต่อ graph สี่ node นี้ทำให้มันเกิดขึ้น

#include <cstdio>
#include <vector>
#include <queue>
#include <tuple>
#include <climits>
#include <unordered_set>
using namespace std;

// Four nodes: S=0, B=1, C=2, G=3.  Directed edges (from, to, cost).
const int S=0, B=1, C=2, G=3, N=4;
const char* name[N] = {"S","B","C","G"};
vector<tuple<int,int,int>> edges = { {S,B,3}, {S,C,1}, {C,B,1}, {B,G,2} };

// An admissible but INCONSISTENT heuristic (guessed distance to goal G).
int h[N] = { 3, 0, 3, 0 };   // h[S]=3, h[B]=0, h[C]=3, h[G]=0

vector<vector<pair<int,int>>> adj;

int dijkstra() {                      // true optimal S -> G
    vector<int> d(N, INT_MAX); d[S]=0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq; pq.push({0,S});
    while(!pq.empty()){ auto[dd,u]=pq.top(); pq.pop(); if(dd>d[u]) continue;
        for(auto&e:adj[u]) if(d[u]+e.second<d[e.first]){ d[e.first]=d[u]+e.second; pq.push({d[e.first],e.first}); } }
    return d[G];
}

// Section 8's logic: once a node is popped it is closed and never reopened.
int astarClosedSet() {
    vector<int> g(N, INT_MAX); g[S]=0;
    unordered_set<int> closed;
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> open;
    int ord=0; open.push({g[S]+h[S], ord++, S});
    while(!open.empty()){
        auto[f,o,u]=open.top(); open.pop();
        if(u==G) return g[G];
        if(closed.count(u)) continue;
        closed.insert(u);
        for(auto&e:adj[u]){ int v=e.first, ng=g[u]+e.second;
            if(ng<g[v]){ g[v]=ng; open.push({ng+h[v], ord++, v}); } }
    }
    return -1;
}

// The fix: allow a closed node to be reopened when a cheaper g is found.
int astarReopening() {
    vector<int> g(N, INT_MAX); g[S]=0;
    unordered_set<int> closed;
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> open;
    int ord=0; open.push({g[S]+h[S], ord++, S});
    while(!open.empty()){
        auto[f,o,u]=open.top(); open.pop();
        if(u==G) return g[G];
        closed.erase(u);                 // may be re-expanded if a better route arrives
        for(auto&e:adj[u]){ int v=e.first, ng=g[u]+e.second;
            if(ng<g[v]){ g[v]=ng; open.push({ng+h[v], ord++, v}); } }
    }
    return -1;
}

int main(){
    adj.assign(N,{});
    for(auto&e:edges) adj[get<0>(e)].push_back({get<1>(e), get<2>(e)});

    printf("consistency check  h(u) <= cost(u,v) + h(v)  for every edge:\n");
    for(auto&e:edges){ int u=get<0>(e), v=get<1>(e), c=get<2>(e);
        bool ok = h[u] <= c + h[v];
        printf("  %s->%s cost %d :  h(%s)=%d  vs  cost+h(%s)=%d   %s\n",
               name[u],name[v],c, name[u],h[u], name[v], c+h[v], ok?"ok":"VIOLATED");
    }
    printf("\noptimal cost (Dijkstra)          = %d\n", dijkstra());
    printf("A* with closed set, no reopening = %d   <- Section 8's code\n", astarClosedSet());
    printf("A* that reopens closed nodes     = %d\n", astarReopening());
    return 0;
}

Output:

consistency check  h(u) <= cost(u,v) + h(v)  for every edge:
  S->B cost 3 :  h(S)=3  vs  cost+h(B)=3   ok
  S->C cost 1 :  h(S)=3  vs  cost+h(C)=4   ok
  C->B cost 1 :  h(C)=3  vs  cost+h(B)=1   VIOLATED
  B->G cost 2 :  h(B)=0  vs  cost+h(G)=2   ok

optimal cost (Dijkstra)          = 4
A* with closed set, no reopening = 5   <- Section 8's code
A* that reopens closed nodes     = 4

route ที่ถูกที่สุดจริงคือ S -> C -> B -> G cost 1 + 1 + 2 = 4 แต่ A* แบบเร็วใน Section 8 คืน 5 ลองไล่ trace ดู: จาก S มันค้นพบ B ที่ g = 3 (edge S->B) และ C ที่ g = 1 (edge S->C) เพราะ h(B) = 0 priority ของ node B จึงเป็น f = 3 ต่ำกว่า f = 1 + 3 = 4 ของ C — ดังนั้น B ถูก pop และปิดก่อน และการขยายมันไปถึงเป้าหมายที่ g = 5 จากนั้น ทีหลัง C ถึงถูก pop และ C เจอทางที่ถูกกว่าไป B (g = 2 ผ่าน C->B) แต่ B ถูกปิดไปแล้ว การปรับปรุงนั้นจึงถูกเขียนลงใน gScore แล้วก็ถูกทิ้ง — มันไม่เคยส่งต่อไปถึงเป้าหมาย

ต้นเหตุตัวเดียวคือ edge C->B ตัวที่ถูกทำเครื่องหมาย VIOLATED: h(C) = 3 แต่การก้าวไป B cost แค่ 1 และเหลือค่าประมาณ h(B) = 0 — ค่าเดาตกลง 3 สำหรับก้าวที่มีค่าแค่ 1 นั่นคือ inconsistency และ edge ที่ violate เพียงตัวเดียวก็เพียงพอที่จะทำให้ A* เวอร์ชันเร็วคืน path ที่ไม่ใช่อันถูกที่สุด

มีสองวิธีที่จะปลอดภัย และวิธีแรกคือวิธีที่ทำให้สบายใจ (1) ใช้ heuristic ที่ consistent heuristic ทางเรขาคณิตมาตรฐานจาก Section 6 — Manhattan, Euclidean, Chebyshev, octile — ล้วน consistent ทั้งหมด ตราบใดที่ edge cost ของคุณคือระยะทางจริงระหว่างช่อง เพราะแต่ละก้าวเปลี่ยน heuristic ได้อย่างมากที่สุดเท่ากับ cost ของก้าวนั้น นั่นคือเหตุผลว่าทำไม code grid ใน Section 8 จึงถูกต้องในทางปฏิบัติ และทำไมคุณแทบไม่เจอ bug นี้บน grid ธรรมดา (2) เมื่อคุณจำเป็นต้องใช้ heuristic ที่ inconsistent จริง ๆ — ค่าประมาณที่ปรับด้วยมือ, learned heuristic, หรือค่าสูงสุดของหลาย heuristic ซึ่งทั้งหมดโผล่มาใน pathfinding ขั้นสูง — ให้อนุญาต node ที่ปิดแล้วถูกเปิดใหม่ได้ อย่างที่ astarReopening ทำด้วย closed.erase(u) มันคืนคำตอบที่ถูกต้อง (กลับไปเป็น 4) โดยแลกกับการขยาย node บางตัวมากกว่าหนึ่งครั้งเป็นครั้งคราว

15. Tie-breaking: taming the flood of equal f-costs

บน grid ที่สม่ำเสมอ จำนวนช่องมหาศาลจะลงเอยด้วย f เท่ากัน บนพื้นที่โล่ง ทุก route สั้นที่สุดจาก S ไป G cost เท่ากันหมด ดังนั้นทุกช่องบนทุก route เหล่านั้นจึงถือค่า f ที่เท่ากันหนึ่งค่า เมื่อ A* ไม่มีกฎในการตัดสินเสมอเหล่านั้น มันจะขยายพวกมันตามลำดับอะไรก็ตามที่บังเอิญตกลงไปใน heap — ซึ่งหมายความว่ามันแผ่ออกทั่ว ทั้ง พื้นที่ที่เสมอกันก่อนที่จะยอมเลือกเป้าหมาย ดูสิว่ามันเสีย cost แค่ไหนบน grid 15x15 ที่โล่งสนิท จากมุมหนึ่งไปอีกมุม สิ่งเดียวที่เปลี่ยนจาก harness ใน Section 13 คือ priority กลายเป็น triple (f, tieKey, insertionOrder) และ tieKey ถูกเติมด้วยสามวิธีต่างกัน

// The heap compares tuples left to right, so tieKey is consulted ONLY when two
// cells have the same f. It never changes the path length, just the search order.
int f = ng + Manhattan(nx, ny, gx, gy);
int tieKey = 0;                              // NONE: ties fall back to insertion order

if (mode == LOWER_H)                         // prefer the cell with the smaller h (closer to goal)
    tieKey = Manhattan(nx, ny, gx, gy);

else if (mode == CROSS) {                    // prefer cells near the straight S->G line
    int dx1 = nx - gx, dy1 = ny - gy;
    int dx2 = sx - gx, dy2 = sy - gy;
    tieKey = abs(dx1 * dy2 - dx2 * dy1);     // |cross product|: distance-ish from that line
}

open.push({f, tieKey, order++, id(nx, ny)});

Output:

no tie-break (FIFO)      path = 28 steps   cells expanded = 224
tie-break: prefer low h   path = 28 steps   cells expanded = 28
tie-break: cross product   path = 28 steps   cells expanded = 41

ทั้งสามหา path สั้นที่สุด 28 step ได้ — tie-breaking ไม่เคยเปลี่ยนความยาว เปลี่ยนแค่ว่าคุณได้ route ไหนในบรรดาที่ดีเท่ากัน และคุณทำงานหนักแค่ไหนกว่าจะได้มัน แต่เมื่อไม่มีกฎตัดสินเสมอ A* ขยาย 224 ช่องจาก 225 ช่องของ grid: แทบทั้งกระดาน เพราะทุกช่องเสมอกันและได้คิวของมัน การเลือก h ที่เล็กกว่าเมื่อเสมอกันยุบมันลงเหลือ 28 — มันเดินแทบตรงไปหาเป้าหมาย เพราะบนพื้นที่โล่ง neighbor ที่ h ต่ำกว่าคือตัวที่มุ่งตรงไปหามันเสมอ ส่วนกฎ cross product ที่โน้ม search เข้าหาเส้นตรงจากจุดเริ่มต้นถึงเป้าหมาย ขยาย 41 และให้ path ที่อยู่ตรงกลางมากที่สุดและดูเป็นธรรมชาติที่สุดในสามแบบ

ทั้งสองกฎถูกมาก: prefer-low-h คือตัวเลขเพิ่มมาตัวเดียวที่คำนวณอยู่แล้ว และ cross product คือ cross product 2D ตัวเดียวที่วัดคร่าว ๆ ว่าช่องหนึ่งอยู่ห่างจากเส้นตรง S ถึง G แค่ไหน ดังนั้นการเสมอจึงตัดสินไปทางช่องที่เกาะเส้นนั้น เก็บไว้เป็น key รอง อย่างเคร่งครัด — ให้ปรึกษาเฉพาะตอน f เท่ากันเป๊ะ — ทั้งสองจึงไม่มีทางเปลี่ยน cost ของ path A* จึงยังคง optimal และแค่ทำงานน้อยลงมาก

16. Weighted A*: trading a little optimality for a lot of speed

บางครั้งแม้แต่ A* ที่ปรับมาดีแล้วก็ยังสำรวจมากกว่าที่คุณจะรับไหว — agent หลายร้อยตัว, map ใหญ่มาก, frame budget แน่น Weighted A* ซื้อความเร็วด้วยปุ่มเดียว แทนที่จะเป็น f = g + h มันเรียงด้วย f = g + w*h โดยมี weight w >= 1 การพอง h ทำให้ search โลภมากขึ้น: มันเอนเข้าหาเป้าหมายแรงขึ้นและขยาย node น้อยลง ราคาที่จ่ายคือ optimality — แต่เป็นราคาที่ มีขอบเขต ซึ่งคือสิ่งที่ทำให้กลเม็ดนี้ใช้ได้จริง นี่คือมันบน map ที่มีสิ่งกีดขวาง ที่สี่ค่า weight

// The only change from ordinary A* is the w in the priority. Everything else -
// the level, Walkable, Manhattan, the closed set - is exactly the Section 13 harness.
int WeightedAStar(double w, int sx,int sy,int gx,int gy, int *expanded) {
    auto id = [&](int x,int y){ return y*W+x; };
    priority_queue<tuple<double,int,int>, vector<tuple<double,int,int>>, greater<>> open;
    unordered_map<int,int> g, cameFrom;
    unordered_set<int> closed;
    int ord=0; *expanded=0;
    g[id(sx,sy)] = 0;
    open.push({ w*Manhattan(sx,sy,gx,gy), ord++, id(sx,sy) });
    int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};
    while(!open.empty()){
        auto [f,o,k] = open.top(); open.pop();
        int cx=k%W, cy=k/W;
        if(cx==gx && cy==gy){ int len=0,c=k; while(c!=id(sx,sy)){c=cameFrom[c];len++;} return len; }
        if(closed.count(k)) continue;
        closed.insert(k); (*expanded)++;
        for(int i=0;i<4;i++){
            int nx=cx+dx[i], ny=cy+dy[i];
            if(!Walkable(nx,ny)) continue;
            int nk=id(nx,ny), ng=g[k]+1;
            if(!g.count(nk) || ng<g[nk]){
                g[nk]=ng; cameFrom[nk]=k;
                open.push({ ng + w*Manhattan(nx,ny,gx,gy), ord++, nk });   // g + w*h
            }
        }
    }
    return -1;
}

// driver: run the same query at several weights
for (double w : {1.0, 1.5, 2.0, 4.0}) {
    int e; int cost = WeightedAStar(w, sx,sy,gx,gy,&e);
    printf("w = %.1f :  path cost = %d   cells expanded = %d\n", w, cost, e);
}

Output:

w = 1.0 :  path cost = 36   cells expanded = 101   (optimal)
w = 1.5 :  path cost = 36   cells expanded = 48
w = 2.0 :  path cost = 38   cells expanded = 44
w = 4.0 :  path cost = 38   cells expanded = 43

ดูการกระโดดจาก w = 1.0 ไป w = 1.5: path ยังคงเป็น 36 ที่ optimal แต่ search ยุบจาก 101 ช่องเหลือ 48 — งานน้อยกว่าครึ่ง โดยได้ฟรี บน map นี้ ดันไปที่ w = 2.0 แล้ว path ยาวขึ้นเล็กน้อยเป็น 38 (ประมาณ 6% เกิน optimal) ในขณะที่ search หดลงอีกนิด เลยจากนั้นผลตอบแทนลดลง เมื่อ w วิ่งเข้าหา infinity weighted A* จะเสื่อมกลายเป็น greedy best-first search จาก Section 13

การันตีที่ทำให้มันปลอดภัยพอจะ ship ได้: weighted A* ไม่มีวันคืน path ที่ cost มากกว่า w เท่าของ optimal ด้วย w = 1.5 คุณได้สัญญาว่าจะได้ route ที่ยาวกว่าที่ดีที่สุดที่เป็นไปได้อย่างมากที่สุด 50% — และในทางปฏิบัติ อย่างในนี้ คุณมักลงเอยห่างจาก bound นั้นมาก สำหรับเกมนั่นหมายความว่าคุณหมุน w ขึ้นจนกว่า search จะถูกพอสำหรับ frame budget ของคุณ โดยรู้ว่ากรณีเลวร้ายที่สุดคือ route ที่ยาวขึ้นนิดหน่อย ไม่ใช่เส้นที่พังหรือน่าเกลียด

17. Waypoint graphs: the third way to represent a level

Section 2 สร้าง grid; Section 11 สร้าง navmesh มี representation ที่สาม เก่ากว่า navmesh และยังใช้กันอยู่ ที่นั่งอยู่ระหว่างสองอันนั้น: waypoint graph แทนที่จะคลุมพื้นที่ที่เดินได้ (grid cell, navmesh polygon) คุณโปรย waypoint — จุดเดี่ยว ๆ — ไว้ตามที่ที่สำคัญ (ประตู, มุม, จุดกำบัง, กลางห้อง) แล้วเชื่อม waypoint สองจุดด้วย edge เมื่อ agent เดินเป็นเส้นตรงโล่ง ๆ ระหว่างสองจุดได้

ผลตอบแทนคือ graph นั้น เล็กจิ๋ว: level ที่จะเป็นหลายพัน grid cell อาจเป็น waypoint แค่ไม่กี่โหล ดังนั้น A* บนมันจึงแทบฟรี นั่นคือเหตุผลว่าทำไม waypoint graph จึงเป็นมาตรฐานในเกม 3D ยุคเก่า — network ของ node ที่วางด้วยมือใน engine อย่าง Quake และ Source — ที่การรัน A* บน grid เต็ม ๆ ของ level 3D แพงเกินไป designer จึงหย่อน node ลงไปด้วยมือ ไอเดียนี้ยังอยู่รอดมาถึงทุกวันนี้สำหรับ routing ระดับสูงแบบหยาบ ("ฉันจะผ่านห้องไหนบ้าง") มักเป็น layer บนสุดของ scheme แบบ hierarchical จาก Section 12

ต้นทุนคือภาพสะท้อนกลับด้านของผลตอบแทน ต้องมีใครสักคน — designer หรือ tool แบบ offline — วาง waypoint และ agent เดินได้แค่ตาม edge ที่คุณให้ไว้ ดังนั้น path จึงดีได้แค่เท่าที่ graph ดี waypoint ที่ห่างกันจะให้ path ที่ดีดไปมาระหว่างจุดตายตัวอย่างเห็นได้ชัด และไม่ตามรูปทรงจริงตรงกลางเลย navmesh เลี่ยงปัญหาทั้งสองด้วยการคลุมพื้นผิวที่เดินได้ทั้งหมดโดยอัตโนมัติ ซึ่งเป็นเหตุผลว่าทำไมมัน ไม่ใช่ waypoint graph จึงกลายเป็น default สำหรับโลก 3D ต่อเนื่อง แต่ search ที่อยู่ข้างใต้ไม่เคยเปลี่ยน: A* ไม่สนใจ — grid cell, navmesh polygon, หรือ waypoint ที่วางด้วยมือ มันก็แค่ "node, neighbor, edge cost, และ heuristic" สี่อย่างเดิมจาก Section 7

18. The funnel algorithm: exact string-pulling on a navmesh

Section 10 กับ 11 ต่างก็เอ่ยชื่อ funnel algorithm ในฐานะวิธี native ของ navmesh ในการทำให้ path ตรง แต่ไม่เคยแสดงมันเลย มันคุ้มที่จะได้เห็นอย่างจริงจัง เพราะมันคือวิธีที่ทุก navmesh path ที่คุณเคยเฝ้าดู agent เดิน ได้รูปทรงมาจริง ๆ

ทวน setup จาก Section 11: A* บน navmesh คืน ลำดับของ polygon ที่ต้องข้าม และประตูระหว่างพวกมัน — ขอบที่ใช้ร่วมกัน หรือ portal — เป็นที่รู้กันเป๊ะ การเดินผ่านกลาง polygon แต่ละอันจะซิกแซก การ smooth grid ใน Section 10 แก้ซิกแซกด้วยการสุ่มจุดตามเส้นตรงแล้วหวังว่ามันจะยังเดินได้ บน navmesh เราทำได้ดีกว่า เพราะขอบ portal ยื่น corridor ที่เป๊ะให้เรา funnel algorithm ดึงเชือกให้ตึงผ่าน corridor นั้นแบบเรขาคณิต โดยไม่ต้องสุ่มเลย

ไอเดียคือ funnel ที่เคลื่อนที่ได้: apex (จุดสุดท้ายที่ path ยึดมั่นแล้ว) บวกเส้นหนวดสองเส้นที่วิ่งจาก apex ไปยังปลาย ซ้าย และ ขวา ของ portal ที่กำลังพิจารณาอยู่ ขณะที่คุณเดินหน้าไปทีละ portal ปลายจุดใหม่แต่ละจุดทำได้แค่ บีบ funnel ให้แคบลง — ดึงหนวดซ้ายไปทางขวา หรือหนวดขวาไปทางซ้าย มีสองอย่างที่เกิดขึ้นได้:

• ปลายจุดใหม่ยังทำให้ funnel เป็นลิ่มที่ถูกต้อง (หนวดซ้ายยังอยู่ซ้ายของหนวดขวา): บีบข้างนั้นแล้วเดินต่อ
• หนวด ไขว้กัน — ข้างหนึ่งถูกดึงเลยอีกข้างไป จุดที่ไขว้กันนั้นคือมุมที่ path ถูกบังคับทางกายภาพให้ต้องเลี้ยวอ้อม: ล็อกมันไว้เป็น apex ใหม่ ปล่อยมันออกมาเป็นมุมของ path แล้วเริ่ม funnel ใหม่จากตรงนั้น

นี่คือ "Simple Stupid Funnel Algorithm" ฉบับกระชับของ Mikko Mononen เวอร์ชันที่ code navmesh ส่วนใหญ่อ้างอิง รันบน corridor รูปตัว L ที่เลี้ยวมุม

#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;

struct V { float x, y; };

// twice the signed area of triangle a,b,c. >0 = c is left of a->b, <0 = right.
float triArea2(V a, V b, V c){ return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y); }
bool vEqual(V a, V b){ float dx=a.x-b.x, dy=a.y-b.y; return dx*dx+dy*dy < 1e-6f; }

// portals: portal[i] = (left endpoint, right endpoint).
// portal[0] is (start,start); the last is (goal,goal).
vector<V> stringPull(vector<pair<V,V>> portal){
    vector<V> pts;
    V apex = portal[0].first, left = portal[0].first, right = portal[0].second;
    int apexIdx=0, leftIdx=0, rightIdx=0;
    pts.push_back(apex);
    for(int i=1;i<(int)portal.size();){
        V pl = portal[i].first, pr = portal[i].second;
        // tighten right side
        if(triArea2(apex,right,pr) <= 0.0f){
            if(vEqual(apex,right) || triArea2(apex,left,pr) > 0.0f){
                right = pr; rightIdx = i;                  // narrow the funnel
            } else {                                       // right crossed left: lock in left as a corner
                pts.push_back(left);
                apex = left; apexIdx = leftIdx;
                left = apex; right = apex; leftIdx = apexIdx; rightIdx = apexIdx;
                i = apexIdx + 1; continue;
            }
        }
        // tighten left side
        if(triArea2(apex,left,pl) >= 0.0f){
            if(vEqual(apex,left) || triArea2(apex,right,pl) < 0.0f){
                left = pl; leftIdx = i;                    // narrow the funnel
            } else {                                       // left crossed right: lock in right as a corner
                pts.push_back(right);
                apex = right; apexIdx = rightIdx;
                left = apex; right = apex; leftIdx = apexIdx; rightIdx = apexIdx;
                i = apexIdx + 1; continue;
            }
        }
        i++;
    }
    if(pts.empty() || !vEqual(pts.back(), portal.back().first))
        pts.push_back(portal.back().first);
    return pts;
}

int main(){
    // An L-shaped corridor of width 2. It runs right (+x), then turns up (+y).
    // The inside corner of the bend is at (2,2); the tight path should cut across it.
    // Each gate is (outer-wall endpoint, inner-wall endpoint), wound consistently.
    V start{0.5f, 1.0f}, goal{3.0f, 5.5f};
    vector<pair<V,V>> portals = {
        { start, start },
        { {1,0}, {1,2} },     // vertical gate at x=1
        { {2,0}, {2,2} },     // vertical gate at x=2  (inner endpoint = the corner)
        { {4,3}, {2,3} },     // horizontal gate at y=3
        { {4,4}, {2,4} },     // horizontal gate at y=4
        { goal, goal },
    };
    vector<V> path = stringPull(portals);
    printf("tight path through the corridor (%d corners):\n", (int)path.size());
    for(auto p: path) printf("  (%.1f, %.1f)\n", p.x, p.y);
    return 0;
}

Output:

tight path through the corridor (3 corners):
  (0.5, 1.0)
  (2.0, 2.0)
  (3.0, 5.5)

corridor วิ่งไปทางขวา แล้วเลี้ยวขึ้น มุมด้านในของโค้งอยู่ที่ (2, 2) จากประตูสี่บานที่ path ข้าม funnel ปล่อยมุมภายในออกมาเป๊ะหนึ่งมุม — (2, 2) — และคืน route สองท่อนจากจุดเริ่มต้นไปมุมนั้นไปเป้าหมาย นั่นคือ path ที่ตึงและเป๊ะ: มันเกาะมุมเดียวที่ต้องเกาะ และตรงดิ่งทุกที่อื่น ซึ่งคือสิ่งที่ทำให้การเคลื่อนที่บน navmesh ดูเป็นธรรมชาติโดยไม่ต้องมีการ smooth ทีละช่องแบบที่ grid ต้องการ function triArea2 ที่ทำงานทั้งหมดก็แค่ cross product 2D; เครื่องหมายของมันบอกว่าจุดหนึ่งอยู่ซ้ายหรือขวาของเส้นหนวด

19. When the map changes: replanning, and why you repath on a timer

ทุกอย่างที่ผ่านมาสมมติว่า map อยู่นิ่งขณะที่คุณ search เกมจริงไม่เป็นแบบนั้น: ประตูเปิดปิด, สะพานถูกทำลาย, ลังถูกดันเข้าไปใน corridor และเหนืออื่นใด เป้าหมายเคลื่อนที่ — ยามที่ไล่ผู้เล่นกำลังเล็งไปยังจุดที่ผู้เล่นออกจากไปแล้วตอนที่ path คำนวณเสร็จ path คือภาพนิ่งของโลกที่เปลี่ยนไปแล้ว คำถามจริงจึงไม่ใช่ "ฉันจะหา path ยังไง" แต่เป็น "บ่อยแค่ไหน และยังไง ฉันจะหาอันใหม่" การคำนวณใหม่ทุกเฟรมคือคำตอบที่ล่อใจ และมันผิดด้วยเหตุผลแยกกันสองข้อ

Cost. A* ไม่ฟรี และ "ทุกเฟรม ทุก agent" คูณ cost ของมันด้วย frame rate และขนาดฝูงของคุณพร้อมกัน นี่คือ chaser ที่วางแผนไปหาเป้าหมายที่เดินเตร่เป็นเวลา 150 เฟรม วัดสามวิธี — คำนวณใหม่ทุกเฟรม, คำนวณใหม่ตาม timer คงที่, และคำนวณใหม่เฉพาะตอนที่เป้าหมายลอยห่างจากที่มันวางแผนไว้ล่าสุดเกินไม่กี่ช่อง astarCost(...) คือ A* จาก Section 13 ที่คืนจำนวนช่องที่มันขยาย:

int lastPlanX = tx, lastPlanY = ty;   // where the target was at the last threshold-replan

for (int f = 0; f < frames; f++) {
    targetRandomWalk(&tx, &ty);        // target drifts one cell

    // Policy A: replan every frame
    callsEvery++;  expEvery  += astarCost(chaserX, chaserY, tx, ty);

    // Policy B: replan on a timer (every 10 frames)
    if (f % 10 == 0) { callsTimer++; expTimer += astarCost(chaserX, chaserY, tx, ty); }

    // Policy C: replan only when the target strayed > 3 cells from the last plan
    if (manhattan(tx, ty, lastPlanX, lastPlanY) > 3) {
        callsThresh++; expThresh += astarCost(chaserX, chaserY, tx, ty);
        lastPlanX = tx; lastPlanY = ty;
    }
}

Output:

over 150 frames, planning cost (A* calls / total cells expanded):
  every frame          : 150 calls,  19564 cells
  timer (every 10)      :  15 calls,   2020 cells
  threshold (moved > 3) :   9 calls,    984 cells

การ repath ตาม timer ทำงานหนึ่งในสิบ; การ repath เฉพาะตอนที่เป้าหมายเคลื่อนที่มากพอที่จะมีความหมายทำงานราวหนึ่งในยี่สิบ — 984 ช่องที่ขยายเทียบกับเกือบสองหมื่น — สำหรับการไล่ที่ผู้เล่นแยกไม่ออกจากเวอร์ชันคำนวณทุกเฟรม

Jitter. เหตุผลที่ละเอียดกว่าคือการคำนวณใหม่ตลอดเวลาทำให้ agent กระตุก เมื่อสอง route มี cost เกือบเท่ากัน การเปลี่ยนแปลงเล็กน้อย — เป้าหมายก้าวไปหนึ่งช่อง, สิ่งกีดขวางขยับนิดหน่อย — พลิก A* จาก route หนึ่งไปอีกอันแล้วกลับ agent ที่ตามอยู่ path ปัจจุบันอย่างซื่อสัตย์จะกระตุกไปมาระหว่างทั้งสองเห็นได้ชัด และอาจถึงกับหยุดค้าง ตัดสินใจเดินไม่ได้เพราะมันเอาแต่ตัดสินใจใหม่ การ repath ตาม timer (เช่นทุก 0.2 ถึง 0.5 วินาที) หรือเฉพาะเมื่อมี trigger จริง ให้เวลาแต่ละ path ได้ถูกเดินตามจริง ๆ ซึ่งดูตั้งใจกว่ามากเมื่อเทียบกับ path สมบูรณ์แบบที่คำนวณใหม่หกสิบครั้งต่อวินาที

ดังนั้น pattern มาตรฐานคือ replanning แบบ event-driven หรือ throttled: repath เมื่อเป้าหมายเคลื่อนเกิน threshold, เมื่อ path ปัจจุบันถูกบล็อก, หรือเมื่อ timer ลั่น — ไม่ใช่ตามตารางทุกเฟรมตายตัว ใน Unity:

using UnityEngine;
using UnityEngine.AI;

public class ThrottledChaser : MonoBehaviour
{
    public Transform target;
    public float repathInterval = 0.3f;   // at most one repath every 0.3s ...
    public float moveThreshold = 1.5f;    // ... and only if the target moved this far

    private NavMeshAgent agent;
    private Vector3 lastTargetPos;
    private float timer;

    void Awake() { agent = GetComponent<NavMeshAgent>(); }

    void Update()
    {
        timer += Time.deltaTime;
        if (timer < repathInterval) return;                       // not time yet

        Vector3 delta = target.position - lastTargetPos;
        if (delta.sqrMagnitude < moveThreshold * moveThreshold)
            return;                                               // target hasn't moved enough

        timer = 0f;
        lastTargetPos = target.position;
        agent.SetDestination(target.position);                    // the one expensive call
    }
}

ใช้ search เดิมซ้ำ: incremental replanning. เมื่อโลกเปลี่ยนแค่นิดเดียว การทิ้ง search ก่อนหน้าทั้งหมดแล้วเริ่มใหม่คือการสิ้นเปลือง — ส่วนใหญ่ของมันยังใช้ได้อยู่ algorithm ตระกูลหนึ่ง ตัวที่รู้จักดีที่สุดคือ D* Lite (และญาติของมัน LPA*, Lifelong Planning A*) ใช้ประโยชน์จากตรงนี้: พวกมันเก็บ search จากครั้งก่อนไว้แล้ว ซ่อม เฉพาะส่วนที่ได้รับผลกระทบจากการเปลี่ยนแปลง แทนที่จะวางแผนใหม่จากศูนย์ เมื่อประตูบานเดียวปิดลงใน map ใหญ่ D* Lite ซ่อม node ไม่กี่ตัวใกล้ประตูนั้นและใช้ที่เหลือซ้ำ ซึ่งถูกกว่า A* สด ๆ อย่างมาก — เหตุผลที่มันเป็นตัวหลักในหุ่นยนต์และในเกมที่ cost เปลี่ยนตลอดเวลา ไอเดียที่ควรจำไป: การเปลี่ยนโลกแค่นิดเดียวควรมี cost ในการตอบสนองแค่นิดเดียว

20. Following the path: steering and local avoidance (RVO/ORCA)

path คือ list ของจุด มันไม่ใช่การเคลื่อนที่ ชิ้นสุดท้ายของ pipeline — ชิ้นที่ผู้เล่นเฝ้าดูจริง ๆ — เปลี่ยน list นั้นให้เป็นการเคลื่อนที่ทีละวินาที และจัดการสิ่งที่ path ไม่มีทางรู้ได้ มันแยกออกอย่างสะอาดเป็นสองงานที่ทำงานคนละ scale

Path following คือ control ระดับ local ที่เดิน agent ไปตาม waypoint follower ที่ง่ายที่สุดจะบังคับเลี้ยวเข้าหา waypoint ปัจจุบัน และพอเข้ามาในรัศมี arrive เล็ก ๆ ก็เลื่อนไปยังจุดถัดไป:

using System.Collections.Generic;
using UnityEngine;

public class PathFollower : MonoBehaviour
{
    public float speed = 4f;
    public float arriveRadius = 0.2f;     // "close enough" to a waypoint
    public float slowRadius = 1.5f;       // start easing off near the final point

    private List<Vector3> path;
    private int index;

    public void SetPath(List<Vector3> newPath) { path = newPath; index = 0; }

    void Update()
    {
        if (path == null || index >= path.Count) return;

        Vector3 toTarget = path[index] - transform.position;
        float distance = toTarget.magnitude;

        if (distance < arriveRadius) { index++; return; }   // reached it; aim at the next next frame

        // ease down only on the final leg, so the agent doesn't overshoot the goal
        float wantSpeed = (index == path.Count - 1)
            ? speed * Mathf.Clamp01(distance / slowRadius)
            : speed;

        transform.position += toTarget.normalized * wantSpeed * Time.deltaTime;
    }
}

นั่นเรียบง่ายโดยตั้งใจ แต่มันแสดงรูปร่างของปัญหาแล้ว: path ดิบให้ ที่ ที่จะไป; follower ตัดสินใจ วิธี — อัตราการเลี้ยว, การชะลอตอนถึง, และ (ในเวอร์ชันที่สมบูรณ์กว่า) การมองไปข้างหน้าบน path นิดหน่อยเพื่อให้ agent เลี้ยวมุมได้ลื่นแทนที่จะหยุดกึกที่ทุก waypoint การทำ layer นี้ให้ถูกคือส่วนใหญ่ของสิ่งที่ทำให้การเคลื่อนที่รู้สึกดี และมันแยกออกจาก search ที่สร้าง path โดยสิ้นเชิง

Local avoidance คืออีกงานหนึ่ง: กัน agent ไม่ให้เดินทะลุกันและทะลุสิ่งกีดขวางที่เคลื่อนที่ซึ่ง path ไม่เคยคิดถึง นี่ ไม่ใช่ ปัญหา pathfinding — คุณจ่ายไหวไม่ได้ที่จะรัน A* สู้กับฝูงทุกเฟรม และต่อให้ทำได้ ฝูงก็เคลื่อนไปแล้วตอนที่คุณทำเสร็จ แทนที่จะเป็นแบบนั้น agent แต่ละตัวใช้เหตุผลกับ velocity โดยตรง คำถามหลักคือ: จากตำแหน่งของ neighbor และมันเคลื่อนยังไง velocity ตัวไหนของฉันเองจะพาฉันไปชนมันในไม่ช้า เซ็ตของ velocity "แย่ ๆ" นั้นเรียกว่า velocity obstacle นี่คือหัวใจของมัน — เวลาจนกว่าสองแผ่นดิสก์ที่เคลื่อนที่จะแตะกันครั้งแรก:

#include <cstdio>
#include <cmath>
using namespace std;

struct Vec { float x, y; };
float dot(Vec a, Vec b){ return a.x*b.x + a.y*b.y; }
Vec  sub(Vec a, Vec b){ return {a.x-b.x, a.y-b.y}; }

// Time until agent A (moving vA) first touches agent B (at pB, moving vB), within horizon tau.
// Returns -1 if they never get within the combined radius R inside [0, tau].
float timeToCollision(Vec pA, Vec vA, Vec pB, Vec vB, float R, float tau){
    Vec p = sub(pB, pA);          // B relative to A
    Vec u = sub(vB, vA);          // relative velocity
    float a = dot(u,u);
    float b = 2*dot(p,u);
    float c = dot(p,p) - R*R;
    if(a < 1e-9f) return (c <= 0.0f) ? 0.0f : -1.0f;    // no relative motion
    float disc = b*b - 4*a*c;
    if(disc < 0) return -1.0f;                           // paths never close within R
    float t = (-b - sqrtf(disc)) / (2*a);               // earliest contact
    if(t < 0) t = (-b + sqrtf(disc)) / (2*a);
    if(t < 0 || t > tau) return -1.0f;
    return t;
}

int main(){
    Vec pA{0,0}, pB{6,0};       // B is 6 units to the right ...
    Vec vB{-1,0};               // ... and walking straight toward A
    float R = 1.0f, tau = 5.0f; // combined radius 0.5+0.5, look 5 seconds ahead
    Vec cand[4] = { {1,0}, {1,0.5f}, {1,1}, {0,0} };
    const char* label[4] = { "straight at B (1.0, 0.0)", "veer up a little (1.0, 0.5)",
                             "veer up more   (1.0, 1.0)", "stop           (0.0, 0.0)" };
    for(int i=0;i<4;i++){
        float t = timeToCollision(pA, cand[i], pB, vB, R, tau);
        if(t < 0) printf("A velocity %-28s -> SAFE (no collision within %.0fs)\n", label[i], tau);
        else      printf("A velocity %-28s -> COLLISION at t = %.2fs\n", label[i], t);
    }
    return 0;
}

Output:

A velocity straight at B (1.0, 0.0)     -> COLLISION at t = 2.50s
A velocity veer up a little (1.0, 0.5)  -> SAFE (no collision within 5s)
A velocity veer up more   (1.0, 1.0)    -> SAFE (no collision within 5s)
A velocity stop           (0.0, 0.0)    -> COLLISION at t = 5.00s

agent สองตัวกำลังเข้าหากันแบบประจันหน้า การขับตรงเข้าหากันชนกันใน 2.5 วินาที; การเบี่ยงออกแม้แต่นิดเดียว — (1, 0.5) — ปลอดภัยสนิท; และที่บอกอะไรได้มากคือ การ หยุด ไม่ช่วย เพราะอีกตัวยังเดินมาเรื่อย ๆ (แตะกันที่ t = 5) เซ็ตของ velocity ที่ชนกันประกอบเป็นกรวย นั่นคือ velocity obstacle; การเคลื่อนที่ปลอดภัยคือ velocity ที่ใกล้ "มุ่งไปยัง waypoint ถัดไป" ที่สุดที่อยู่ นอก กรวยนั้น คำนวณมันทุกเฟรมสู้กับ neighbor ที่อยู่ใกล้ ๆ แล้ว agent จะไหลอ้อมกันได้ลื่น

การปรับที่ทำให้มันใช้ได้จริงในฝูงคือ reciprocity (ความต่างตอบแทน) ถ้า agent ทั้งสองสมมติว่าอีกตัวจะเดินตรงไปและต่างก็หลบเต็มจำนวน พวกมันจะหลบเกิน; เฟรมถัดไปเห็นว่าไม่มีปัญหา ก็เดินตรงกลับ แล้วชนกันอีก — เต้นสลับไปมาไม่รู้จบ RVO (Reciprocal Velocity Obstacles) แก้ด้วยการให้ agent แต่ละตัวรับผิดชอบการหลบ ครึ่งหนึ่ง โดยไว้ใจว่าอีกตัวจะรับอีกครึ่ง ORCA (Optimal Reciprocal Collision Avoidance) คือสูตรสมัยใหม่ที่เร็วกว่าของไอเดียเดียวกัน แสดงเป็น linear constraint; มันคือสิ่งที่อยู่ข้างใน avoidance ของ NavMeshAgent ของ Unity และระบบฝูงส่วนใหญ่ global pathfinding เลือก corridor; reciprocal local avoidance เจรจาเมตรสุดท้าย

21. Glossary

• Pathfinding — การหา route จากตำแหน่งเริ่มต้นไปยังเป้าหมายที่หลบสิ่งกีดขวาง ปกติด้วย cost ต่ำที่สุดเท่าที่จะทำได้
• Obstacle avoidance / steering — การหลบแบบ reactive ระยะสั้น สำหรับสิ่งที่ไม่ได้ถูกคิดไว้ใน path ที่วางแผนไว้
• Graph — กลุ่มของ node ที่เชื่อมกันด้วย edge โครงสร้างทั่วไปที่ search algorithm ทุกตัวในบทนี้รันอยู่บน
• Grid — graph ที่ง่ายที่สุดสำหรับ pathfinding: ช่องขนาดเท่ากันเป็น node เชื่อมกับช่องข้างเคียง
• BFS (breadth-first search) — สำรวจ graph ทีละวงด้วย FIFO queue หา shortest path ตามจำนวน hop เมื่อทุก edge cost เท่ากัน
• Dijkstra's algorithm — สำรวจ node ตามลำดับ cost ที่รู้ว่าถูกที่สุดก่อน โดยใช้ priority queue หา shortest path ตาม total cost บน graph ที่มี weight
• Priority queue — queue ที่คืนไอเทมที่ priority ต่ำที่สุดให้ก่อนเสมอ ปกติสร้างด้วย binary heap
• A* — Dijkstra's algorithm ที่เพิ่ม heuristic เข้าไป ทำให้มันค้นหาไปในทิศทางของเป้าหมายแทนที่จะขยายออกทุกทิศเท่า ๆ กัน
• Heuristic (h) — ค่าประมาณ cost ที่เหลือจาก node หนึ่งไปยังเป้าหมาย
• g-cost — cost จริงที่รู้แล้วจากจุดเริ่มต้นไปยัง node
• f-cost — g + h; ค่าที่ open set ของ A* ถูกเรียงลำดับตาม
• Admissible heuristic — heuristic ที่ไม่เคย overestimate cost ที่เหลือจริง จำเป็นสำหรับ A* ที่จะการันตี path ถูกที่สุด
• Manhattan distance — |dx| + |dy|; ตรงกับการเดิน grid แบบ 4 ทิศทาง
• Euclidean distance — ระยะทางเส้นตรง ตรงกับการเดินอิสระหรือทแยงมุม
• Open set — node ที่ถูกค้นพบแล้วแต่ยังขยายไม่ครบ
• Closed set — node ที่ขยายครบแล้ว จะได้ไม่ถูกประมวลผลซ้ำ
• came-from map — บันทึกไว้ต่อ node ว่ามันถูกไปถึงจาก neighbor ตัวไหนด้วย cost ถูกที่สุด ใช้สร้าง path สุดท้ายกลับคืนมา
• String-pulling / path smoothing — การยุบ path ที่ซิกแซกให้เป็นเส้นตรง ด้วยการเช็ค line-of-sight
• Navmesh — mesh ของ polygon ที่เดินได้เชื่อมกัน คลุมพื้นผิวของ level ใช้แทน grid ในเกม 3D ส่วนใหญ่
• Portal — ขอบที่ใช้ร่วมกันระหว่าง polygon navmesh สองอันที่อยู่ติดกัน ใช้เป็น graph edge สำหรับ pathfinding
• Funnel algorithm — เวอร์ชันที่แม่นยำและเป็น native ของ navmesh สำหรับ string-pulling ร้อย path ที่ตึงผ่านลำดับของ portal
• Recast — library แบบ open-source ที่สร้าง navmesh จาก raw level geometry
• Detour — runtime library คู่กันที่รัน pathfinding query กับ navmesh ที่ Recast สร้าง
• NavMeshAgent — component ของ Unity สำหรับเคลื่อนตัวละครตาม navmesh ที่ bake ไว้ รวมถึง local avoidance พื้นฐาน
• Hierarchical pathfinding — ค้นหา graph ระดับ cluster แบบหยาบก่อน แล้วค่อยลงรายละเอียด path เฉพาะใน cluster ที่มันผ่าน
• Greedy best-first search — เรียง open set ด้วย h อย่างเดียว; เร็วมาก แต่ไม่การันตีว่าจะหา path ถูกที่สุด
• Consistency / monotonicity — heuristic ที่ h(n) <= cost(n, n') + h(n') สำหรับทุก edge; แข็งกว่า admissibility และเป็นสิ่งที่ทำให้การ optimize ด้วย closed set ของ A* ปลอดภัย
• Tie-breaking — กฎรองสำหรับเรียงลำดับ node ใน open set ที่มี f-cost เท่ากัน ช่วยลดจำนวน node ที่ A* ขยายลงอย่างมาก
• Weighted A* — เรียงด้วย g + w*h โดย w > 1; เร็วกว่า A* และการันตีว่าคืน path ที่ไม่แย่ไปกว่า w เท่าของ cost ที่ optimal
• Waypoint graph — level ที่แทนด้วยจุดที่วางด้วยมือหรือ tool เชื่อมกันด้วย edge เส้นตรงโล่ง ๆ
• Replanning / repathing — การคำนวณ path ใหม่เมื่อโลกหรือเป้าหมายเปลี่ยน; ทำตาม timer หรือ trigger ไม่ใช่ทุกเฟรม
• D* Lite / LPA* — algorithm แบบ incremental ที่ซ่อม path ก่อนหน้าเฉพาะรอบ ๆ จุดที่เปลี่ยน แทนที่จะวางแผนใหม่จากศูนย์
• Path following — การบังคับเลี้ยวทุกเฟรมที่เคลื่อน agent ไปตาม path ที่คำนวณไว้ (การถึง, การมองไปข้างหน้า, อัตราการเลี้ยว)
• Local avoidance — การบังคับเลี้ยวแบบ reactive ทุกเฟรมที่กัน agent ไม่ให้ชนกันและชนสิ่งกีดขวางที่เคลื่อนที่; แยกจาก global pathfinding
• Velocity obstacle — เซ็ตของ velocity ของ agent ที่จะนำไปสู่การชน neighbor ภายในช่วงเวลาที่กำหนด
• RVO / ORCA — วิธี local avoidance แบบต่างตอบแทนที่ agent แต่ละตัวรับผิดชอบการหลบส่วนหนึ่ง; ORCA คือสูตรที่ใช้ใน avoidance ของ agent ใน Unity

22. Exercises

private static readonly (int dx, int dy, float cost)[] Directions8 =
{
    (0, -1, 1f), (0, 1, 1f), (-1, 0, 1f), (1, 0, 1f),                 // orthogonal
    (-1, -1, 1.41421356f), (1, -1, 1.41421356f),                      // diagonals
    (-1, 1, 1.41421356f), (1, 1, 1.41421356f),
};

private IEnumerable<(Vector2Int, float)> GetNeighbors(Vector2Int cell)
{
    foreach (var (dx, dy, cost) in Directions8)
    {
        Vector2Int next = cell + new Vector2Int(dx, dy);
        if (!map.IsWalkable(next.x, next.y)) continue;

        bool isDiagonal = dx != 0 && dy != 0;
        if (isDiagonal)
        {
            // block cutting a corner: both adjacent orthogonal cells must also be open
            bool sideA = map.IsWalkable(cell.x + dx, cell.y);
            bool sideB = map.IsWalkable(cell.x, cell.y + dy);
            if (!sideA || !sideB) continue;
        }

        yield return (next, cost);
    }
}

private float Heuristic(Vector2Int a, Vector2Int b)
{
    float dx = a.x - b.x;
    float dy = a.y - b.y;
    return Mathf.Sqrt(dx * dx + dy * dy); // Euclidean: matches free 8-directional movement
}