Bí mật đằng sau NPC Game: Thiết kế và thực hiện hệ thống AI trong MMORG

[Trần Cường]

Trần Cường

Theo tin tức ngày 30/07 của Youxiguancha, ở trong game chúng ta không chỉ có 1 loại thuật toán tìm đường, nói chung, trước tiên xem thử trực tiếp tìm đường có thể đến đích không, nếu có thể đến thì trực tiếp trở về, nếu thất bại, lại thử tìm 1 con đường phức tạp hơn, lần lượt đi thử các cách như tìm đường tham lam, tìm đường A*, tìm đường lưới điều hướng..., cho đến khi tìm thấy con đường có thể đi đến đích.  AI trong game MMORPG, không phải là chỉ trí tuệ nhân tạo theo nghĩa rộng, mà là chỉ NPC ở trong game có thể thông qua sự thay đổi của môi trường hoặc sự việc để tiến hành phán đoán logic, từ đó sinh ra hành vi tương tác cụ thể với người chơi. Nó chủ yếu bao gồm 3 phần, lần lượt là nhận biết, quyết sách, hành động. Nhận biết: là chỉ khả năng phát hiện sự thay đổi của môi trường xung quanh, ví dụ như người chơi bước vào trong tầm nhìn, bị tấn công…; Quyết sách: là suy nghĩ đưa ra phản hồi nào đó dựa vào sự thay đổi của môi trường, là bộ phận cấu thành chủ yếu của toàn bộ khung AI, thường gặp có máy trạng thái (state machine), cây hành vi (behavior tree); Hành động: tức là phản hồi cụ thể của NPC, ví dụ như thao tác thi triển kỹ năng, tìm đường… AI MMORPG là được xây dựng dựa trên 4 tính năng cơ bản tìm đường, di chuyển, kỹ năng, tầm nhìn. Tìm đường, di chuyển và kỹ năng thuộc về hành động, còn tầm nhìn là 1 loại nhận biết. **3 cách thực hiện thường thấy trong AI** **01. AI-Hard Code đơn giản** Lấy 1 ví dụ thường gặp ở trong game, 1 con lợn rừng khi không có người thì phải tự động tuần tra; Khi có người lọt vào tầm nhìn thì nó phải tiếp cận người chơi này; Khi khoảng cách giữa nó và người chơi đạt đến 2m, nó phải thi triển 1 kỹ năng; Khi huyết lượng của nó thấp hơn 20%, nó sẽ chạy trốn. Với sự phát triển game càng ngày càng sâu, NPC càng ngày càng nhiều, ví dụ hươu nhỏ không tấn công mà chỉ biết chạy, sói sẽ không chạy nhưng sẽ thi triển kỹ năng.  Lúc này vấn đề đã xuất hiện, chúng ta nếu thực hiện 1 AI riêng cho mỗi một NPC, một tựa game có thể có hàng ngàn loại NPC, khối lượng công việc sẽ rất lớn, hơn nữa còn rất khó để mở rộng và duy trì. Nhưng AI đơn giản, trực tiếp, hiệu suất cao thì thường sử dụng ứng phó ở giai đoạn đầu của dự án, tức là ban đầu khi dự án ra mắt, không có thời gian, không có khả năng làm AI thì có thể viết 1 AI đơn giản dùng để test. **02. Máy trạng thái (Finite-state machine, FSM)** Máy trạng thái có thể quy nạp thành 3 yếu tố, tức là trạng thái, sự kiện và hành động hiện tại. Khi xảy ra một sự kiện, sẽ kích hoạt một hành động, hoặc thực hiện 1 lần chuyển đổi trạng thái.  Máy trạng thái có 3 khuyết điểm: Thứ nhất là hình quy trình trạng thái quá phức tạp, rất khó duy trì; Thứ hai là khó mở rộng, khi thêm trạng thái mới cần suy nghĩ quan hệ giữa các trạng thái hiện tại; Thứ ba là kế hoạch không thể bổ sung tham gia đầy đủ, chỉ có thể do lập trình viên hoàn thành, điều này sẽ tăng thêm lượng công việc cho lập trình viên. **04. Cây hành vi (Behavior tree)** Trong cây hành vi có 1 root node, nhiều child node. Node chủ yếu phân thành node điều khiển, node điều kiện và node hành vi. Node điều kiện và Node hành vi khi thực hiện đều có 1 kết quả, thành công, thất bại hoặc đang vận hành, node điều khiển dựa vào kết quả trả về thực hiện hành động bước tiếp theo.  Ưu điểm của cây hành vi là trực quan logic, vừa xem là hiểu ngay, kế hoạch có thể trực tiếp cài đặt nhờ vào công cụ, không cần chương trình can thiệp. Còn khuyết điểm là số lượng nhánh cây rất lớn, quá trình mỗi lần tìm node thích hợp tiêu hao quá lớn. **4 CÁCH THỰC HIỆN TÌM ĐƯỜNG AI** 　　**01. Tìm đường theo đường thẳng** Tìm đường theo đường thẳng là đơn giản nhất, thuật toán tạo đường thẳng thường hay sử dụng đều có thể dùng được, nhưng cũng rất dễ thất bại, bởi vì toàn bộ bản đồ của chúng ta không phải là 1 đồng bằng lớn, nó có thể có đủ loại chướng ngại. 　　**02. Tìm đường tham lam (greedy pathfinding)** Chiến lược của tìm đường tham tham là mỗi lần đều tiếp cận từng bước theo phương hướng khoảng cách khá gần, nếu 1 phương hướng nào đó không thể đi, thì thử phương hướng khác. Thật ra nó vẫn chưa đủ thông minh, khi nó gặp chướng ngại, nó có thể phải đi vòng rất xa, hoặc phải mất một thời gian rất dài mới có thể thật sự tìm thấy con đường của nó. 　　**03. Tìm đường A*** Tìm đường A* khi bắt đầu từ 1 điểm bất kỳ, đưa mấy điểm xung quanh nó vào trong bảng open, sau đó từ trong bảng open lấy ra điểm có hàm số nhỏ nhất, đồng thời cập nhật bảng open và bảng close. Bảng close trong đó có trách nhiệm lưu trữ điểm đã được khảo sát, bảng open lưu trữ điểm đã tạo ra nhưng chưa khảo sát. Hàm số đánh giá: f(n)=g(n)+h(n) g(n) là giá từ điểm khởi đầu cho đến điểm hiện tại; h(n) là giá từ điểm hiện tại đến điểm cuối. **04. Tìm đường lưới điều hướng**  Bản đồ đồng bằng lớn được tạo thành từ rất nhiều ô vuông nhỏ, nếu khi tìm đường, cần phải đi qua mỗi ô vuông nhỏ, vậy sẽ lãng phí rất nhiều thời gian cho việc tính toán mỗi ô vuông này. Vào lúc này, có thể cho lưới điều hướng được xử lý trước, cắt đồng bằng lớn trên bản đồ thành 1 hình đa giác lồi. Trong hình đa giác này, sẽ liên kết tổ chức các kết cấu số liệu nhất định, và ở trong hình đa giác này sẽ lại thông qua A* để tìm đường, như vậy có thể cùng lúc bỏ qua rất nhiều ô, 1 lần có thể tìm thấy đích đến. Ở trong game chúng ta không chỉ có 1 loại thuật toán tìm đường, nói chung, trước tiên xem thử trực tiếp tìm đường có thể đến đích không, nếu có thể đến thì trực tiếp trở về, nếu thất bại thì lại thử tìm 1 con đường phức tạp hơn, lần lượt đi thử các cách như tìm đường tham lam, tìm đường A*, tìm đường lưới điều hướng..., cho đến khi tìm thấy con đường có thể đi đến đích.