Bad Apple gồm 6.500 biểu thức chính quy tìm kiếm trong Vim

• Để phát video Bad Apple bên trong Vim, mỗi khung hình được chuyển thành một truy vấn tìm kiếm, rồi vẽ hình chỉ bằng highlight kết quả tìm kiếm trên một lưới khoảng trắng 120x90
• Video được tách bằng ffmpeg thành khoảng 6.500 khung hình PNG, sau đó trong Python, mỗi ảnh được chuyển thành mảng 2D gồm 0 và 1 để biểu diễn các pixel đen
• Kết hợp các mẫu OR \%l, \%c, \zs, \ze và \| của Vim để highlight một hình chữ nhật theo phạm vi hàng/cột cụ thể chỉ bằng một lần tìm kiếm
• Quá trình rút gọn khung hình thành các mẫu tìm kiếm hình chữ nhật không dùng lời giải tối ưu, mà chọn chuỗi tìm kiếm ngắn nhất trong ba cách: gộp từ trên xuống dưới, gộp từ trái sang phải, và RLE theo từng hàng
• Macro đưa mẫu tìm kiếm của từng dòng vào thanh ghi / rồi chuyển sang dòng tiếp theo để lật khung hình, giảm hiện tượng nhấp nháy và tụt khung hình khi dán trực tiếp truy vấn dài vào ô tìm kiếm

---

Phát Bad Apple bằng highlight tìm kiếm trong Vim

• Mục tiêu là xem video Bad Apple mà không rời khỏi Vim
• Thứ thực sự thay đổi trên màn hình không phải nội dung tệp, mà là truy vấn tìm kiếm hiện tại của Vim
• Video kết quả bị giới hạn ở độ phân giải 120x90
  • Do kích thước màn hình nên khó phóng to hơn

Trích xuất khung hình và nhị phân hóa

• Sử dụng video trong repository badapple-frames của Felixoofed và gợi ý lệnh ffmpeg để thu được khoảng 6.500 khung hình PNG
• Mã Python resize từng PNG về 120x90, chuyển sang đen trắng, rồi coi pixel có giá trị nhỏ hơn 10 là 1
  • 1 nghĩa là pixel đen
  • 0 nghĩa là pixel sáng
• Video gốc có kích thước 480x360, nhưng sau khi đo kích thước terminal thì được thu nhỏ xuống 120x90
• Hàm text_preview được dùng để in 0 thành ., 1 thành # nhằm kiểm tra kết quả chuyển đổi

Làm ký tự terminal trông như pixel

• Nếu tạo một lưới văn bản trong tệp Vim và tìm kiếm các ký tự cụ thể, highlight kết quả tìm kiếm có thể trông như một hình vẽ
• Highlight tìm kiếm mặc định có màu xanh nên không rõ nét, vì vậy dùng thiết lập hi Search cterm=NONE ctermfg=grey ctermbg=grey
  • Đặt màu chữ và màu nền của ký tự được tìm thấy cùng một màu xám để chúng trông như các khối
• Với font thông thường, chữ cao theo chiều dọc nên pixel trông giống hình chữ nhật
• Dùng font Square để ký tự terminal gần giống hình vuông hơn, giúp lưới trông tự nhiên hơn

Vẽ hình chữ nhật bằng mẫu tìm kiếm

• Tìm kiếm trong Vim có thể khớp dựa trên số hàng và số cột cụ thể
• Mẫu ví dụ \%>5c\%<15c\%>4l\%<9l khớp với hình chữ nhật nằm giữa cột 5~15 và hàng 4~9
• Nhiều hình chữ nhật có thể được nối OR bằng \| để khớp đồng thời trong một chuỗi tìm kiếm
• Nhờ tính năng này, bài toán được chuyển thành phân rã các pixel đen của từng khung hình thành nhiều tập hợp hình chữ nhật

Thuật toán rút gọn khung hình thành hình chữ nhật

