Vim में खोजे जाने वाले 6,500 regex से बना Bad Apple

 (eieio.games)
1 पॉइंट द्वारा GN⁺ 2025-01-13 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Vim के अंदर Bad Apple वीडियो चलाने के लिए हर फ्रेम को search query में बदला गया, और 120x90 खाली grid पर सिर्फ search highlights से स्क्रीन बनाई गई
  • वीडियो को ffmpeg से लगभग 6,500 PNG frames में बाँटा गया, फिर Python में हर image को 0 और 1 की 2D array में बदलकर काले pixels दिखाए गए
  • Vim के \%l, \%c, \zs, \ze और \| OR pattern को मिलाकर किसी खास row-column range rectangle को एक search में highlight किया गया
  • frames को rectangle search patterns में घटाने की प्रक्रिया optimal solution के बजाय top→bottom merge, left→right merge, और row-wise RLE में से सबसे छोटी search string चुनने वाली है
  • macro हर line के search pattern को / register में डालता है और अगली line पर जाकर frames आगे बढ़ाता है, जिससे लंबी queries को search window में सीधे paste करने पर होने वाली flicker और frame drop कम होते हैं

Vim search highlight से Bad Apple चलाना

  • लक्ष्य Vim छोड़े बिना Bad Apple वीडियो देखना है
  • स्क्रीन पर असल में बदलने वाली चीज file content नहीं, बल्कि Vim की current search query है
  • final video 120x90 resolution तक सीमित है
    • screen size की वजह से इसे और बड़ा करना मुश्किल था

Frame extraction और binarization

  • Felixoofed के badapple-frames repository में मौजूद video और ffmpeg command suggestion का उपयोग करके लगभग 6,500 PNG frames मिले
  • Python code से हर PNG को 120x90 में resize किया गया और black-and-white में बदला गया; फिर pixel value 10 से कम होने पर उसे 1 माना गया
    • 1 का मतलब black pixel है
    • 0 का मतलब bright pixel है
  • original video 480x360 था, लेकिन terminal size नापने के बाद इसे 120x90 तक घटाया गया
  • text_preview function 0 को ., और 1 को # के रूप में print करके conversion result की जाँच करने के लिए इस्तेमाल हुआ

Terminal characters को pixel जैसा दिखाना

  • Vim file में text grid बनाकर किसी खास character को search करने पर search result highlight image जैसा दिख सकता है
  • default search highlight blue होता है, इसलिए वह साफ नहीं दिखता; इसके लिए hi Search cterm=NONE ctermfg=grey ctermbg=grey setting इस्तेमाल की गई
    • matched character का foreground और background color एक ही grey रखा गया, ताकि वह block जैसा दिखे
  • सामान्य font में अक्षर vertically लंबे होते हैं, इसलिए pixels rectangle जैसे दिखते हैं
  • Square font का उपयोग करके terminal characters को square के करीब बनाया गया, ताकि grid ज्यादा natural दिखे

Rectangles को search pattern से draw करना

  • Vim search किसी खास line number और column number के आधार पर match कर सकता है
  • example pattern \%>5c\%<15c\%>4l\%<9l 5~15 columns और 4~9 lines के बीच के rectangle को match करता है
  • कई rectangles को \| से OR करके एक search string में एक साथ match कराया जा सकता है
  • इस capability की वजह से हर frame के black pixels को कई rectangle sets में तोड़ने की problem बन जाती है

