Cách giải quyết va chạm vật rắn 2D

 (sassnow.ski)
3 điểm bởi GN⁺ 2024-05-25 | 1 bình luận | Chia sẻ qua WhatsApp
  • Giải quyết va chạm vật rắn trong vật lý game 2D là bài toán tính toán sự thay đổi vận tốc để các vật thể đã chạm hoặc chồng lấn không xuyên qua nhau ở khung hình tiếp theo
  • Vòng lặp game cập nhật vị trí theo từng khung hình bằng vận tốc và Δt, nên nếu hình học bị chồng lấn ở vị trí mới, các vật thể sẽ đi xuyên qua nhau nếu không có xử lý riêng
  • Va chạm không chỉ là có tiếp xúc hay không, mà còn phải xét cả việc các vật thể đang tiếp xúc có tiếp tục di chuyển về phía nhau theo vận tốc hiện tại hay không
  • Có thể xác định một vật có đang rời xa bề mặt hay không bằng dấu của tích vô hướng giữa pháp tuyến (normal) và vận tốc; dương nghĩa là có thành phần cùng hướng, âm nghĩa là có thành phần ngược hướng
  • Với hai vật thể, vận tốc tương đối và pháp tuyến va chạm quan trọng hơn vận tốc riêng lẻ; khi đang tiếp xúc, nếu vận tốc pháp tuyến tương đối là âm thì có thể xem là va chạm

Phạm vi của vật lý vật rắn và giải quyết va chạm

  • Đối tượng là vật lý vật rắn (rigid body physics), xử lý các vật thể không biến dạng dù chịu lực
    • Trong thực tế, mọi vật thể đều biến dạng ở cấp độ phân tử nên không tồn tại vật rắn hoàn hảo
    • Trong hầu hết mô phỏng vật lý, việc tính toán đến những biến dạng chi tiết như vậy là rất khó hoặc tốn kém
    • Nếu vật thể trông đủ thực tế, việc đơn giản hóa như vật rắn là một cách làm thực dụng
  • Xử lý va chạm trong game engine thường được chia thành hai bước
    • Phát hiện va chạm (collision detection): xác định những vật thể nào trong cảnh đang va chạm
    • Giải quyết va chạm (collision resolution): quyết định trạng thái tiếp theo dựa trên hướng di chuyển, vận tốc, vật liệu, v.v. của các vật thể đang va chạm
  • Trọng tâm ở đây không phải là bước tìm giao cắt hình học, mà là giải quyết va chạm, tức quyết định chuyển động sau va chạm

Cách va chạm phát sinh trong vòng lặp game

  • Phần lớn game lặp đi lặp lại việc tính toán lại vị trí của các vật thể trong cảnh bên trong một vòng lặp lớn
  • Ở mỗi lần lặp, vị trí của vật thể được cập nhật dựa trên vận tốc (velocity) hiện tại
    • Vận tốc là đại lượng vector có cả độ lớn và hướng
    • Độ dài của mũi tên biểu thị tốc độ, còn hướng mũi tên chỉ hướng di chuyển
  • Thay đổi vị trí trong một khoảng thời gian cố định Δt được biểu diễn bằng độ dời (displacement)
    • Độ dời cũng là đại lượng vector có độ lớn và hướng
    • Nếu vòng lặp game chạy 60 lần mỗi giây, Δt sẽ là 1/60 giây
  • Vị trí mới thu được bằng cách cộng độ dời tính từ vận tốc hiện tại vào vị trí cũ
  • Nếu vị trí mới của hai vật thể khiến hình học của chúng chồng lấn nhau, khi không có xử lý riêng, các vật thể sẽ xuyên qua rồi đi qua nhau

Giá trị mà giải quyết va chạm cần tìm

  • Mục tiêu của giải quyết va chạm là xác định thay đổi vận tốc của từng vật thể để khi mô phỏng tiếp tục, các vật thể không còn xuyên qua nhau
  • Vận tốc trước và sau va chạm được biểu diễn bằng các ký hiệu sau
    • v_a,i, v_b,i: vận tốc trước va chạm của vật thể a, b
    • v_a,f, v_b,f: vận tốc sau va chạm của vật thể a, b
    • Δv_a, Δv_b: thay đổi vận tốc của từng vật thể do va chạm gây ra
  • Rốt cuộc, giải quyết va chạm là bài toán tìm các giá trị Δv_a và Δv_b
  • Để tạo ra va chạm trông thực tế, thay đổi vận tốc được chọn phải thỏa mãn các định luật vật lý liên quan

