Cấu trúc dữ liệu không gian cho các đối tượng chuyển động?

Question

Tôi đã tự hỏi cấu trúc dữ liệu tốt nhất để xử lý nhiều đối tượng di chuyển (hình cầu, hình tam giác, hộp, điểm, v.v.) là gì? Tôi đang cố gắng trả lời hai câu hỏi, phát hiện Neighbor và Collsion gần nhất.

Tôi nhận ra rằng cấu trúc dữ liệu như R cây được sử dụng cho các truy vấn lân cận gần nhất và Oct/Kd/BSP được sử dụng cho các vấn đề phát hiện va chạm đối phó với các đối tượng tĩnh hoặc với rất ít đối tượng di chuyển.

Tôi chỉ hy vọng rằng có điều gì khác ngoài kia tốt hơn.

Tôi đánh giá cao tất cả sự trợ giúp.

Answer 1

Hình cầu có thể sẽ giúp bạn với nhiều đối tượng chuyển động; bạn tính toán bán kính bình phương của đối tượng, và theo dõi nó từ trung tâm của nó. Nếu khoảng cách bình phương giữa các trung tâm của hai đối tượng nhỏ hơn tổng của bán kính bình phương của hai đối tượng, thì bạn có khả năng va chạm. Mọi thứ được thực hiện với khoảng cách bình phương; không có rễ vuông.

Bạn có thể sắp xếp các hàng xóm gần nhất theo khoảng cách bình phương tối thiểu giữa các đối tượng của bạn. Việc phát hiện va chạm có thể phức tạp, tất nhiên, và với những vật thể không có hình cầu, Bounding Spheres không nhất thiết sẽ giúp bạn có được thông tin va chạm, nhưng nó có thể cắt tỉa cây đối tượng bạn cần so sánh với va chạm khá độc đáo.

Bạn sẽ cần, tất nhiên, để theo dõi TRUNG TÂM của đối tượng của bạn; và lý tưởng bạn muốn cho mỗi đối tượng cứng nhắc, tránh phải tính toán lại các kích thước hình cầu (mặc dù phép tính toán lại không đặc biệt khó khăn, đặc biệt nếu bạn sử dụng một cây cứng nhắc với mỗi quả cầu của mình cho các vật thể không cứng nhắc, nhưng nó trở nên phức tạp).

Về cơ bản, để trả lời câu hỏi của bạn về cấu trúc dữ liệu, bạn có thể giữ tất cả các đối tượng của mình trong một mảng chính; Tôi muốn có một bộ các mảng "khu vực" bao gồm các tham chiếu đến các đối tượng trong mảng chủ mà bạn có thể sắp xếp các đối tượng vào một cách nhanh chóng dựa trên tọa độ Descartes của chúng; mảng "khu vực" nên có một chồng chéo được xác định ít nhất là 2x bán kính đối tượng lớn nhất trong mảng đối tượng chính của bạn (nếu điều đó khả thi; một câu hỏi về đối tượng giới hạn phạm vi hình cầu so với số lượng đối tượng rõ ràng là đi lên)

bạn đã có, bạn có thể thực hiện kiểm tra va chạm nhanh bằng cách so sánh khoảng cách của tất cả các đối tượng trong một vùng với nhau, một lần nữa, đây là nơi định nghĩa vùng trở nên quan trọng, bởi vì bạn đang cân bằng đáng kể số vùng Tuy nhiên, nó đơn giản hơn một chút chỉ vì các phép so sánh khoảng cách của bạn đi xuống các phép trừ đơn giản (và các hoạt động abs(), tất nhiên). các đối tượng và điều đó có thể không phải là tán thành, nhưng bạn đã giảm số lượng so sánh tiềm năng rất đáng kể vào thời điểm đó.

Về cơ bản, đó là hệ thống hai tầng; đầu tiên là mảng khu vực, theo đó bạn thực hiện sắp xếp thô trên cảnh của mình. Thứ hai, bạn có so sánh khoảng cách nội vùng của bạn; trong đó bạn sẽ làm phát hiện va chạm cơ bản của bạn và va chạm gắn cờ trên các đối tượng đã va chạm. Có lẽ là phòng trong loại thuật toán này để sử dụng cây trong xác định khu vực động để thậm chí ra kích thước khu vực của bạn để đảm bảo rằng kích thước khu vực của bạn không phát triển quá nhanh với các khu vực "đông đúc"; loại điều đó, mặc dù, là không tầm thường, bởi vì với các đối tượng có kích thước khác nhau, sắp xếp của bạn về mật độ trở nên ... phức tạp, để nói rằng ít nhất.

Answer 2

Một phương pháp thú vị để thực hiện phát hiện va chạm là sử dụng các hộp giới hạn theo hướng dọc trục (AABB) được tổ chức trong cấu trúc octree đặc biệt. Sự giúp đỡ của AABB bởi vì chúng tạo ra các tính toán va chạm thô sơ rất nhanh chóng vì bạn chỉ cần thực hiện tối đa 6 so sánh.

Có một vài thủ thuật bạn nên sử dụng với cấu trúc octree:

1) Các khu vực ranh giới mà một nút chiếm nên được hai lần lớn như nó sẽ là một octree bình thường (nơi phân vùng octree sự không gian chồng lên nhau). Vì mỗi nút nên chồng chéo một nửa diện tích của các nút lân cận của nó. Vì AABB chỉ có thể thuộc về một nút, kích thước và chồng chéo này cho phép nó duy trì trong một nút trong một khoảng thời gian dài hơn.

