Quản Lý Cấu Trúc Phân Cấp Cảnh Game
Vài tháng đầu năm nay, tôi đã có ý định ghi chép lại thiết kế mô-đun quản lý cấu trúc phân cấp cảnh trong engine game của chúng tôi. Mỗi lần định viết đều phát sinh vài thay đổi nhỏ, mãi đến gần đây các thuật toán và cấu trúc dữ liệu mới ổn định. Hôm nay xin ghi lại chi tiết để lưu trữ.
Trong game, các đối tượng cảnh thường được lưu trữ dưới dạng cấu trúc cây. Lý do là vì trạng thái không gian của mỗi đối tượng thường bị ảnh hưởng bởi đối tượng cấp trên gắn kết với nó. Về mặt quản lý, mỗi đối tượng nên biết rõ phạm vi ảnh hưởng của mình và phải nắm được đối tượng cha đang tác động đến nó. Điều này dẫn đến việc sử dụng phổ biến cấu trúc cây - đặc biệt quan trọng trong thiết kế editor khi cấu trúc này được hiển thị trực quan trên giao diện. Tuy nhiên, tôi cho rằng trong runtime, việc duyệt từ cha sang con không thực sự cần thiết và có thể được xử lý riêng khi cần thiết. Về bản chất dữ liệu, việc cả cha nhớ con và con nhớ cha là sự trùng lặp thông tin mối quan hệ. Nếu không cần lưu thứ tự anh em của đối tượng con, trong cấu trúc dữ liệu cốt lõi chỉ cần để con ghi nhớ cha là đủ.
Việc loại bỏ thông tin dư thừa giúp đơn giản hóa cấu trúc dữ liệu, giảm chi phí bảo trì và hạn chế lỗi phát sinh. Đặc biệt với kiến trúc ECS, tôi mong muốn tất cả đối tượng đều phẳng (flat), chỉ cần một “parent id” trong thành phần transform là có thể dựng xây toàn bộ cấu trúc phân cấp cảnh.
Mỗi đối tượng có khả năng chứa đối tượng khác sẽ sở hữu các điểm gắn kết (slot) với các ma trận biến đổi tương đối. Các đối tượng khác sẽ được treo vào các slot này. Slot là dữ liệu tĩnh được tạo ra khi thiết kế, thường không cho phép thay đổi runtime. Tuy nhiên đối tượng có thể điều chỉnh ma trận biến đổi tương đối so với slot. Chẳng hạn, toàn bộ cảnh có một nút gốc với slot mặc định là ma trận đơn vị. Mọi đối tượng runtime đều gắn vào đây, khiến world matrix cuối cùng của mỗi đối tượng được quyết định bởi chuỗi “slot matrix + local matrix”.
Thành phần transform mô tả thông tin không gian của đối tượng trong cảnh bao gồm các thuộc tính:
- world matrix - Ma trận trong không gian thế giới
- base matrix - Ma trận trong không gian cục bộ của đối tượng cha
- scale - Hệ số tỷ lệ tương đối so với base matrix
- rotation - Góc xoay tương đối so với base matrix
- translation - Vectơ tịnh tiến tương đối so với base matrix
- parent id - Mã định danh đối tượng cha
- slot name - Tên slot được gắn vào
Trong đó, world matrix và base matrix được tính toán theo từng cấp trong runtime. Các tham số scale/rotation/translation là tùy chọn, mặc định sẽ trùng với gốc tọa độ slot: scale=1, rotation=0, translation=(0,0,0). Parent id và slot name quyết định thông tin phân cấp không gian.
Đối với các đối tượng chứa đối tượng khác, sẽ có một cấu trúc dữ liệu tĩnh lưu trữ ma trận biến đổi tương ứng với từng slot name. Nếu cần điều chỉnh vị trí runtime, có thể bỏ qua slot và dùng trực tiếp SRT; nếu vị trí cố định từ thời gian thiết kế, thông tin sẽ được lưu trong slots, lúc đó chỉ cần lưu slot name mà không cần SRT. Việc tách biệt này mang lại độ linh hoạt cao - có thể tái sử dụng prefab đã có cấu trúc phân cấp từ thời thiết kế, đồng thời vẫn cho phép điều chỉnh runtime.
Thiết kế không lưu danh sách con trực tiếp giúp đơn giản hóa cấu trúc dữ liệu nhưng gây khó khăn cho việc tính toán world matrix. Phương pháp “thô bạo” là mỗi lần render sẽ truy ngược lên từ parent qua các slot, nhân các ma trận với nhau. Tuy nhiên, so với tần suất render cao, việc chỉnh sửa SRT của đối tượng cảnh xảy ra rất ít và số lượng thay đổi cũng nhỏ hơn nhiều tổng số đối tượng. Việc xử lý phức tạp cho mỗi frame render là cực kỳ tốn kém. Dù có thể đánh dấu các nút đã tính toán để tránh lặp, nhưng đa dạng trạng thái đánh dấu lại làm tăng độ phức tạp của cấu trúc dữ liệu.
Một phương pháp truyền thống khác là khi chỉnh sửa đối tượng, sẽ đưa toàn bộ con cháu vào tập cần cập nhật. Tuy nhiên cách này đòi hỏi cấu trúc dữ liệu phải lưu danh sách con - điều mà thiết kế hiện tại không có và tôi cũng không muốn thêm vào. Hơn nữa, tôi không thích việc phát sinh thao tác ngầm định (như đánh dấu con) khi chỉnh sửa dữ liệu.
Khung ECS hiện tại cho phép duyệt các thành phần cùng loại và xác định các thành phần bị thay đổi trong frame. Tuy nhiên thứ tự duyệt không được đảm bảo - trong khi bài toán này lại đòi hỏi thứ tự xử lý: cha phải được tính trước con. Thứ tự giữa các anh em không quan trọng.
Giải pháp trực quan nhất là duyệt rồi sắp xếp lại theo thứ tự topo. Thay vì lưu trực tiếp danh sách con, chúng ta có thể dùng thuật toán topo sort trên mảng phẳng các cặp (parent id, object id). Bài toán sắp xếp topo hoàn toàn là vấn đề thuật toán, dễ dàng implement bằng Lua (về sau có thể tối ưu bằng C). Tuy nhiên cần lưu ý độ phức tạp O(n+m) của topo sort không phải là chi phí nhỏ.
Để giảm n, chúng ta loại các nút lá ra khỏi giai đoạn sắp xếp. Các nút lá sẽ đợi đến render, lúc đó chỉ cần kiểm tra sự thay đổi của world matrix cha là quyết định có cần cập nhật không.
Với các nút không phải lá, thuật toán mỗi frame như sau:
- Duyệt tất cả đối tượng bị sửa, đưa vào tập cập nhật
- Duyệt các đối tượng chưa sửa, phân vào tập cập nhật/tập chờ cập nhật/tập không đổi. Nút gốc mặc định trong tập không đổi, các nút khác vào tập chờ. Nếu cha thuộc tập nào, con sẽ vào tập đó
- Topo sort tập chờ
- Duyệt tập chờ đã sắp xếp, nếu cha trong tập cập nhật thì đưa con vào tập cập nhật
- Topo sort lần cuối trên tập cập nhật
Lưu ý: Hai lần topo sort gây chi phí cao, có thể tối ưu bằng cách:
- Lưu kết quả cập nhật cuối cùng của frame trước
- Chỉ thực hiện các bước sau nếu đối tượng sửa chưa có trong kết quả frame trước
- Nếu bỏ qua các bước, dùng lại tập từ frame trước nhưng loại bỏ các đối tượng không cần sửa trong frame này, đồng thời giữ lại một ngưỡng số lượng nhất định để tránh xung đột giữa các frame
Vì đa phần các frame chỉ sửa một lượng nhỏ đối tượng cố định, nên thứ tự xử lý các đối tượng “dễ biến đổi” có thể được cache. Khi các frame liên tiếp cùng sửa các đối tượng trong tập cache, thứ tự xử lý sẽ không cần thay đổi.
Khi tính toán world matrix:
- Nếu cha chưa được cập nhật và không đổi cha, giữ nguyên base matrix rồi nhân với SRT
- Nếu cha được cập nhật, cần tính lại base matrix từ parent id và slot name
Một tối ưu quan trọng khác: Khi thiết kế cảnh, các đối tượng tạo thành cấu trúc không gian phức tạp. Sau khi hoàn thiện, có thể tạo prefab với đánh