Vim'de aranan 6.500 düzenli ifadeden oluşan Bad Apple

 (eieio.games)
1 puan yazan GN⁺ 2025-01-13 | 1 yorum | WhatsApp'ta paylaş
  • Vim içinde Bad Apple videosunu oynatmak için her kare arama sorgusuna dönüştürülüyor ve 120x90'lık boşluk ızgarası üzerinde yalnızca arama vurgularıyla görüntü çiziliyor
  • Video, ffmpeg ile yaklaşık 6.500 PNG kareye bölünüyor; ardından Python'da her görsel 0 ve 1'lerden oluşan 2B diziye çevrilerek siyah pikseller işaretleniyor
  • Vim'in \%l, \%c, \zs, \ze ve \| OR desenleri birleştirilerek belirli satır-sütun aralığındaki dikdörtgenler tek aramada vurgulanıyor
  • Kareleri dikdörtgen arama desenlerine indirgeme sürecinde en iyi çözüm yerine yukarıdan aşağı birleştirme, soldan sağa birleştirme ve satır bazlı RLE arasından en kısa arama dizgesini seçen bir yaklaşım kullanılıyor
  • Makro, her satırdaki arama desenini / yazmacına koyup sonraki satıra geçerek kareleri ilerletiyor; böylece uzun sorgular doğrudan arama çubuğuna yapıştırıldığında oluşan titreşim ve kare hızı düşüşü azaltılıyor

Vim arama vurgusuyla Bad Apple oynatmak

  • Amaç, Vim'den çıkmadan Bad Apple videosunu izlemek
  • Ekranda gerçekten değişen şey dosya içeriği değil, Vim'in geçerli arama sorgusu
  • Ortaya çıkan video 120x90 çözünürlükle sınırlı
    • Ekran boyutu nedeniyle bunu daha büyük yapmak zordu

Kare çıkarma ve ikilileştirme

  • Felixoofed'in badapple-frames deposundaki video ve önerilen ffmpeg komutu kullanılarak yaklaşık 6.500 PNG kare elde ediliyor
  • Python kodu her PNG'yi 120x90 boyutuna yeniden ölçekleyip siyah-beyaza çeviriyor; ardından piksel değeri 10'dan küçükse bunu 1 olarak işliyor
    • 1, siyah piksel anlamına geliyor
    • 0, açık renkli piksel anlamına geliyor
  • Orijinal video 480x360'tı, ancak terminal boyutu ölçüldükten sonra 120x90'a küçültüldü
  • text_preview işlevi, dönüşüm sonucunu doğrulamak için 0'ı ., 1'i # olarak yazdırıyor

Terminal karakterlerini piksel gibi göstermek

  • Vim dosyası içinde bir metin ızgarası oluşturulup belirli karakterler aranırsa, arama sonucu vurgusu bir çizim gibi görünebiliyor
  • Varsayılan arama vurgusu mavi olduğu için yeterince belirgin değil; bu yüzden hi Search cterm=NONE ctermfg=grey ctermbg=grey ayarı kullanılıyor
    • Aranan karakterlerin ön plan ve arka plan rengi aynı griye ayarlanarak blok gibi görünmeleri sağlanıyor
  • Normal fontlarda karakterler dikey olarak uzun olduğu için pikseller dikdörtgen gibi görünüyor
  • Square fontu kullanılarak terminal karakterleri kareye daha yakın hale getiriliyor ve ızgara daha doğal görünüyor

Dikdörtgenleri arama deseni olarak çizmek

  • Vim araması, belirli satır numaraları ve sütun numaraları temel alınarak eşleşme yapabiliyor
  • Örnek desen \%>5c\%<15c\%>4l\%<9l, 5-15. sütunlar ile 4-9. satırlar arasındaki bir dikdörtgeni eşleştiriyor
  • Birden fazla dikdörtgen \| ile OR bağlanarak tek bir arama dizgesinde aynı anda eşleştirilebiliyor
  • Bu sayede her karenin siyah piksellerini birden çok dikdörtgen kümesine ayırma problemine dönüşüyor

