Triển Khai Máy Chủ AOI

Trong các cuộc thảo luận trước đây, chúng tôi đã nhiều lần đề cập đến việc thực hiện AOI (Area of Interest). Do trò chơi vẫn đang trong giai đoạn phát triển, từng module cần được xây dựng từng bước. Ở giai đoạn đầu, khi số lượng đối tượng trong thế giới game còn ít, thuật toán O(N²) đơn giản - kiểm tra định kỳ khoảng cách giữa các đối tượng - hoàn toàn có thể đáp ứng yêu cầu. Tuy nhiên đây chỉ là giải pháp tạm thời. Trong vài ngày qua, tôi đã bắt tay vào triển khai máy chủ AOI độc lập như đã chia sẻ trên blog trước đó.

Giao thức giao tiếp giữa máy chủ cảnh quan và máy chủ AOI

Với tư cách là một tiến trình độc lập, việc thiết kế giao thức là yếu tố then chốt. Sau khi cân nhắc kỹ lưỡng, chúng tôi xác định cần 5 giao thức, trong đó 4 giao thức do máy chủ cảnh quan (scene server) gửi đến máy chủ AOI (như liệt kê dưới đây), và 1 giao thức ngược lại từ AOI server gửi về scene server:

1. Tạo đối tượng AOI mới - Đồng thời thiết lập bán kính AOI mặc định. Lưu ý: Mỗi đối tượng đều có bán kính AOI riêng. Khi các đối tượng khác lần đầu tiên bước vào phạm vi bán kính này, hệ thống sẽ kích hoạt thông báo AOI.

2. Xóa đối tượng AOI - Đồng thời có thể phát sinh thông báo “rời đi” giữa đối tượng này với các đối tượng AOI khác.

3. Cập nhật vị trí đối tượng AOI - Thiết lập tọa độ mới (2D/3D) và cung cấp giá trị vận tốc tuyến tính ước tính. Điều này giúp dự đoán chuyển động và tối ưu hóa việc kiểm tra khoảng cách.

4. Thiết lập bán kính AOI riêng biệt - Cho phép thiết lập bán kính AOI riêng giữa một đối tượng với đối tượng cụ thể khác, thay thế giá trị mặc định. Cần lưu ý rằng bán kính AOI có hai loại: bán kính vào (enter radius) và bán kính ra (leave radius). Thông thường, khi một đối tượng được tạo, hệ thống sẽ thiết lập bán kính vào cho tất cả các đối tượng khác. Khi kích hoạt thông báo AOI, logic cảnh quan sẽ điều chỉnh lại bán kính ra. Ví dụ: Bán kính mặc định là 10 mét. Khi một đối tượng mới được tạo, bất kỳ vật thể nào bước vào phạm vi 10m sẽ nhận được thông báo AOI. Sau đó, hệ thống sẽ thiết lập bán kính rời đi là 12m. Khi vật thể kia di chuyển ra ngoài 12m, thông báo rời đi sẽ được gửi, và bán kính vào sẽ được thiết lập lại.

Chi tiết triển khai

Phương pháp lưới (Grid-based Algorithm)
Đây là cách triển khai phổ biến nhất nhờ tính đơn giản và hiệu quả. Dù là lưới nhỏ (mỗi ô chỉ chứa một đối tượng) hay lưới lớn (mỗi ô là một vùng không gian, trong đó sử dụng thuật toán O(N²) để so sánh), phương pháp này đều dễ triển khai. Tuy nhiên, nó tồn tại một số hạn chế:

• Tiêu hao bộ nhớ: Kích thước lưới phụ thuộc vào quy mô cảnh quan, không liên quan đến số lượng đối tượng thực tế.
• Hiệu suất với bán kính thay đổi: Khi bán kính AOI thay đổi liên tục, phương pháp lưới cố định sẽ gặp khó khăn về hiệu suất.

Giải pháp dựa trên sắp xếp đoạn thẳng
Một đồng nghiệp từng chia sẻ ý tưởng tạo các đoạn thẳng trên 2-3 trục tọa độ cho mỗi đối tượng, sau đó thực hiện sắp xếp chèn các điểm đầu/cuối đoạn. Tuy nhiên, tôi không đi sâu vào phương pháp này do tính phức tạp của nó.

Giải pháp tối ưu hóa với bộ đếm thời gian (Timer-based Optimization)
Khi N (số lượng đối tượng) lớn, việc kiểm tra O(N²) trở nên không khả thi. Tôi đề xuất một giải pháp mới:

• Ước tính thời gian gặp nhau ngắn nhất: Dựa trên khoảng cách và vận tốc của hai đối tượng, tính toán thời gian ngắn nhất để chúng có thể tiếp cận nhau.
• Quản lý bộ đếm thời gian thông minh: Khi scene server gửi tọa độ, đồng thời cung cấp vận tốc tuyến tính ước tính. Hệ thống sẽ tính toán thời gian gặp nhau dựa trên gấp đôi vận tốc này, sau đó đăng ký bộ đếm thời gian. Nếu vận tốc thực tế không vượt quá hai lần giá trị ước tính, hệ thống sẽ bỏ qua kiểm tra khoảng cách. Ngược lại, các bộ đếm liên quan sẽ được cập nhật.

Giải pháp tiết kiệm bộ nhớ
Để giảm độ phức tạp không gian O(N²), chúng tôi áp dụng chiến lược sau:

• Thiết lập phạm vi hoạt động: Giả sử 100 mét là phạm vi hoạt động hợp lý cho đa số NPC. Nếu khoảng cách giữa hai đối tượng lớn hơn tổng 200m và bán kính AOI lớn nhất của chúng, hệ thống sẽ không theo dõi mối quan hệ này.
• Phát hiện di cư: Khi một đối tượng di chuyển vượt quá 100m so với vị trí gốc, hệ thống sẽ thực hiện kiểm tra lại toàn bộ mối quan hệ với các đối tượng khác (độ phức tạp O(N)), nhưng tần suất xảy ra thấp nên có thể chấp nhận được.

Kết luận

Khung kiến trúc AOI server này kết hợp nhiều kỹ thuật tối ưu hóa, từ phương pháp lưới truyền thống đến giải pháp dựa trên timer và quản lý bộ nhớ thông minh. Việc triển khai dự kiến mất 2-3 ngày, nhưng sẽ mang lại hiệu suất đáng kể cho các cảnh quan game quy mô lớn. Trong tương lai, chúng tôi sẽ tiếp tục nghiên cứu các phương pháp dự đoán chuyển động phức tạp hơn để further tối ưu hóa hệ thống.