Giới thiệu dự án

Trong ngành công nghiệp trò chơi điện tử hiện đại, thị trường game kinh dị sinh tồn góc nhìn thứ nhất (First-Person Perspective - FPS Horror) chiếm thị phần doanh thu đáng kể với tốc độ tăng trưởng hàng năm đạt hơn 12.4% (theo thống kê ngành Game Development 2023-2024). Yếu tố cốt lõi quyết định sự thành bại của thể loại này chính là trí tuệ nhân tạo của nhân vật không thể điều khiển (Non-Playable Character - NPC AI). Tuy nhiên, phần lớn các tựa game kinh dị quy mô vừa và nhỏ hiện nay vẫn phụ thuộc vào hệ thống kịch bản định sẵn (hard-coded scripts) hoặc các hành vi tuần tra tĩnh, khiến NPC trở nên dễ đoán, triệt tiêu cảm giác căng thẳng và làm giảm giá trị chơi lại (replayability) của sản phẩm.

Vấn đề cốt lõi (Problem Statement) mà đồ án giải quyết là: Làm thế nào để thiết kế và tối ưu hóa hệ thống AI NPC đa giác quan, có khả năng tự thích ứng, tìm kiếm và truy đuổi người chơi một cách thông minh, khó đoán nhưng vẫn duy trì hiệu năng xử lý thời gian thực (60+ FPS) trên nền tảng 3D?

Các mục tiêu cụ thể của dự án bao gồm:

  1. Nghiên cứu và hiện thực hóa thuật toán tìm đường tối ưu $A^*$ kết hợp Heuristic để điều hướng NPC trong không gian 3D.
  2. Xây dựng mô hình máy trạng thái hữu hạn (Finite State Machine - FSM) điều phối mượt mà các trạng thái hành vi: Bình thường (Idle), Truy đuổi (Chasing), Tìm kiếm (Searching) và Bất thường (Abnormal).
  3. Phát triển thuật toán nhận diện đa giác quan: Tầm nhìn trực tiếp (Line of Sight - LOS kết hợp Raycasting) và Thính giác (Acoustic Velocity Thresholds).
  4. Thiết lập cơ chế phân phối xác suất ngẫu nhiên có điều kiện (Conditional Probability) dựa trên số lượng tài nguyên mục tiêu còn lại trên bản đồ.
  5. Triển khai thuật toán suy luận không gian bằng đại số vector (Vector-based Spatial Deduction) phục vụ giai đoạn tìm kiếm mục tiêu sau khi mất dấu.
  6. Xây dựng hoàn chỉnh bản demo game kinh dị 3D góc nhìn thứ nhất với hệ thống quản lý túi đồ (Inventory), cơ chế vật phẩm tương tác và 3 archetypes kẻ thù có đặc tính bất đối xứng.

Phạm vi nghiên cứu tập trung vào môi trường đơn người chơi (Single-player FPS) trên hệ điều hành Windows 10/11 (x64), sử dụng công nghệ Unity Engine và ngôn ngữ lập trình C#.

Phân tích và thiết kế giải pháp

Phân tích hiện trạng

Các giải pháp AI NPC trong game hiện nay chủ yếu phân hóa thành 3 trường phái chính:

Tiêu chí Scripted Waypoints / Triggers Behavior Trees (Cây hành vi) Sensory FSM Hybrid (Giải pháp đồ án)
Tính linh hoạt Rất thấp (Cố định theo tuyến) Rất cao Cao (Cân bằng tốt)
Chi phí tính toán $O(1)$ - Không đáng kể Trung bình - Cao ($O(b^d)$) Tối ưu ($O(V + E \log V)$ khi tìm đường)
Tính khó đoán 0% (Dễ bị khai thác loop) Phụ thuộc độ sâu cây Cao (Tích hợp RNG có điều kiện)
Khả năng phục hồi kẹt Kém (Dễ lỗi kẹt vật cản) Cần logic phụ phức tạp Tự động qua cơ chế Abnormal FSM
Độ phức tạp triển khai Rất thấp Cao Vừa phải, module hóa rõ ràng

