Amanotes

Using Swept AABB to detect and process collision

Level: Very Beginner

What is AABB?

AABB stands for Axis-Aligned Bounding Box, it is an algorithm to detect collision between rectangle’s edges, in this case, those edges are parallel with coordinate axes. Basically, we will check two rectangles overlap with each other or not.

What is Swept AABB?

We will have some problems if we use AABB, let’s see this example:

At first frame, rectangle 1 doesn’t collide with a blue rectangle. And next frame, the rectangle 1 move to the next position, but velocity too fast and make it go through the blue rectangle. If we check collision at this frame, the rectangle 1 doesn’t collide with the blue one.

Let’s think if we can predict the next position in the next frame, we will know and prevent our object from this problem. This is called Swept AABB.

AABB Collision

To check 2 rectangles are overlapped each other or not, we will check each pair of corresponding edges.

We always have this at the same time:

  • other.left <= object.right
  • other.right >= object.left
  • other.top >= object.bottom
  • other.bottom <= object.top

If one of these conditions is wrong, so 2 rectangles aren’t overlapped.

In this example, we have ‘left’ of ‘other’ greater than ‘right’ of ‘object’

Noted: all examples in this article use bottom-left origin.

This is a simple function to check collision:

We can invert condition to check faster.

Using Swept

First, we calculate the distance between the corresponding edges.

In this,

  • dxEntry, dyEntry: the distance need to move to begin contact
  • dxExit, dyExit: the distance need to move to exit contact

We also need to check sign of velocity and calculate the distance in each case

Next, from distance and velocity, we can calculate the time

||   time = distance / velocity

In order to collide, both axes ‘x’ and ‘y’ need to get collided. So, we will take the longest time to begin collision.

And when end collision, we only need one of axes exit collision, so we will take the quickest time to exit collision.

 

We can check collision by:

  • time to begin collision from 0 to 1
  • time to end collision must be bigger than time to begin collision.

Finally, we will return time to begin a collision.

Handle collision

We can use to calculate distance need to move to the next frame based on the returned time.

Broad-Phasing

To optimize, we can do one more step by using a rectangle made from the position at the current frame and the next frame to check collision with another object.

We put this code at the top of Swept AABB function.

 

Detect collision direction

That’s it! This algorithm is very simple, right?.

I hope this basic concept can help you in your project and move to the more difficult algorithms like SAT (Separating Axis Theorem)

 

By Luu The Vinh
Product Developer of Amanotes

 

 

Xét và xử lý va chạm bằng Swept AABB

Xin chào các bạn, bài viết hôm nay mình sẽ giới thiệu cho các bạn về xử lý va chạm trong game bằng Swept AABB. Khi các bạn tự viết framework có phần xử lý va chạm thì có thể sử dụng phương pháp này.

AABB là gì?

AABB là viết tắt của Axis-Aligned Bounding Box, nó là thuật toán xét va chạm giữa các cạnh của hình chữ nhật mà ở đây các cạnh này nó song song với cùng hệ trục tọa độ. Vậy cơ bản là xét xem 2 hình chữ nhật nó có chồng lên nhau hay không.

Swept AABB?

Với Swept AABB, chúng ta sẽ xem trước ở frame kế tiếp hình chữ nhật mình có va chạm hay không. Có thì mình xử lý nó theo ý mình muốn.

Ví dụ:

Ở frame đầu tiên, hình chữ nhật chưa có va chạm, frame tiếp theo hình chữ nhật di chuyển 1 đoạn và va chạm với thanh màu xanh. Mình sẽ dự đoán trước và quyết định vị trí kế tiếp của nó, như ở đây nó sẽ đi đoạn ngắn hơn thay vì như bình thường sẽ là ở vị trí nét đứt.

ví dụ swept aabb

Xét va chạm AABB

Để xem 2 hình chữ nhật có va chạm hay không thì mình sẽ xét từng cặp cạnh của 2 hình như sau:

ví dụ 2 hình chữ nhật va chạm với nhau

