Commander Keen का Adaptive Tile Refresh

 (fabiensanglard.net)
2 पॉइंट द्वारा GN⁺ 2023-07-29 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Adaptive Tile Refresh(ATR) Commander Keen 1~3 में इस्तेमाल की गई एक scrolling तकनीक थी, जिसे EGA की धीमी full-screen refresh से बचने के लिए बनाया गया था, ताकि पूरी screen के बजाय सिर्फ बदली हुई tiles को फिर से draw किया जाए
  • EGA mode Dh 320x200 16-color screen को 4 planes (C0~C3) में बांटकर store करता है, और अगर हर frame में पूरी 32KiB screen को ISA bus पर लिखा जाए, तो यह लगभग 5fps तक सीमित रह जाता है, जिससे 60Hz refresh मुश्किल हो जाती है
  • ATR CRTC_START, OFFSET, PEL registers से virtual screen के अंदर vertical और horizontal movement संभालता है, और edge तक पहुंचने पर jolt के जरिए screen reference को वापस करता है, फिर सिर्फ जरूरी tiles को VRAM में overwrite करता है
  • jolt की cost फिर से draw की जाने वाली tiles की संख्या पर निर्भर करती है; Commander Keen 1 के उदाहरण में 250 में से सिर्फ 40 tiles बदलीं, यानी पूरी screen का केवल 16% फिर से draw हुआ, और ज्यादा repeating tiles वाली map design performance को तय करती थी
  • Commander Keen 4~6 में ATR की जगह 64KiB VRAM aperture के wraparound का इस्तेमाल करके लगातार panning करते हुए नई दिखाई देने वाली edge strips ही draw करने का तरीका अपनाया गया, जिससे कुछ Super VGA cards पर uninitialized memory में जाने की compatibility समस्या पैदा हुई

EGA में सामने आई bandwidth limit

  • Commander Keen EGA(Enhanced Graphic Adapter) लगे PCs पर सबसे अच्छा चलता था, और graphics programming configuration registers और VRAM में mapped 64KiB memory window के जरिए की जाती थी
  • EGA internal data को 4 planes C0, C1, C2, C3 में store करता है
    • C0 हर 4-bit pixel value का least significant bit(LSB) store करता है
    • C3 most significant bit(MSB) store करता है
    • हर plane 200 lines का होता है, प्रति line 40 bytes
  • 4-bank structure CRT screen के साथ चलने के लिए bandwidth सुनिश्चित करने वाली design थी, और CRTC 4 bytes को parallel में read करता है
  • Commander Keen द्वारा इस्तेमाल किया गया EGA mode Dh 320x200 resolution और 16 colors देता है
    • mode 10h की तरह 64 color values में से ink को reconfigure करने का तरीका इस्तेमाल नहीं करता
    • mode Dh में भी default 16 colors के भीतर palette colors बदले जा सकते हैं, जिसका इस्तेमाल Commander Keen के simple fade in/out effect में होता है

Adaptive Tile Refresh ने full-screen redraw से कैसे बचाया

  • ATR ने जिस core bottleneck को हल किया, वह bandwidth था
  • 320x200 pixels की 4-bit values, यानी लगभग 32KiB, हर frame में लिखना ISA bus पर बहुत बड़ा बोझ डालता है
  • पूरी screen को हर बार refresh करने वाला simple loop लगभग 5 frames per second पर ही रह जाता है
  • EGA में 4 banks में एक साथ लिखने का तरीका भी है, लेकिन यह screen clear करने या Wolfenstein 3D में columns replicate करने में मददगार होने के बावजूद Commander Keen की scrolling समस्या के लिए उपयुक्त नहीं था