• Lưới 90x120 có khoảng 10.000 pixel, nên nếu tạo mẫu theo từng pixel, chuỗi tìm kiếm có thể dài tới hàng chục nghìn ký tự
• Trong thử nghiệm cơ bản, bản thân tìm kiếm của Vim nhanh, nhưng chuỗi tìm kiếm quá dài làm giảm tốc độ khung hình
• Cách viết ban đầu là tìm các đoạn liên tiếp gồm 1 theo từng hàng, rồi nếu chúng chồng lấn với đoạn ở hàng tiếp theo thì gộp thành hình chữ nhật
  • Tìm các đoạn liên tiếp gồm 1 ở hàng đầu tiên
  • Tìm phần chồng lấn giữa các đoạn ở hàng tiếp theo và các đoạn ở hàng trước
  • Nếu diện tích hình chữ nhật sau khi gộp lớn hơn diện tích riêng lẻ của từng hàng thì gộp
  • Nếu có thể, tiếp tục gộp đoạn mới vào hình chữ nhật hiện có
• Cách này không tối ưu vì nó không nhìn xa hơn một hàng
  • Có những trường hợp hiện tại trông như phép gộp tệ, nhưng nếu xét cả các hàng sau thì lại có thể là phép gộp tốt, và cách này sẽ bỏ lỡ

Ba cách tạo mẫu để tránh nghẽn cổ chai

• Nhiều chuỗi tìm kiếm có độ dài khoảng 500~2.000 ký tự, nhưng ở một số khung hình, chuỗi tìm kiếm được tạo ra dài hơn 10.000 ký tự
• Chuỗi tìm kiếm dài làm tốc độ khung hình giảm từ khoảng 40 FPS xuống còn một chữ số
• Độ dài chuỗi tìm kiếm không phải chỉ báo thay thế hoàn hảo cho hiệu năng, nhưng trong trường hợp này, nhiều mẫu có độ dài tương tự được nối bằng OR, nên số lượng mẫu và thời gian tìm kiếm có thể cùng tăng
• Thay vì tìm thuật toán tổng quát tối ưu, cả ba thuật toán đơn giản đều được chạy và mẫu tìm kiếm ngắn nhất được chọn
  • Cách gộp từ trên xuống dưới
  • Cách gộp từ trái sang phải
  • Cách RLE theo từng hàng
• Số lần được chọn như sau
  • Cách gốc, gộp từ trên xuống dưới: 1.110 lần
  • Gộp từ trái sang phải: 2.239 lần
  • RLE một hàng: 3.300 lần
• RLE được chọn thường xuyên nhất, nhưng trong trường hợp xấu có thể rất tệ, nên tránh dùng riêng lẻ

Lật khung hình bên trong Vim

• Cửa sổ trung tâm phía trên trong Vim chứa một tệp toàn khoảng trắng có 90 dòng x 120 cột
  • Vì tìm kiếm dựa trên hàng/cột nên không cần ký tự thực sự
• Hai bên trái phải đặt các buffer trống để căn giữa ảnh
• Cửa sổ phía dưới chứa khoảng 6.500 mẫu tìm kiếm, mỗi mẫu một dòng
• Macro đọc mẫu tìm kiếm ở dòng hiện tại, đưa vào thanh ghi tìm kiếm rồi chuyển sang dòng tiếp theo

• Macro đã dùng

  • Macro có dạng "ay$:let @/=@a^M+
  • Cách hoạt động như sau
  • "a: dùng thanh ghi a làm đích
  • y$: sao chép đến cuối dòng hiện tại
  • :let @/=@a: đặt thanh ghi tìm kiếm / thành nội dung của thanh ghi a
  • ^M: thực thi lệnh
  • +: di chuyển tới đầu dòng tiếp theo
  • Nếu đã ghi macro này vào thanh ghi q, có thể dùng 1500@q để lật 1.500 khung hình nhanh nhất có thể
  • Nếu dán trực tiếp truy vấn dài vào ô tìm kiếm như /^Ra^M, ô tìm kiếm có thể phình ra theo truy vấn hàng nghìn ký tự, gây nhấp nháy và tụt khung hình
  • Đặt trực tiếp thanh ghi tìm kiếm bằng let @/=@a giúp tránh vấn đề này

Hạn chế và mã đã công bố

• Vì sử dụng tính năng tìm kiếm theo hàng/cột của Vim, có thể có ý kiến phản biện rằng đây không hẳn chỉ được cấu thành từ các biểu thức chính quy truyền thống
• Không có xử lý để duy trì tốc độ khung hình ổn định
  • Tốc độ khung hình trong toàn bộ video có dao động ở một số đoạn