Kareleri dikdörtgenlere indirgeyen algoritma

  • 90x120'lik ızgara yaklaşık 10.000 piksel içerdiğinden, desenler piksel düzeyinde oluşturulursa arama dizgesi on binlerce karaktere ulaşabiliyor
  • Temel testlerde Vim'in arama işlemi hızlı olsa da, aşırı uzun arama dizgeleri kare hızını düşürüyor
  • İlk yazılan yöntem, satır bazında art arda gelen 1 aralıklarını bulup bunlar sonraki satırdaki aralıklarla çakışıyorsa dikdörtgene birleştiriyor
    • İlk satırda art arda gelen 1 aralıkları bulunuyor
    • Sonraki satırdaki aralıklarla önceki satır aralıklarının kesişimi bulunuyor
    • Birleştirilmiş dikdörtgenin alanı, satırların ayrı ayrı alanından büyükse birleştiriliyor
    • Mümkün olduğunda mevcut dikdörtgene yeni aralıklar eklenmeye devam ediliyor
  • Bu yöntem bir satırdan daha ileriyi görmediği için en iyi çözüm değil
    • O anda kötü bir birleştirme gibi görünse bile, sonraki satırlar hesaba katıldığında iyi sonuç verebilecek durumları kaçırıyor

Darboğazı önlemek için üç desen üretim yöntemi

  • Birçok arama dizgesi 500-2.000 karakter civarındaydı, ancak bazı karelerde 10.000 karakteri aşan dizgeler oluştu
  • Uzun arama dizgeleri kare hızını yaklaşık 40 FPS'den tek haneli değerlere kadar düşürdü
  • Arama dizgesinin uzunluğu performans için kusursuz bir gösterge olmasa da, bu durumda benzer uzunlukta çok sayıda desenin OR ile bağlanması hem desen sayısını hem arama süresini artırabiliyor
  • En iyi genel algoritmayı aramak yerine üç basit algoritma birlikte çalıştırılıyor ve en kısa arama deseni seçiliyor
    • Yukarıdan aşağı birleştirme yöntemi
    • Soldan sağa birleştirme yöntemi
    • Satır bazlı RLE yöntemi
  • Seçilme sayıları şöyle:
    • Orijinal yöntem olan yukarıdan aşağı birleştirme: 1.110 kez
    • Soldan sağa birleştirme: 2.239 kez
    • Tek satırlık RLE: 3.300 kez
  • RLE en sık seçilen yöntem oldu, ancak kötü durumlarda sonucu çok kötü olabildiğinden tek başına kullanılmadı

Vim içinde kare ilerletmek

  • Vim'in üst orta penceresinde 90 satır x 120 sütundan oluşan boşluk dosyası bulunuyor
    • Arama satır ve sütun temelli olduğu için gerçek karakterlere ihtiyaç yok
  • Sağ ve solda, görüntüyü ortalamak için boş tamponlar yer alıyor
  • Alt pencerede yaklaşık 6.500 arama deseni satır satır tutuluyor
  • Makro, mevcut satırdaki arama desenini okuyup arama yazmacına koyuyor ve sonraki satıra geçiyor

  • Kullanılan makro

    • Makro şu biçimde: "ay$:let @/=@a^M+
    • Çalışma şekli şöyle:
    • "a: a yazmacını hedefler
    • y$: imlecin bulunduğu yerden satır sonuna kadar kopyalar
    • :let @/=@a: arama yazmacı / değerini a yazmacının içeriğine ayarlar
    • ^M: komutu çalıştırır
    • +: bir sonraki satırın başına gider
    • Bu makro q yazmacına kaydedildiyse, 1500@q ile 1.500 kare mümkün olan en yüksek hızda ilerletilebilir
    • /^Ra^M gibi uzun sorgular arama çubuğuna doğrudan yapıştırıldığında, arama çubuğu binlerce karakterlik sorguya uyacak şekilde büyüyebilir; bu da titreşim ve kare hızı düşüşüne yol açabilir
    • let @/=@a ile arama yazmacını doğrudan ayarlamak bu sorunu önlüyor

Sınırlar ve yayımlanan kod

  • Vim'in satır-sütun arama özelliği kullanıldığı için, bunun yalnızca geleneksel düzenli ifadelerden oluştuğunu söylemeye itiraz edilebilir
  • Kare hızını kararlı tutmaya yönelik bir işlem yok
    • Video boyunca kare hızı zaman zaman dalgalanıyor
  • Yine de yalnızca arama sorgularıyla Vim içinde video oynatmaya yakın, genel amaçlı bir sonuç elde edilmiş
  • Kod düzenlenmiş değil, ancak vim-badapple deposunda incelenebilir