Chỉ tiếp xúc thôi thì chưa thể biết có va chạm

  • Hai vật thể đang chạm nhau không có nghĩa là chúng luôn đang va chạm
  • Va chạm là tình huống mà nếu tiếp tục di chuyển theo vận tốc hiện tại, các vật thể sẽ xuyên qua nhau
  • Cùng một cảnh tiếp xúc, tùy theo hướng vận tốc của hai vật thể mà có thể là va chạm hoặc không
  • Vì vậy điều kiện va chạm cần đồng thời có hai yếu tố
    • Hình học của các vật thể phải chạm hoặc chồng lấn nhau
    • Các vật thể vẫn phải đang di chuyển theo hướng va chạm

Pháp tuyến bề mặt và hướng rời xa

  • Có thể xác định một vật thể có đang rời xa một bề mặt hay không bằng hướng pháp tuyến (normal direction) của bề mặt đó
  • Hướng pháp tuyến vuông góc với bề mặt và chỉ hướng trực tiếp rời xa bề mặt
    • Với bề mặt phẳng, hướng pháp tuyến tại mọi điểm là như nhau
    • Với mặt cong, hướng pháp tuyến thay đổi theo từng điểm
    • Trên chu vi hình tròn, hướng từ tâm đến điểm tương ứng trên chu vi là hướng pháp tuyến
  • Hướng pháp tuyến được biểu diễn bằng một vector chuẩn hóa có độ dài bằng 1
    • Vector có độ dài bằng 1 còn được gọi là vector đơn vị (unit vector)
    • Có thể thêm ký hiệu ^ phía trên biến để biểu thị rằng đó là vector đã chuẩn hóa
  • Hướng pháp tuyến tại một điểm vuông góc với tiếp tuyến (tangent) của bề mặt tại điểm đó

Xác định thành phần hướng bằng tích vô hướng

  • Khi tính một vector hướng cùng chiều với vector khác đến mức nào, có thể dùng tích vô hướng (dot product)
  • Với vector 2 chiều, tích vô hướng là tổng các tích của những thành phần tương ứng, và kết quả là một số vô hướng, không phải vector
  • Về mặt hình học, tích vô hướng có thể được xem là độ dài hình chiếu vô hướng khi chiếu một vector lên hướng của vector kia, nhân với độ dài của vector được chiếu lên
  • Dấu của tích vô hướng cho biết quan hệ hướng giữa hai vector
    • Nếu góc giữa hai vector nhỏ hơn 90°, tích vô hướng là dương và nhìn chung chúng chỉ cùng hướng
    • Nếu góc lớn hơn 90°, tích vô hướng là âm và nhìn chung chúng chỉ ngược hướng
    • Nếu góc đúng bằng 90°, tích vô hướng bằng 0
  • Nếu tích vô hướng giữa vector vận tốc của vật thể và pháp tuyến bề mặt là dương, vật thể đang rời xa bề mặt đó

Áp dụng cho va chạm giữa hai vật thể

  • Nếu có hai vật thể, chẳng hạn hai hộp, thì mỗi vật thể có một vector vận tốc riêng
  • Lúc này dùng vận tốc tương đối (relative velocity) của hai vật thể thay vì vận tốc riêng lẻ
    • Vận tốc tương đối là hiệu vận tốc của hai vật thể
    • Về mặt hình học, đó là vector hướng từ đầu mút của v_b đến đầu mút của v_a
    • Ví dụ, tình huống hai xe mỗi xe chạy 50km/h và đâm trực diện vào nhau, nếu các điều kiện như nhau, tương đương với việc một xe đâm vào xe đang đứng yên ở tốc độ 100km/h
  • Hướng tương ứng với bề mặt được biểu diễn bằng pháp tuyến va chạm (collision normal)
    • Cách tính pháp tuyến va chạm thay đổi tùy theo hình dạng hoặc hình học của các vật thể va chạm
    • Ví dụ ở đây là va chạm đỉnh-cạnh (vertex-edge collision), trong đó một điểm hoặc đỉnh của vật thể này va chạm với cạnh của vật thể kia
    • Trong va chạm đỉnh-cạnh, pháp tuyến va chạm vuông góc với cạnh đó
  • Theo quy ước, nếu ký hiệu các vật thể là a, b, pháp tuyến va chạm hướng về vật thể a
    • Việc gọi vật thể nào là a hoặc b không quan trọng, miễn là nhất quán trong toàn bộ phép tính