2) Cũng trong mỗi nút - và có thể ở mỗi cấp của cấu trúc phân cấp - bạn giữ liên kết đến các hàng xóm của nút. Điều này sẽ liên quan đến rất nhiều mã bổ sung nhưng nó sẽ cho phép bạn di chuyển các phần tử giữa các nút trong gần thời gian O (1) thay vì thời gian O (2logn).

Nếu octree chiếm quá nhiều bộ nhớ, bạn có thể thay đổi nó để sử dụng cấu trúc octree thưa thớt, chỉ giữ cây cho các phần của thế giới trò chơi thực sự chứa các thực thể. Tuy nhiên, điều này có nghĩa là bạn phải thực hiện nhiều tính toán hơn cho mỗi khung hình khi các thực thể di chuyển qua thế giới. Một số ý tưởng khác bạn có thể muốn thử thay vì một octree là sử dụng một cây kd (tôi tin đó là tên chính xác), hoặc sử dụng AABB để xây dựng cấu trúc từ dưới lên.

Cây KD (từ bộ nhớ) phân vùng không gian bằng các mặt phẳng được căn chỉnh theo trục, do đó chúng phù hợp để sử dụng với AABB. Một ý tưởng khác là thay vì buộc các thế hệ octree từ trên xuống (bắt đầu với một hộp envoloping toàn thế giới), bạn xây dựng nó từ các thực thể cơ sở và xây dựng AABB lớn hơn mà phát triển cho đến khi lớn nhất bao gồm toàn bộ thế giới. Mặc dù tôi không chắc chắn về cách nó sẽ làm việc với nhiều thực thể chuyển động nhanh.

(Nó được một lúc kể từ khi tôi đã thực hiện loại hình không gian mã hóa phát triển trò chơi.)

Answer 3

1. Bạn có thể phân vùng cảnh trong một octree và sử dụng cảnh mạch lạc. Đối tượng chuyển động của bạn mà bạn đang thử nghiệm sẽ nằm trong một nút cụ thể của cây cho một số lượng khung hình cụ thể tùy thuộc vào tốc độ của nó. Điều này có nghĩa là bạn có thể giả sử nó sẽ nằm trong nút và do đó nhanh chóng cắt ra rất nhiều đối tượng không có trong nút đó. Tất nhiên các bit khó khăn là khi đối tượng của bạn là gần với cạnh của phân vùng của bạn, bạn sẽ phải chắc chắn rằng bạn cập nhật nút mà đối tượng được in

2. Một đối tượng chuyển động có hướng và tốc độ. Bạn có thể dễ dàng chia cảnh trong hai phần bằng cách sử dụng một phân chia vuông góc từ hướng đối tượng của bạn của phong trào. Bất kỳ đối tượng nào ở phía bên trái của bộ phận này không cần phải được kiểm tra. Tất nhiên bù cho vận tốc của vật thể khác. Vì vậy, nếu đối tượng khác là hợp lý chậm, bạn có thể dễ dàng cắt nó ra khỏi kiểm tra thêm.

3. Luôn đơn giản hóa bất kỳ hình dạng nào bạn đang thử nghiệm với thứ gì đó giống như hộp giới hạn trục được căn chỉnh. Thử nghiệm va chạm ban đầu

4. Bạn có thể lấy khoảng cách giữa đối tượng của bạn và đối tượng di chuyển khác cộng với vận tốc. Nếu đối tượng chuyển động khác đang di chuyển theo cùng hướng chung với vận tốc nhanh hơn, bạn có thể loại bỏ nó khỏi séc của bạn.

5. Có nhiều tối ưu hóa khác tùy thuộc vào hình dạng của đối tượng. Vòng kết nối hoặc hình vuông hoặc hình dạng phức tạp hơn tất cả đều có tối ưu hóa cụ thể mà bạn có thể thực hiện trong khi di chuyển.

6. Giả sử một số đối tượng dừng hoặc có thể ngừng di chuyển, bạn có thể theo dõi các đối tượng dừng. các đối tượng này có thể được xử lý như các đối tượng tĩnh và do đó các kiểm tra nhanh hơn và bạn có thể áp dụng tất cả các kỹ thuật tối ưu hóa tĩnh cho chúng.

7. Tôi biết nhiều hơn nhưng không thể nghĩ ra bất kỳ điều gì trên đầu của tôi. Đã không làm điều này trong một thời gian.

Bây giờ tất nhiên điều này phụ thuộc vào cách bạn đang thực hiện phát hiện va chạm. Bạn có từng bước cập nhật vị trí của đối tượng dựa trên vận tốc và kiểm tra như thể nó là tĩnh. Hoặc bạn có đền bù cho vận tốc bằng cách ép đùn hình dạng và tìm ra các điểm va chạm ban đầu hay không. Trước đây cần một bước nhỏ cho đối tượng chuyển động nhanh. Sau này là phức tạp hơn và tốn kém nhưng cho kết quả tốt hơn. Ngoài ra nếu bạn sẽ có đối tượng quay thì mọi thứ trở nên phức tạp hơn một chút.

Answer 4

quét và prune rộng giai đoạn + gjk giai đoạn hẹp

Answer 5

RDC có thể được sử dụng, đặc biệt nếu đối tượng của bạn là thưa thớt (không có nhiều nút giao thông).