İlgili okumalar

1 yorum

 
GN⁺ 2025-01-13
Hacker News yorumları

  • nolen’ın bir şeyi 1000 kat büyütmeyi bileceğini tahmin ediyordum :))) Geçmişte benzer teknikler denemiştim ama ayrı ayrıydı ve kesinlikle bir günde yapılmış şeyler değildi. İlginizi çekerse:
    Bad Matrix (terminalde tput ile blok yazdırma): https://www.evalapply.org/posts/bad-matrix/
    Animating Text Art in Javascript (sabit bir ızgaraya metin yazdırıp flipbook gibi canlandırma): https://www.evalapply.org/posts/animate-text-art-javascript/...
    oxo (tic-tac-toe tahtasını terminale biçimli basma ve kazanma/kaybetme/beraberlik sonucunu regex ile eşleştirme): https://github.com/adityaathalye/oxo/blob/7681e75edaeec5aa1f...
    Yine de o Bad Apple hepsinden iyi

  • Bad Apple’a gerçekten takılmamı sağlayan teknik demo, NES’te çalışan sürümdü
    https://somethingnerdy.com/downloads/
    Kendi Everdrive’ımda çalıştırdığım video burada
    https://inversethought.com/jordi/video/badapple.mp4
    Ses de eksiksiz geliyor. Veri yaklaşık 1 GB; normal oyunların birkaç yüz KB’ı geçmediği ve CPU’sunda hesaplama için yalnızca 3 adet 8 bit register bulunan bir sistemde bunu yapmışlar

    • Harika. Biraz NES geliştirmesi yapmış biri olarak grafik performansını tutturmanın kolay olmadığını düşünüyorum. Normalde bir satırda birkaç sprite olsa bile NES sprite’ları “eritmeye” başlar; doğru terimi bilmiyorum
      Sprite yerine arka plan tile map’i mi kullandıklarını merak ediyorum. Bu da grafik bant genişliği açısından epey etkileyici
      “Tam ses çalma hızı (44.2 kHz)” denmiş; sesin bu kadar net olması da şaşırtıcı. Bunun kartuşun sağladığı bir genişletme özelliği olup olmadığını merak ediyorum. Hatırladığım kadarıyla NES’in PCM kanalı bu bit hızının yanına bile yaklaşmıyordu ve örnek boyutu da sanırım 8 bitti
    • Hangi kısmını ilginç bulduğunuza bağlı olarak, NES’te yapılmış benzer bir Bad Apple da hoşunuza gidebilir. Ek zorluk olarak Super Mario Bros.’un ACE’i üzerinden çalışıyor ve tüm veriler kontrolcüden akıtılıyor
      https://www.youtube.com/watch?v=lfG8DbxFibY
      Birlikte hazırlanmış açıklama videosu da var
      https://www.youtube.com/watch?v=Wa0u1CjGtEQ
    • Gerçekten harika; bu çalışma hakkında yazılı bir özet varsa okumak isterim

  • Vim makrosunu “yeniden oynatılabilir” kılmak için sonunda bir sonraki satıra geçiren kısım yerine, aşağıdaki komutla her satır için makroyu bir kez çalıştırmak da mümkün
    :%norm @q

    • Vay, bugün bunu öğrendim. Bu püf noktasını bilmemem epey şaşırtıcı
      Eskiden Vim golf yaparken genelde makroyu özyinelemeli hale getirirdim. Makroyu kaydedip sonunu +@q ile bitirirdim. Yani bir sonraki satıra geçip makroyu yeniden çalıştırma yöntemi. Böylece makroyu bir kez çalıştırınca tüm satırları taramış olurdu
      Tuş vuruşu sayısı açısından çok verimli ama pratikte düşünmesi zor ve ele pek oturmuyor, o yüzden çok kullanılmıyor. Yine de golf için eğlenceli bir teknik

  • Geçen ay bu Govee Curtain Lights indirimdeydi
    https://us.govee.com/products/govee-curtain-lights
    Bildiğim kadarıyla buna animasyonlu GIF yüklenebiliyor. Bu yüzden “Bad Apple” GIF’i yapma işini Kanban panoma ekledim ama cihaz belleğinin ne kadar olduğunu ve ne kadar iyi çalışacağını henüz bilmiyorum
    Remmy Scarlet’ın kanatlarını açtığı sahne bazen hâlâ tüylerimi diken diken ediyor

    • Bunu Twinkly ışıklarla denedim; ne yazık ki ışıkların belleği yetersiz kaldığı için birkaç saniyeden fazla çalıştıramadım
    • 64x32 çözünürlükte bir Bad Apple GIF’im var; boyutu 1 MB’ın biraz altında
      https://ezgif.com/ çok işime yaradı

  • Bad Apple’dan bıkılmıyor. İnternetin en iyi şeyi. Ayrıca neredeyse her izlediğimde o fikri neden önce ben düşünemedim diye biraz kıskanıyorum
    Bu blogdaki dipnot uygulamasını da gerçekten çok beğendim. Muhtemelen alıp kullanacağım

    • O dipnotlar yetenekli arkadaşım Jake’in sitesinden (https://jakelazaroff.com/) alınmış. Daha önce burada onun çalışmalarını görmüş olabilirsiniz
      Büyük ekranlarda yan not olarak görünüyor, küçük ekranlarda ise tıklayınca açılan satır içi dipnota dönüşüyor. İstediğiniz gibi alabilirsiniz

  • Dikdörtgen minimizasyon probleminde buradaki sorun, StackOverflow’da tartışılan sorundan farklı görünüyor. SO başlığı örtüşmeyen dikdörtgenlere bölmeyi ele alıyor, ama bu Vim projesi örtüşmeye izin veriyor
    Bu yüzden en iyi çözümü bulma problemi çok daha kolay olabilir gibi görünüyor

    • Algoritma açısından aslında tam tersi. Örtüşmeye izin veren minimum örtü problemi NP-zordur; örtüşmeye izin vermeyen minimum bölme problemi için ise polinom zamanlı algoritmalar var. Franzblau ve Kleitman’ın 1984 tarihli “An Algorithm for Covering Polygons with Rectangles” makalesine bakın: https://core.ac.uk/download/pdf/82333912.pdf
      Elbette bu sadece akademik bir yan not; bir öğleden sonra projesinde çalışan bir şey ortaya çıkarma bağlamında bir tarafın pratikte gerçekten daha kolay olduğu anlamına gelmeyebilir
    • İyi nokta. Evet, dikdörtgenlerin örtüşebileceği gerçeğini tamamen atlamışım. Bu projeyi muhtemelen burada noktalayacağım ve mevcut çözümden de oldukça memnunum, ama bunun problemi ciddi biçimde basitleştirdiği doğru gibi

  • Paralel aday çözüm üreteci gerçekten iyi bir fikir; ama her seferinde en güçlü algoritmayı yapmak zorunda olmadığımı fark etmem uzun sürüyor. Çünkü biraz daha düzeltirsem her duruma uyan bir çözüm yapabilirim gibi geliyor

    • Prototipi yeterince hızlı hale getirmenin yolları arasında muhtemelen en sevdiğim yöntem. Çalıştığında çok keyifli
      Yine de “mükemmel” olanı kullanmak yerine bir adım geri çekilip bu yöntemi kullanabileceğini fark etmenin gerçekten zor olduğuna katılıyorum

  • Epey havalı. Yaratıcılık güzel. Bunun temel aldığı oyunlar da oldukça iyi ve bullet hell hipnotize edici

  • Doom’u ya da Bad Apple’ı beklenmedik şekillerde çalıştıran insanlar gerçekten harika
    Hamilelik testinde Doom çalıştırmak gibi ilginç örnekler de var

    • Buna pek katılamayacağım. Aslında daha çok, hamilelik testi kabuğunun içine rastgele bir mikrodenetleyici koyup Doom çalıştırmaya benziyordu

  • 2006 Dünya Kupası’nı iş yerinde izlediğim aklıma geldi. Ev sunucuma ssh ile giriş yapıp terminalde maçı izleyebiliyordum
    Başka türlü izlemek için bant genişliği yetmiyordu