AI Trong Game Development: Từ Pathfinding Đến Behavior Tree

AI Trong Game Development: Từ Pathfinding Đến Behavior Tree

Game AI không phải là machine learning hay neural network - đó là các thuật toán và hệ thống được thiết kế để tạo ra hành vi thông minh và thú vị cho NPC (Non-Player Character). Mục tiêu của game AI không phải là tạo ra AI thông minh nhất, mà là tạo ra AI vui nhất để chơi cùng. Bài viết này sẽ hướng dẫn bạn các kỹ thuật game AI phổ biến nhất, từ pathfinding cơ bản đến behavior tree nâng cao. Tham khảo các dự án game AI mẫu tại kho source game LamGame.

1. A* Pathfinding: Thuật Toán Tìm Đường Kinh Điển

A* (A-star) là thuật toán tìm đường phổ biến nhất trong game development. A* kết hợp ưu điểm của Dijkstra (đảm bảo tìm đường ngắn nhất) và Greedy Best-First Search (tìm nhanh nhờ heuristic). Thuật toán sử dụng hàm đánh giá f(n) = g(n) + h(n) trong đó g(n) là chi phí thực tế từ start đến node n, và h(n) là ước lượng chi phí từ n đến goal (heuristic).

Heuristic phổ biến nhất cho grid-based map là Manhattan distance (cho 4-directional movement) và Euclidean distance (cho 8-directional hoặc free movement). Heuristic phải là admissible - không bao giờ overestimate chi phí thực tế - để đảm bảo A* tìm được đường ngắn nhất.

public class AStarPathfinder
{
    public List<Vector2Int> FindPath(Vector2Int start, Vector2Int goal, bool[,] walkable)
    {
        var openSet = new SortedSet<(float f, Vector2Int pos)>();
        var cameFrom = new Dictionary<Vector2Int, Vector2Int>();
        var gScore = new Dictionary<Vector2Int, float>();

        gScore[start] = 0;
        openSet.Add((Heuristic(start, goal), start));

        while (openSet.Count > 0)
        {
            var current = openSet.Min.pos;
            openSet.Remove(openSet.Min);

            if (current == goal)
                return ReconstructPath(cameFrom, current);

            foreach (var neighbor in GetNeighbors(current, walkable))
            {
                float tentativeG = gScore[current] + Cost(current, neighbor);
                if (tentativeG < gScore.GetValueOrDefault(neighbor, float.MaxValue))
                {
                    cameFrom[neighbor] = current;
                    gScore[neighbor] = tentativeG;
                    float f = tentativeG + Heuristic(neighbor, goal);
                    openSet.Add((f, neighbor));
                }
            }
        }
        return null; // Không tìm được đường
    }

    float Heuristic(Vector2Int a, Vector2Int b)
        => Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y); // Manhattan
}

Đối với game có map lớn, A* thuần có thể chậm. Các tối ưu phổ biến bao gồm: Hierarchical A* - chia map thành các cluster và tìm đường ở mức cluster trước, sau đó refine trong từng cluster. Jump Point Search (JPS) - tối ưu cho uniform-cost grid, nhanh hơn A* nhiều lần bằng cách skip các node không cần thiết. Flow Field - tính toán một lần cho toàn bộ map, phù hợp khi nhiều unit cùng di chuyển đến một điểm (RTS game).

2. NavMesh Trong Unity

Unity cung cấp hệ thống NavMesh (Navigation Mesh) built-in cho 3D pathfinding. NavMesh là một simplified mesh đại diện cho các vùng walkable trong scene. Unity tự động bake NavMesh từ geometry của scene, và NavMeshAgent component xử lý pathfinding và movement tự động. Đối với game 2D, bạn có thể sử dụng NavMesh package cho 2D hoặc implement A* riêng trên tilemap.

NavMesh hỗ trợ nhiều tính năng nâng cao: NavMesh Obstacles cho dynamic obstacles (cửa đóng/mở, vật cản di chuyển), Off-Mesh Links cho các kết nối đặc biệt (nhảy qua hố, leo thang), và NavMesh Areas với cost khác nhau (đường nhựa nhanh hơn đầm lầy). Agent có thể có kích thước khác nhau - enemy lớn không đi qua cửa hẹp, enemy nhỏ có thể chui qua khe.

3. Finite State Machine (FSM)

FSM là pattern đơn giản nhất để quản lý AI behavior. Mỗi NPC có một tập hợp các state (Idle, Patrol, Chase, Attack, Flee) và các transition rules giữa chúng. Tại mỗi thời điểm, NPC chỉ ở một state duy nhất và thực hiện behavior tương ứng. Transition xảy ra khi điều kiện được thỏa mãn, ví dụ: từ Patrol chuyển sang Chase khi phát hiện player trong tầm nhìn.

public enum EnemyState { Idle, Patrol, Chase, Attack, Flee }

public class EnemyFSM : MonoBehaviour
{
    private EnemyState currentState = EnemyState.Patrol;
    public float detectRange = 10f, attackRange = 2f, fleeHealthPercent = 0.2f;

