Bí quyết đằng sau hệ thống giao thông của Pizza Tycoon trên CPU 25 MHz

Bí quyết đằng sau hệ thống giao thông của Pizza Tycoon trên CPU 25 MHz

Bài viết này phân tích cách trò chơi kinh điển Pizza Tycoon (1994) đã tạo ra hệ thống giao thông sống động dù chỉ chạy trên bộ vi xử lý 25 MHz. Bằng cách phân tích mã Assembly, tác giả phát hiện ra một giải pháp cực kỳ tối giản và hiệu quả, tránh xa các thuật toán phức tạp của lập trình hiện đại.

Bối cảnh và thách thức

Tôi đang phát triển Pizza Legacy, một bản mã nguồn mở tái hiện lại tựa game DOS năm 1994 mang tên Pizza Tycoon. Một trong những đặc điểm nổi bật của game là chế độ xem đường phố cận cảnh, nơi người chơi có thể thấy dòng xe cộ tấp nập di chuyển trên đường.

Điều đáng kinh ngạc là tất cả những hiệu ứng này diễn ra mượt mà trên một bộ vi xử lý 386 chỉ có tốc độ 25 MHz. Khi bắt đầu dự án vào năm 2010, tôi đã dành 14 năm để cố gắng tái tạo hệ thống giao thông này. Những nỗ lực trước đây của tôi thường thất bại vì tôi áp dụng các tư duy lập trình hiện đại như đồ thị cảnh (scene graphs), thuật toán tìm đường (pathfinding) hay phát hiện va chạm phức tạp, khiến hệ thống trở nên quá nặng nề.

Bản đồ thành phố trong game

Cuối cùng, tôi đã quay lại nghiên cứu mã Assembly gốc của game để hiểu cách các nhà phát triển trước đây đã làm được điều này.

Thiết kế bản đồ và hệ thống đường một chiều

Chìa khóa để tối ưu hóa hiệu năng nằm ở chính thiết kế của bản đồ. Trong Pizza Tycoon, bản đồ được xây dựng từ một lưới ô (grid) kích thước 160x120. Mỗi ô đường đều mang một hướng đi cố định.

Ví dụ, ô đường 0x16 chỉ cho phép xe đi từ trái sang phải, trong khi ô 0x06 chỉ dành cho xe đi từ phải sang trái. Về cơ bản, toàn bộ thành phố là một tập hợp các đường một chiều.

Lưới ô của bản đồ

Điều này có nghĩa là xe cộ không cần thực hiện bất kỳ thuật toán tìm đường nào. Khi một xe biết nó đang ở ô nào, nó chỉ cần đi theo hướng được định sẵn bởi ô đó. Tại các ngã rẽ, xe sẽ tung đồng xu ngẫu nhiên: 50% cơ hội đi thẳng và 50% cơ hội rẽ. Tuy nhiên, có một quy tắc nhỏ để tránh việc xe quay vòng liên tục: nếu bạn vừa rẽ trái, ngã rẽ tiếp theo sẽ buộc bạn phải đi thẳng.

Cơ chế di chuyển và xử lý logic

Xe di chuyển với tốc độ 1 pixel mỗi khung hình (frame). Tuy nhiên, logic xử lý ranh giới giữa các ô chỉ chạy mỗi 16 khung hình một lần (vì mỗi ô rộng 16 pixel).

Khi một xe mới xuất hiện, bộ đếm tiến trình của nó được đặt ngẫu nhiên từ 1 đến 16. Điều này giúp phân tán tải xử lý, đảm bảo không phải tất cả các xe đều kiểm tra logic thay đổi ô cùng một lúc.

Hướng di chuyển của xe trên các ô

Phát hiện va chạm tối giản

Đây là phần thú vị nhất. Thay vì sử dụng hệ thống phát hiện va chạm phức tạp, bản gốc sử dụng phương pháp kiểm tra từng cặp (O(n²)) nhưng được tối ưu hóa cực kỳ thông minh.

Mỗi khung hình, hệ thống sẽ kiểm tra từng chiếc xe với tất cả các xe còn lại để xem chúng có bị va chạm ở khung hình tiếp theo hay không. Tuy nhiên, mã lệnh được viết để "thoát" (early exit) càng sớm càng tốt.

Bước đầu tiên là kiểm tra hướng di chuyển. Vì đường là một chiều, một chiếc xe đi về phía Đông không bao giờ có thể va chạm với một chiếc xe đi về phía Tây trên cùng một con đường. Do đó, cặp xe này sẽ bị loại bỏ ngay lập tức mà không cần đọc bất kỳ tọa độ nào. Nhờ đó, phần lớn các phép kiểm tra va chạm tốn rất ít tài nguyên CPU.

Khi một xe bị chặn, nó sẽ chờ trong 10 ticks, tạo ra hiệu ứng tắc đường tự nhiên mà không cần bất kỳ mô hình vật lý nào.

Sinh xe và kết luận

Khi người chơi cuộn bản đồ, game sẽ quét các ô trong khung nhìn và sinh xe ngẫu nhiên dựa trên mật độ giao thông của khu vực đó. Những chiếc xe đi ra khỏi màn hình sẽ được "tái sinh" ở phía bên kia với hướng ngược lại, giúp duy trì số lượng xe ổn định mà không cần quản lý bộ nhớ phức tạp.

Bài học rút ra từ quá trình này là đôi khi chúng ta over-engineering (làm quá lên) các vấn đề. Bản gốc của Pizza Tycoon không cần tìm đường, không cần vật lý, và không cần phát hiện va chạm chính xác tuyệt đối. Nó chỉ cần những quy tắc đơn giản, hiệu quả và chạy tốt trên phần cứng hạn chế.