Nếu tôi là bạn, tôi sẽ bắt đầu bằng cách triển khai một cây BSP (phân vùng không gian nhị phân) đơn giản. Vì bạn đang làm việc trong 2D, kiểm tra hộp bị ràng buộc thực sự nhanh chóng.Về cơ bản bạn cần ba lớp: CBspTree, CBspNode và CBspCut (không thực sự cần thiết)
- CBspTree có một ví dụ nút gốc của lớp CBspNode
- CBspNode có một thể hiện của CBspCut
- CBspCut tượng trưng cho cách bạn cắt một tập trong hai bộ rời rạc. Điều này có thể được giải quyết gọn gàng bằng cách giới thiệu đa hình (ví dụ: CBspCutX hoặc CBspCutY hoặc một số đường cắt khác). CBspCut cũng có hai CBspNode
Giao diện hướng tới thế giới bị chia sẽ trải qua lớp cây và có thể là một ý tưởng hay để tạo thêm một lớp trên đó, trong trường hợp bạn muốn thay thế BSP giải pháp với ví dụ một cây quad. Một khi bạn nhận được hang của nó. Nhưng trong kinh nghiệm của tôi, một BSP sẽ làm tốt.
Có các chiến lược khác nhau về cách lưu trữ các mục của bạn trong cây. Ý tôi là, bạn có thể chọn để có ví dụ một số loại thùng chứa trong mỗi nút chứa tham chiếu đến các đối tượng chiếm khu vực đó. Điều này có nghĩa là mặc dù (như bạn đang tự hỏi mình) rằng các mặt hàng lớn sẽ chiếm nhiều lá, tức là sẽ có nhiều tài liệu tham khảo cho các đối tượng lớn và các mục rất nhỏ sẽ xuất hiện ở các lá đơn.
Theo kinh nghiệm của tôi, điều này không có tác động lớn. Tất nhiên nó quan trọng, nhưng bạn phải làm một số thử nghiệm để kiểm tra xem nó thực sự là một vấn đề hay không. Bạn sẽ có thể giải quyết vấn đề này bằng cách đơn giản bỏ những thứ đó ở các nút nhánh trong cây, tức là bạn sẽ không lưu trữ chúng trên "cấp độ lá". Điều này có nghĩa là bạn sẽ tìm thấy những vật thể đó nhanh chóng trong khi đi ngang qua cây.
Khi nói đến câu hỏi đầu tiên của bạn. Nếu bạn chỉ sử dụng phân mục này để thử nghiệm va chạm và không có gì khác, tôi đề nghị rằng những thứ không bao giờ va chạm không bao giờ được đưa vào cây. Một tên lửa ví dụ như bạn nói, không thể va chạm với tên lửa khác. Điều đó có nghĩa là bạn thậm chí không cần phải cất tên lửa trong cây.
Tuy nhiên, bạn có thể muốn sử dụng bsp cho những thứ khác nữa, bạn không chỉ định điều đó nhưng hãy ghi nhớ điều đó (để chọn các đối tượng có nghĩa là chuột). Nếu không, tôi đề nghị bạn lưu trữ mọi thứ trong bsp, và giải quyết xung đột sau này. Chỉ cần hỏi bsp của một danh sách các đối tượng trong một khu vực nhất định để có được một tập giới hạn các ứng cử viên va chạm có thể và thực hiện kiểm tra sau đó (giả sử các đối tượng biết những gì họ có thể va chạm với, hoặc một số cơ chế bên ngoài khác).
Nếu bạn muốn tăng tốc độ điều gì đó, bạn cũng cần phải chăm sóc merge và chia, tức là khi mọi thứ được đưa ra khỏi cây, rất nhiều nút sẽ trở nên trống rỗng hoặc số lượng các mục dưới đây một số mức nút sẽ giảm xuống dưới một số ngưỡng hợp nhất. Sau đó, bạn muốn kết hợp hai subtrees thành một nút chứa tất cả các mục. Tách ra sẽ xảy ra khi bạn chèn các mục vào thế giới. Vì vậy, khi số lượng các mục vượt quá một số ngưỡng tách bạn giới thiệu một cắt mới, mà chia tách thế giới trong hai. Các ngưỡng hợp nhất và chia này phải là hai hằng số mà bạn có thể sử dụng để điều chỉnh hiệu quả của cây.
Hợp nhất và chia nhỏ chủ yếu được sử dụng để giữ cho cây cân bằng và để đảm bảo rằng nó hoạt động hiệu quả như nó có thể theo thông số kỹ thuật của nó. Đây thực sự là những gì bạn cần phải lo lắng. Di chuyển mọi thứ từ một vị trí và do đó việc cập nhật cây là nhanh. Nhưng khi nói đến sáp nhập và tách nó có thể trở nên đắt tiền nếu bạn làm điều đó quá thường xuyên.
Điều này có thể tránh được bằng cách giới thiệu một số loại hệ thống tách và hợp nhất lười biếng, tức là bạn có một số loại gắn cờ hoặc sửa đổi dơ bẩn. Hợp nhất tất cả các hoạt động có thể được nhóm, tức là di chuyển 10 đối tượng và chèn 5 đối tượng có thể là một lô.Một khi lô hoạt động đó kết thúc, bạn kiểm tra xem cây có bị bẩn hay không và sau đó bạn thực hiện các thao tác hợp nhất và/hoặc chia tách cần thiết.
Đăng một số nhận xét nếu bạn muốn tôi giải thích thêm.
Chúc mừng!
Sửa
Có rất nhiều thứ có thể được tối ưu hóa trong cây. Nhưng như bạn đã biết, tối ưu hóa sớm là gốc rễ của mọi điều ác. Vì vậy, bắt đầu đơn giản. Ví dụ, bạn có thể tạo một số hệ thống gọi lại chung mà bạn có thể sử dụng khi duyệt qua cây. Bằng cách này bạn không phải truy vấn cây để lấy danh sách các đối tượng khớp với hộp "câu hỏi" bị ràng buộc, thay vào đó bạn có thể duyệt qua cây và thực hiện cuộc gọi đó mỗi lần bạn nhấn vào một cái gì đó. "Nếu hộp ràng buộc này tôi cung cấp giao cắt bạn, sau đó thực hiện gọi lại này với các thông số"