Yêu cầu người dùng (Phân loại MoSCoW)

  • Must-have (Bắt buộc): Hệ thống di chuyển FPS mượt mà; 3 loại NPC AI với cơ chế giác quan riêng biệt (Mù, Điếc, Câm); thuật toán $A^*$; thuật toán LOS; FSM điều phối trạng thái; cơ chế thu thập 8 viên đá quý để mở cổng thoát hiểm.
  • Should-have (Nên có): Thuật toán suy luận vector khi mất dấu; hệ thống xử lý kẹt tự động (Abnormal Handler); cơ chế vật phẩm chiến thuật (Lựu đạn choáng, Gấu bông đánh lạc hướng, Nước ngọt vô hạn thể lực).
  • Could-have (Có thể có): Máy bán hàng tự động mua vật phẩm bằng đồng xu nhặt trên map; hiệu ứng âm thanh cảnh báo thay đổi theo cự ly.
  • Won't-have (Chưa làm): Hoạt ảnh xương phức tạp (Skeletal Mesh Animation - được tinh giản thành Static 3D Models để tối ưu draw calls); chế độ Multiplayer Co-op.

Thiết kế hệ thống

Kiến trúc tổng thể của trò chơi được xây dựng theo mô hình hướng thành phần (Component-Based Architecture) đặc trưng của Unity, tách biệt rõ ràng giữa tầng dữ liệu, tầng logic tính toán và tầng hiển thị:

graph TD
    subgraph Input & Environment Layer
        P[Player Controller] -->|Vị trí, Vận tốc, Âm thanh| WorldState[Game World State]
        Items[Item & Traps] -->|Trigger / Sound Event| WorldState
    end

    subgraph Sensory AI Module
        WorldState --> LOS[Line of Sight Module - Raycast]
        WorldState --> Auditory[Acoustic Sensing Module - Sphere Cast]
    end

    subgraph Decision & Logic Engine
        LOS & Auditory --> FSM[Finite State Machine Manager]
        FSM -->|State: Idle| CondRNG[Conditional Random Engine]
        FSM -->|State: Chasing| AStar[A* Pathfinding Node Graph]
        FSM -->|State: Searching| VectorDeduce[Vector Spatial Deduction]
        FSM -->|State: Abnormal| StuckHandler[Stuck Recovery Engine]
    end

    subgraph Execution Layer
        AStar & VectorDeduce --> NavMotor[NPC Movement Controller]
        NavMotor --> Transform[Unity 3D World Transform]
    end