Frame को rectangles में घटाने का algorithm

  • 90x120 grid में लगभग 10,000 pixels होते हैं, इसलिए pixel-level pattern बनाने पर search string tens of thousands characters तक लंबी हो सकती है
  • basic tests में Vim search अपने आप में fast है, लेकिन बहुत लंबी search string frame rate गिरा देती है
  • पहले लिखी गई method row-wise 1 के continuous runs ढूँढती है, और next row के runs से overlap होने पर उन्हें rectangle में merge करती है
    • पहली row में 1 के continuous runs ढूँढे जाते हैं
    • next row के runs और previous row runs के overlaps ढूँढे जाते हैं
    • अगर merged rectangle का area, अलग-अलग rows के area से बड़ा हो, तो merge किया जाता है
    • जहाँ संभव हो, existing rectangle में नया run लगातार merge किया जाता है
  • यह method एक row से आगे नहीं देखती, इसलिए optimal नहीं है
    • अभी खराब merge जैसा दिखने वाला case, बाद की rows तक सोचने पर अच्छा merge हो सकता है; ऐसे cases छूट जाते हैं

Bottleneck से बचने के लिए pattern generation की तीन methods

  • कई search strings 500~2,000 characters के स्तर की थीं, लेकिन कुछ frames में 10,000 characters से लंबी search strings बनीं
  • लंबी search strings ने frame rate को लगभग 40 FPS से single digits तक गिरा दिया
  • search string length performance का perfect proxy नहीं है, लेकिन इस case में similar length patterns को OR से बड़ी संख्या में जोड़ने पर pattern count और search time साथ-साथ बढ़ सकते हैं
  • optimal general algorithm खोजने के बजाय तीन simple algorithms सभी चलाए गए और सबसे छोटा search pattern चुना गया
    • top→bottom merge method
    • left→right merge method
    • row-wise RLE method
  • selection counts इस प्रकार हैं
    • original method, top→bottom merge: 1,110 बार
    • left→right merge: 2,239 बार
    • single-row RLE: 3,300 बार
  • RLE सबसे ज्यादा बार चुना गया, लेकिन bad cases में यह बहुत खराब हो सकता है, इसलिए इसे अकेले इस्तेमाल करने से बचा गया

Vim के अंदर frames आगे बढ़ाना

  • Vim के top-center window में 90 lines x 120 columns की blank file रखी गई
    • search row-column basis पर होता है, इसलिए actual characters की जरूरत नहीं है
  • left और right में image को center में रखने के लिए blank buffers रखे गए
  • bottom window में लगभग 6,500 search patterns line-wise रखे गए
  • macro current line के search pattern को पढ़कर search register में डालता है और next line पर चला जाता है

  • इस्तेमाल किया गया macro

    • macro "ay$:let @/=@a^M+ format में है
    • इसका behavior इस प्रकार है
    • "a: register a को target के रूप में use करना
    • y$: current line के end तक copy करना
    • :let @/=@a: search register / को register a के content से set करना
    • ^M: command execute करना
    • +: next line की शुरुआत में जाना
    • अगर इस macro को register q में record किया गया हो, तो 1500@q से 1,500 frames को जितना संभव हो उतनी तेजी से आगे बढ़ाया जा सकता है
    • /^Ra^M की तरह search window में लंबी query सीधे paste करने पर search window हजारों characters वाली query के हिसाब से बड़ी होती है, जिससे flicker और frame drop हो सकते हैं
    • let @/=@a से search register को सीधे set करने पर इस समस्या से बचा जा सकता है

सीमाएँ और published code

  • क्योंकि Vim के row-column search feature का उपयोग किया गया है, यह आपत्ति संभव है कि इसे सिर्फ traditional regular expressions से बना कहना मुश्किल है
  • frame rate को stable बनाए रखने के लिए कोई handling नहीं है
    • पूरे video में frame rate कुछ जगहों पर डगमगाता है
  • फिर भी, सिर्फ search queries से Vim के अंदर video चलाने के general-purpose solution के करीब result बनाया गया
  • code व्यवस्थित नहीं है, लेकिन vim-badapple repository में देखा जा सकता है

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

