Adaptive Tile Refresh của Commander Keen

 (fabiensanglard.net)
2 điểm bởi GN⁺ 2023-07-29 | 1 bình luận | Chia sẻ qua WhatsApp
  • Adaptive Tile Refresh (ATR) là kỹ thuật cuộn màn hình được Commander Keen 1~3 dùng để tránh việc làm mới toàn màn hình chậm chạp của EGA, bằng cách chỉ vẽ lại các tile đã thay đổi thay vì toàn bộ màn hình
  • Chế độ EGA Dh lưu màn hình 320x200 16 màu trên 4 plane (C0~C3), và nếu ghi toàn bộ 32KiB màn hình qua bus ISA ở mỗi khung hình thì chỉ đạt khoảng 5fps, rất khó để cập nhật ở 60Hz
  • ATR dùng các thanh ghi CRTC_START, OFFSET, PEL để xử lý dịch chuyển dọc và ngang bên trong màn hình ảo; khi chạm mép thì thực hiện jolt để đưa mốc màn hình trở lại, rồi chỉ ghi đè các tile cần thiết vào VRAM
  • Chi phí của jolt phụ thuộc vào số tile cần vẽ lại; trong ví dụ của Commander Keen 1, chỉ 40 tile trên tổng 250 tile thay đổi, tức chỉ vẽ lại 16% toàn màn hình, và thiết kế bản đồ có nhiều tile lặp lại quyết định hiệu năng
  • Commander Keen 4~6 bỏ ATR để chuyển sang cách tiếp tục panning bằng wraparound của aperture VRAM 64KiB và chỉ vẽ các dải mép mới lộ ra; tuy nhiên trên một số card Super VGA đã xuất hiện vấn đề tương thích do đi vào vùng nhớ chưa được khởi tạo

Giới hạn băng thông trên EGA

  • Commander Keen chạy tốt nhất trên PC có EGA (Enhanced Graphic Adapter), và việc lập trình đồ họa được thực hiện thông qua các thanh ghi cấu hình cùng cửa sổ bộ nhớ 64KiB ánh xạ tới VRAM
  • EGA lưu dữ liệu nội bộ trên 4 plane C0, C1, C2, C3
    • C0 lưu bit thấp nhất (LSB) của mỗi giá trị pixel 4 bit
    • C3 lưu bit cao nhất (MSB)
    • Mỗi plane gồm 200 dòng, mỗi dòng 40 byte
  • Cấu trúc 4 bank này được thiết kế để bảo đảm đủ băng thông theo kịp màn hình CRT, và CRTC đọc song song 4 byte
  • Chế độ EGA Dh mà Commander Keen dùng cung cấp độ phân giải 320x200 và 16 màu
    • Không dùng cách tái cấu hình mực vẽ từ tập 64 giá trị màu như mode 10h
    • Ngay cả trong mode Dh, vẫn có thể đổi màu palette trong tập 16 màu cơ bản, và Commander Keen dùng điều này cho hiệu ứng fade in/out đơn giản

Adaptive Tile Refresh tránh vẽ lại toàn màn hình như thế nào

  • Nút thắt cổ chai chính mà ATR giải quyết là băng thông
  • Việc ghi giá trị 4 bit của 320x200 pixel, khoảng 32KiB, ở mỗi khung hình là gánh nặng quá lớn với bus ISA
  • Một vòng lặp đơn giản làm mới toàn bộ màn hình mỗi lần chỉ đạt khoảng 5 khung hình/giây
  • EGA cũng có cách ghi đồng thời vào cả 4 bank, nhưng dù hữu ích cho việc xóa màn hình hay nhân bản cột trong Wolfenstein 3D, nó không phù hợp với bài toán cuộn màn hình của Commander Keen