Các bạn để ý sẽ thấy, khi 2 hình đè lên nhau thì mình luôn có ĐỒNG THỜI:

  • other.left <= object.right
  • other.right >= object.left
  • other.top >= object.bottom
  • other.bottom <= object.top

Như vậy nếu 1 trong 4 điều kiện trên sai thì 2 hình không có va chạm với nhau.

ví dụ 2 hình chữ nhật chưa va chạm

Ví dụ ở đây ta có left của other lớn hơn right của object, nên không có va chạm.

Tất cả ví dụ mình lấy gốc tọa độ là bottom-left

Hàm xét va chạm có thể viết đơn giản như sau:

Ở trên, mình có hàm kiểm tra hai Rect có va chạm với nhau hay không, mình lấy điều kiện ngược lại cho gọn hơn.

Xét va chạm với Swept AABB

Đầu tiên, mình tìm khoảng cách giữa các cạnh của hai hình

ví dụ 2 hình chữ nhật chưa va chạm

Trong đó,

  • dxEntrydyEntry: là khoảng cách cần đi để các bắt đầu va chạm.
  • dxExitdyExit: là khoảng cách cần đi kể từ lúc này để khi hết va chạm.

Nó cũng như top, left, right, bottom của AABB cơ bản phía trên. Mình xét thêm hướng của vận tốc, để nó đồng bộ với dấu lúc sau tính thời gian không ngược khi có va chạm.

Tiếp theo, từ khoảng cách và vận tốc, mình tìm thời gian để bắt đầu và kết thúc va chạm:

thời gian = quãng đường / vận tốc

Để xảy ra va chạm, cả hai trục x và y phải ĐỒNG THỜI XẢY RA VA CHẠM, vậy mình lấy thời gian bắt để đầu va chạm lớn nhất.

Còn khi hết va chạm, chỉ cần 1 trong 2 trục thoát khỏi là được, nên mình lấy thời gian kết thúc va chạm nhỏ nhất giữa 2 trục x, y.

ví dụ 2 hình chữ nhật bắt đầu xảy ra va chạm

Có được thời gian rồi thì mình bắt đầu xét va chạm:

  • Lớn hơn 1.0f: frame tiếp theo nó vẫn chưa thể va chạm.
  • Thời gian để kết thúc va chạm nhỏ hơn 0.0f: 2 hình chữ nhật đang đi ra xa nhau.
  • Thời gian để kết thúc va chạm phải lớn hơn thời gian để va chạm (va chạm xong rồi thì sau đó mới hết chứ đúng không).

Khi có thể va chạm mình sẽ trả về thời gian va chạm đó, còn không trả về 1.0f

Xử lý va chạm

Dựa vào thời gian trả về, mình tính quãng đường đi tiếp theo

Broad-Phasing

Tối ưu một tí, mình dùng Broad-Phasing để xét xem nó có thể va chạm trong frame tiếp theo không, không thì mình return luôn cho nhanh.

ví dụ Broad-Phasing

Mình tạo 1 hình chữ nhật dựa trên vị trí ban đầu và kế tiếp, sau đó lấy hình chữ nhật đó xét xem có chồng lên với hình kia không. Nếu có thì va chạm, còn không thì chắc chắn không thể nên không cần xét tiếp.

Cuối cùng là thêm vào phần đầu của hàm xét va chạm

Kiểm tra hướng va chạm

Mình dựa vô vị trí của object để suy ra hướng

Cơ bản xét va chạm chỉ cần thế thôi, từ đây thì các bạn có thể dùng cho các trường hợp cụ thể mà chỉnh sửa thêm cho phù hợp với nó.

Trường hợp 2 vật di chuyển, các bạn tính lại vận tốc của object so với other là được, xem object di chuyển còn other đứng yên.

Full code các bạn có thể xem ở đây: Swept AABB

Bài viết tham khảo: Swept AABB Collision Detection and Response

 Lưu Thế Vinh
Product Developer of Amanotes
Using Swept AABB to detect and process collision
Rate this post

Everyone can music ♫

Post a Comment