- RollerCoaster Tycoon ra mắt năm 1999 là một trò chơi mô phỏng được viết gần như بالكامل bằng assembly, vẫn duy trì hiệu năng ổn định ngay cả khi xử lý hàng nghìn vị khách theo thời gian thực
- Nhà phát triển Chris Sawyer đã chọn khả năng kiểm soát ở mức thấp thay vì ngôn ngữ bậc cao, qua đó hoàn thiện một trong những trò chơi assembly quy mô lớn cuối cùng với hiệu suất CPU được đẩy lên tối đa
- Thông qua dự án của fan OpenRCT2, các mẫu tối ưu hóa tinh vi và kỹ thuật tiết kiệm bộ nhớ của bản gốc đã được phân tích bằng phương pháp đảo ngược
- Trò chơi sử dụng phép dịch bit và phân chia chi tiết kiểu dữ liệu để tăng tốc độ tính toán và hiệu quả bộ nhớ đệm, đồng thời cho phép mô phỏng quy mô lớn nhờ giới hạn độ sâu tìm đường và loại bỏ phép tính va chạm
- Cấu trúc này là một hình mẫu tối ưu hóa tận dụng sáng tạo các ràng buộc kỹ thuật, và đến nay vẫn cho thấy tầm quan trọng của cách tiếp cận loại bỏ các phép tính không cần thiết ngay từ giai đoạn thiết kế
Phân tích cấu trúc tối ưu hóa của RollerCoaster Tycoon
- RollerCoaster Tycoon (RCT), phát hành năm 1999, được viết gần như hoàn toàn bằng assembly, và được đánh giá là một trò chơi vẫn giữ được tốc độ khung hình ổn định trên phần cứng thời đó dù phải mô phỏng hàng nghìn tác thể theo thời gian thực
- Dựa trên nội dung được đề cập trong podcast game của Đức Stay Forever, bài viết phân tích cụ thể cách Chris Sawyer đạt được mức tối ưu hóa cực đoan như vậy
- Mã nguồn gốc không được công khai, nhưng thông qua dự án OpenRCT2 do cộng đồng fan thực hiện, có thể xác nhận bằng phân tích đảo ngược cấu trúc mã và các kỹ thuật tối ưu hóa
-
Tối đa hóa hiệu năng dựa trên assembly
- RCT được viết bằng assembly thay vì C hay C++, cho phép kiểm soát hiệu năng chi tiết hơn rất nhiều so với các game cùng thời
- Ví dụ, Doom (1993) phần lớn được viết bằng C, trong khi RCT gần như được triển khai hoàn toàn bằng assembly
- Cách tiếp cận này đã là điều hiếm thấy từ cuối những năm 1990, và RCT được xem là một trong những game assembly quy mô lớn cuối cùng
- Vào thời điểm đó, khả năng tối ưu hóa tự động của trình biên dịch còn hạn chế, nên tối ưu hóa thủ công tạo ra khác biệt rất lớn về hiệu năng
-
Phân tích mã qua OpenRCT2
- OpenRCT2 là dự án mã nguồn mở do fan tái hiện hoàn chỉnh trò chơi gốc, vẫn giữ nguyên tài nguyên của bản gốc đồng thời duy trì độ tương thích 100%
- Các phiên bản đầu tái hiện hành vi gần như giống hệt mã gốc, sau đó được bổ sung nhiều cải tiến khác nhau
- Nhờ dự án này, có thể quan sát được các mẫu tối ưu hóa tinh vi trong mã nguồn gốc
-
Phân chia chi tiết kiểu dữ liệu — tiết kiệm bộ nhớ
- RCT lưu dữ liệu tiền tệ với kích thước khác nhau tùy tình huống
- Ví dụ: tổng giá trị công viên dùng biến 4 byte, còn giá trong cửa hàng dùng biến 1 byte
- Mục tiêu của cách phân chia này là tiết kiệm bộ nhớ và cải thiện hiệu quả bộ nhớ đệm; tuy nhiên, trên CPU hiện đại khác biệt hiệu năng gần như không còn, nên trong OpenRCT2 chúng được thống nhất thành biến 8 byte duy nhất
-
Tối ưu phép toán bằng dịch bit
- Trong mã có các phép toán như
NewValue = OldValue >> dùng để thay thế phép chia cho lũy thừa của 2
- Kiểu tối ưu hóa này chỉ khả thi khi phép nhân/chia liên quan đến lũy thừa của 2, nên có thể thấy ngay cả các công thức trong game cũng được thiết kế để phù hợp với điều kiện đó
- Nói cách khác, cấu trúc toán học đã được xây dựng có tính đến hiệu quả tính toán của CPU ngay từ giai đoạn thiết kế game
-
Thiết kế game có tính đến hiệu năng
- Vì Chris Sawyer vừa là lập trình viên vừa là nhà thiết kế game duy nhất, RCT có thể xây dựng cấu trúc chú trọng hiệu năng ngay từ bước thiết kế
- Ví dụ tiêu biểu là hệ thống khách tham quan (Pathfinding)
- Trong phần lớn game mô phỏng, khách sẽ chọn đích đến rồi tìm đường, nhưng ở RCT khách đi bộ ngẫu nhiên rồi tình cờ phát hiện trò chơi
- Cách làm này là một cấu trúc tránh được chi phí tìm đường quy mô lớn, nhờ đó có thể xử lý đồng thời hàng nghìn vị khách
- Khi bắt buộc phải tìm đường (ví dụ: thợ bảo trì di chuyển đến trò chơi bị hỏng), game áp dụng giới hạn độ sâu tìm kiếm để tránh tụt khung hình
- Khách thường chỉ tìm tối đa 5 giao lộ, thợ bảo trì tối đa 8
- Khách đã mua bản đồ sẽ có giới hạn tìm kiếm tăng lên 7
- Những giới hạn này không chỉ là một thỏa hiệp kỹ thuật đơn thuần mà còn là một cấu trúc tối ưu hóa được tích hợp tự nhiên vào lối chơi
-
Xử lý đám đông và lược bỏ tránh va chạm
- RCT loại bỏ hoàn toàn phép tính va chạm hay né tránh giữa các vị khách
- Hàng nghìn vị khách có thể cùng chia sẻ một ô đường đi
- Thay vào đó, game theo dõi mật độ dân số xung quanh để giảm mức độ hạnh phúc của khách khi khu vực quá đông
- Người chơi vẫn phải quản lý tình trạng đông đúc, nhưng lượng tính toán thì thấp hơn rất nhiều
- Đây được đánh giá là ví dụ tiêu biểu cho việc loại bỏ các phép tính vật lý phức tạp mà vẫn giữ nguyên trải nghiệm game
-
Hàm ý cho phát triển hiện đại
- Tối ưu hóa trong RCT được xem là một ví dụ tận dụng sáng tạo các ràng buộc kỹ thuật
- Ngày nay cách tiếp cận này vẫn khả thi, nhưng đòi hỏi sự phối hợp chặt chẽ giữa lập trình viên và nhà thiết kế
- Đôi khi, thay vì giải quyết một vấn đề kỹ thuật, loại bỏ chính vấn đề đó ngay từ giai đoạn thiết kế lại mang đến cải thiện hiệu năng lớn hơn
2 bình luận
Mong mọi người hãy dành nhiều tình cảm cho RollerCoaster Tycoon.
Ý kiến trên Hacker News
Warcraft 1, 2 và StarCraft đều dùng kích thước bản đồ theo lũy thừa của 2
Nhờ vậy, ngay cả trên CPU 386/486 chậm, chúng vẫn có thể tăng tốc bằng phép dịch bit thay cho phép chia và nhân
Việc render bản đồ, sprite, font, hiệu ứng sương mù... được xử lý bằng hàng nghìn dòng assembly, còn phần còn lại là mã có tính di động cao viết bằng C
Với Blackthorne, các bản SNES, Genesis và DOS đều được port thủ công bằng assembly riêng, còn bản PC thì tạo macro cho 100 nghìn dòng mã render để phục vụ VGA Mode X
Từ những trải nghiệm đó, Blizzard rút ra bài học rằng “assembly ngốn quá nhiều thời gian phát triển”
Comanche: Maximum Overkill là một game mô phỏng trực thăng dựa trên voxel được viết hoàn toàn bằng assembly, nhưng việc port sang protected mode quá khó nên từ các bản sau đã chuyển sang render polygon
EA đã công khai mã nguồn series Command & Conquer, nhưng không có Tiberian Sun và Red Alert 2
Giá mà StarCraft cũng được công khai vì mục đích bảo tồn lịch sử
Từ đó tôi hoàn toàn mê game
Cũng tò mò không biết ông ấy có hoạt động trong demoscene không
Tôi từng làm tư vấn viên một thời gian ngắn vào khoảng lúc WC3 phát hành
Như bài viết đã nói, có vẻ khi nhà thiết kế và lập trình viên là cùng một người thì kết quả thường ấn tượng hơn nhiều
Cấu trúc phân tầng của các tập đoàn lớn rồi cũng có thể tạo ra thứ gì đó nếu dồn đủ nhân lực, nhưng những kết quả thật sự sáng tạo thường bắt đầu và hoàn thiện trong đầu của một cá nhân
Tôi cũng nghĩ tương lai của các công cụ phát triển AI có thể sẽ là sự quay lại của “thời đại phát triển một người” kiểu này
Nhà thiết kế game vẫn cần cân nhắc các đặc tính số học
Nhà thiết kế giỏi thường hiểu rằng những yếu tố như hiệu quả tính toán hay độ chính xác có thể ảnh hưởng đến cân bằng game
Dạo này có không ít người làm game bỏ qua chuyện đó, nhưng đôi khi đó lại là nguyên nhân ngầm khiến chất lượng game đi xuống
Bây giờ phép cộng mất khoảng 1 chu kỳ, phép nhân 3 chu kỳ, phép chia 12 chu kỳ, và nhiều phép toán còn được xử lý song song
Thời Pentium ngày xưa thì phép chia mất tới 46 chu kỳ và xung chỉ khoảng 100MHz
Giờ đây bố cục bộ nhớ mới là thứ quan trọng hơn nhiều — chỉ một lần cache miss là mất 100~1000 chu kỳ
Tính toán trên
int[]nhanh hơnMonster[]rất nhiềuCó sự đánh đổi giữa tốc độ, độ chính xác, kích thước lưu trữ và độ phức tạp
Những bài báo như Toward an API for the Real Numbers đưa ra cách tiếp cận nhằm giải quyết dần các vấn đề này
Có nhiều phương pháp như sai số số thực dấu chấm động, interval arithmetic, symbolic computation..., nhưng rốt cuộc nếu không hiểu trade-off thì sẽ sớm vướng vấn đề
Ví dụ, Fumito Ueda trong Shadow of the Colossus đã cân nhắc rất kỹ tính khả thi về mặt kỹ thuật, và Doom cũng là sự kết hợp giữa sáng tạo và công nghệ
Có thể tham khảo bài phỏng vấn liên quan
Bug, tính nhất quán của cốt truyện và cảm giác nhập vai còn quan trọng hơn
Tất nhiên nếu tụt khung hình quá nặng thì chất lượng sẽ giảm, nhưng nếu game chạy mượt trên phần cứng mục tiêu thì nên tập trung cải thiện ở các mặt khác
Tôi điều chỉnh để có thể nạp hằng số tức thời bằng lệnh Thumb-2, qua đó tránh được memory stall
Nhờ vậy có thể dùng số ngẫu nhiên nhanh và hiệu quả, và mọi bài test đều qua
Nhưng sau này khi chuyển sang Cortex-M0 thì đoạn mã đó bị bỏ đi
Tôi thấy thú vị ở chỗ các ràng buộc kỹ thuật được chuyển hóa thành yếu tố gameplay
Nó làm tôi nhớ đến hệ thống Blood Moon trong The Legend of Zelda
Câu giải thích “dùng
>>3thay cho/8để tiết kiệm phép chia” là không đúng với compiler hiện đạiNếu kiểu dữ liệu phù hợp, compiler sẽ tự tối ưu thành phép dịch bit
Tôi khá ngạc nhiên khi thấy câu “dịch trái trong nhị phân thì thành gấp đôi”
Thật lạ khi đến năm 2026 mà những khái niệm cơ bản như vậy lại có thể trở nên mới mẻ đến thế
Câu “compiler không đổi phép nhân với lũy thừa của 2 thành phép dịch bit” là một trò đùa rất cũ
Ngay từ những năm 2000, compiler đã tối ưu kiểu đó một cách hiển nhiên đến mức chỉ muốn ngáp
Đọc rất thú vị. Về RCT thì cũng xin gợi ý thêm các tài liệu dưới đây
Tôi tò mò liệu ở các studio lớn, việc nâng tầm ràng buộc kỹ thuật thành đặc trưng của game có còn khả thi không
Cũng như trong storytelling, trở ngại khiến câu chuyện trở nên hấp dẫn hơn, nhà phát triển solo có thể biến giới hạn kỹ thuật thành yếu tố sáng tạo
Tôi nghĩ đến những cách tiếp cận như diễn giải bug hay glitch thành mini-game
Khi nhìn vào phần pathfinding của RCT, tôi nhớ đến video YouTube của Marcel Vos
Anh ấy đăng rất nhiều video đào sâu vào cách RCT hoạt động bên trong