KIỂM TRA VÀ XỬ LÝ VA CHẠM VỚI SWEPT AABB (PHẦN 1)

Bài toán va chạm là một nỗi ám ảnh và lo sợ của những lập trình viên trong việc phát triễn game, thông thường họ thường chọn cho mình phương án sử dụng các API sẵn có để giải quyết bài toán. Đa số các lập trình viên đều sử dụng phương pháp tính bao hình (AABB) là phương án cho bài toán va chạm, tuy nhiên phương pháp này khi nâng cấp lên các thuật toán nâng cao hơn như SAT và GJK lại gặp rất nhiều khó khăn. Swept AABB là một giải thuật trung gián, nó ứng dụng tư tưởng của giải thuật bao AABB thông thường nhưng là chuyển tiếp đến các giải thuật nâng cao khác, giúp lập trình viên dễ dàng tiếp cận và sử dụng.

Ghi chú: Bài viết này sẽ giúp bạn đọc tìm hiểu thuật toán AABB, thuật toán lấy căn bản là toán vector, tuy nhiên sẽ không quá phức tạp để có thể hiểu và ứng dụng vào bài toán thực tế. Các ví dụ được biểu diễn trên nền C/C++ và hoàn toàn có thể chuyển đối sang bất kì ngôn ngữ khác như: C#, Java,...

SWEPT LÀ GÌ?

AABB được diễn tả gồm 3 vấn đề cơ bản, mà hiếm khi chúng được nhìn nhận ngay lần đầu tiếp cận. 3 vấn đề đó bao gồm:

Trường hợp 1: trường hợp căn bản của AABB. Hình vuông màu xanh là trạng thái của đối tượng trước khi diễn ra va chạm, hình xanh lá cây là trạng thái của đối tượng sau khi di chuyển, hình AABB là trạng thái của đối tượng sau khi di chuyển và được xử lý thông qua thuật giải AABB. Hình chử nhật màu xám là đối tượng tỉnh không di chuyển. Kết quả của trường hợp thứ nhất: sau khi hình vuông xanh xảy ra va chạm với hình xám thì sẽ được chuyển về vị trí cạnh điểm va chạm và không bị va chạm với hình xám.

 Trường hợp 2: Tương tự như trường hợp 1, nhưng đích đến di chuyển ở đây sẽ nằm phí đối diện (hơn phân nữa về phía đối diện) như vậy AABB sẽ tính toán kết quả và chạm trở về phía đối diện của vật cản.

Trường hợp 3: khi kết quả của quá trình di chuyển là đối tượng đích cách quá xa với vật cản và không hề diễn ra va chạm với vật cản, điều đó 2 đối tượng sẽ dường như không có va chạm diễn ra.

Vậy vấn đề là đâu? Và tại sao ta lại cần swept?

Vấn đề nảy sinh khi đối tượng di chuyển quá nhanh, và dường như sau 1 frame di chuyển hoàn toàn không thể kiểm tra được các đối tượng có va chạm hay không vì toàn bộ đều rơi vào trường hợp thứ 3. Để giải quyết vấn đề đó, ta cần biết được khoảng di chuyển của đối tượng qua thời gian, từ đó kiểm tra chính xác các va chạm, đó gọi là swept!.

HIỆN THỰC SWEPT AABB

Trong phần tiếp theo của bài viết, đối tượng va chạm được xác định bởi tọa độ góc trái trên và chiều rộng, chiều dài của chúng. Một yếu tố khóa của swept trong tính toán mà không thể bỏ qua là vận tốc của đối tượng.

Ghi chú: Vận tốc của đối tượng là giá trị cho biết bước di chuyển của đối tượng sau mỗi 1 giấy. Nếu chúng ta nhân vận tốc với một khoảng thời gian, thì chúng ta sẽ thu được vùng di chuyển của đối tượng trong khoảng thời gian đó.

 cấu trúc của một đối tượng va chạm được định dạng trong một box như sau:

Phương thức kiểm tra SweptAABB được mô tả như sau:

Trong đó:

-         Box1: là đối tượng di chuyển.

-         Box2: là đối tượng tĩnh xét va chạm.

-         Normalx, Normaly là giá trị để xác định kết quả phản ứng sau quá trình va chạm.

Ghi chú:  thông thường sau những va chạm, đối tượng sẽ chuyển hướng 90 độ so với góc di chuyển ban đầu.

Giá trị trả về của phương thức sweptAABB nằm trong khoảng 0 đến 1, trong đó chỉ định trạng thái va chạm đang diễn ra. Nếu giá trị là 0 cho biết đang bắt đầu di chuyển, giá trị là 1 cho biết kết thúc di chuyển (không xảy ra va chạm nữa), giá trị 0.5 cho biết đối tượng đang va chạm ở đoạn giữa.

Và bây giờ chúng ta sẽ chính thức đi vào quá trình tính toán của swept, trước tiên, thuật toán sẽ tính toán những khoảng cách, thời gian cần thiết trên mỗi trục x, y để xác định thời điểm va chạm.

Trong đó các giá trị: InvEntry là khoảng cách gần nhất của 2 cạnh bất kỳ của 2 đối tượng, InvExit là khoảng cách xa nhất của 2 cạnh bất kỳ của 2 đuối tượng. Ở đây chúng ta vạch sẵn đường đi của đối tượng để dự đoán thời gian có thể xãy ra va chạm của 2 đối tượng.

Tiếp theo, chúng ta sẽ căn cứ vào vận tốc của đối tượng và các chỉ số khoảng cách để tính toán khả năng va chạm của 2 đối tượng.

Và câu hỏi được đặt ra ở đây là: tại sao chúng ta phải tính toán xEntry, xExit, yEntry, yExit bằng phép toán chia vận tốc.

Trả lời: trong mỗi đơn vị thời gian di chuyển, đối tượng sẽ di chuyển đúng một khoảng cách bằng vận tốc, như vậy, phép toán chia xác định xảy ra va chạm khi giá trị phép tính từ 0 đến 1.

 EntryTime cho biết thời gian xảy ra va chạm, exitTime thời gian kết thúc va chạm.

Như vậy, cơ bản ta xác định được thêm 1 điều kiện không diễn ra va chạm là thời gian kết thúc va chạm sớm hơn thời gian bắt đầu va chạm.

Với giá trị trả về là 1 cho biết không có khả năng xảy ra va chạm.

Tiếp theo, khi va chạm được xác nhận diễn ra, vận tốc sẽ được biến đổi để thể hiện được phản ứng của đối tượng với va chạm.

Vì mỗi đối tượng chỉ có 4 điểm vị trí, nên sẽ có tối đa 4 trường hợp tương tác va chạm diễn ra. Với cách tính đơn giản như trên, đã chỉ ra được giá trị kết quả của va chạm và thời gian va chạm.

Trên đây là toàn bộ code hướng dẫn kỹ thuật Swept AABB, nhưng sẽ không đúng trong một số trường hợp, vì trên thực tế, đối tượng không chỉ thay đổi về vận tốc mà còn các thuộc tính như: hướng, cách di chuyển, vv.. Và đó chính là nội dung của phần tiếp theo.

Nguồn: http://www.gamedev.net/page/resources/_/technical/game-programming/swept-aabb-collision-detection-and-response-r3084