Xử Lý Dữ Liệu Liên Kết Đồng Loại Trong ECS

Anonymous trong Tin Tức Mới Nhất và Dữ Liệu Lớn

2021-11-01 Khoảng 1200 từ 6 phút

Như đã trình bày trong bài viết trước về mô hình xử lý dưới ECS, thách thức lớn nhất của mô hình ECS nằm ở việc xử lý các thành phần (component) đồng loại có mối liên hệ tương hỗ với nhau.

Dữ liệu lý tưởng nhất cho ECS xử lý là những dữ liệu độc lập hoàn toàn, mỗi đơn vị dữ liệu không có bất kỳ mối liên hệ nào với đơn vị khác. Khi nhiều đơn vị dữ liệu có mối liên hệ cố hữu, chúng ta có thể coi chúng là các thành phần khác nhau thuộc cùng một thực thể (entity), từ đó tận dụng khái niệm entity để quản lý. Trong trường hợp này, chúng ta vẫn có thể lặp qua các dữ liệu theo thứ tự cố định.

Tuy nhiên, trong các hệ thống phức tạp, việc các dữ liệu đồng loại liên kết với nhau là điều không thể tránh khỏi. Ví dụ điển hình là trong quản lý cảnh quan 3D, các nút (node) có quan hệ cha-con với nhau. Quá trình tính toán trạng thái không gian của các nút đòi hỏi thứ tự lặp dữ liệu cụ thể, đồng thời cần truy cập trạng thái của nút cha. Đây chính là bài toán hóc búa mà các framework ECS cần giải quyết.

Trong suốt một năm qua, tôi đã thử nghiệm nhiều phương pháp khác nhau để giải quyết vấn đề này:

Giải pháp đầu tiên là sử dụng một thành phần đặc biệt, được thiết kế để tồn tại độc lập như một entity vĩnh viễn, không bao giờ bị xóa nhưng có thể tái sử dụng. Thành phần này cung cấp một ID duy nhất, các entity khác sẽ dùng ID này để tham chiếu.

Ưu điểm của giải pháp này là chi phí xử lý bổ sung không cao, giao diện đơn giản, phù hợp với lập trình C nguyên thủy. Trong Lua, chỉ cần mở rộng cú pháp select một chút là có thể kiểm soát hiệu quả.

Tuy nhiên nhược điểm cũng rất rõ ràng: quản lý vòng đời của các thành phần này đòi hỏi nhiều mã nguồn và thiết kế phức tạp để đảm bảo tính chính xác. Việc sử dụng giải pháp này giống như thao tác con trỏ thô (raw pointer) trong C mà không có bất kỳ cơ chế quản lý nào.

Giải pháp thứ hai mà tôi thử nghiệm chỉ phù hợp với giao diện Lua. Cụ thể là sử dụng một bảng Lua (lua table) làm đối tượng tham chiếu trong entity, với trạng thái được đồng bộ hóa bởi framework底层. Đối tượng này được thiết kế như một tham chiếu yếu (weak reference), khi entity bị xóa, tham chiếu yếu sẽ nhận biết và báo lỗi khi có yêu cầu giải tham chiếu.

Giải pháp này mang tính tổng quát hơn, nhưng chỉ phù hợp với tầng Lua và có chi phí xử lý nhất định.

Giải pháp gần đây nhất mà tôi đang áp dụng có cách tiếp cận hoàn toàn khác. Thay vì chia sẻ cùng một bản sao dữ liệu giữa các module, tôi tạo ra một bản sao dữ liệu liên kết riêng biệt nằm ngoài framework ECS, đồng thời giữ một bản sao khác trong framework. Hai bản sao này đều chứa cùng một ID để liên kết truy vấn.

Lấy ví dụ thực tế, gần đây tôi đang phát triển một trò chơi mô phỏng hệ thống ống dẫn chất lỏng tương tự Factorio. Trong hệ thống này, dòng nước không có hướng cố định mà thay đổi theo áp suất và động lượng của từng đoạn ống. Thuật toán tham khảo từ nhật ký phát triển của Factorio yêu cầu thực hiện sắp xếp topo toàn bộ các đoạn ống, xử lý theo hướng ngược lại với chiều dòng chảy. Điều này là cần thiết vì dung tích ống có hạn - phải để nước chảy ra ở hạ nguồn trước rồi mới cho nước vào ở thượng nguồn. Khó khăn nhất là các đoạn ống phân nhánh, nơi dòng nước có thể hội tụ từ nhiều nguồn hoặc phân tán sang nhiều nhánh, đòi hỏi phân bổ theo tỷ lệ dựa trên trạng thái lân cận toàn cục để tránh tình trạng “một số ống bình đẳng hơn các ống khác” trong thực thi dù chúng đều bình đẳng về quy tắc.

Tôi thiết kế toàn bộ mạng lưới ống dẫn như một hệ thống độc lập bên ngoài ECS. Mỗi đoạn ống đều có một ID duy nhất, trong khi thành phần quản lý ống trong ECS chỉ chứa lượng nước và ID, không lưu trữ thông tin khác. Từ góc nhìn ECS, các đoạn ống hoàn toàn độc lập, có thể thêm/bớt nước cho từng đoạn riêng lẻ. Tuy nhiên, quá trình lưu thông chất lỏng lại được xử lý bởi module mạng ống riêng biệt. Việc đồng bộ mực nước chỉ cần thực hiện mỗi frame.

Quy trình xử lý từ phía ECS như sau:

Đồng bộ thông tin bơm nước và tiêu thụ nước từ các máy móc sang mạng ống thông qua ID.
Cập nhật trạng thái mạng ống (tính toán dòng chảy).
Lặp qua tất cả các đoạn ống, lấy mực nước hiện tại từ mạng ống thông qua ID và cập nhật vào thành phần tương ứng.

Đặc biệt, mạng ống cần duy trì một thứ tự sắp xếp topo mỗi frame để đảm bảo cập nhật đúng chiều dòng chảy. May mắn là trong thực tế, một khi dòng chảy ổn định, thứ tự này hầu như không thay đổi (trừ khi có dòng chảy ngược). Ngay cả khi có thay đổi, chúng cũng diễn ra rất nhỏ giọt và dần dần. Thuật toán này quá phức tạp để triển khai trong ECS, vì framework này chỉ tối ưu cho việc lặp dữ liệu theo thứ tự cố định, không hỗ trợ truy cập ngẫu nhiên hiệu quả.

Chúng tôi không cần duy trì một bảng ánh xạ ID để đồng bộ giữa hai hệ thống. Lý do là khi thứ tự được xác định, trong bước 1, các máy bơm và thiết bị tiêu thụ nước gần như luôn nằm ở hai đầu đối lập của mạng ống đã được sắp xếp. Điều này cho phép đạt được độ phức tạp gần O(1). Trong bước 3, vì thứ tự lặp của ECS luôn cố định (theo thứ tự tạo đối tượng), module mạng ống có thể tối ưu để truy vấn các ID theo trình tự liên tục, đảm bảo chi phí gần như O(1) cho mỗi truy vấn.