Registers से बनी smooth scrolling

  • ATR पहले VRAM के अंदर screen से बड़ी virtual screen बनाता है, और display area को move करने के लिए CRTC कहां से read करेगा यह तय करने वाले CRTC_START value को बदलता है
  • Vertical scrolling अपेक्षाकृत सरल है
    • Display screen के ऊपर और नीचे 16 lines जोड़ने पर प्रति plane 40 x 232 = 9,280 bytes इस्तेमाल होते हैं
    • Screen को एक line ऊपर move करते समय CRTC_START को 40 bytes बढ़ाया जाता है
    • एक line नीचे move करते समय CRTC_START को 40 bytes घटाया जाता है
  • Horizontal scrolling में OFFSET register और PEL register को साथ में इस्तेमाल किया जाता है
    • OFFSET को 2 पर set करने से lines के बीच 16 bytes padding जुड़ती है, जिससे virtual screen के left और right में 16 pixels की margin मिलती है
    • CRTC_START को 1 बढ़ाने पर plane structure की वजह से screen 8-pixel units में move होती है, जो बहुत coarse है
    • Horizontal Pel Panning, यानी PEL register, CRTC_START के बाद अधिकतम 7 bits skip करने देता है, जिससे pixel-level horizontal scrolling संभव होती है
  • असल left-right movement में coordinate को 8 से divide किए गए value से CRTC_START adjust किया जाता है, और coordinate के remainder (% 8) से PEL set किया जाता है

jolt और tile-level partial refresh

  • Virtual screen के edge पर पहुंचने पर ATR jolt perform करके virtual screen को फिर से center में align करता है
  • पूरी screen को फिर से draw करने में लगभग 200ms लगते और frame rate 5fps तक गिर जाता, इसलिए jolt full redraw के बजाय सिर्फ बदली हुई tiles को overwrite करके काम करता है
  • Commander Keen levels 16x16 tiles से बने होते हैं
    • Artist tiles draw करता है, तो build system हर tile को unique ID देता है
    • Level designer 2D editor में tile IDs place करके map बनाता है
    • Engine track करता है कि virtual screen में कौन-सी tile IDs मौजूद हैं
  • jolt के समय current virtual screen state और फिर से center में align किए गए target state के tile IDs compare किए जाते हैं
    • Same tiles को skip किया जाता है
    • केवल अलग tiles को VRAM में overwrite किया जाता है
  • jolt की efficiency फिर से draw की जाने वाली tiles की संख्या के उलट अनुपात में होती है, इसलिए game designer को tilemap इस तरह बनाना पड़ता था कि repeating tiles ज्यादा आएं
  • Commander Keen 1 के उदाहरण में, दाईं ओर smooth movement के दौरान virtual screen खत्म होने पर 16-pixel left jolt हुआ, तब 250 में से सिर्फ 40 tiles बदलीं
    • Redraw ratio पूरी screen का 16% था
  • Background के ऊपर sprite layer draw होती है
    • Engine उन dirty tile coordinates की list रखता है जिन्हें sprites ने overwrite किया था
    • हर नए frame में dirty list से गुजरकर background tiles restore किए जाते हैं और फिर sprites दोबारा draw किए जाते हैं

