Làm thế nào để bạn xử lý các đối tượng di chuyển giữa các quad khi sử dụng quadtrees?

Question

Tôi đang cố gắng sử dụng quadtrees để phát hiện va chạm trong trò chơi tôi đang tạo, nhưng tôi không chắc chắn cách xử lý các đối tượng có thể di chuyển giữa các quad khác nhau? Cách duy nhất tôi có thể nghĩ về nó là bằng cách xóa toàn bộ cây mỗi khung, và sau đó thêm mọi thứ vào trong đó, nhưng điều đó có vẻ như có thể nhận được cpu chuyên sâu và không hiệu quả lắm. Bạn có kiểm tra từng đối tượng mỗi khung để xem liệu nó đã di chuyển ra ngoài ranh giới của quad hiện tại của nó chưa, và nếu vậy thì loại bỏ nó và readd nó? Điều đó một lần nữa có vẻ như nó có thể là khá kém hiệu quả bởi vì bạn sẽ thực hiện kiểm tra va chạm trên mọi đối tượng chuyển động mỗi khung hình.

Ngoài ra, liên quan đến quadtrees nhưng không liên quan đến các đối tượng di chuyển xung quanh trong chúng, làm thế nào để bạn xử lý nhiều đối tượng trong cùng một quad? Hầu hết các trang web mà tôi đã đọc về chúng trên nói rằng bạn chỉ nên có một, có thể hai, các đối tượng trong một quad, và nếu bạn nhận được nhiều hơn thế thì sau đó đẩy chúng xuống trong cây. Nếu bạn có một tình huống như this thì sao? Bạn có ba vòng tròn và tất cả chúng đều ở các cạnh của cấp dưới chúng nên chúng không thể đi xa hơn nữa, nhưng có ba vòng tròn cùng cấp, mà mọi người nói bạn không nên có.

Answer 1

Tôi không nghĩ rằng nó đặc biệt không hiệu quả để thực hiện đề xuất của bạn: kiểm tra xem một đối tượng đã di chuyển bên ngoài quadtree của nó chưa, và nếu có thì xóa và thêm lại nó. Bất kỳ đối tượng nào chuyển từ khung này sang khung khác sẽ cần phải có một số phát hiện va chạm được thực hiện trên nó, chắc chắn? Và các hoạt động quadtree chỉ được thực hiện nếu nó di chuyển quadtrees, và thời gian CPU đã dành có thể bị lu mờ bởi thời gian CPU làm chính xác hơn "Đối tượng A có đối tượng cảm ứng B?" tính toán. Vì vậy, tôi không biết rằng bạn có thể làm tốt hơn.

Câu hỏi thứ 2: Tôi không biết người khác triển khai quadtrees như thế nào, nhưng tôi cho phép đối tượng chiếm nhiều hơn một quadtree, chính xác vì lý do bạn đưa ra trong sơ đồ của bạn (khi đối tượng nằm trong một ranh giới) . Vì vậy, một đối tượng có một "danh sách hiện tại của quads" thay vì một "quad hiện tại".

Answer 2

Xóa/thêm lại có thể được tối ưu hóa bằng cách di chuyển cây quad thay vì xóa mục khỏi cây hoàn toàn và sau đó thêm lại, tức là di chuyển đến tứ kết "cha mẹ" và sau đó thêm "cha mẹ" nó - nếu nó không phù hợp với "cha mẹ", hãy chuyển đến "ông bà", v.v.

Vì mối quan tâm thứ hai của bạn, bạn sẽ cần sự linh hoạt - nếu tất cả 3 đều ở trên cạnh, thì bạn có thể không hạ thấp chúng - nhưng điều đó nên (tha thứ cho việc chơi chữ) một trường hợp cạnh.