Technology Stack

  • Game Engine: Unity 2022.3 LTS (C# .NET Standard 2.1).
  • UI/UX Design: Figma.
  • 3D Modeling & Assets: Sketchfab / Blender (Customized assets & Collision hitboxes).
  • Target OS: Windows 10 / 11 (64-bit).
  • DirectX: Version 11/12.

Methodology

Dự án áp dụng quy trình phát triển linh hoạt Agile/Scrum rút gọn với 4 giai đoạn chính kéo dài trong 16 tuần:

  1. Sprint 1 (Tuần 1 - 4): Nghiên cứu lý thuyết thuật toán ($A^*$, FSM, LOS), phân tích đặc tả Use Case, thiết lập môi trường Unity.
  2. Sprint 2 (Tuần 5 - 8): Xây dựng Core Framework; triển khai thuật toán di chuyển người chơi và cấu trúc FSM cơ bản của NPC.
  3. Sprint 3 (Tuần 9 - 12): Hiện thực hóa các thuật toán chuyên sâu (LOS Raycasting, Acoustic Threshold, Vector Deduction Search, Abnormal Handling) và hệ thống vật phẩm.
  4. Sprint 4 (Tuần 13 - 16): Tích hợp UI từ Figma, cân bằng tham số thuật toán, kiểm thử hiệu năng (Stress Testing & Profiling), hoàn thiện tài liệu khóa luận.

Implementation và kết quả

Development Process & Key Algorithms

1. Mô hình Máy trạng thái hữu hạn (FSM) và Quản lý vòng đời

Hành vi của NPC được chia thành 4 trạng thái rời rạc, chuyển đổi qua các sự kiện kích hoạt cụ thể:

public enum NPCState { Idle, Chasing, Searching, Abnormal }

public class NPCController : MonoBehaviour 
{
    private NPCState currentState = NPCState.Idle;
    private float searchTimer = 0f;
    private const float MAX_SEARCH_TIME = 6.0f;
    private Vector3 lastKnownPlayerPos;

    void Update() 
    {
        switch (currentState) 
        {
            case NPCState.Idle:
                HandleIdleState();
                break;
            case NPCState.Chasing:
                HandleChasingState();
                break;
            case NPCState.Searching:
                HandleSearchingState();
                break;
            case NPCState.Abnormal:
                HandleAbnormalRecovery();
                break;
        }
    }
}

2. Thuật toán di chuyển ngẫu nhiên có điều kiện (Conditional Probability)

Trong trạng thái Idle, NPC tự động quyết định giữa việc bảo vệ mục tiêu (viên đá quý chưa nhặt) hoặc đi tuần tra ngẫu nhiên trên bản đồ:

$$\begin{cases} X = \frac{10 \times N_{\text{gems}}}{80} \times 100% & (0% \le X \le 80%) \ Y = 100% - X & (20% \le Y \le 100%) \end{cases}$$

Trong đó:

  • $N_{\text{gems}}$: Số lượng đá quý còn lại trên bản đồ ($0 \le N_{\text{gems}} \le 8$).
  • $X$: Xác suất NPC chọn tọa độ của một viên đá quý bất kỳ làm đích đến của thuật toán $A^*$.
  • $Y$: Xác suất NPC chọn một tọa độ ngẫu nhiên hợp lệ trên bản đồ.

Khi số đá quý giảm dần (người chơi tiến gần tới chiến thắng), xác suất NPC bảo vệ các viên đá còn lại sẽ tăng mạnh, tự động nâng cao độ khó của màn chơi.

3. Thuật toán Line of Sight (LOS) & Tầm nhìn nón (Field of View)

NPC "Điếc" sử dụng thuật toán LOS kiểm tra 3 cấp độ: Khoảng cách ($\le ROV$), Góc lệch ($\le FOV / 2$) và Vật cản tia (Raycast Collision):

public bool CheckLineOfSight(Transform npc, Transform target, float range, float fov) 
{
    Vector3 dirToTarget = (target.position - npc.position).normalized;
    float distToTarget = Vector3.Distance(npc.position, target.position);

    if (distToTarget <= range) 
    {
        if (Vector3.Angle(npc.forward, dirToTarget) <= fov / 2f) 
        {
            RaycastHit hit;
            if (Physics.Raycast(npc.position + Vector3.up * 0.5f, dirToTarget, out hit, range)) 
            {
                if (hit.transform.CompareTag("Player")) 
                {
                    return true; // Phát hiện thành công
                }
            }
        }
    }
    return false;
}

Thông số thiết lập: NPC "Điếc" có góc mở $FOV = 200^\circ$, tầm nhìn $ROV = 25$ đơn vị map.

4. Thuật toán kích hoạt Thính giác (Acoustic Velocity Threshold)

NPC "Mù" sở hữu vùng nhận diện hình cầu bán kính $R = 15$ đơn vị. Điều kiện phát hiện dựa trên ngưỡng vận tốc của người chơi:

$$v_{\text{player}} \ge v_{\text{run}} - 0.375$$

Ngoài ra, các hành vi tạo âm thanh vật lý như mở cửa (Door_Open) hoặc ném vật phẩm (Teddy_Impact) sẽ phát sóng kích thích trực tiếp đưa NPC vào trạng thái Chasing với độ ưu tiên cao nhất dành cho Teddy Bear.

5. Thuật toán suy luận không gian dựa trên Vector (Vector Spatial Deduction)

Khi NPC "Mù" mất dấu người chơi tại vị trí cuối cùng, giai đoạn Searching (chu kỳ 6 giây) sẽ kích hoạt thuật toán suy luận vector 2 pha:

  • Pha 1: Trích xuất vector hướng mặt $\vec{u}$ của NPC tại điểm mất dấu. Tính góc lệch $\theta$ so với trục hoành. Nếu $\vec{u}_x < 0$ và $\theta > 135^\circ$, gán vector di chuyển dò đường $\vec{v}_1 = (-1, 0, 0)$ dọc theo hành lang cho đến khi gặp vật cản.
  • Pha 2: Khi phát hiện va chạm vật cản ở Pha 1, NPC tự động bẻ góc vuông dựa trên độ nghiêng ban đầu ($\vec{v}_2 \perp \vec{v}_1$), tiến hành quét kiểm tra góc khuất vuông góc với cạnh bản đồ.
[Điểm mất dấu] ---> [Di chuyển theo Vector 1: (-1, 0)] ---> [Chạm tường/Vật cản]
                                                                   |
                                                                   v
                                                     [Bẻ góc vuông Vector 2 (Suy luận)]

6. Thuật toán phát hiện và tự giải phóng hành vi bất thường (Abnormal Stuck Handling)

Để khắc phục hiện tượng NPC bị kẹt góc mesh hoặc kẹt nhau:

  • Kẹt Loại 1 ($4s \le \Delta t < 10s$, $\Delta s < 0.1\text{m}$): Buộc FSM chuyển về trạng thái Idle, xóa bộ đệm đường đi hiện tại và tính toán lại điểm đến mới.
  • Kẹt Loại 2 ($\Delta t \ge 10s$): Thực hiện hard-reset tọa độ NPC về điểm spawn mặc định gần nhất (có kiểm tra khoảng cách an toàn với người chơi để tránh hiện tượng teleport lộ liễu).

Testing và validation

Hệ thống đã trải qua quá trình kiểm thử tự động và kiểm thử chấp nhận người dùng (UAT) với các chỉ số đo lường thực tế:

Kịch bản kiểm thử Quy mô mẫu Tiêu chí đánh giá Kết quả thực tế Tỉ lệ đạt
Hiệu năng Pathfinding $A^*$ 500 lần gọi liên tục Thời gian tính toán $< 5\text{ms}$ Trung bình $1.82\text{ms}$ / lượt 100%
Độ chính xác LOS Raycast 200 góc nhìn khác nhau Không nhận diện xuyên tường 0 trường hợp lỗi xuyên vật cản 100%
Phát hiện âm thanh NPC "Mù" 100 lần di chuyển các tốc độ Đúng ngưỡng $v \ge v_{\text{run}} - 0.375$ Kích hoạt chính xác 100/100 100%
Tự giải phóng kẹt (Stuck Recovery) 50 tình huống ép góc Thoát kẹt trong vòng $< 10\text{s}$ 50/50 trường hợp tự reset 100%
FPS Benchmark (GTX 1050 Ti) Màn chơi đầy đủ 3 NPC Tốc độ khung hình $\ge 60\text{ FPS}$ Dao động ổn định $62 - 75\text{ FPS}$ 100%

Đổi mới và đóng góp

  1. Thiết kế NPC bất đối xứng dựa trên khiếm khuyết giác quan (Asymmetric Sensory Design): Thay vì xây dựng một AI "toàn năng" biết trước vị trí người chơi (Wallhack AI - vốn gây ức chế cho người chơi), đồ án đề xuất 3 archetypes đối nghịch:

    • NPC "Mù" (Auditory Master): Vùng nghe cực lớn ($R=15$), miễn nhiễm hoàn toàn với Lựu đạn choáng, bị đánh lạc hướng bởi Gấu bông.
    • NPC "Điếc" (Visual Master): Góc nhìn siêu rộng ($FOV = 200^\circ$), miễn nhiễm hoàn toàn với âm thanh và Gấu bông, bị khống chế 5 giây bởi Lựu đạn choáng.
    • NPC "Câm" (Stealth Hybrid): Kết hợp cả hai giác quan nhưng bán kính nhỏ hơn, di chuyển hoàn toàn không phát ra tiếng động, tốc độ chậm hơn nhưng tạo áp lực tâm lý cao.

  2. Cơ chế suy luận tìm kiếm hai pha (Two-Phase Vector Search): Thay thế phương pháp tìm kiếm ngẫu nhiên thuần túy (Pure Random Wander) bằng suy luận hướng mặt kết hợp phản xạ va chạm, giúp hành vi NPC sau khi mất dấu giống với phản xạ kiểm tra góc khuất của con người hơn 40%.

  3. Tối ưu hóa tài nguyên tính toán: Giảm thiểu $35%$ chi phí CPU overhead bằng cách kết hợp điều kiện RNG với bộ đệm trạng thái FSM, chỉ kích hoạt thuật toán tìm đường đắt đỏ ($A^*$) khi trạng thái thực sự thay đổi hoặc mục tiêu di chuyển vượt ngưỡng sai số.

Ứng dụng thực tế và triển khai

Khả năng ứng dụng

  • Sản xuất Game Độc lập (Indie Game Development): Cung cấp framework AI hoàn chỉnh, dễ dàng tích hợp vào các dự án game kinh dị, hành động lén lút (Stealth Action) trên Unity.
  • Mô phỏng huấn luyện an ninh/lẩn tránh: Ứng dụng mô hình tầm nhìn LOS và trường âm thanh trong việc xây dựng môi trường huấn luyện chiến thuật mô phỏng.

Yêu cầu cấu hình triển khai (System Requirements)

Thành phần Cấu hình tối thiểu Cấu hình khuyến nghị
Hệ điều hành Windows 10 64-bit Windows 10/11 64-bit
Bộ xử lý (CPU) Intel Core i3-6100 / AMD Ryzen 3 1200 Intel Core i5-8400 / AMD Ryzen 5 2600
Bộ nhớ RAM 4 GB 8 GB Dual-Channel
Card đồ họa (GPU) NVIDIA GeForce GTX 750 Ti (2GB) NVIDIA GeForce GTX 1060 (6GB) / AMD RX 580
DirectX Version 11 Version 12
Dung lượng ổ cứng 1.5 GB còn trống 2.0 GB SSD

Hạn chế và hướng phát triển

Hạn chế kỹ thuật

  • Các mô hình 3D nhân vật hiện chưa tích hợp hệ thống khung xương động (Rigging & Skeletal Animation) để ưu tiên tối ưu hóa draw call và tốc độ khung hình cho máy cấu hình yếu.
  • Bản đồ hiện tại là một mặt phẳng đồng mức duy nhất, chưa khai thác đường đi đa tầng trong không gian 3D phức tạp (Multi-level 3D Pathfinding).

Hướng phát triển trong tương lai

  • Nâng cấp kiến trúc AI: Chuyển đổi từ FSM sang Cây hành vi nâng cao (Behavior Trees) kết hợp Hệ thống lập kế hoạch hành động theo mục tiêu (Goal-Oriented Action Planning - GOAP).
  • Hệ thống tạo map ngẫu nhiên (Procedural Level Generation): Ứng dụng thuật toán Wave Function Collapse để mỗi màn chơi có cấu trúc mê cung hoàn toàn mới.
  • Học tăng cường (Reinforcement Learning): Tích hợp Unity ML-Agents để huấn luyện NPC tự học các tuyến đường chặn đầu người chơi dựa trên kinh nghiệm từ hàng nghìn ván đấu.

Đối tượng hưởng lợi

  • Sinh viên ngành Kỹ thuật Phần mềm / Công nghệ Thông tin: Tài liệu tham khảo toàn diện về cách kết hợp lý thuyết giải thuật ($A^*$, FSM, Xác suất thống kê, Đại số vector) vào sản phẩm phần mềm thực tế.
  • Lập trình viên Game (Game Developers): Sở hữu mã nguồn mẫu và kiến trúc module hóa về hệ thống AI cảm giác (Sensory AI) có thể tái sử dụng ngay trong các dự án Unity.
  • Nhà nghiên cứu / Giảng viên: Dữ liệu thực nghiệm về mối tương quan giữa thuật toán AI kinh dị và độ khó thích ứng (Dynamic Difficulty Adjustment) đối với tâm lý người chơi.

Câu hỏi thường gặp

1. Hệ thống AI NPC này có gây tụt khung hình khi tăng số lượng NPC lên nhiều không?

Nhờ cấu trúc FSM phân tầng, các phép toán Raycast phức tạp chỉ được kích hoạt khi mục tiêu nằm trong khoảng cách giới hạn ($ROV$). Với phần cứng hiện đại, hệ thống có thể duy trì trên 60 FPS với 15-20 NPC hoạt động đồng thời trên cùng một bản đồ.

2. Thuật toán giải phóng kẹt (Abnormal Handling) có làm mất tính tự nhiên của game không?

Hoàn toàn không. Ở Kẹt Loại 1 ($< 10s$), NPC chỉ đổi hướng di chuyển mới như thể đang "đổi ý". Ở Kẹt Loại 2 ($> 10s$), việc reset vị trí có thuật toán kiểm tra tầm nhìn, đảm bảo không dịch chuyển tức thời ngay trước mắt người chơi.

3. Làm thế nào để thay đổi độ khó của trò chơi?

Độ khó có thể tùy biến dễ dàng qua 3 tham số: Tốc độ di chuyển của NPC ($v_{\text{NPC}}$), Bán kính hình cầu thính giác ($R_{\text{audio}}$) và Trọng số xác suất bảo vệ đá quý trong công thức $X$.

4. Hệ thống có hỗ trợ bản đồ có cửa mở/đóng động không?

Có. Hệ thống NavMesh và Raycast được liên kết với sự kiện tương tác cửa. Khi cửa mở hoặc đóng, trạng thái vật cản (Obstacle Layer) sẽ cập nhật ngay lập tức để NPC định tuyến lại đường đi.

5. Chi phí bản quyền và công cụ cần thiết để phát triển tiếp dự án là gì?

Toàn bộ dự án được xây dựng trên các công cụ miễn phí hoặc mã nguồn mở: Unity Personal Edition, Visual Studio Community, Figma Free Tier và các model 3D theo giấy phép Creative Commons từ Sketchfab, giúp chi phí bản quyền bằng 0.

Kết luận

Khóa luận tốt nghiệp "Nghiên cứu các thuật toán và ứng dụng phát triển game 3D với hệ thống AI NPC" đã hoàn thành trọn vẹn các mục tiêu nghiên cứu và kỹ thuật đề ra. Bằng cách kết hợp linh hoạt giữa cấu trúc Máy trạng thái hữu hạn (FSM), giải thuật tìm đường $A^*$, kỹ thuật kiểm tra tầm nhìn trực tiếp (LOS Raycasting), nhận diện thính giác theo vận tốc và thuật toán tìm kiếm suy luận không gian vector, đề tài đã chứng minh tính khả thi trong việc xây dựng một hệ thống AI NPC sống động, bất đối xứng và giàu tính thử thách. Dự án không chỉ đóng góp một giải pháp kỹ thuật hiệu quả cho dòng game kinh dị góc nhìn thứ nhất mà còn là nền tảng vững chắc để tiếp tục mở rộng sang các kiến trúc AI nâng cao trong tương lai.