Định nghĩa va chạm bằng vận tốc pháp tuyến tương đối

  • Khi tính tích vô hướng giữa vận tốc tương đối v_ab và pháp tuyến va chạm n^, ta có thể xác định hai vật thể có đang di chuyển theo hướng va chạm hay không
  • Giá trị này được gọi là vận tốc pháp tuyến tương đối (relative normal velocity)
    • Đây là thành phần theo hướng pháp tuyến va chạm của vận tốc tương đối
    • Ở đây dấu của nó là quan trọng, nhưng về sau nó cũng đóng vai trò quan trọng khi tính lực tác dụng trong va chạm
  • Dấu của vận tốc pháp tuyến tương đối phân biệt trạng thái va chạm
    • Nếu giá trị là dương, hai vật thể đã đang rời xa nhau
    • Nếu giá trị là âm, hai vật thể vẫn đang đâm vào nhau
  • Cuối cùng, va chạm xảy ra khi một điểm của vật thể này đang chạm vào vật thể kia và vận tốc pháp tuyến tương đối là âm

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-05-25
Ý kiến trên Hacker News
  • Xin chào, tôi là tác giả bài viết! Bổ sung thêm một chút bối cảnh: bài này chỉ là phần 1 trong loạt blog về vật lý vật rắn mà tôi định viết
    Bài viết này hướng tới những người giống tôi: không phải nhà phát triển game và cũng không có nền tảng toán học vững. Vì vậy tôi đã giải thích khá lâu cả những khái niệm mà với người có kinh nghiệm trong lĩnh vực này có thể gần như hiển nhiên. Nếu có câu hỏi, tôi rất sẵn lòng trả lời
    • Góp ý một chút: ví dụ ở phần mở đầu “Mario bật lên sau khi giẫm lên Goomba…” có vẻ hơi dễ gây hiểu nhầm. Hầu hết các game Super Mario cổ điển trên NES và SNES không cần và cũng không dùng phần lớn những phép tính như vậy
      Người mới học phát triển game thường hiểu lầm rằng để xử lý va chạm thì cần tính toán va chạm vật rắn hoặc một engine vật lý 2D như Box2D. Nếu bạn muốn làm game bi-a hoặc game có các hộp đổ sập như Angry Birds thì đúng, nhưng với platformer 2D, thường chỉ cần phát hiện va chạm bằng cách so sánh các hình chữ nhật căn theo trục, rồi thay đổi tọa độ X/Y của nhân vật để hoàn tác phần chồng lấn, hoặc đặt vận tốc Y sau khi nhảy/tiếp đất là đủ. Cách này cũng giúp tinh chỉnh cảm giác điều khiển nhân vật chi tiết hơn; nó vẫn có quán tính, nhưng thường không phải quán tính chân thực về mặt vật lý. Nếu người mới dùng vật lý chân thực, chuyển động rất dễ trở nên lơ lửng và không thỏa mãn
      Ví dụ tutorial có thể bắt đầu bằng cách tiếp cận đơn giản không cần engine vật lý này: https://www.love2d.org/wiki/Tutorial:Baseline_2D_Platformer
    • Rất hay. Phần “A word about math” thực sự quan trọng. Tôi cũng không giỏi toán lắm, nhưng trước đây từng đơn giản hóa cực độ các khái niệm toán học để tạo một mô phỏng vật lý rất cơ bản
      Tôi lặp đi lặp lại việc chồng các thành phần như điểm và đường, thêm nhiều bước nhỏ cùng các đường debug trực quan; kết quả rất ọp ẹp và chậm, nhưng dù sao cũng hoạt động ở một mức nào đó
    • Bài viết tuyệt vời và đọc rất thú vị. Tôi cũng là người không có nền tảng toán học vững, nên cảm ơn vì đã giải thích những khái niệm “hiển nhiên” như thế này :)
      Sắp tới bạn có dự định đọc và giải thích XPBD (Extended Position Based Dynamics - http://mmacklin.com/xpbd.pdf) không? Có vẻ khái niệm này đang ngày càng được chú ý, và tôi đã dùng khá thành công trong Bevy qua https://github.com/Jondolf/bevy_xpbd. Nó có vẻ ổn định hơn cách tiếp cận thông thường
    • Tôi đọc bài này rất thích :) Từ góc nhìn của một người từng chật vật với nội dung tương tự ở trường, bài này rất dễ hiểu
      Sẽ thật tuyệt nếu bạn thêm RSS feed để tôi có thể tiếp tục theo dõi
    • Phần giải thích thật sự rất tốt!
      Tôi tò mò là bạn đã dùng công cụ nào để tạo trang đó?
  • Ồ! Một bài viết được nghiên cứu kỹ, giải thích sâu, lại còn có tương tác nữa
    Thành thật mà nói, lúc đầu nhìn tên miền và thấy tên miền cấp cao nhất là “.ski”, tôi tưởng đây là trang của người đã viết Mechanical Watch [1] và các bài tuyệt vời khác. Hóa ra là một người hoàn toàn khác, nhưng chất lượng thì tương tự. Tên miền cấp cao nhất “.ski” này có bí quyết gì vậy nhỉ :)
    1. https://news.ycombinator.com/item?id=31261533
    • Lý do rất đơn giản. “ski” là hậu tố phổ biến nhất trong họ Ba Lan, ví dụ nổi tiếng nhất là Kowalski. Có khá nhiều người là người Ba Lan hoặc gốc Ba Lan
      Tác giả của https://ciechanow.ski mà chúng ta thích ở đây cũng là một lập trình viên Ba Lan làm việc tại Apple
  • Hiện tôi đang cùng con trai làm một game bắn súng không gian 2D như dự án phụ. Góc nhìn từ trên xuống; ý tưởng là mỗi người chơi điều khiển một con tàu nào đó bay trong một không gian khép kín đầy mảnh vỡ không gian và bắn đối thủ
    Một yếu tố quan trọng của game là có thể di chuyển các mảnh vỡ không gian trong đấu trường, rồi dùng chúng một cách sáng tạo để nhốt đối thủ hoặc ngăn họ đạt mục tiêu. Trong khuôn khổ dự án, tôi định bỏ qua game engine hoàn toàn. Tôi muốn dạy con trai thêm một chút về cấu trúc ứng dụng, và dù sau này có dùng game engine có sẵn thì ít nhất cũng muốn trải qua quá trình tự triển khai toàn bộ một lần. Mọi thứ vẫn ổn cho đến khi chúng tôi bắt đầu tiếp cận phát hiện và xử lý va chạm. Từ lúc đó tình hình xấu đi rất nhanh. Dù có nền tảng toán lý thuyết, tôi nhanh chóng bị choáng ngợp bởi lượng edge case khổng lồ, và cuối cùng bỏ cuộc để dùng Box2D. Tôi không phải nhà phát triển game chuyên nghiệp, nhưng có hơn 20 năm kinh nghiệm phát triển và nền tảng toán học, vậy mà vẫn mắc sai lầm khi đánh giá thấp vấn đề này. Nói bằng lời thì nghe dễ, nhưng càng đi vào chi tiết, độ phức tạp dường như tăng theo cấp số nhân
    • Game đó có thật sự cần va chạm vật lý chân thực không? Nếu không, đó có thể là độ phức tạp không cần thiết. Gần như toàn bộ game bắn súng 2D trước năm 2000, và chỉ một phần rất nhỏ các game sau đó, dùng cách như vậy
      Cách phổ biến để làm game bắn súng bằng phép so sánh hình chữ nhật rất đơn giản có ở đây: https://kidscancode.org/blog/2016/08/pygame_shmup_part_3/
      Tuy nhiên, nếu các vật thể mảnh vỡ không gian cần va chạm và kết cụm một cách thực tế, và bạn muốn khiến tàu của người chơi khó đẩy các cụm vật thể nặng, thì dùng thư viện vật lý là hợp lý
    • Bạn đã xem tích phân Verlet [1] chưa? Nó khá thuyết phục và thực dụng cho nhiều mục đích, và thực ra khá đơn giản. Tôi đã tự ngạc nhiên khi có thể tạo một hệ thống vật lý cơ bản chỉ trong vài giờ sau khi xem tutorial tuyệt vời này [2]
      [1]https://m.youtube.com/watch?v=lS_qeBy3aQI&pp=ygUSVmVybGV0IGl...

