Một hòn đá rơi xuống theo một quỹ đạo liên tục. Tại mọi khoảnh khắc, dù chia nhỏ tới đâu, nó đều có một vị trí xác định. Giữa hai thời điểm bất kỳ luôn tồn tại vô hạn thời điểm khác.
Máy tính không làm được điều đó. Nó chỉ tính được hữu hạn lần mỗi giây, mỗi lần cho ra một vị trí, rồi nhảy sang lần kế tiếp. Ở sáu mươi khung hình một giây, hòn đá trong game không rơi. Nó dịch chuyển tức thời sáu mươi lần mỗi giây, và mắt người ghép những cú dịch chuyển đó thành chuyển động.
Toàn bộ lập trình game, ở tầng sâu nhất, là việc quản lý khoảng cách giữa hai điều trên. Bài viết này nói về khái niệm nằm dưới khoảng cách đó, cùng bốn lớp lỗi mà nó sinh ra và những giải pháp kinh điển của ngành.
Khái niệm gốc: rời rạc hóa miền liên tục
Rời rạc hóa là việc thay một đại lượng biến thiên liên tục bằng một dãy hữu hạn các giá trị được lấy mẫu tại những điểm cách nhau.
Trong game, ít nhất bốn thứ bị rời rạc hóa cùng lúc. Thời gian bị chia thành các bước. Không gian bị chia thành lưới, ô, hoặc bị lượng tử hóa xuống độ chính xác của số thực dấu phẩy động. Chuyển động bị chia thành các khung hình hoạt ảnh. Và mọi giá trị số đều bị làm tròn về một biểu diễn hữu hạn.
Điểm cần nắm ngay từ đầu là rời rạc hóa không phải một khiếm khuyết tạm thời của phần cứng yếu, thứ sẽ biến mất khi máy đủ nhanh. Nó là điều kiện tồn tại của tính toán. Dù máy tính nhanh gấp một triệu lần, nó vẫn tính từng bước một, và mọi hệ quả trong bài này vẫn còn nguyên.
Chú thích: Mô phỏng không đi theo đường cong, nó nhảy giữa các điểm nằm trên đường cong. Khoảng cách giữa hai đường là toàn bộ vùng vấn đề của lập trình game thời gian thực.
Vòng lặp mô phỏng như một mô hình tính toán
Phần lớn phần mềm chạy theo mô hình phản ứng: chương trình ngồi im, người dùng làm gì đó, chương trình xử lý rồi ngồi im tiếp. Một ứng dụng quản lý kho không tự động thay đổi khi không ai đụng vào nó.
Game chạy theo mô hình ngược lại. Nó tiến về phía trước liên tục dù người chơi có làm gì hay không. Kẻ địch vẫn di chuyển, thời gian hồi chiêu vẫn đếm, vật thể vẫn rơi. Người chơi không kích hoạt vòng lặp, họ chỉ can thiệp vào nó.
Cấu trúc tối giản của vòng lặp đó gồm ba bước lặp mãi: đọc đầu vào, cập nhật trạng thái, dựng hình.
Ở bài viết trước về mô hình hình thức, luật được mô tả là hàm nhận trạng thái và hành động rồi trả về trạng thái mới. Trong mô phỏng thời gian thực, hàm đó có thêm một tham số thứ ba, và nó là tham số gây ra mọi rắc rối: khoảng thời gian đã trôi qua, thường được gọi là delta time hoặc dt.
Trạng thái mới bằng hàm luật áp lên trạng thái cũ, đầu vào của người chơi, và dt.
Một chi tiết đáng chú ý về dt mà người mới thường không nhận ra. Delta time cho khung hình hiện tại về mặt logic là không tính được, vì trước khi mô phỏng xong khung hình đó ta không thể biết nó kéo dài bao lâu. Cách xử lý mà gần như mọi game đang tồn tại đều dùng là lấy delta time của khung hình trước và giả định khung hình này sẽ kéo dài xấp xỉ như vậy.
Nói cách khác, ngay từ dòng đầu tiên, vòng lặp game đã đứng trên một phép đoán.
Bốn lớp lỗi sinh ra từ rời rạc hóa
Lớp thứ nhất: sai số tích lũy. Mỗi bước mô phỏng đều xấp xỉ, và sai số của các bước cộng dồn. Với một số phương pháp tính, sai số này không chỉ tích lũy mà còn tự khuếch đại. Hệ lò xo giảm chấn tích phân bằng phương pháp Euler tường minh, thay vì tắt dần và hội tụ về gốc, lại tăng năng lượng theo thời gian, và hiện tượng này xảy ra ngay cả với bước thời gian nhỏ. Luôn tồn tại một độ cứng lò xo mà vượt qua đó thì hệ sẽ nổ tung, bất kể ta chia nhỏ bước thời gian tới đâu.
Lớp thứ hai: xuyên vật thể. Nếu vật thể di chuyển đủ nhanh so với bước thời gian, nó có thể nhảy từ bên này sang bên kia một bức tường mà chưa từng chồng lấn với bức tường ở bất kỳ bước nào. Một viên đạn bay 1000 pixel mỗi giây, mô phỏng ở 15 khung hình một giây, dịch chuyển 66 pixel mỗi bước, và sẽ đi xuyên qua một bức tường dày 32 pixel. Đây là lỗi kinh điển nhất trong toàn bộ mô phỏng thời gian thực, và cách xử lý là dùng phát hiện va chạm liên tục, tức kiểm tra cả đoạn đường đi giữa hai bước chứ không chỉ hai điểm đầu cuối.
Lớp thứ ba: hành vi phụ thuộc tốc độ khung hình. Nếu dt được truyền thẳng vào mô phỏng, thì cùng một game chạy trên hai máy khác nhau sẽ cho kết quả khác nhau. Sai lệch giữa mô phỏng chạy ở 30 và 60 khung hình một giây được ghi nhận vào khoảng 10 đến 30 phần trăm. Hệ quả có thể tinh vi như game cho cảm giác hơi khác tùy tốc độ khung hình, hoặc cực đoan như hệ lò xo văng ra vô cực, vật thể nhanh xuyên tường, và nhân vật rơi xuyên sàn.
Lớp thứ tư: mất tính xác định. Đây là hệ quả nghiêm trọng nhất về mặt hệ thống. Khi mô phỏng không xác định, hai máy nhận cùng một chuỗi đầu vào vẫn cho ra hai trạng thái khác nhau, và điều đó phá vỡ đồng bộ mạng, phá vỡ tính năng phát lại trận đấu, và làm cho lỗi không tái hiện được. Tính xác định có nghĩa là cùng đầu vào thì cho ra chính xác cùng đầu ra, và nó đặc biệt quan trọng với game chơi mạng cũng như những game đòi hỏi tinh chỉnh cực kỳ chính xác như game đối kháng hoặc game nền tảng.
Chú thích: Phim nhựa là phép rời rạc hóa quen thuộc nhất. Không có chuyển động nào trên cuộn phim, chỉ có những khung hình tĩnh cách nhau đều đặn, và bộ não người ghép chúng lại thành chuyển động.
Giải pháp kinh điển: bước thời gian cố định kèm bộ tích lũy
Bài viết Fix Your Timestep của Glenn Fiedler, xuất bản năm 2004, đưa ra giải pháp đã trở thành chuẩn của ngành. Ý tưởng cốt lõi nằm ở một câu: tách rời tốc độ mô phỏng khỏi tốc độ dựng hình.
Mô phỏng luôn chạy với bước cố định, thường là 1 chia 60 giây. Dựng hình chạy nhanh nhất có thể tùy phần cứng. Nối hai thứ đó lại với nhau là một biến tích lũy.
Cách hoạt động như sau. Mỗi khung hình, đo thời gian thực đã trôi qua và cộng vào bộ tích lũy. Sau đó, chừng nào bộ tích lũy còn lớn hơn hoặc bằng bước cố định, chạy một bước mô phỏng với đúng bước cố định đó rồi trừ đi khỏi bộ tích lũy. Phần thời gian dư chưa đủ một bước không bị vứt đi mà được chuyển sang khung hình sau qua chính biến tích lũy.
Hệ quả là trong một khung hình dựng hình, mô phỏng có thể chạy không lần, một lần, hai lần hoặc nhiều hơn, tùy máy nhanh hay chậm, nhưng mỗi bước mô phỏng luôn nhận đúng cùng một dt.
Hai chi tiết bổ sung làm cho giải pháp này dùng được trong thực tế.
Chi tiết thứ nhất là giới hạn trên cho delta time, thường đặt ở khoảng 0,25 giây. Nếu không có giới hạn này, một lần treo máy dài, chẳng hạn khi lập trình viên dừng ở một điểm ngắt trong trình gỡ lỗi, sẽ khiến bộ tích lũy phình lên và vòng lặp phải chạy hàng nghìn bước mô phỏng, khiến khung hình sau càng chậm hơn, khiến bộ tích lũy càng phình thêm. Hiện tượng này có tên riêng là vòng xoáy tử thần.
Chi tiết thứ hai là nội suy khi dựng hình. Vì mô phỏng và dựng hình không đồng bộ, tại thời điểm vẽ thường có một phần bước còn dư trong bộ tích lũy. Tỷ lệ giữa phần dư và bước cố định cho ra một hệ số từ 0 đến 1, và game vẽ trạng thái nội suy giữa trạng thái trước và trạng thái hiện tại theo hệ số đó. Không có bước này, hình ảnh sẽ giật nhẹ dù mô phỏng hoàn toàn đúng.
Lợi ích thì đáng kể. Bước cố định cho mô phỏng xác định bất kể tốc độ dựng hình, và trong game chơi mạng nó được ghi nhận là giảm mất đồng bộ tới khoảng 95 phần trăm.
Chú thích: Vòng lặp bước thời gian cố định. Bước 3 có thể chạy không lần hoặc nhiều lần trong một khung hình, nhưng mỗi lần luôn nhận đúng cùng một dt, và đó là thứ tạo ra tính xác định.
Chọn phương pháp tích phân: vì sao game khác mô phỏng khoa học
Khi đã có bước thời gian cố định, câu hỏi tiếp theo là trong mỗi bước thì tính vị trí mới thế nào. Đây là bài toán tích phân số, và cách chọn phương pháp cho thấy một khác biệt triết học đáng chú ý giữa game và mô phỏng khoa học.
Phương pháp Euler tường minh cập nhật vị trí theo vận tốc cũ rồi mới cập nhật vận tốc. Nó rẻ nhất, dễ hiểu nhất, và như đã nói ở trên, nó bơm năng lượng vào hệ theo thời gian.
Phương pháp Euler bán ẩn khác đúng một chỗ: đảo thứ tự hai dòng lệnh, cập nhật vận tốc trước rồi dùng vận tốc mới để cập nhật vị trí. Về bậc chính xác nó vẫn là bậc một, không hơn gì Euler tường minh. Nhưng nó là phương pháp bảo toàn cấu trúc, và kết quả thực tế tốt hơn hẳn: cùng hệ lò xo giảm chấn với cùng bước thời gian, Euler bán ẩn cho kết quả ổn định và rất gần với nghiệm chính xác. Phần lớn engine vật lý thương mại dùng chính phương pháp này. Nó rẻ, dễ cài đặt, ổn định hơn nhiều so với Euler tường minh, và có xu hướng bảo toàn năng lượng trung bình ngay cả khi bị đẩy tới giới hạn.
Phương pháp Verlet là bậc hai và cũng bảo toàn cấu trúc, cho độ chính xác cao hơn và tốn ít bộ nhớ hơn khi mô phỏng số lượng lớn hạt.
Phương pháp Runge-Kutta bậc bốn thì chính xác hơn tất cả những cái trên, và đây là chỗ thú vị. Nó không phải phương pháp bảo toàn cấu trúc, tức nó vẫn đưa thêm năng lượng vào hệ và sinh sai số tích lũy trong quá trình mô phỏng dài. Nó cũng đắt hơn nhiều lần vì mỗi bước phải tính lại nhiều lần, và nếu có va chạm thì mỗi lần tính lại đều kéo theo kiểm tra va chạm.
Kết luận thực dụng của giới làm game khá thẳng thắn: với game, độ ổn định quan trọng hơn độ chính xác. Một mô phỏng sai lệch vài phần trăm so với vật lý thật nhưng không bao giờ nổ tung thì dùng được. Một mô phỏng chính xác hơn nhưng thỉnh thoảng làm nhân vật văng ra ngoài bản đồ thì không. Trong nhiều trường hợp, chạy Euler bán ẩn ở tần số cao còn nhanh hơn và tốt hơn là chạy Runge-Kutta bậc bốn.
Đây chính là điểm phân biệt tư duy mô phỏng game với tư duy mô phỏng khoa học. Nhà khoa học tối ưu độ trung thực với hiện thực. Người làm game tối ưu độ ổn định và độ nhất quán của trải nghiệm, và sẵn sàng đánh đổi độ trung thực để có hai thứ đó.
Rời rạc hóa không chỉ xảy ra với thời gian
Sau khi quen với ý này ở trục thời gian, đáng chú ý là nó lặp lại ở mọi trục khác trong game.
Không gian bị rời rạc hóa thành lưới ô vuông trong game chiến thuật và roguelike, thành lưới điều hướng cho trí tuệ nhân tạo tìm đường, thành các khối trong game xây dựng. Ngay cả trong game ba chiều liền mạch, tọa độ vẫn là số thực dấu phẩy động, tức một tập hữu hạn các giá trị phân bố không đều, và điều đó sinh ra hàng loạt vấn đề khi nhân vật ở rất xa gốc tọa độ.
Giá trị số bị rời rạc hóa thêm một lần nữa khi gửi qua mạng, vì băng thông có hạn nên vị trí và góc quay thường bị lượng tử hóa xuống ít bit hơn trước khi truyền đi.
Hoạt ảnh bị rời rạc hóa thành các khung hình khóa, rồi nội suy trở lại giữa chúng.
Nhìn từ góc này, mọi thứ trong một trò chơi đều là xấp xỉ hữu hạn của một cái gì đó liên tục, và toàn bộ nghề lập trình game là nghệ thuật chọn chỗ nào chấp nhận được xấp xỉ thô, chỗ nào bắt buộc phải mịn.
Khi rời rạc là công cụ thiết kế chứ không phải hạn chế
Có một mặt thứ hai của câu chuyện, và nó ít được nói tới.
Trong nhiều thể loại, người thiết kế cố tình rời rạc hóa thô hơn mức phần cứng bắt buộc, vì bước rời rạc thô làm cho hệ thống dễ đọc và dễ làm chủ hơn.
Game đối kháng là ví dụ rõ nhất. Ở đó, mọi thứ đều được đo bằng khung hình chứ không bằng giây. Một đòn đánh có bao nhiêu khung hình khởi động, bao nhiêu khung hình có hiệu lực, bao nhiêu khung hình hồi phục. Người chơi nghiêm túc học thuộc những con số đó và ra quyết định dựa trên chúng. Nếu hệ thống này chạy theo thời gian liên tục, toàn bộ chiều sâu chiến thuật của thể loại sẽ biến mất, vì không còn gì để đếm và so sánh.
Cùng logic đó giải thích khung hình bất tử sau khi trúng đòn, khoảng dừng một vài khung hình khi đòn đánh chạm mục tiêu, và coyote time được định nghĩa bằng số khung hình chứ không bằng mili giây. Tất cả đều là những đơn vị rời rạc mà người chơi có thể cảm nhận và dần dần học được.
Lưới ô vuông trong game chiến thuật theo lượt cũng vậy. Nó không tồn tại vì máy không mô phỏng nổi không gian liên tục, mà vì lưới làm cho khoảng cách trở nên đếm được, và khoảng cách đếm được làm cho quyết định trở nên tính toán được.
Nói cách khác, rời rạc hóa bắt đầu như một ràng buộc của máy tính và kết thúc như một công cụ để tạo ra tính đọc được. Đây là một trường hợp nữa của quy luật đã bàn ở bài về phần cứng: rất nhiều quy ước thiết kế sinh ra từ giới hạn kỹ thuật rồi tìm được một chức năng thứ hai đủ giá trị để tồn tại tiếp.
Danh sách kiểm tra cho một vòng lặp mô phỏng đúng
Nếu chuyển toàn bộ bài viết thành một danh sách kiểm tra thực dụng, có sáu mục.
Mô phỏng có tách rời khỏi tốc độ dựng hình không. Nếu logic game nằm chung một hàm với lệnh vẽ và nhận dt biến thiên, thì mọi vấn đề trong bài này đang chờ sẵn.
Delta time có bị giới hạn trên không. Thiếu mục này, một lần treo máy sẽ thành một vòng xoáy không thoát ra được.
Phần thời gian dư có được giữ lại cho khung hình sau không, hay bị vứt đi.
Có nội suy khi dựng hình không. Thiếu nó thì mô phỏng đúng nhưng hình ảnh vẫn giật.
Vật thể nhanh nhất trong game di chuyển bao nhiêu trong một bước, và con số đó có nhỏ hơn vật thể mỏng nhất mà nó phải va chạm không. Nếu không, cần phát hiện va chạm liên tục.
Cùng một chuỗi đầu vào chạy hai lần có cho ra cùng một kết quả không. Nếu câu trả lời là không, thì tính năng phát lại, gỡ lỗi theo bản ghi và chơi mạng đều sẽ rất khó về sau.
Sáu câu hỏi này không mất nhiều thời gian để trả lời, nhưng chúng loại bỏ được phần lớn những lỗi khó chịu nhất mà một dự án game gặp phải, và tốt nhất là trả lời chúng ở tuần đầu tiên chứ không phải ở tháng thứ mười.
Tài liệu tham khảo
- Fiedler, Glenn. Fix Your Timestep, Gaffer on Games, 2004. Bài viết chuẩn của ngành về bước thời gian cố định, bộ tích lũy và nội suy khi dựng hình. https://gafferongames.com/post/fix_your_timestep/
- Fiedler, Glenn. Integration Basics, Gaffer on Games. Nguồn của so sánh giữa Euler tường minh, Euler bán ẩn và Runge-Kutta bậc bốn trên hệ lò xo giảm chấn. https://gafferongames.com/post/integration_basics/
- Game Mechanics Optimizations, Fixed Timestep (Gaffer Method). Nguồn của các con số định lượng về sai lệch giữa 30 và 60 khung hình, ví dụ xuyên tường, và mức giảm mất đồng bộ mạng. https://github.com/raduacg/game-mechanics-optimizations/blob/main/06_fixed_timestep.md
- Cute Framework, Game Loop and Time. Nguồn của lưu ý rằng delta time của khung hình hiện tại không tính được và mọi game đều dùng giá trị của khung hình trước. https://randygaul.github.io/cute_framework/topics/game_loop_and_time
- Cute Framework, CF_DELTA_TIME_FIXED. Nguồn của định nghĩa tính xác định và vì sao nó quan trọng với game chơi mạng, game đối kháng và game nền tảng. https://randygaul.github.io/cute_framework/time/cf_delta_time_fixed
- Tetra, tài liệu về enum Timestep. Nguồn của mô tả đánh đổi giữa chế độ bước cố định và bước biến thiên trong một engine thực tế. https://docs.rs/tetra/latest/tetra/time/enum.Timestep.html
- Pronost, Nicolas. Game Physics: Numerical Integration, Đại học Utrecht. Bài giảng về Euler, Euler ngược, Euler bán ẩn và Verlet. https://perso.liris.cnrs.fr/npronost/UUCourses/GamePhysics/lectures/lecture%205%20Numerical%20Integration.pdf
- GameDev.net, How Does Runge-Kutta 4 Work in Games. Thảo luận thực hành về vì sao ổn định quan trọng hơn chính xác trong game. https://gamedev.net/forums/topic/679116-how-does-runge-kutta-4-work-in-games/
- GameDev.net, Fix Your Time Step, thảo luận về giới hạn delta time và về việc bước biến thiên khiến mô phỏng mất tính xác định. https://gamedev.net/forums/topic/684244-fix-your-time-step-need-help/5321957/
- A Review of Differentiable Simulators, arXiv. Nguồn của công thức hình thức cho Euler bán ẩn và bối cảnh về phương pháp bảo toàn cấu trúc. https://arxiv.org/pdf/2407.05560
0 Lời bình