    void Update()
    {
        switch (currentState)
        {
            case EnemyState.Patrol:
                PatrolBehavior();
                if (PlayerInRange(detectRange)) TransitionTo(EnemyState.Chase);
                break;
            case EnemyState.Chase:
                ChaseBehavior();
                if (PlayerInRange(attackRange)) TransitionTo(EnemyState.Attack);
                if (!PlayerInRange(detectRange)) TransitionTo(EnemyState.Patrol);
                if (HealthPercent < fleeHealthPercent) TransitionTo(EnemyState.Flee);
                break;
            case EnemyState.Attack:
                AttackBehavior();
                if (!PlayerInRange(attackRange)) TransitionTo(EnemyState.Chase);
                if (HealthPercent < fleeHealthPercent) TransitionTo(EnemyState.Flee);
                break;
            case EnemyState.Flee:
                FleeBehavior();
                if (!PlayerInRange(detectRange)) TransitionTo(EnemyState.Idle);
                break;
        }
    }

    void TransitionTo(EnemyState newState)
    {
        OnExitState(currentState);
        currentState = newState;
        OnEnterState(newState);
    }
}

FSM hoạt động tốt cho AI đơn giản với ít state. Tuy nhiên, khi số lượng state và transition tăng lên, FSM trở nên khó quản lý - đây gọi là vấn đề "state explosion". Ví dụ, nếu bạn thêm state "PickupHealth" và "CallForHelp", bạn cần thêm transition từ mọi state hiện có đến các state mới, tạo ra mạng lưới transition phức tạp và khó debug.

4. Behavior Tree: Giải Pháp Cho AI Phức Tạp

Behavior Tree (BT) là pattern phổ biến nhất cho game AI phức tạp, được sử dụng rộng rãi trong các game AAA như Halo, Unreal Engine AI, và nhiều game khác. BT tổ chức behavior thành cấu trúc cây với các loại node chính:

• Composite nodes: Điều khiển flow - Sequence (chạy children lần lượt, dừng khi một child fail), Selector (chạy children lần lượt, dừng khi một child succeed), Parallel (chạy tất cả children đồng thời).
• Decorator nodes: Modify behavior của child - Inverter (đảo kết quả), Repeater (lặp lại), Cooldown (chờ thời gian giữa các lần chạy).
• Leaf nodes: Thực hiện action cụ thể - Action (MoveTo, Attack, PlayAnimation), Condition (IsPlayerInRange, IsHealthLow, HasAmmo).

Ví dụ behavior tree cho enemy: Root → Selector → [Sequence(IsHealthLow → Flee), Sequence(IsPlayerInRange → Chase → IsInAttackRange → Attack), Patrol]. Selector sẽ thử từng branch từ trái sang phải: nếu máu thấp thì chạy trốn, nếu không thì kiểm tra player có trong tầm không để chase và attack, nếu không thì patrol. Cấu trúc này rõ ràng, dễ đọc, và dễ mở rộng hơn FSM rất nhiều.

5. Utility AI

Utility AI là approach mà mỗi action được đánh giá bằng một "utility score" dựa trên context hiện tại, và action có score cao nhất được chọn. Ví dụ: score của Attack = damage potential × (1 - risk), score của Heal = (1 - healthPercent) × healAmount, score của Flee = (1 - healthPercent) × threatLevel. Utility AI tạo ra behavior tự nhiên và emergent hơn FSM hoặc BT vì NPC liên tục đánh giá tất cả options thay vì follow một flow cứng nhắc. Kỹ thuật này đặc biệt phù hợp cho simulation game và game có nhiều NPC với personality khác nhau.

6. GOAP (Goal-Oriented Action Planning)

GOAP là hệ thống AI planning nâng cao, nổi tiếng nhờ game F.E.A.R. Trong GOAP, NPC có goals (mục tiêu) và actions (hành động). Mỗi action có preconditions (điều kiện tiên quyết) và effects (kết quả). GOAP planner sử dụng A* search trên action space để tìm chuỗi actions tối ưu đạt được goal. Ví dụ: Goal = KillEnemy, Actions = [GetGun(precond: none, effect: hasGun), LoadGun(precond: hasGun, effect: gunLoaded), Shoot(precond: gunLoaded, effect: enemyDead)]. Planner tự động tìm ra sequence: GetGun → LoadGun → Shoot.

GOAP mạnh mẽ vì NPC tự tìm ra cách đạt mục tiêu thay vì follow script cứng. Nếu bạn thêm action mới (ví dụ MeleeAttack không cần gun), planner tự động cân nhắc nó mà không cần sửa code hiện có. Tuy nhiên, GOAP phức tạp hơn nhiều so với FSM và BT, và debugging có thể khó khăn vì behavior là emergent.

Game AI là lĩnh vực rộng lớn và thú vị. Hãy bắt đầu với FSM cho prototype, chuyển sang Behavior Tree khi AI cần phức tạp hơn, và cân nhắc Utility AI hoặc GOAP cho game simulation. Nếu bạn đam mê AI programming trong game, hãy xem các cơ hội việc làm game tại LamGame.