Tham Chiếu Đối Tượng Trong ECS

Trong hệ thống ECS, việc các Entity phải tham chiếu lẫn nhau là điều khó tránh khỏi. Bản thân tôi khi áp dụng mô hình ECS luôn khuyến khích việc sử dụng tham chiếu. Vì vậy, tôi đã xây dựng các giải pháp tương ứng cho nhiều mẫu tham chiếu phụ thuộc phổ biến.

Trong phiên bản phát triển gần đây của luaecs, chúng tôi giới thiệu một cơ chế tham chiếu ở tầng Lua: khi tạo Entity, có thể chỉ định một bảng (table) làm tham chiếu cho đối tượng đó. Hệ thống sẽ tự động cập nhật bảng này để duy trì trạng thái hợp lệ (giống như bộ lặp trong quá trình select). Nhờ đó, tầng nghiệp vụ có thể đồng bộ dữ liệu từ Entity bất kỳ lúc nào thông qua tham chiếu này.

Tuy nhiên, tôi chưa bao giờ thực sự hài lòng với giải pháp này và luôn tìm kiếm phương án thay thế. “Niệm niệm bất vong, tất hữu hồi hưởng” - như một lời hồi đáp, hôm qua tôi đã thử nghiệm một phương án mới khả dĩ hơn.

Phương án cũ có hiệu quả nhất định khi đa số Entity sau khi tạo ra không cần duy trì tham chiếu ở tầng nghiệp vụ. Nếu chúng ta dành sẵn tham chiếu cho mọi Entity thì tính tùy chọn của thành phần này sẽ bị vô hiệu hóa. Vấn đề nằm ở chỗ: việc quyết định có nên tạo tham chiếu ngay từ đầu rất khó khăn trong thực tiễn phát triển.

Một điểm cần lưu ý: việc tìm kiếm nhanh giữa các thành phần anh em có độ phức tạp O(log N) vì các thành phần cùng loại được sắp xếp theo ID có thứ tự và dùng thuật toán tìm kiếm nhị phân. Tuy nhiên, luaecs đã tối ưu đặc biệt cho việc duyệt tuần tự, khiến độ phức tạp trong vòng lặp select gần như đạt O(1).

Ngược lại, quá trình từ tham chiếu tìm đến các thành phần khác của Entity lại mang tính truy cập ngẫu nhiên, không thể áp dụng chiến lược tối ưu tương tự. Việc tối ưu độ phức tạp O(1) cho quá trình định vị Tag dùng để chọn lọc từ tham chiếu thực tế không mang lại nhiều ý nghĩa.

Khác biệt hoàn toàn với phương án cũ, giải pháp mới hoàn toàn phi xâm nhập (non-intrusive), không thay đổi bất kỳ cấu trúc dữ liệu nào hiện có trong luaecs world. Mô hình này gần giống với cơ sở dữ liệu trong bộ nhớ - chúng ta có thể chọn một thành phần cụ thể làm khóa (key) và xây dựng cấu trúc chỉ mục (index) bổ sung cho nó. Cấu trúc này bản chất là một dạng cache, cho phép xóa bỏ hoàn toàn khi thực hiện lưu trữ lâu dài (persistence) trên ECS world. Đồng thời, có thể tạo nhiều chỉ mục khác nhau cho nhiều khóa khác nhau.

Khóa dùng để tạo chỉ mục bắt buộc phải là kiểu số nguyên. Cấu trúc chỉ mục được xây dựng dưới dạng bảng băm (hash table). Khi cần tham chiếu Entity, người dùng chỉ cần thêm một thành phần chứa ID duy nhất cho Entity, sau đó lưu lại ID này. Khi cần giải tham chiếu (dereference), dùng ID để truy vấn bảng băm và xây dựng bộ lặp truy cập Entity.

Lần đầu tiên giải tham chiếu, hệ thống sẽ dùng thuật toán duyệt O(n) để tìm Entity tương ứng và ghi nhớ vị trí của nó. Các lần sau không cần xây dựng lại bộ lặp này. Kích thước cache cố định, khi xảy ra va chạm băm (hash collision), bản ghi cũ sẽ bị ghi đè. Do dữ liệu trong luaecs có thể bị di chuyển khi xóa Entity, mỗi lần lấy bộ lặp hệ thống đều thực hiện kiểm tra hai lần - nếu bản ghi cũ không còn hiệu lực sẽ tự động hiệu chỉnh lại.

Giải pháp này được tối ưu dựa trên những nguyên lý sau:

1. Chúng ta có thể tự do duy trì tham chiếu cho mọi Entity chỉ bằng cách lưu lại bất kỳ ID nào. Tuy nhiên, tần suất giải tham chiếu thực tế rất thấp - chỉ một số ít trường hợp cần tìm lại Entity thông qua tham chiếu đã lưu. Các thao tác thường xuyên vẫn nên thực hiện trong vòng lặp select, tức là xử lý hàng loạt mối quan hệ giữa các đối tượng.

2. Đối với các tham chiếu được sử dụng thường xuyên, quá trình giải tham chiếu phải đủ nhanh; với các tham chiếu dự phòng, hiệu suất thấp hơn có thể chấp nhận được. So với tổng số Entity, số lượng mối quan hệ giữa các Entity thường dùng luôn ở mức thấp.

3. Nếu một Entity cần duy trì tham chiếu sau khi tạo, thời điểm giải tham chiếu lần đầu thường rất sớm (chỉ có vài Entity được tạo giữa lúc tạo và giải tham chiếu). Nói cách khác, nếu bạn lưu một tham chiếu nhưng càng lâu không dùng đến, khả năng sử dụng nó càng thấp.

Điểm cuối cùng này đặc biệt phù hợp với thực tiễn sử dụng trong dự án của tôi: đa số các thao tác giải tham chiếu xảy ra trong quá trình tạo hàng loạt Entity.

Trong quá trình triển khai, chúng tôi áp dụng một tối ưu đơn giản: khi duyệt tìm Entity theo ID, hệ thống sẽ thực hiện theo thứ tự ngược với thứ tự tạo. Mặc dù độ phức tạp vẫn là O(n), nhưng khả năng tìm thấy sẽ nhanh hơn. Đồng thời, khi dữ liệu Entity bị di chuyển do xóa Entity khác (dẫn đến bộ lặp cũ失效), việc tìm vị trí mới chỉ cần quét ngược về phía trước từ vị trí ban đầu, vì toàn bộ quá trình di chuyển luôn diễn ra theo hướng tiến.