Cuộn mượt bằng thanh ghi

  • ATR trước hết tạo một màn hình ảo lớn hơn màn hình thật trong VRAM, rồi thay đổi giá trị CRTC_START để quyết định CRTC sẽ bắt đầu đọc từ đâu và nhờ đó di chuyển vùng hiển thị
  • Cuộn dọc tương đối đơn giản
    • Nếu thêm 16 dòng ở phía trên và dưới màn hình hiển thị, mỗi plane sẽ dùng 40 x 232 = 9,280 byte
    • Khi di chuyển màn hình lên 1 dòng, tăng CRTC_START thêm 40 byte
    • Khi di chuyển màn hình xuống 1 dòng, giảm CRTC_START đi 40 byte
  • Cuộn ngang dùng kết hợp thanh ghi OFFSET và PEL
    • Đặt OFFSET thành 2 sẽ thêm 16 byte đệm giữa các dòng, tạo ra khoảng trống 16 pixel ở bên trái và phải của màn hình ảo
    • Nếu tăng CRTC_START thêm 1 thì do cấu trúc plane, màn hình sẽ dịch theo bước 8 pixel, quá thô
    • Horizontal Pel Panning, tức thanh ghi PEL, có thể bỏ qua tối đa 7 bit sau CRTC_START, nhờ đó cho phép cuộn ngang theo từng pixel
  • Việc dịch trái/phải thực tế được thực hiện bằng cách điều chỉnh CRTC_START theo phần nguyên của tọa độ chia cho 8, và đặt PEL theo phần dư của tọa độ (% 8)

jolt và cập nhật từng phần theo đơn vị tile

  • Khi chạm tới mép của màn hình ảo, ATR thực hiện jolt để căn màn hình ảo trở lại giữa
  • Vẽ lại toàn bộ màn hình sẽ mất khoảng 200ms và làm tụt xuống 5fps, nên jolt hoạt động bằng cách chỉ ghi đè các tile đã thay đổi thay vì vẽ lại toàn bộ
  • Các màn chơi trong Commander Keen được tạo từ tile 16x16
    • Họa sĩ vẽ các tile, rồi hệ thống build gán cho mỗi tile một ID duy nhất
    • Nhà thiết kế màn chơi đặt các ID tile trong trình biên tập 2D để tạo bản đồ
    • Engine theo dõi tile ID nào đang có mặt trên màn hình ảo
  • Tại thời điểm jolt, hệ thống so sánh ID tile của trạng thái màn hình ảo hiện tại với trạng thái đích sau khi đã căn lại vào giữa
    • Tile giống nhau thì bỏ qua
    • Chỉ các tile khác nhau mới bị ghi đè vào VRAM
  • Hiệu quả của jolt tỉ lệ nghịch với số tile phải vẽ lại, nên nhà thiết kế game buộc phải xây dựng tilemap sao cho có nhiều tile lặp lại
  • Trong ví dụ của Commander Keen 1, khi đang di chuyển mượt sang phải rồi màn hình ảo chạm giới hạn và xảy ra jolt 16 pixel sang trái, chỉ 40 tile trên tổng 250 tile thay đổi
    • Tỷ lệ phải vẽ lại chỉ là 16% toàn màn hình
  • Phía trên nền sẽ được vẽ thêm lớp sprite
    • Engine duy trì danh sách tọa độ các dirty tile mà sprite đã ghi đè lên
    • Ở mỗi khung hình mới, nó duyệt danh sách dirty để khôi phục các tile nền rồi vẽ lại sprite