[2]https://m.youtube.com/watch?v=3HjO_RGIjCU&pp=ygUSdmVybGV0IGl...

  • Dù vậy, tôi nghĩ đây sẽ là một bài học hay cho con trai bạn. Không phải lúc nào việc theo đuổi giấc mơ tự tay làm mọi phần của dự án từ đầu cũng đáng giá
  • Nếu không hữu ích ngay bây giờ thì sau này nó cũng sẽ là tài liệu tham khảo có ích. http://www.jeffreythompson.org/collision-detection/table_of_... đề cập đến phát hiện va chạm giữa điểm, hình tròn, hình chữ nhật, đường thẳng, đa giác và tam giác
  • Tôi luôn thích phần giải thích của game N: https://www.metanetsoftware.com/technique/tutorialA.html
    Đó là thời Flash còn có mặt ở khắp nơi
  • Tôi đã rất vui khi làm một demo TypeScript về chủ đề này với các quả bóng nảy và va chạm. Học được rất nhiều
    Mã nguồn: https://github.com/vandrieu/canvas-bouncing-ball
    Logic va chạm nằm trong src/collision.ts
    Kết quả/demo: https://vandrieu.github.io/canvas-bouncing-ball/
    • Demo thật sự rất hay, làm tốt lắm! Nếu bạn không phiền, tôi muốn thử biến nó thành một game nhiều người chơi nhỏ
      Nếu được, bạn có thể thêm giấy phép không?
  • Nếu muốn đi sâu hơn đến động lực học vật rắn và các ràng buộc, loạt bài blog này rất hữu ích với tôi: https://www.toptal.com/game/video-game-physics-part-i-an-int...
  • Va chạm là sự vi phạm ràng buộc không giao nhau theo từng cặp giữa các vật thể. Lực va chạm là hệ số nhân Lagrange của ràng buộc này. Pháp tuyến va chạm là đạo hàm riêng đã chuẩn hóa của hàm ràng buộc theo cấu hình của một vật thể
    • Cách đó có vẻ phù hợp khi tính toán vật lý ở tần số trên 1kHz và dùng thuật toán tích phân ổn định về mặt số học, tôn trọng bảo toàn năng lượng
      Nhưng trong game, người ta thường dùng phương pháp Euler-Cromer khá tùy ý cho cập nhật vật lý có khi xuống tới 30Hz, nên cần một cách tiếp cận khá khác
    • Thú vị đấy! Có tài liệu nào giải thích thêm về góc nhìn này không?
  • Tuyệt thật! Tôi thích phần giải thích, tính tương tác, và đặc biệt là giọng văn thân thiện của bài. Mong chờ các bài tiếp theo
  • Làm một engine vật lý vật rắn 2D là một dự án thật sự thú vị. Tôi từng làm một cái bằng JavaScript trước khi học đại số tuyến tính, và đã đào sâu vào toán để khiến nó chạy được
    Tôi mất vài tháng, nhưng cũng chỉ mới chạm nhẹ bề mặt ở mức hơi vượt qua các kiến thức cơ bản phổ biến. Việc tạo ra một engine ổn định, nơi các vật thể không lún vào nhau hoặc rung giật, là một hố thỏ không đáy, và hầu hết các bài viết nặng về toán mà tôi tìm được cũng gần như không bàn đến. Tôi đã hiểu phần toán nhờ loạt bài cũ của Christ Hecker
    http://www.chrishecker.com/Rigid_Body_Dynamics
    • Đúng vậy! “Part 3: Collision Response” về cơ bản là tài liệu tham khảo mà các bài này đang dùng
  • Tôi bắt đầu với canvas để học JavaScript, và đã làm vài game trình duyệt nhỏ dễ thương mà không có kinh nghiệm phát triển game. Một trong số đó là bản clone Galaga, nhìn chung chạy khá tốt
    Phần khó là va chạm của đạn. Tôi lẽ ra phải lấy vị trí hiện tại của viên đạn và vị trí ở bước thời gian tiếp theo, rồi xem hitbox của kẻ địch theo cách tương tự để kiểm tra có giao nhau không, nhưng tôi chỉ kiểm tra bước thời gian hiện tại. Vì vậy viên đạn có thể đi xuyên qua kẻ địch một cách kỳ diệu! Ngớ ngẩn thật. Có lẽ một ngày nào đó tôi sẽ quay lại sửa