Tránh O (n^2) phức tạp cho phát hiện va chạm

Question

Tôi đang phát triển trò chơi 2D dựa trên nền gạch đơn giản. Tôi có một cấp độ, dân cư với các đối tượng có thể tương tác với gạch và với nhau. Kiểm tra va chạm với tilemap là khá dễ dàng và nó có thể được thực hiện cho tất cả các đối tượng với một phức tạp tuyến tính. Nhưng bây giờ tôi phải phát hiện va chạm giữa các đối tượng và bây giờ tôi phải kiểm tra mọi đối tượng chống lại mọi đối tượng khác, kết quả là độ phức tạp vuông.

Tôi muốn tránh sự phức tạp của hình vuông. Có bất kỳ phương pháp nổi tiếng nào để giảm các cuộc gọi phát hiện xung đột giữa các đối tượng hay không. Có bất kỳ cấu trúc dữ liệu nào (giống như cây BSP), có thể dễ dàng duy trì và cho phép từ chối nhiều lần va chạm cùng một lúc.

Ví dụ, tổng số đối tượng ở mức khoảng 500, khoảng 50 người trong số họ nhìn thấy trên màn hình tại một thời điểm ...

Cảm ơn!

Answer 1

Tại sao bạn không để các ô lưu trữ thông tin về những đối tượng chiếm chúng. Sau đó, va chạm có thể được phát hiện bất cứ khi nào một đối tượng được di chuyển đến một lát mới, bằng cách nhìn thấy nếu ngói đó đã chứa một đối tượng khác.

Điều này sẽ hầu như không có gì.

Answer 2

Bạn có thể sử dụng quadtree để chia không gian và giảm số lượng đối tượng bạn cần để kiểm tra va chạm.

See this article - Quadtree demonstration.

And perhaps this - Collision Detection in Two Dimensions.

Or this - Quadtree (source included)

Nó có vẻ - ở cái nhìn đầu tiên - mà phải mất rất nhiều sức mạnh của CPU để duy trì cây, nhưng nó cũng làm giảm số lượng ngân phiếu đáng kể (xem phần trình diễn trong liên kết thứ nhất).

Answer 3

Trò chơi của bạn đã có khái niệm về sơ đồ trang web liên quan đến trò chơi. Bạn có thể đồng lựa chọn sơ đồ trang web này để phát hiện va chạm hoặc che phủ lưới thứ cấp trên trường chơi của bạn được sử dụng đặc biệt để theo dõi sprite và phát hiện xung đột.

Trong lưới của bạn, mỗi sprite chiếm một hoặc nhiều ô. Các sprite biết gạch nó chiếm, và gạch biết sprites chiếm nó. Khi một sprite di chuyển, bạn chỉ cần kiểm tra các va chạm trong các tile mà sprite chiếm. Điều này có nghĩa là không phát hiện va chạm nào là cần thiết, trừ khi sprites gần đủ để chiếm cùng một khối, và thậm chí sau đó, bạn chỉ cần kiểm tra các xung đột giữa các sprites gần nhau.

Nếu trò chơi của bạn là như vậy mà sprites sẽ thường xuyên kết hợp với nhau, bạn có thể muốn thực hiện lưới của bạn như là một quadtree để cho phép mỗi gạch được chia nhỏ và ngăn chặn quá nhiều sprites từ chiếm cùng ngói.

Ngoài ra, tùy thuộc vào việc triển khai của bạn, bạn có thể cần phải sử dụng hộp giới hạn lớn hơn một chút để xác định khả năng chứa ngói so với mức sử dụng để xác định xung đột. Bằng cách đó bạn sẽ được đảm bảo rằng các sprites sẽ chồng chéo lên nhau và chiếm cùng một ô xếp trước khi chạm vào các đường biên va chạm của chúng.