• Dù vậy, kết quả khá gần với một giải pháp tổng quát để phát video trong Vim chỉ bằng truy vấn tìm kiếm
• Mã chưa được dọn dẹp, nhưng có thể xem trong repository vim-badapple

[GN⁺]

Ý kiến trên Hacker News

• Nếu là nolen thì tôi biết kiểu gì cũng sẽ phóng đại lên 1000 lần :))) Trước đây tôi từng thử các kỹ thuật tương tự, nhưng là riêng lẻ và chắc chắn không phải làm trong một ngày. Nếu bạn quan tâm:
  Bad Matrix (in các khối ra terminal bằng tput): https://www.evalapply.org/posts/bad-matrix/
  Animating Text Art in Javascript (in chữ lên lưới cố định để tạo hoạt ảnh như flipbook): https://www.evalapply.org/posts/animate-text-art-javascript/...
  oxo (định dạng và in bàn cờ tic-tac-toe ra terminal, rồi dùng regex để khớp kết quả thắng/thua/hòa): https://github.com/adityaathalye/oxo/blob/7681e75edaeec5aa1f...
  Dù vậy Bad Apple kia vẫn là đỉnh nhất

• Bản demo kỹ thuật thật sự khiến tôi mê Bad Apple là phiên bản chạy trên NES
  https://somethingnerdy.com/downloads/
  Đây là video tôi chạy nó trên Everdrive của mình
  https://inversethought.com/jordi/video/badapple.mp4
  Âm thanh cũng phát đầy đủ. Dữ liệu khoảng 1GB, và họ làm được chuyện này trên một hệ thống mà game thông thường không quá vài trăm KB, còn CPU chỉ có 3 thanh ghi 8-bit để tính toán

  • Tuyệt thật. Từ góc nhìn của người từng làm một chút phát triển NES, tôi nghĩ để đạt được hiệu năng đồ họa đó hẳn không dễ. Thường chỉ cần vài sprite trên một dòng là NES đã bắt đầu “làm tan” sprite rồi, tôi không biết thuật ngữ chính xác là gì
    Tôi tò mò liệu họ có dùng tile map nền thay vì sprite không. Nếu vậy thì xét về băng thông đồ họa cũng khá ấn tượng
    Có ghi “tốc độ phát toàn bộ âm thanh (44,2kHz)”, nên việc âm thanh trong như vậy cũng đáng ngạc nhiên. Tôi tò mò liệu đó có phải là tính năng do cartridge mở rộng không. Theo tôi nhớ thì kênh PCM của NES hoàn toàn không đạt tới bitrate đó, và kích thước mẫu hình như cũng là 8-bit
  • Tùy bạn thấy phần nào thú vị, có thể bạn cũng sẽ thích một bản Bad Apple tương tự được triển khai trên NES. Khó hơn nữa là nó chạy thông qua ACE của Super Mario Bros., và toàn bộ dữ liệu được stream qua tay cầm
    https://www.youtube.com/watch?v=lfG8DbxFibY
    Cũng có video giải thích được làm kèm theo
    https://www.youtube.com/watch?v=Wa0u1CjGtEQ
  • Thật sự rất ngầu, nếu có bài viết tổng kết nào về việc này thì tôi muốn đọc

• Đoạn ở cuối đưa xuống dòng tiếp theo để làm macro Vim “có thể phát lại” cũng có thể được thực hiện bằng lệnh dưới đây để chạy mỗi dòng một lần macro
  :%norm @q

  • Ồ, hôm nay mới học được. Khá ngạc nhiên là tôi không biết mẹo này
    Trước đây khi chơi Vim golf, tôi thường tạo macro theo kiểu đệ quy. Ghi macro và kết thúc bằng +@q. Tức là chuyển sang dòng tiếp theo rồi chạy lại macro. Như vậy khi chạy macro một lần, nó sẽ quét qua mọi dòng
    Xét về số phím bấm thì rất hiệu quả, nhưng thực tế lại khó nghĩ ra và không quen tay nên không dùng nhiều. Dù vậy đây là kỹ thuật vui để chơi golf