Double buffer và drifting trong bộ ba phần sau

  • Để tránh artifact hình ảnh, toàn bộ hệ thống được nhân đôi bằng hai framebuffer
    • Một buffer được CRTC đọc trong khi buffer còn lại có thể được ghi vào ở vị trí khác trong VRAM
    • Mỗi buffer dùng (320 + 32) * (200 + 32) * 4 / 8 = 40,832 byte
    • Toàn bộ double buffer chiếm 40,832 * 2 = 81,664 byte, vượt quá 64KiB của card EGA gốc do IBM sản xuất
  • Theo VileR, chỉ bo mạch IBM EGA nguyên bản mới trang bị 64KiB; còn phần lớn các bản sao EGA xuất hiện vào khoảng 1986~1987 đều có 256K, và đến thời điểm Commander Keen phát hành thì gần như không còn card EGA dưới 256K
  • Commander Keen 1~3 cho thấy rất rõ các mẫu lặp mà ATR đòi hỏi trên màn hình, trong khi Commander Keen 4~6 không còn đặc điểm đó rõ rệt nữa
  • Bộ ba Keen thứ hai tận dụng hành vi wraparound khi CRTC_START chạm cuối khối 64KiB để quay lại đầu khối
    • Màn hình tiếp tục panning và chỉ vẽ các hàng tile mép mới xuất hiện
    • Khi jolt biến mất, nhu cầu tạo các vùng lặp có màu sắc tương tự cũng giảm đi
  • Cách này không hẳn là thêm tính năng mới, mà gần hơn với một cải tiến loại bỏ jolt
    • Hai phần tử của double buffer cùng drift trong không gian VRAM với cùng tốc độ nên không chồng lấn lên nhau
    • Trong đa số trường hợp, nó hoạt động tốt
  • Tuy nhiên, trên một số card Super VGA đã phát sinh vấn đề
    • Ở các card có cách triển khai khác chuẩn và bộ nhớ lớn hơn, thay vì wraparound từ cuối về đầu, con trỏ có thể đi vào vùng nhớ có thật nhưng chưa được khởi tạo
    • Thay vì xử lý riêng cho từng loại card phi chuẩn, Carmack chọn giải pháp đơn giản hơn: khi chạm cuối màn hình thì chấp nhận hitch và sao chép toàn bộ màn hình lên phía trên
  • Kỹ thuật drifting này có thể đã ngăn việc lưu cả tile lẫn sprite trong VRAM để tận dụng sao chép VRAM-to-VRAM tốc độ cao, nhưng cũng có thể điều đó không phải vấn đề lớn vì lượng nội dung phải vẽ ở mỗi khung hình là rất ít

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-07-29
Ý kiến trên Hacker News

  • Độ mượt khi cuộn của Commander Keen 4~6 là thứ không game nào trên PC bắt kịp trong nhiều năm, ngay cả sau khi các game chuyển sang đồ họa 256 màu
    Nhờ công việc kỹ thuật đáng kinh ngạc của John Carmack và nghệ thuật palette 16 màu của Adrian Carmack, có thể nói id đã làm ra những game platform đẹp nhất trên PC trong một thời gian ở thập niên 1990
    Adrian Carmack không có họ hàng với Carmack nổi tiếng hơn, nhưng tôi xem ông là một bậc thầy ẩn mình của palette 16 màu

    • Thật khá lạ khi nghĩ rằng tất cả các game Commander Keen cổ điển đều được phát triển và phát hành trong khoảng từ tháng 12/1990 đến tháng 12/1991
      Tốc độ tiến bộ về đồ họa và gameplay thật sự khủng khiếp
      Sự thay đổi từ game đầu tiên: https://en.wikipedia.org/wiki/Commander_Keen_in_Invasion_of_...
      Sự thay đổi đến game cuối cùng: https://en.wikipedia.org/wiki/Commander_Keen_in_Goodbye,_Gal...
      Hồi đó tôi đã trực tiếp chơi khi còn nhỏ, vậy mà đã quên mất mọi chuyện diễn ra nhanh đến vậy
    • Nếu nói về game platform trên PC đẹp nhất trong một thời gian ở thập niên 1990, tôi sẽ chọn Prince Of Persia
      Không có ý hạ thấp Commander Keen, nhưng tôi cảm thấy hình ảnh và cơ chế game của PoP là độc nhất vô nhị theo tiêu chuẩn thời đó
      Lần đầu chơi khoảng năm 7 tuổi, nó để lại ấn tượng như phép màu; đến giờ đây vẫn là game platform tôi thích nhất nên có lẽ tôi hơi thiên vị
      Tất nhiên PoP hoàn toàn không có cuộn màn hình, còn phần đó thì là ma thuật hắc ám của Commander Keen
    • Có thể đó là góc nhìn khi nhìn lại bây giờ, nhưng nhiều phát triển mang tính đột phá như thế này trông khá đơn giản so với phát triển ngày nay
      “Bộ nhớ chậm, vậy chỉ vẽ lại những gì đã thay đổi” giờ gần như là một ý tưởng hiển nhiên
      Dù vậy, phần tối ưu hóa trong các bản 4~6 vẫn thú vị. Ở các bản 1~3, họ làm toàn bộ công việc vì giả định bộ đệm không wrap, nhưng trên thực tế nó có wrap nên công việc đó trở nên vô ích; điểm này cũng đáng chú ý
    • Jazz Jackrabbit thì sao? Game đó cũng có cuộn VGA rất mượt

  • Tôi từng làm một game dựa trên tile bằng DirectX 5 trên Windows 98, và ban đầu đã triển khai một cách tương tự như mô tả trong bài này
    Màn hình không cuộn, nhưng vì có thể phải vẽ lại nhiều tile nên tình huống đơn giản hơn một chút
    Cuối cùng tôi gỡ bỏ toàn bộ đoạn code đó, vì khi profiling chi phí vẽ toàn màn hình trên card RIVA TnT thì thời gian quá nhỏ đến mức còn không đo được
    Thật may là tôi đã bỏ lỡ thời EGA trong phát triển PC. Nếu ở thời đó, chắc tôi đã chẳng hoàn thành được gì

    • Tôi thì ngược lại, tôi thích kiểu lập trình cấp thấp đó
      Tối ưu bằng bit shift thay cho phép nhân, viết code lõi bằng assembly, rồi khi vi xử lý phát triển thì ghi 16 bit hoặc 32 bit mỗi lần
      Vì có ít tài liệu, tôi cứ học từ sách ở thư viện địa phương và các đĩa mềm chứa file txt
      Tôi quá trẻ và thiếu kinh nghiệm nên chẳng hoàn thành được gì, nhưng đã làm được cuộn dọc mượt, gần như làm cho cuộn ngang chạy được, và cũng triển khai double buffering cho một khối lập phương 3D xoay. Nó còn bao gồm cả depth buffering, toán học và vẽ polygon theo từng dòng
      Rồi DirectX xuất hiện, điểm tiếp xúc với máy móc biến mất, và khối lập phương 3D xoay trở nên quá dễ nên không còn vui nữa
    • Ngay cả khi đó, khoảng cách giữa card đồ họa chậm nhất và nhanh nhất đã bắt đầu nới rộng đáng kể
      Bus mở rộng từ 8 bit lên 16/32 bit, card đồ họa hỗ trợ posted writes để CPU phải chờ ít hơn, CPU cũng nhanh hơn, nên các hệ thống nhanh có thể ghi màn hình 640x480x256 với hơn 300 khung hình mỗi giây
      Trong trường hợp này có thể là bộ đệm bộ nhớ hệ thống được cache cùng bản sao DMA, hoặc blitter đã xử lý việc vẽ. Nhưng ngay cả thời Windows 98, trong số các card 3D giá rẻ cũng có loại truy cập CPU rất chậm, chỉ nhỉnh hơn chút so với card bus ISA cũ
      Khi độ phân giải màn hình trở nên quá cao, hiện nay phần nào đó lại đảo chiều một chút. Dù có thể vẽ lại toàn màn hình 4K ở 60 khung hình mỗi giây, cũng khó gọi đó là hiệu quả
      Game thường vẫn vẽ lại toàn bộ, nhưng desktop compositor thì tối ưu khá nhiều, chẳng hạn như động gán layer vào các hardware plane để giảm vùng phải vẽ lại

  • Cùng thời kỳ đó tôi làm ở một công ty game khác, và đã tự nghĩ ra kỹ thuật cuộn giống cách tiếp cận thứ hai
    Tôi không nghĩ đó là chuyện quá đáng kinh ngạc. Nếu khi đó đang giải cùng một bài toán, có lẽ bạn cũng sẽ đi đến kết luận tương tự
    Tôi cũng tự làm driver âm thanh PWM để phát âm thanh mẫu qua loa PC, và có vẻ những người khác cũng đều làm vậy
    PC đã không nhận được đủ tình yêu trước khi tất cả chúng ta chuyển sang console. Nhìn những demo như 8088 MPH của Hornet đến giờ tôi vẫn thấy phấn khích

    • Nếu đó là game đã phát hành, bạn có thể cho biết tựa game để mọi người so sánh không? Tôi đồng ý rằng phần lớn mọi người hẳn đã nghĩ ra các giải pháp tương tự, nhưng tôi tò mò liệu trải nghiệm khi chơi có cùng cảm giác không
    • Nếu chuyện đó không quá ghê gớm, tại sao ngay cả trong số các game platform cuộn màn hình hàng đầu thời đó vẫn có nhiều game giật như vậy?
      Nó không phải điều kiện bắt buộc để có một game vui, nhưng độ mượt mà Keen thể hiện, đặc biệt trên phần cứng cấu hình thấp như dưới 10MHz, thời đó thật sự khiến người ta mở to mắt
    • Danh tiếng thường đến từ khả năng thương mại hóa và marketing chứ không phải bản thân phát minh
      Hẳn đã có vô số phát minh tuyệt vời không được biết đến trong hàng nghìn năm
      Tôi cũng từng “phát minh” ra thứ tương tự 10 năm trước khi LinkedIn xuất hiện, nhưng không thể thương mại hóa thành công. Tôi cho rằng phần lớn phát minh đã không được biết đến rộng rãi
      Vì vậy nhiều startup bắt đầu với hai người: một chuyên gia và một doanh nhân
      Nên nói vậy không sai. Phát minh này có thể không có gì đặc biệt, nhưng nó trở nên đặc biệt nhờ sự kết hợp giữa tính mới, tính hữu dụng và thương mại hóa thành công

  • Trong cuốn sách xuất sắc Masters of Doom, Keen được mô tả là một trò kiểu Mario, tức game cuộn ngang
    id đã đề xuất công nghệ này với Nintendo như một lựa chọn để port Mario lên PC, nhưng Nintendo từ chối, và thế là Keen ra đời
    Đây là một bước nhảy vọt khổng lồ đối với game PC, mở ra một kỷ nguyên game PC mới
    Tuy nhiên điều tôi vẫn chưa hiểu rõ là: công nghệ giữa NES và PC khác nhau ở điểm nào mà Nintendo có thể triển khai cuộn ngang sớm hơn PC vài năm?

    • EGA về bản chất cung cấp một framebuffer lớn
      Trong chế độ đồ họa EGA, bạn có thể vẽ bất cứ thứ gì tùy ý như đường thẳng, hình tròn, từng pixel riêng lẻ, và nó được tạo ra để dùng theo cách đó
      Nhưng cuộn màn hình thì không miễn phí. Bạn phải tự sao chép bộ nhớ, và như bài viết được liên kết cho thấy, nếu cứ làm kiểu brute force thì do giới hạn băng thông bus ISA, chỉ đạt khoảng 5 khung hình/giây
      NES và các máy chơi game 8/16-bit khác không được tạo ra để vẽ mọi thứ tùy ý. Chúng được tạo ra để render tile
      Bạn chỉ cần định nghĩa lưới tile nền và cung cấp offset cuộn. Sprite cũng hoạt động tương tự nhưng có thể di chuyển độc lập. Tất cả những thứ này được cung cấp miễn phí ở 60 khung hình/giây
      Nhược điểm là không dễ render thứ tùy ý. Ví dụ, nếu muốn tô một pixel riêng lẻ ở đâu đó thì phải dùng cách vòng vo khá nặng
      Đây không hẳn là vấn đề Nintendo đã “tìm ra” trước IBM; đúng hơn là IBM đã tạo một hệ thống đồ họa đa dụng phù hợp với máy tính đa dụng và đồ họa tĩnh, cung cấp khả năng kiểm soát chi tiết đến từng pixel. Nhìn vào card EGA thì đó là một thiết bị khá đồ sộ với nhiều silicon
      Ngược lại, Nintendo đã tạo ra một hệ thống đồ họa chuyên dụng đơn giản hơn nhiều, được tối ưu cho việc đẩy các tile di chuyển
    • Thực ra họ đã tạo một bản port SMB3 và cho Nintendo xem
      Khi Nintendo không chấp nhận, họ tạo asset mới và sau này nó trở thành Keen
      Video bản port ở đây: https://youtu.be/1YWD6Y9FUuw
    • Tôi không chắc, nhưng theo tôi biết NES có chip đồ họa chuyên dụng để thao tác sprite, còn trên PC thì tất cả những việc này phải làm bằng phần mềm
    • Phương pháp trong bài là dùng framebuffer pixel độc lập để mô phỏng bằng phần mềm các tile do phần cứng quản lý
      Với NES, https://www.nesdev.org/wiki/PPU có vẻ là điểm khởi đầu tốt
      Thách thức cốt lõi không phải là bản thân việc “tìm ra cách cuộn ngang”, mà là điều chỉnh để engine game cuộn ngang chạy đẹp trong không gian bộ nhớ và giới hạn băng thông của một hệ thống hoàn toàn khác
    • NES và GB có vẻ là dựa trên tile
      Vì game được xây dựng dựa trên sprite có layer, nên cách “tăng tốc” 2D đó khá hợp lý

  • Trong cuộc phỏng vấn John Carmack của Lex Fridman, họ điểm qua toàn bộ các đổi mới chính của từng game
    Đây là một tập thực sự thú vị, nếu có thời gian thì rất đáng xem. Dài khoảng 5 tiếng

  • Tôi vẫn nhớ thời mình tin rằng đã biết gần như mọi yếu tố bí mật trong Commander Keen Goodbye Galaxy
    Bạn bè ở trường thường hỏi tôi chỉ các bí mật trong những màn họ chơi trên máy tính của trường sau giờ học

    • Ghen tị thật. Ở trường tôi, trong số những người tôi từng nói chuyện, tôi là mọt công nghệ duy nhất từng nghe đến Commander Keen

  • Cứ thấy fabiensanglard.net là tôi lập tức muốn upvote

    • Anh ấy đúng là một kho báu. Cuốn sách CPS1 cũng rất xuất sắc
      Nếu ai biết blog game cổ điển nào khác có chiều sâu kỹ thuật thì mong chia sẻ
      https://nicole.express/ và https://sudden-desu.net/ cũng là những trang tôi thích

  • Tôi hiểu cách cuộn dọc hoạt động khi điều chỉnh điểm bắt đầu framebuffer theo từng scanline, nhưng ban đầu chưa rõ cuộn ngang có thể thực hiện thế nào mà không làm framebuffer bị xoắn vặn nghiêm trọng
    Nghĩ thêm một chút, tôi nhận ra nó giống như vẽ hình lên mặt bên của một hình trụ. Dù vẽ mép trái của ảnh ở đâu, luôn có cách xoay hình trụ rồi thiết lập các thanh ghi CRTC_START và PEL để nhìn thấy toàn bộ ảnh một cách rõ nét
    Phần “khi chạm tới mép màn hình, giải pháp đơn giản là chấp nhận khựng một chút và sao chép toàn bộ màn hình lên trên” cũng rất thú vị
    Tôi nhớ khi khởi động Keen thường có thông báo kiểu “VGA compatibility mode enabled”, và tôi luôn thắc mắc nó có nghĩa là gì

  • Commander Keen thực sự là một trò chơi nhỏ rất đáng yêu
    Chắc phải tìm cách chạy lại mới được
    Nhưng nên chạy nó thế nào nhỉ? Từ khi thành “người lớn” đến giờ mình không dùng Windows khoảng 20 năm rồi, vậy chơi trên Debian bằng cách nào?

    • Có thể chơi ngay: https://archive.org/details/msdos_Commander_Keen_1_-_Maroone...
    • Không đồng ý. Đây là game dành cho những đứa trẻ vì lý do nào đó có thể dùng máy tính nhưng lại không có Nintendo
      Thời đó máy tính đắt hơn console khoảng 10 lần, nên thường là do người lớn có quan điểm rất mạnh về việc trẻ con nên làm gì
      So với các game NES và Genesis thì nó thiếu linh hồn. Hồi đó mình thích, nhưng gần đây chơi lại trên DosBox thì thấy rõ là không thể so sánh được
    • DosBox chạy các game VGA cũ rất tốt, và hoạt động trên gần như mọi nền tảng, kể cả trong trình duyệt: https://archive.org/details/msdos_Commander_Keen_1_-_Maroone...
    • Chắc là DosBox
    • Commander Keen và Jill of the Jungle từng là những game đầu tiên đưa mình đến với PC. Kỷ niệm thật đẹp

  • Vài năm trước mình đã triển khai phương pháp thứ hai, nhưng chỉ vẽ mép phía trước thôi cũng đã rất chậm
    Tuy vậy, mình viết bằng C và chưa từng học lập trình assembly một cách bài bản
    https://github.com/geon/kate/blob/master/src/platform/dos/eg...