Double buffer और दूसरी trilogy की drifting

  • Visual artifacts से बचने के लिए पूरा system दो framebuffers में duplicate किया गया था
    • एक को CRTC read कर रहा होता है, जबकि दूसरे में VRAM के किसी और location पर लिखा जा सकता है
    • हर buffer (320 + 32) * (200 + 32) * 4 / 8 = 40,832 bytes इस्तेमाल करता है
    • पूरा double buffer 40,832 * 2 = 81,664 bytes का होता है, जो IBM के original EGA card के 64KiB से ज्यादा है
  • VileR के अनुसार 64KiB वाला board केवल original IBM EGA board था, और 1986~1987 के आसपास आए अधिकांश EGA clones में 256K लगा था; Commander Keen release के समय 256K से कम EGA cards लगभग नहीं थे
  • Commander Keen 1~3 में ATR द्वारा जरूरी repeating patterns screen पर साफ दिखते हैं, लेकिन Commander Keen 4~6 में वही characteristic उतनी स्पष्ट नहीं है
  • दूसरी Keen trilogy CRTC_START के 64KiB block के end तक पहुंचने पर फिर से block की शुरुआत में लौटने वाले wraparound behavior का इस्तेमाल करती है
    • Screen को लगातार pan किया जाता है और सिर्फ नई दिखाई देने वाली edge tile row/strip draw की जाती है
    • jolt हटने से मिलते-जुलते colors के repeating fields बनाने की जरूरत कम हो जाती है
  • यह तरीका कोई नया feature जोड़ने के बजाय jolt हटाने वाला improvement ज्यादा था
    • Double buffer के दोनों elements VRAM space में same speed से drift करते हैं, इसलिए वे एक-दूसरे पर overlap नहीं करते
    • ज्यादातर cases में यह ठीक काम करता है
  • कुछ Super VGA cards पर समस्या आती है
    • Standard से अलग implementation और ज्यादा memory वाले cards में end से beginning पर wraparound न होकर वह वास्तविक uninitialized memory में जा सकता था
    • Carmack ने कई non-standard cards के लिए अलग-अलग handling करने के बजाय, screen end पर पहुंचने पर hitch स्वीकार करते हुए पूरी screen को ऊपर copy करने वाला आसान solution चुना
  • इस drifting technique ने tiles और sprites को VRAM में store करके fast VRAM-to-VRAM copy इस्तेमाल करने का तरीका शायद रोका होगा, लेकिन हर frame में draw होने वाली amount बहुत कम होने से यह शायद बड़ी समस्या नहीं रही

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2023-07-29
Hacker News की रायें

  • Commander Keen 4~6 की scrolling smoothness को PC पर कई सालों तक कोई गेम टक्कर नहीं दे पाया, और games के 256-color graphics पर चले जाने के बाद भी ऐसा ही रहा
    John Carmack के शानदार technical काम और Adrian Carmack की 16-color palette art की बदौलत, id ने 1990s में कुछ समय तक PC पर सबसे अच्छे दिखने वाले platform games बनाए थे
    Adrian Carmack, ज़्यादा प्रसिद्ध Carmack के रिश्तेदार नहीं हैं, लेकिन मुझे लगता है वे 16-color palette के छिपे हुए उस्ताद थे

    • यह काफी अजीब लगता है कि classic Commander Keen games सभी December 1990 से December 1991 के बीच develop और release हुए थे
      graphics और gameplay में progress की रफ्तार वाकई जबरदस्त थी
      पहले game से बदलाव: https://en.wikipedia.org/wiki/Commander_Keen_in_Invasion_of_...
      आखिरी game तक बदलाव: https://en.wikipedia.org/wiki/Commander_Keen_in_Goodbye,_Gal...
      उस समय बच्चे के रूप में खुद खेला था, और भूल गया था कि चीजें इतनी तेजी से हो रही थीं
    • 1990s में कुछ समय के लिए सबसे अच्छा दिखने वाला PC platform game चुनना हो तो मैं Prince Of Persia चुनूंगा
      Commander Keen को कमतर बताने का इरादा नहीं है, लेकिन PoP के visuals और game mechanics उस समय के हिसाब से बिल्कुल अलग स्तर के लगते थे
      करीब 7 साल की उम्र में जब पहली बार खेला तो जादू जैसा लगा था, और आज भी यह मेरा पसंदीदा platform game है, इसलिए bias तो है
      बेशक PoP में scrolling बिल्कुल नहीं है, और वही हिस्सा Commander Keen का काला जादू है
    • हो सकता है यह आज पीछे मुड़कर देखने का नजरिया हो, लेकिन ऐसी innovative development में से बहुत कुछ आज की development से तुलना करें तो काफी simple लगता है
      “memory slow है, इसलिए सिर्फ बदली हुई चीजें ही फिर से draw करें” — यह अब लगभग obvious idea है
      फिर भी parts 4~6 की optimization interesting है। parts 1~3 में buffer wrap नहीं होगा, यह मानकर पूरा काम किया गया था, लेकिन असल में wrap होने से वह काम बेकार हो गया — यह भी दिलचस्प है
    • Jazz Jackrabbit का क्या? उस game की VGA scrolling भी वाकई smooth थी

  • Windows 98 पर DirectX 5 के साथ एक tile-based game बनाया था, और शुरुआत में इस लेख में बताए गए तरीके जैसा ही कुछ implement किया था
    screen scroll नहीं होती थी, लेकिन कई tiles को फिर से draw करना पड़ सकता था, इसलिए स्थिति थोड़ी सरल थी
    आखिर में वह code पूरा हटा दिया, क्योंकि RIVA TnT card पर full screen draw करने की cost profile की तो समय इतना कम लगा कि उसे measure भी नहीं कर पाए
    PC development में EGA era miss कर दिया, इसके लिए खुश हूं। उस दौर में होता तो शायद कुछ भी पूरा नहीं कर पाता

    • मुझे इसके उलट ऐसी low-level programming पसंद थी
      multiplication की जगह bit shifts से optimize करना, core code assembly में लिखना, और processor के बेहतर होने के साथ एक बार में 16-bit या 32-bit लिखना
      resources कम थे, इसलिए local library की किताबों और txt files वाली floppy disks से लगातार सीखता रहा
      बहुत छोटा और कम अनुभवी था, इसलिए कुछ पूरा नहीं किया, लेकिन smooth vertical scrolling बना ली थी और horizontal scrolling भी लगभग चलने लगी थी; rotating 3D cube की double buffering भी implement कर ली थी। इसमें depth buffering, math और line-by-line polygon drawing तक शामिल था
      फिर DirectX आया और machine से सीधा संपर्क गायब हो गया; rotating 3D cube इतना आसान हो गया कि मजा नहीं रहा
    • उस समय भी सबसे slow graphics card और सबसे fast graphics card के बीच gap काफी बढ़ चुका था
      bus 8-bit से 16/32-bit तक चौड़ी हो रही थी, graphics cards posted writes support करने लगे थे जिससे CPU को कम wait करना पड़ता था, और CPU भी तेज हो रहे थे, इसलिए तेज systems 640x480x256 screen को 300 frames प्रति second से ज्यादा लिख सकते थे
      इस case में शायद cached system memory buffer और DMA copy थी, या blitter drawing संभाल रहा था। लेकिन Windows 98 के दौर में भी कुछ low-end 3D cards में CPU access बहुत slow था, जो पुराने ISA bus cards से बस थोड़ा ही बेहतर था
      screen resolution बहुत ज्यादा बढ़ जाने से अब कुछ हद तक फिर उलट स्थिति भी है। 4K full screen को 60 frames per second पर redraw कर पाना भी हो, तो उसे efficient कहना मुश्किल है
      games आमतौर पर अब भी सब कुछ फिर से draw करते हैं, लेकिन desktop compositors redraw area घटाने के लिए layers को dynamically hardware planes में assign करने जैसी काफी optimizations करते हैं

  • उसी समय दूसरी game company में काम करता था, और दूसरे approach जैसी scrolling technique खुद निकाली थी
    मुझे यह इतना हैरान करने वाला नहीं लगता। अगर उस समय वही problem solve कर रहे होते, तो शायद similar conclusion पर पहुंचते
    PC speaker पर sampled sounds play करने के लिए अपना PWM audio driver भी बनाया था, और लगता है बाकी लोग भी यही कर रहे थे
    हम सबके console पर चले जाने से पहले PC को पर्याप्त प्यार नहीं मिला। Hornet के 8088 MPH जैसे demos आज भी रोमांचित कर देते हैं

    • अगर release हुआ game था, तो तुलना के लिए title बता सकते हैं? मैं मानता हूं कि ज्यादातर लोगों ने similar solutions सोचे होंगे, लेकिन जानना चाहता हूं कि खेलने का result वैसा ही महसूस होता था या नहीं
    • अगर वह इतना बड़ा काम नहीं था, तो उस समय के top scrolling platform games में भी इतने सारे games इतने jerky क्यों थे?
      यह मजेदार game की जरूरी शर्त नहीं है, लेकिन खासकर 10MHz से कम जैसे low-end hardware पर Keen की smoothness उस समय आंखें खोल देने वाली थी
    • reputation अक्सर invention खुद से नहीं, बल्कि commercialization और marketing ability से आती है
      हजारों सालों में अनगिनत शानदार inventions रही होंगी जिनके बारे में किसी को पता नहीं चला
      मैंने भी LinkedIn आने से 10 साल पहले वैसी ही कोई चीज “invent” की थी, लेकिन उसे successfully commercialize नहीं कर पाया। मुझे लगता है ज्यादातर inventions widely known नहीं हो पातीं
      इसलिए कई startups दो लोगों से शुरू होते हैं: एक expert और एक businessperson
      इसलिए यह गलत बात नहीं है। यह invention अपने आप में शायद कुछ खास न हो, लेकिन newness, usefulness और successful commercialization के combination ने इसे खास बना दिया

  • बेहतरीन किताब Masters of Doom में बताया गया है कि Keen, Mario-टाइप यानी horizontal scrolling गेम था
    id ने Mario को PC पर पोर्ट करने के विकल्प के तौर पर यह तकनीक Nintendo को प्रस्तावित की थी, लेकिन Nintendo ने मना कर दिया और इसी तरह Keen पैदा हुआ
    PC गेम्स के लिए यह एक बहुत बड़ी छलांग थी, और इसने PC गेम्स के नए युग की शुरुआत की
    हालांकि जो बात अब भी ठीक से समझ नहीं आती, वह यह है कि NES और PC तकनीक में ऐसा क्या अलग था कि Nintendo, PC से कई साल पहले horizontal scrolling लागू कर सका

    • EGA मूल रूप से एक बड़ा framebuffer देता है
      EGA graphics mode में आप लाइन, सर्कल, अलग-अलग pixels जैसी कोई भी मनचाही चीज़ draw कर सकते हैं, और इसे इसी तरह इस्तेमाल करने के लिए बनाया गया था
      लेकिन scrolling मुफ्त में नहीं मिलती। memory को सीधे copy करना पड़ता है, और linked लेख दिखाता है कि अगर brute force से करें तो ISA bus bandwidth limit की वजह से सिर्फ करीब 5 frames per second ही मिलते हैं
      NES और दूसरे 8/16-bit game consoles मनचाही चीज़ draw करने के लिए नहीं बनाए गए थे। वे tiles render करने के लिए बनाए गए थे
      आपको background tile grid define करना और scroll offset देना होता था। sprites भी लगभग वैसे ही काम करते थे, लेकिन स्वतंत्र रूप से move कर सकते थे। यह सब 60 frames per second पर मुफ्त में मिल जाता था
      कमी यह थी कि मनचाही चीज़ आसानी से render नहीं की जा सकती थी। उदाहरण के लिए कहीं एक single pixel रंगना हो तो काफी गंभीर workaround चाहिए होता था
      बात यह नहीं थी कि Nintendo ने IBM से पहले कोई समस्या “समझ” ली थी; बल्कि IBM ने general-purpose computers और static graphics के लिए एक general-purpose graphics system बनाया था, जो हर pixel पर fine-grained control देता था। EGA card देखें तो वह बहुत silicon वाला, काफी बड़ा device है
      दूसरी तरफ Nintendo ने tiles को धकेलकर move कराने के लिए बनाया गया कहीं ज्यादा सरल dedicated graphics system बनाया था
    • असल में उन्होंने SMB3 का port बनाया और Nintendo को दिखाया था
      Nintendo ने स्वीकार नहीं किया तो उन्होंने नए assets बनाए, जो बाद में Keen बना
      port का video यहां है: https://youtu.be/1YWD6Y9FUuw
    • पक्का नहीं, लेकिन मेरी समझ में NES में sprite manipulation के लिए dedicated graphics chip था और PC पर यह सब software में करना पड़ता था
    • लेख का तरीका independent pixel framebuffer का इस्तेमाल करके software में hardware-managed tiles की नकल करने का है
      NES के लिए https://www.nesdev.org/wiki/PPU एक अच्छा starting point लगता है
      मुख्य चुनौती “horizontal scrolling कैसे करें, यह पता लगाना” अपने आप में नहीं है, बल्कि पूरी तरह अलग system के memory space और bandwidth constraints के भीतर horizontal scrolling game engine को अच्छा दिखने लायक चलाना है
    • लगता है NES और GB tile-based थे
      layers वाले sprite-based तरीके से games बनाए जाते थे, इसलिए 2D को “accelerate” करने का तरीका काफी समझ में आता था

  • Lex Fridman के John Carmack interview में हर game के मुख्य innovations को पूरा cover किया गया है
    वाकई दिलचस्प episode है, समय हो तो strongly recommend करता हूं। यह करीब 5 घंटे का है

  • मुझे अब भी वह दौर याद है जब मुझे लगता था कि Commander Keen Goodbye Galaxy के लगभग सारे secret elements मुझे पता हैं
    स्कूल के दोस्त मुझसे पूछते थे कि school के बाद school computer पर वे जो levels खेलते थे, उनके secrets बता दूं

    • जलन होती है। मेरे school में, जिन लोगों से मैंने बात की, उनमें Commander Keen के बारे में सुनने वाला मैं ही अकेला geek था

  • fabiensanglard.net दिखते ही मैं तुरंत upvote कर देता हूं

    • वह सचमुच खजाने जैसे इंसान हैं। CPS1 book भी बेहतरीन है
      अगर किसी को तकनीकी रूप से गहराई वाले दूसरे classic game blogs पता हों तो share करें
      https://nicole.express/ और https://sudden-desu.net/ भी मेरी पसंदीदा sites हैं

  • framebuffer start point को scanline unit में adjust करने पर vertical scrolling कैसे होती है, यह तो समझ गया था, लेकिन horizontal scrolling बिना framebuffer को बुरी तरह तोड़े-मरोड़े कैसे संभव है, यह शुरू में साफ नहीं था
    थोड़ा और सोचने पर समझ आया कि यह cylinder की side पर picture बनाने जैसा है। image का left edge आप कहीं भी draw करें, cylinder को घुमाकर CRTC_START और PEL registers set कर दें तो पूरी image को साफ देखने का तरीका हमेशा मौजूद होता है
    “screen edge पर पहुंचने पर आसान समाधान के तौर पर झटकों को स्वीकार करते हुए पूरी screen को ऊपर copy कर दिया” वाला हिस्सा भी दिलचस्प है
    Keen शुरू करते समय आम तौर पर “VGA compatibility mode enabled” जैसा message आता था, ऐसा याद है, और मैं हमेशा सोचता था कि इसका मतलब क्या है

  • Commander Keen सच में एक बहुत प्यारा छोटा गेम था
    इसे फिर से चलाने का तरीका ढूँढना पड़ेगा
    लेकिन इसे चलाने का सबसे अच्छा तरीका क्या होगा? “बड़ा” होने के बाद से लगभग 20 साल से Windows इस्तेमाल नहीं किया है, तो Debian पर इसे कैसे खेल सकता हूँ?

    • सीधे खेल सकते हैं: https://archive.org/details/msdos_Commander_Keen_1_-_Maroone...
    • सहमत नहीं हूँ। यह उन बच्चों के लिए गेम था जिनके पास किसी वजह से कंप्यूटर तो था, लेकिन Nintendo नहीं था
      उस समय कंप्यूटर console से करीब 10 गुना महंगे थे, इसलिए आमतौर पर वजह यह होती थी कि बड़ों की इस बारे में मजबूत राय होती थी कि बच्चे को क्या करना चाहिए
      NES और Genesis गेम्स से तुलना करें तो इसमें रूह की कमी है। उस वक्त मुझे यह पसंद था, लेकिन हाल ही में DosBox में फिर से खेलकर लगा कि वाकई इसकी तुलना नहीं हो सकती
    • DosBox पुराने VGA गेम्स बहुत अच्छी तरह चलाता है, और browser के अंदर समेत लगभग हर platform पर चलता है: https://archive.org/details/msdos_Commander_Keen_1_-_Maroone...
    • शायद DosBox होगा
    • Commander Keen और Jill of the Jungle वे गेम्स थे जिनसे मुझे पहली बार PC से परिचय हुआ था। सच में बहुत अच्छी यादें हैं

  • कुछ साल पहले मैंने दूसरा तरीका implement किया था, लेकिन सिर्फ आगे वाले edge को draw करना भी बहुत धीमा था
    हालांकि मैंने इसे C में लिखा था, और assembly programming ठीक से कभी नहीं सीखी
    https://github.com/geon/kate/blob/master/src/platform/dos/eg...