Ghi Chú Phát Triển (13): Thiết Kế Và Triển Khai Dịch Vụ AOI

Trong buổi họp sáng nay sau khi thống nhất kế hoạch công việc, tôi nhận ra đã đến lúc bắt tay vào triển khai mô-đun AOI.
Khái niệm AOI (Area of Interest) có hai ứng dụng chính trong hệ thống:

Ứng dụng thứ nhất: Giải quyết vấn đề kích hoạt AI của NPC. Trong bối cảnh game có hàng trăm NPC (gấp 10 lần số lượng nhân vật điều khiển bởi người chơi - PC), điều kiện kích hoạt trí tuệ nhân tạo thường dựa vào khoảng cách với các đối tượng khác. Nếu không có mô-đun AOI, mỗi NPC sẽ phải quét toàn bộ đối tượng trong cảnh để tính khoảng cách - thuật toán có độ phức tạp O(N*N). Chúng tôi sẽ xây dựng một mô-đun AOI độc lập để tối ưu hóa quá trình so sánh, đồng thời thông báo qua tin nhắn khi hai đối tượng tiếp cận trong phạm vi nhất định.

Ứng dụng thứ hai: Giảm lượng thông tin đồng bộ gửi về PC. Những đối tượng ở xa sẽ bị lọc trạng thái thay đổi, trong khi PC duy trì một danh sách các đối tượng lân cận. AOI sẽ đảm nhiệm việc cập nhật danh sách này thông qua cơ chế thông báo sự kiện.

Kiến trúc dịch vụ AOI

Trên máy chủ, chúng tôi khuyến nghị tách riêng mô-đun AOI thành một dịch vụ độc lập. Cảnh game sẽ cập nhật tọa độ đối tượng cho AOI, ngược lại AOI sẽ gửi các sự kiện tương ứng về cho cảnh.

Ba phương pháp triển khai cổ điển

1. Phương pháp ngây thơ: So sánh định kỳ khoảng cách giữa tất cả các đối tượng. Ưu điểm dễ triển khai, phù hợp kiểm tra giao thức, nhưng kém hiệu quả với số lượng đối tượng lớn.
2. Kỹ thuật chia lưới không gian: Chia cảnh thành các ô vuông đều, mỗi ô duy trì danh sách đối tượng. Khi đối tượng di chuyển qua ô khác, hệ thống cập nhật danh sách. Ưu điểm hiệu suất tốt hơn do giảm phạm vi so sánh, nhưng tốn bộ nhớ và không phù hợp với bản đồ quá rộng. Có thể tối ưu bằng cách sử dụng lưới lục giác.
3. Danh sách liên kết tứ phương (thêm chiều cho không gian 3D): Theo dõi các đoạn thẳng và kích hoạt sự kiện khi di chuyển. Thuật toán phức tạp nhưng linh hoạt với nhiều bán kính AOI khác nhau.

Thiết kế API mới

Sau khi cân nhắc kỹ lưỡng, tôi quyết định đơn giản hóa thiết kế trước đây bằng các quyết định trọng yếu:

• Chỉ hỗ trợ AOI bán kính cố định
• Chỉ gửi thông báo khi vào vùng quan tâm, không thông báo khi rời đi
• Phân loại đối tượng thành Watcher (người quan sát) và Marker (đối tượng bị quan sát), một đối tượng có thể đồng thời là cả hai

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

typedef void* (*aoi_Alloc)(void* ud, void* ptr, size_t old_sz, size_t new_sz);
typedef void (aoi_Callback)(void* ud, uint32_t id1, uint32_t id2);

struct aoi_space;
struct aoi_space* aoi_create(aoi_Alloc alloc, void* ud, float radius);
void aoi_release(struct aoi_space*);

// Cập nhật trạng thái đối tượng
// mode: "w" (chỉ Watcher), "m" (chỉ Marker), "wm" (cả hai), "d" (xóa đối tượng)
void aoi_update(struct aoi_space* space, uint32_t id, const char* mode, float pos[3]);

// Gửi sự kiện AOI
void aoi_message(struct aoi_space* space, aoi_Callback cb, void* ud);

Giải thích logic trạng thái

Mỗi tick, hệ thống phân loại trạng thái của đối tượng thành:

1. Static (tĩnh): Không thay đổi tọa độ từ tick trước
2. Shift (vi dịch): Di chuyển trong phạm vi bán kính/2
3. Move (vận động): Di chuyển vượt ngưỡng bán kính/2 hoặc lần đầu xuất hiện

Cơ chế xử lý sự kiện

1. Cập nhật trạng thái:

   • Thêm đối tượng mới vào tập Move new
   • Đánh dấu drop với các đối tượng cần xóa
   • Cập nhật trạng thái dựa trên khoảng cách di chuyển

2. Xử lý tập hợp:

   • So sánh các đối tượng trong tập Shift new với các tập Static, Shift và chính nó
   • So sánh tập Move new với tất cả các tập hợp để tạo cặp Hotspot (đối tượng cần kiểm tra)

3. Quản lý Hotspot:

   • Xóa cặp Hotspot nếu khoảng cách > bán kính
   • Giữ lại cặp Hotspot nếu khoảng cách < bán kính chờ xử lý ở tick sau

Ưu điểm của giải pháp

• Các đối tượng ở trạng thái Static hoặc Shift không nằm trong vùng quan tâm sẽ không bị kiểm tra
• Giảm đáng kể số lần tính toán khoảng cách nhờ phân loại trạng thái
• Cấu trúc dữ liệu đơn giản (mảng một chiều và danh sách liên kết đơn) thay vì danh sách liên kết đôi phức tạp

Cải tiến trong quá trình triển khai

• Tối ưu hóa bằng cách gộp tập Static và Shift thành một
• Sử dụng bộ nhớ đệm cố định thay vì cấp phát động để giảm fragmentation
• Xây dựng công cụ kiểm thử đồ họa trực quan do bạn V hỗ trợ

Kế hoạch tiếp theo

• Hoàn thiện mã nguồn trên GitHub trong tuần này
• Tối ưu hóa bộ phân bổ bộ nhớ tùy chỉnh
• Kiểm tra độ chính xác của logic xử lý sự kiện

!Hình minh họa AOI

Mặc dù thuật toán có độ phức tạp cao, nhưng nhờ cách phân loại trạng thái thông minh, hệ thống có thể xử lý hàng ngàn đối tượng đồng thời với hiệu suất tối ưu. Tôi tin tưởng đây sẽ là một giải pháp nền tảng vững chắc cho các hệ thống game quy mô lớn.