1 टिप्पणियां

 
GN⁺ 2025-01-13
Hacker News की टिप्पणियां

  • nolen से उम्मीद थी कि वह किसी चीज़ को 1000 गुना बड़ा करना जानता होगा :))) पहले इसी तरह की तकनीकें आज़माई थीं, लेकिन अलग-अलग, और एक दिन में तो बिल्कुल नहीं। अगर रुचि हो:
    Bad Matrix (tput से terminal में blocks आउटपुट करना): https://www.evalapply.org/posts/bad-matrix/
    Animating Text Art in Javascript (fixed grid में text आउटपुट करके flipbook की तरह animate करना): https://www.evalapply.org/posts/animate-text-art-javascript/...
    oxo (tic-tac-toe board को terminal में format करके आउटपुट करना, और जीत/हार/ड्रॉ के नतीजे regex से match करना): https://github.com/adityaathalye/oxo/blob/7681e75edaeec5aa1f...
    फिर भी वह Bad Apple सबसे बढ़िया है

  • Bad Apple में सचमुच मुझे खींच लेने वाला tech demo वह version था जो NES पर चला था
    https://somethingnerdy.com/downloads/
    मेरे Everdrive पर चलाए गए video यहां है
    https://inversethought.com/jordi/video/badapple.mp4
    आवाज़ भी पूरी तरह आती है। डेटा करीब 1GB है, और यह ऐसे system पर किया गया जहां आम game का size कुछ सौ KB से ज़्यादा नहीं होता और CPU में calculation के लिए सिर्फ तीन 8-bit registers हैं

    • शानदार। NES development थोड़ा कर चुका हूं, इसलिए लगता है graphics performance match करना आसान नहीं रहा होगा। आम तौर पर एक line में कुछ ही sprites हों तो NES sprites को ‘पिघलाना’ शुरू कर देता है, सही term नहीं पता
      जानना चाहूंगा कि sprites की जगह background tile map इस्तेमाल किया गया था क्या। वह भी graphics bandwidth के लिहाज़ से काफी impressive है
      “कुल audio playback rate (44.2kHz)” लिखा है, और आवाज़ इतनी साफ़ है यह भी हैरान करने वाला है। सोच रहा हूं क्या यह cartridge की expanded capability है। याद के मुताबिक NES का PCM channel उस bitrate के करीब भी नहीं था, और sample size भी शायद 8-bit था
    • आपने किस हिस्से को दिलचस्प पाया, इस पर निर्भर करते हुए NES पर बना मिलता-जुलता Bad Apple भी पसंद आ सकता है। अतिरिक्त मुश्किल के तौर पर यह Super Mario Bros. के ACE के जरिए चलता है, और सारा data controller से stream होता है
      https://www.youtube.com/watch?v=lfG8DbxFibY
      साथ में बनाया गया explanation video भी है
      https://www.youtube.com/watch?v=Wa0u1CjGtEQ
    • वाकई कमाल है, अगर इस काम पर कोई write-up हो तो पढ़ना चाहूंगा

  • Vim macro को “फिर से play किया जा सके” ऐसा बनाने के लिए अंत में अगली line पर ले जाने वाले हिस्से की जगह, नीचे वाले command से हर line पर macro एक बार चला सकते हैं
    :%norm @q

    • वाह, आज कुछ नया सीखा। हैरानी है कि यह trick मुझे नहीं पता थी
      पहले Vim golf करते समय आम तौर पर macro को recursive बनाते थे। macro record करके अंत +@q से करते थे। यानी अगली line पर जाकर macro फिर से चलाना। तब macro को एक बार चलाने पर वह सभी lines पर घूम जाता था
      keystrokes के हिसाब से बहुत efficient है, लेकिन असल में सोचने में मुश्किल और हाथ में आसानी से नहीं बैठता, इसलिए ज़्यादा इस्तेमाल नहीं होता। फिर भी golf के लिए मजेदार technique है

  • पिछले महीने ये Govee Curtain Lights discount पर थे
    https://us.govee.com/products/govee-curtain-lights
    मेरी जानकारी में इनमें animated GIF upload कर सकते हैं। इसलिए “Bad Apple” GIF बनाने का काम Kanban board में जोड़ दिया है, लेकिन device memory कितनी है और यह कितना अच्छा चलेगा, अभी नहीं पता
    कभी-कभी Remmy Scarlet के पंख फैलाने वाला scene अब भी रोंगटे खड़े कर देता है

    • मैंने Twinkly lights के साथ यह किया था, लेकिन अफसोस light की memory कम होने के कारण कुछ seconds से ज्यादा नहीं चला सका
    • मेरे पास 64x32 resolution वाला Bad Apple GIF है, size 1MB से थोड़ा कम है
      https://ezgif.com/ से काफी मदद मिली

  • Bad Apple से मन नहीं भरता। Internet की सबसे बेहतरीन चीज़ है। और लगभग हर बार देखते हुए थोड़ी जलन होती है कि यह idea पहले मेरे दिमाग में क्यों नहीं आया
    इस blog का footnote implementation भी मुझे बहुत पसंद आया। शायद इसे इस्तेमाल करूंगा

    • वे footnotes मेरे talented दोस्त Jake की site (https://jakelazaroff.com/) से लिए गए हैं। हो सकता है आपने पहले यहां उसका काम देखा हो
      बड़ी screen पर sidenotes की तरह दिखते हैं, और छोटी screen पर click करने पर खुलने वाले inline footnotes में बदल जाते हैं। बेझिझक ले सकते हैं

  • rectangle minimization problem में, यहां की problem StackOverflow पर discuss हुई problem से अलग लगती है। SO thread non-overlapping rectangle partitioning से deal करता है, लेकिन यह Vim project overlap allow करता है
    इसलिए optimal solution ढूंढने की problem शायद काफी आसान हो सकती है

    • algorithm के नज़रिए से असल में उल्टा है। overlap allow करने वाला minimum cover problem NP-hard है, और overlap allow न करने वाला minimum partition problem polynomial-time algorithm से हल हो सकता है। Franzblau और Kleitman का 1984 paper “An Algorithm for Covering Polygons with Rectangles” देखें: https://core.ac.uk/download/pdf/82333912.pdf
      बेशक, यह सिर्फ academic aside है, और afternoon project में कुछ चलाने की स्थिति में इसका मतलब यह नहीं कि एक पक्ष सच में practical तौर पर आसान होगा
    • अच्छा point है। सही, rectangles के overlap कर सकने की बात मैं पूरी तरह miss कर गया था। यह project शायद यहीं खत्म करूंगा और current solution से भी काफी संतुष्ट हूं, लेकिन यह बात problem को काफी simplify करती है, यह सही लगता है

  • parallel candidate solution generator सच में अच्छा idea है, लेकिन यह समझने में हर बार देर लगती है कि सबसे powerful algorithm बनाना जरूरी नहीं। क्योंकि लगता है कि बस थोड़ा और सुधार लें तो हर case में चलने वाला solution बन जाएगा

    • prototype को पर्याप्त fast बनाने की tricks में शायद यह मेरी favorite है। जब काम करता है तो मज़ा आता है
      हालांकि इस बात से सहमत हूं कि “perfect” चीज़ इस्तेमाल करने के बजाय एक कदम पीछे हटकर यह तरीका अपनाया जा सकता है, यह समझना वाकई मुश्किल होता है

  • काफी शानदार। creativity अच्छी है। जिन games पर यह आधारित है वे भी काफी ठीक हैं, और bullet hell hypnotic है

  • Doom या Bad Apple को अनपेक्षित तरीकों से चलाने वाले लोग वाकई कमाल के होते हैं
    pregnancy test पर Doom चलाने जैसा दिलचस्प example भी है

    • इससे पूरी तरह सहमत होना मुश्किल है। असल में वह pregnancy test के खोल के अंदर कोई भी microcontroller डालकर Doom चलाने जैसा ही था

  • 2006 football World Cup office में देखने की याद आ गई। home server में ssh से login करके terminal में match देख सकता था
    किसी और तरीके से देखने के लिए bandwidth कम थी