Sắp Xếp Thứ Tự Trong Cấu Trúc Phân Cấp Cảnh

Đây là bài viết tiếp nối của bài “Quản lý cấu trúc phân cấp cảnh”. Gần đây tôi đang tái cấu trúc mô-đun quản lý cảnh của engine. Một trong những động lực chính là do các chức năng hiện có đang trở nên quá phức tạp (vì yêu cầu liên tục tăng) và chúng tôi phải sửa chữa nhiều lỗi phát sinh.

Sau vài ngày suy ngẫm, tôi quyết định tách riêng phần quản lý thứ tự phân cấp ra thành một mô-đun độc lập. Vấn đề cụ thể ở đây liên quan đến:

Trong cảnh game, các đối tượng đều nằm ở các nút của cấu trúc dạng cây. Lý do sử dụng cấu trúc phân cấp là vì một số thuộc tính của đối tượng phụ thuộc vào thuộc tính của nút cha trong cấu trúc phân cấp.

Yêu cầu điển hình là vị trí không gian của đối tượng. Thông thường ma trận không gian cục bộ (so với nút cha) được lưu trữ tại nút đối tượng. Tuy nhiên mô-đun render lại cần tính toán ma trận không gian thế giới. Tương tự, nếu một nút được thiết lập chất liệu mà các nút con không thiết lập riêng, chúng ta kỳ vọng chất liệu sẽ được kế thừa từ nút cha.

Tóm lại, thuộc tính của mỗi nút không chỉ được lưu trữ cục bộ mà còn chịu ảnh hưởng từ nút cha và tổ tiên.

Cấu trúc cây tiêu chuẩn là lưu trữ tham chiếu đến nút cha và danh sách nút con trong mỗi đối tượng. Tuy nhiên tôi không thích cấu trúc dữ liệu này vì ba lý do:

1. Sự dư thừa dữ liệu: Nếu A là cha của B, mối quan hệ này được lưu ở cả danh sách con của A và tham chiếu cha của B. Điều này làm tăng độ phức tạp và dễ sinh lỗi do dữ liệu không nhất quán.

2. Khó khăn trong duyệt cây: So với cấu trúc tuyến tính phẳng, duyệt cây yêu cầu bộ lặp phức tạp hơn. Đặc biệt với khung ECS, cần giữ cho quá trình duyệt đơn giản.

3. Vòng lặp trong cây: Dễ gây lỗi nghiêm trọng nhưng biểu hiện trễ, đồng thời việc kiểm tra trạng thái lỗi tốn kém.

Khi thiết kế ban đầu, chúng tôi đã từ chối cấu trúc truyền thống này. Theo tôi, các đối tượng cảnh chỉ cần lưu ID nút cha là đủ. Hầu hết các đối tượng không cần quan tâm đến danh sách con, nếu nghiệp vụ thực sự cần duyệt con thì có thể ghi nhận riêng.

Nhược điểm rõ ràng là trong cấu trúc phẳng này, các đối tượng cảnh sẽ không có thứ tự. Khi cần lấy thuộc tính phụ thuộc nút cha (như tính toán ma trận thế giới), phải truy ngược toàn bộ tổ tiên - điều này gây ra nhiều phép nhân ma trận dư thừa.

Với cấu trúc cây truyền thống, do duyệt có thứ tự đảm bảo nút cha luôn được xử lý trước nút con, việc tính toán ma trận có thể tối ưu. Câu hỏi đặt ra: Liệu có thể đạt được duyệt có thứ tự trên cấu trúc phẳng (chỉ lưu tham chiếu cha) không?

Trước đây tôi dùng sắp xếp topo và lưu vào bộ nhớ đệm. Nhưng lần tái cấu trúc này, tôi phát hiện ra thuật toán đơn giản hơn có thể triển khai trên cấu trúc dữ liệu nhẹ.

Nếu gán mỗi đối tượng một ID độc lập (gốc là 0), chúng ta cần một hàng đợi chứa tất cả ID thỏa mãn điều kiện: mỗi đối tượng cha luôn nằm trước đối tượng con trong hàng đợi.

Có nhiều hàng đợi thỏa mãn điều kiện này - thứ tự duyệt theo chiều sâu hay ngang đều phù hợp, thậm chí hoán đổi thứ tự anh em cũng không ảnh hưởng. Điều này cho thấy việc duy trì thứ tự khá linh hoạt.

Giả sử hàng đợi bắt đầu trống rỗng, và chúng ta lắng nghe các sự kiện sửa đổi tham chiếu cha. Mỗi sự kiện là một cặp (đối tượng, cha mới). Khi tạo đối tượng mới là cặp (ID mới, ID cũ). Khi xóa đối tượng là đặt tham chiếu cha về null.

Để xử lý hiệu quả, tôi xây dựng bảng chỉ mục ghi nhận vị trí mỗi ID trong hàng đợi và mối quan hệ cha-con. Khi xử lý sự kiện, có ba trường hợp chính:

1. Đối tượng mới tham chiếu đến đối tượng cũ: Thêm ID mới vào cuối hàng đợi vì ID cha đã tồn tại trước đó.

2. Cả cha và con đều là đối tượng mới: Thêm cả hai vào cuối hàng đợi theo thứ tự cha trước con, đồng thời thiết lập cha của nút cha là gốc (ID 0).

3. Đối tượng tồn tại thay đổi cha: Nếu cha mới chưa tồn tại thì thêm vào cuối. Khi phát hiện thứ tự con trước cha (P < Q), cần điều chỉnh đoạn PQ:

   • Tạo hàng đợi tạm T chứa Q và P
   • Duyệt từ P đến Q:
     • Nếu cha của nút đang xét có trong T → thêm vào cuối T
     • Ngược lại → đẩy về phía trước đoạn PQ
   • Sau khi duyệt xong, gắn T vào cuối đoạn PQ

Với trường hợp xóa nút (đặt tham chiếu cha về null), trong quá trình duyệt có thể kiểm tra đồng thời. Nếu phát hiện cha là null, đánh dấu nút đó và các con cháu để xóa toàn bộ.

Tôi đã cô lập toàn bộ thuật toán và cấu trúc dữ liệu này thành một mô-đun Lua riêng, chỉ quản lý hàng đợi ID. Mặc dù thuật toán phức tạp nhưng tôi thấy việc triển khai bằng C sẽ hiệu quả hơn Lua về hiệu suất. Tuy nhiên cấu trúc dữ liệu vẫn dùng bảng Lua thuần túy (không dùng userdata) để đảm bảo tính linh hoạt khi kết hợp với các mô-đun khác.