Làm thế nào để kiểm tra va chạm 2D mà không kiểm tra mọi đối tượng

Question

Tôi đang thực sự tham vọng và làm việc trên trò chơi 2D Shoot 'em Up sẽ có hàng trăm thực thể chạy xung quanh.

Điều tôi đang gặp phải khi rắc rối xung quanh, là cách viên đạn sẽ phát hiện khi nó va chạm với vật thể, mà không kiểm tra đối tượng trên bản đồ. Lý do là tôi cảm thấy rằng nếu tôi có bốn chục viên đạn trên màn hình, mỗi lần kiểm tra va chạm với mọi thực thể trên bản đồ, mỗi chu kỳ, tôi sẽ thấy một số tổn thất hiệu năng khá đáng kể.

Vì vậy, cách tốt nhất để phát hiện va chạm mà không kiểm tra mọi thực thể đơn lẻ là gì?

Tôi có thể xử lý thuật toán va chạm khi có hai đối tượng, tôi dường như không thể tìm cách để hai đối tượng này nhìn thấy nhau mà không kiểm tra mọi người trước.

Tôi đang làm việc trong Java và OpenGL với (sắp được kết cấu) QUADS.

Answer 1

Bạn nên điều tra quadtrees; chúng thường được sử dụng để tra cứu 2D hiệu quả.