Quản Lý Các Đối Tượng Phân Bố Trên Mặt Phẳng Bằng Cây Tứ Phân
Vào cuối tuần, tôi liên tục suy nghĩ về cách lưu trữ và quản lý các đối tượng có tọa độ mặt phẳng trong server game. Mục tiêu là tạo điều kiện thuận lợi cho việc truy vấn các đối tượng lân cận. Trước đây, phương pháp thường dùng là chia lưới không gian thành các ô vuông rồi phân bổ đối tượng vào các ô tương ứng. Tuy nhiên lần này tôi muốn thử một cách tiếp cận khác để giải quyết vấn đề này.
Lý do chính khiến tôi không muốn dùng phương pháp chia lưới: Thứ nhất, với không gian lớn thì phương pháp này tiêu tốn nhiều bộ nhớ và không phù hợp với các bản đồ mở vô hạn. Thứ hai, việc truy vấn các đối tượng xung quanh sẽ gặp khó khăn do độ phân giải của lưới - lưới càng chi tiết thì tốc độ xử lý càng chậm.
Dù có thể tối ưu hóa thuật toán để giảm thiểu các vấn đề trên, tôi quyết định thử nghiệm với cấu trúc cây tứ phân (quadtree). Về mặt lý thuyết, cây tứ phân sẽ tiêu tốn bộ nhớ tuyến tính O(n). Nếu giới hạn độ sâu tối đa của cây, ta có thể tính toán được số lượng node cần thiết. Trong trường hợp chỉ dùng để tính toán vùng quan tâm (AOI), độ sâu 5 tầng là hoàn toàn đủ. Với dự tính này, việc cấp phát trước khoảng 20*n node sẽ đáp ứng dư thừa nhu cầu.
Đặc biệt, tôi muốn xây dựng một không gian có thể mở rộng vô hạn theo mọi hướng từ gốc tọa độ, không bị giới hạn bởi kích thước cố định. Vì vậy, tôi đã cải tiến cấu trúc cây tứ phân truyền thống. Nút gốc (level 1) được xử lý đặc biệt khi chia không gian thành 4 phần, mỗi phần có thể mở rộng vô hạn theo hướng tương ứng.
Tôi phân loại các vùng không gian có thể chia cắt thành 9 loại như sau:
|
|
Trong đó, vùng loại 5 có kích thước cố định và khi chia sẽ tạo ra 4 vùng con cùng loại 5. Các vùng loại 1 khi chia sẽ tạo thành 4 phần thuộc loại 1, 6, 5, 9 theo thứ tự các góc phần tư. Tương tự, các loại 2,3,4 cũng có quy luật chia cắt riêng. Các vùng loại 6,7,8,9 chỉ mở rộng theo một hướng nên khi chia chỉ tạo ra 2 phần - một vùng loại 5 cố định và một vùng giữ nguyên loại ban đầu.
Cấu trúc này khiến cây tứ phân của tôi không còn là dạng đầy đủ - một số nhánh chỉ có 2 node con. Khi đối tượng di chuyển quá xa gốc tọa độ, độ sâu của cây có thể vượt quá 5 tầng nhưng chiều rộng sẽ giảm dần. Nếu đa số đối tượng tập trung gần gốc tọa độ, tốc độ truy vấn sẽ rất nhanh.
Tôi đã thức trắng đêm để triển khai cấu trúc này bằng C, viết hơn 400 dòng code. Vì ứng dụng vào dự án thực tế nên tôi đặc biệt chú trọng hiệu năng, mất gần 8 tiếng để hoàn thiện. Việc triển khai không đơn giản như tưởng tượng và độ dài code vượt xa dự kiến ban đầu.
Thông thường, mỗi node trong cây tứ phân sẽ chứa con trỏ trỏ về node cha, điều này giúp duyệt cây không cần dùng đệ quy. Vì đã quen với cách viết đệ quy nên việc chuyển sang thuật toán duyệt cây không đệ quy (dùng backtracking) khiến tôi gặp không ít khó khăn. Để tối ưu tốc độ tìm kiếm các node lân cận, tôi phải thiết kế một cơ chế đặc biệt riêng.
Đặc biệt, do có thể ước tính tổng số node, tôi xây dựng một pool cấp phát trước với cơ chế garbage collection nội bộ. Việc loại bỏ hoặc thêm node mới trở nên cực kỳ hiệu quả. Về sau tôi nhận ra có thể dùng danh sách free list thay thế mà không làm giảm hiệu năng đáng kể.
Mỗi node lá của cây sẽ chứa một danh sách liên kết các đối tượng. Tôi thiết kế cơ chế danh sách dự phòng để việc cấp phát, giải phóng và di chuyển đối tượng không cần xây dựng lại cấu trúc. Tính toán cho thấy thời gian xử lý khi đối tượng di chuyển hoặc truy vấn vùng AOI đều ở mức hằng số O(1). Nhìn chung, tôi khá hài lòng với kết quả đạt được.
Bổ sung sau 1 ngày: Sau khi ngủ một đêm ngon giấc, tôi nhận ra có thể đơn giản hóa thuật toán bằng cách cho phép tăng động số tầng khi mở rộng về biên. Cách tiếp cận này không làm tăng nhiều gánh nặng lưu trữ và truy vấn mà lại đơn giản hơn nhiều. Sáng hôm sau, tôi đã sửa lại toàn bộ code theo hướng này.