• Tháng trước mấy chiếc Govee Curtain Lights này đang được giảm giá
  https://us.govee.com/products/govee-curtain-lights
  Theo tôi biết thì có thể tải GIF động lên đó. Vì vậy tôi đã thêm việc tạo GIF “Bad Apple” vào bảng kanban, nhưng vẫn chưa biết bộ nhớ thiết bị có bao nhiêu và chạy tốt đến đâu
  Thỉnh thoảng cảnh Remmy Scarlet dang cánh vẫn làm tôi lạnh sống lưng

  • Tôi từng thử làm việc này với đèn Twinkly, nhưng tiếc là bộ nhớ phía đèn không đủ nên không chạy được quá vài giây
  • Tôi có một GIF Bad Apple độ phân giải 64x32, kích thước hơi dưới 1MB
    Nhờ https://ezgif.com/ rất nhiều

• Bad Apple không bao giờ chán. Đây là thứ tuyệt nhất trên internet. Và gần như mỗi lần xem tôi lại hơi ghen tị vì sao mình không nghĩ ra ý tưởng đó trước
  Tôi cũng rất thích cách triển khai chú thích cuối trang của blog này. Có lẽ tôi sẽ lấy về dùng

  • Phần chú thích đó được lấy từ site của người bạn tài năng Jake (https://jakelazaroff.com/). Có thể trước đây bạn đã thấy tác phẩm của anh ấy ở đây
    Trên màn hình lớn, nó hiện thành sidenote; trên màn hình nhỏ, nó chuyển thành chú thích inline bung ra khi nhấp. Cứ thoải mái lấy dùng

• Trong bài toán tối thiểu hóa hình chữ nhật, vấn đề ở đây có vẻ khác với thứ được thảo luận trên StackOverflow. Thread SO nói về phân hoạch thành các hình chữ nhật không chồng lấn, còn dự án Vim này cho phép chồng lấn
  Vì vậy có khả năng bài toán tìm nghiệm tối ưu dễ hơn nhiều

  • Nhìn từ góc độ thuật toán thì thật ra ngược lại. Bài toán phủ tối thiểu cho phép chồng lấn là NP-hard, còn bài toán phân hoạch tối thiểu không cho phép chồng lấn có thuật toán thời gian đa thức. Xem bài báo năm 1984 của Franzblau và Kleitman, “An Algorithm for Covering Polygons with Rectangles”: https://core.ac.uk/download/pdf/82333912.pdf
    Tất nhiên đây chỉ là chuyện bên lề mang tính học thuật, không nhất thiết có nghĩa là trong bối cảnh một dự án làm buổi chiều để chạy được thứ gì đó thì bên nào thực tế dễ hơn
  • Ý hay. Đúng vậy, tôi đã hoàn toàn bỏ sót việc các hình chữ nhật có thể chồng lấn. Có lẽ dự án này sẽ dừng ở đây và tôi cũng khá hài lòng với lời giải hiện tại, nhưng đúng là điểm này dường như làm bài toán đơn giản đi đáng kể

• Bộ sinh nghiệm ứng viên song song là một ý tưởng thật sự hay, nhưng lần nào tôi cũng mất nhiều thời gian để nhận ra rằng không nhất thiết phải tạo thuật toán mạnh nhất. Vì cứ có cảm giác chỉ cần sửa thêm chút nữa là sẽ có được lời giải dùng được cho mọi trường hợp

  • Đây có lẽ là một trong những mẹo tôi thích nhất để tạo prototype đủ nhanh. Mỗi lần chạy được đều rất vui
    Nhưng tôi đồng ý là thật sự khó nhận ra mình có thể lùi lại một bước và dùng cách này thay vì dùng thứ “hoàn hảo”

• Khá ngầu. Sáng tạo tốt. Các game làm nền cho thứ này cũng khá ổn, và danmaku thì thôi miên

• Những người chạy Doom hay Bad Apple theo những cách không ai ngờ tới thật sự rất đáng nể
  Cũng có những ví dụ thú vị như chạy Doom trên que thử thai

  • Tôi khó mà đồng ý mạnh với chuyện đó. Thực chất nó gần giống việc nhét một microcontroller tùy ý vào bên trong vỏ que thử thai rồi chạy Doom hơn

• Tôi nhớ hồi xem World Cup 2006 ở chỗ làm. Tôi có thể ssh vào server ở nhà và xem trận đấu trong terminal
  Băng thông không đủ để xem bằng cách khác