Thêm Chức Năng Phân Nhóm Cho ECS

Hiện tại, chúng ta đang sử dụng ECS để quản lý các đối tượng trong engine game. Khi kích thước cảnh game mở rộng đến một mức độ nhất định, việc thiết lập một cơ chế để lọc nhanh các đối tượng cần render trở nên cực kỳ quan trọng. Nói cách khác, nếu bạn tạo ra 100.000 Entity nhưng chỉ có 1.000 Entity cần được render đồng thời, hiệu năng sẽ phụ thuộc vào việc bạn xử lý ở cấp độ O(n) với n=100.000 hay n=1.000 – sự khác biệt là rất rõ rệt.

Hệ thống ECS hiện tại hỗ trợ tính năng “tag”, cho phép sử dụng visible tag làm khóa chính để lọc nhanh các đối tượng có thể nhìn thấy. Tuy nhiên, khi camera di chuyển, việc cập nhật lại các tag này có thể gây ra vấn đề hiệu năng. Vậy làm thế nào để tránh phải xử lý ở cấp độ O(n) với n=100.000 khi reset các visible tag?

Một giải pháp đầu tiên được nghĩ đến là phân nhóm Entity. Ví dụ, trong những cảnh game quy mô lớn, chúng ta có thể chia nhỏ theo khu vực (block) và đánh nhóm. Dựa vào vị trí camera, hệ thống có thể nhanh chóng xác định được nhóm nào cần quan tâm và nhóm nào có thể bỏ qua.

Ban đầu, tôi từng cân nhắc việc sử dụng nhiều “world” để mô tả toàn bộ cảnh game – mỗi world đại diện cho một nhóm, lưu trữ các Entity theo vị trí địa lý. Tuy nhiên giải pháp này tồn tại nhược điểm rõ ràng: một số giai đoạn render yêu cầu xử lý tập trung, như tạo Z Buffer ở giai đoạn PreZ hoặc xử lý hiệu ứng không gian màn hình ở giai đoạn hậu xử lý – đòi hỏi phải tương tác giữa nhiều nhóm.

Do đó, tôi quyết định lựa chọn phương án thêm trường group id vào Entity. Nếu xem ECS như một cơ sở dữ liệu trong bộ nhớ, yêu cầu của chúng ta chính là khả năng truy vấn với điều kiện “where” – lọc nhanh các Entity thuộc về một tập hợp group id nhất định. Chi phí để lọc các Entity đáp ứng điều kiện phải tỷ lệ thuận với số lượng các Entity đó, chứ không phải tổng số Entity trong toàn bộ world.

Chỉ khi đạt được điều này, hệ thống mới đủ khả năng xử lý các cảnh game quy mô lớn mà không làm ảnh hưởng đến hiệu năng render khi số lượng đối tượng tăng lên.

Tôi mong muốn chức năng phân nhóm này giữ được tính phi xâm nhập (non-intrusive) đối với các tính năng hiện có của ECS – tức là không làm thay đổi cấu trúc dữ liệu đã tồn tại. Khi không sử dụng phân nhóm (ví dụ trong cảnh nhỏ), hệ thống phải vẫn vận hành ổn định như ban đầu.

Dựa trên tiêu chí này, tôi đã thiết kế một cấu trúc dữ liệu như sau:
Mỗi Entity có thể lựa chọn (hoặc nhiều) chỉ mục nhóm. Trường group id chỉ được thiết lập khi tạo Entity và không thể thay đổi sau đó. Quá trình xây dựng sẽ duy trì chỉ mục này dựa trên group id.

Cấu trúc chỉ mục bao gồm 4 trường:

1
2
3
4

uint64_t uid;
uint64_t lastid;
uint32_t groupid;
uint32_t next;

Trong đó:

• uid là ID tự tăng 64-bit, đảm bảo mỗi Entity có một định danh duy nhất khi được tạo
• groupid là mã nhóm mà Entity thuộc về
• lastid trỏ đến đối tượng cùng nhóm đứng trước trong mảng chỉ mục
• next mô tả độ lệch tương đối trong mảng chỉ mục so với Entity cùng nhóm kế tiếp

Cấu trúc này được lưu trữ dưới dạng mảng liên tục như một component thông thường. Vì uid tăng dần đơn điệu và chỉ được thiết lập duy nhất lúc khởi tạo Entity, nên các phần tử trong mảng chỉ mục sẽ có uid được sắp xếp theo thứ tự tăng nghiêm ngặt.

Hệ thống chỉ mục này tự động phân chia các Entity thành nhóm thông qua khóa uid/lastid. Trường next giúp duyệt nhanh các Entity cùng nhóm dựa trên vị trí trong mảng. Khi Entity chưa bị xóa, next sẽ tạo thành một danh sách liên kết giúp duyệt nhóm hiệu quả, đồng thời lastid đảm bảo kiểm tra chéo chính xác.

Trong trường hợp Entity bị xóa, chúng ta không cần cập nhật lại toàn bộ danh sách liên kết ngay lập tức. Khi duyệt lại, next có thể trỏ đến vị trí sai, nhưng lastid sẽ giúp phục hồi nhanh chóng vì Entity đúng sẽ nằm gần vị trí hiện tại.

Với cấu trúc chỉ mục này, hệ thống có thể duyệt nhanh các Entity trong cùng nhóm để đánh dấu tag. Sau đó, các tag này sẽ được sử dụng để truy vấn bình thường. Trong cảnh game quy mô lớn, việc chia nhóm theo khu vực địa lý kết hợp với vị trí camera cho phép tính toán nhanh các nhóm cần render, từ đó tạo ra visible tags một cách hiệu quả.

Ngoài ứng dụng trong render, chức năng phân nhóm còn có thể dùng để xóa hàng loạt các Entity không cần giữ lại trong bộ nhớ – chỉ cần lọc theo groupid rồi tiến hành xóa đồng loạt.

Toàn bộ cải tiến này đã được thể hiện trong commit này.