Hỗ Trợ Chia Sẻ Một Phần Cấu Trúc Cây

Trong các engine đồ họa, cấu trúc cây (cây n-nhánh) là cách biểu diễn tự nhiên và phổ biến nhất cho các đối tượng. Thông thường các nút con sẽ kế thừa một số trạng thái từ nút cha như ma trận biến đổi. Khi render hoặc cập nhật, ta có thể duyệt cây theo thứ tự tiền thứ tự (pre-order traversal) để nhân các ma trận biến đổi theo cấp độ.

Trên nền tảng PC với bộ nhớ dồi dào, chi phí lưu trữ cấu trúc cây thường không đáng kể. Hầu hết các engine đồ họa đều tạo riêng một cấu trúc cây cho mỗi đối tượng render - ví dụ như GameObject trong Unity. Tuy nhiên, trong Ejoy2D, để tối ưu hóa bộ nhớ, một số trạng thái có thể chia sẻ trên nút cây (như ma trận bất biến, tọa độ texture…) đã được chuyển vào khối dữ liệu tài nguyên. Dù vậy, mối quan hệ topo của cấu trúc cây vẫn phải sao chép khi tạo mỗi sprite mới.

Với sự phát triển của công nghệ làm game, trong khi dung lượng RAM trên thiết bị di động tăng trưởng hạn chế, chi phí này ngày càng trở nên đáng kể. Trong các dự án đang phát triển, ngay cả các đối tượng render (không tính tài nguyên đồ họa như texture, model…) cũng chiếm dụng hàng chục MB bộ nhớ. Ví dụ, một đối tượng khổng lồ với hơn 2000 nút đã gây ra vấn đề nghiêm trọng về tốc độ tạo lập và tiêu hao bộ nhớ. Vì sử dụng engine tự phát triển, nhóm kỹ thuật đã thực hiện nhiều biện pháp tối ưu hóa.

Đa số các cấu trúc cây trong engine đồ họa chỉ được chỉnh sửa trong môi trường thiết kế (thêm, di chuyển, sao chép nút). Khi chạy chương trình, cấu trúc cây gần như bất biến. Cách triển khai thông thường sử dụng con trỏ để liên kết các nút, dữ liệu tài nguyên là kết quả serial hóa cấu trúc cây, quá trình tạo lập là quá trình deserial hóa xây dựng lại toàn bộ cây trong bộ nhớ. Ví dụ, Unity gọi các đối tượng cây đã thiết kế là prefab. Nếu prefab phức tạp, thời gian tải và tạo lập đối tượng từ prefab sẽ rất tốn kém.

Một giải pháp tối ưu là thay thế con trỏ bằng ID hoặc offset trong khối dữ liệu tài nguyên. Điều này cho phép tải nguyên khối prefab từ file tài nguyên, các đối tượng chỉ cần trỏ đến vùng nhớ tương ứng mà không cần xây dựng lại. Ejoy2D hiện đang áp dụng phương pháp này, giúp giảm 10MB+ bộ nhớ runtime cho một dự án. Ngoài ra, tài nguyên có thể được giải phóng khỏi bộ nhớ khi không dùng và tải lại khi cần, không lo thay đổi địa chỉ.

Tuy nhiên, để các đối tượng game có thể chia sẻ trực tiếp prefab, vấn đề cốt lõi là: hầu hết đối tượng đều cần chỉnh sửa cấu trúc cây, trong khi topo của prefab không ánh xạ trực tiếp vào bộ nhớ.

Xét vấn đề ánh xạ: Trong Ejoy2D, cấu trúc đối tượng trong tài nguyên (prefab) thực chất là đồ thị có hướng không chu trình (DAG). Ví dụ, một ngôi nhà có treo 3 chiếc đèn lồng, trong tài nguyên chỉ có 1 đối tượng đèn lồng được tham chiếu 3 lần. Khi chạy chương trình, 3 đèn lồng phải là 3 đối tượng độc lập để chỉnh sửa thuộc tính riêng biệt (màu sắc, tần suất đung đưa…). Do đó, khi khôi phục prefab vào bộ nhớ, dữ liệu trạng thái của đèn lồng phải được nhân bản thành 3 bản độc lập.

Xét vấn đề chỉnh sửa: Trong runtime, nhiều nút trên cây prefab có thể bị thay đổi thuộc tính. Ví dụ, một kho hàng trong game có hàng hóa được quyết định lúc chạy chương trình. Trong dự án Momo Chiến Tranh, trạng thái hàng hóa được thiết kế bằng nhiều khung hình ảnh, runtime có thể chọn khung hiển thị để biểu thị mức tồn kho. Nếu hàng hóa cần biểu diễn thực tế, chức năng gắn kết (mount) sẽ được dùng để gắn đối tượng hàng hóa vào điểm gắn trên prefab kho hàng.

Do những yêu cầu phức tạp này, Ejoy2D và các engine khác thường tạo lập đối tượng game bằng cách xây dựng lại toàn bộ cây từ prefab. Khi tạo một sprite từ tài nguyên, bạn sẽ thấy các đối tượng Lua được tạo lập từng tầng. Tuy nhiên, runtime hầu như không chỉnh sửa thuộc tính của đa số đối tượng, mà chỉ dùng dữ liệu có sẵn trong prefab - gây lãng phí không cần thiết. Với cấu trúc cây đơn giản, lãng phí này có thể chấp nhận được, nhưng với dự án mới sử dụng Ejoy2D, khi công cụ hoàn thiện, các cấu trúc phức tạp ngày càng gia tăng, nhóm phát triển đã dành hơn nửa năm để tối ưu vấn đề này.

Gần đây, tôi nhận ra bản chất vấn đề là: Nếu có một cấu trúc cây phức tạp (gọi là bản thiết kế - blueprint), liệu có thể tạo nhiều bản sao dựa trên nó, mỗi bản chỉ chỉnh sửa một phần nhưng chia sẻ phần chưa thay đổi?

Các phương án khả thi:

1. Dự trữ con trỏ trên mỗi nút blueprint trỏ đến danh sách sửa đổi. Khi bản sao chỉnh sửa nút nào, thêm thuộc tính đã sửa vào danh sách đó. Nếu blueprint có nút được tham chiếu nhiều lần (như đèn lồng trong ví dụ), khi sửa phải nhân bản (copy-on-write).
2. Cải tiến phương án 1 bằng cách chỉ dự trữ một khe nhớ, lưu trữ sửa đổi trong đối tượng bản sao. Trước khi duyệt cây, ghi đè sửa đổi vào blueprint, sau đó dọn dẹp hoặc đánh dấu bản sao để bỏ qua sửa đổi không liên quan.
3. Dùng bảng băm (hash table) trong bản sao để lưu trữ sửa đổi. Khi duyệt blueprint, tra bảng băm để tìm thuộc tính đã sửa.
4. Khi sửa nút nào, sao chép một phần cây chỉ chứa nút đó và tổ tiên, các nhánh chưa sửa sẽ trỏ về blueprint gốc. Duyệt trên cây con đã sao chép.

Hiện tại, dự án đang dùng phương án 1, nhưng cấu trúc dữ liệu phức tạp hơn nhiều, phát sinh nhiều lỗi. Tôi đang nghiên cứu cải tiến