Bad Apple ที่ประกอบด้วย regular expression 6,500 ชุดสำหรับค้นหาใน Vim

 (eieio.games)
1 คะแนน โดย GN⁺ 2025-01-13 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • เพื่อเล่นวิดีโอ Bad Apple ภายใน Vim จึงแปลงแต่ละเฟรมให้เป็นคำค้นหา แล้ววาดภาพบนกริดช่องว่างขนาด 120x90 โดยใช้เพียงการไฮไลต์ผลการค้นหา
  • วิดีโอถูกแยกด้วย ffmpeg ออกเป็น เฟรม PNG ราว 6,500 เฟรม จากนั้นใช้ Python แปลงแต่ละภาพเป็นอาร์เรย์ 2 มิติของ 0 และ 1 เพื่อระบุพิกเซลดำ
  • ใช้ \%l, \%c, \zs, \ze และแพตเทิร์น OR \| ของ Vim ร่วมกัน เพื่อไฮไลต์ สี่เหลี่ยมตามช่วงแถว·คอลัมน์ ที่กำหนดได้ด้วยการค้นหาเพียงครั้งเดียว
  • กระบวนการย่อเฟรมให้เป็นแพตเทิร์นค้นหาแบบสี่เหลี่ยมไม่ได้ใช้คำตอบที่เหมาะที่สุด แต่เลือกสตริงค้นหาที่สั้นที่สุดจากวิธีรวมบน→ล่าง, ซ้าย→ขวา และ RLE รายแถว
  • มาโครจะนำแพตเทิร์นค้นหาของแต่ละบรรทัดใส่ไว้ในรีจิสเตอร์ / แล้วเลื่อนไปบรรทัดถัดไปเพื่อเปลี่ยนเฟรม ช่วยลดการกะพริบและอัตราเฟรมตกที่เกิดขึ้นเมื่อวางคำค้นหายาว ๆ ลงในช่องค้นหาโดยตรง

เล่น Bad Apple ด้วยการไฮไลต์การค้นหาใน Vim

  • เป้าหมายคือดูวิดีโอ Bad Apple โดยไม่ต้องออกจาก Vim
  • สิ่งที่เปลี่ยนจริง ๆ บนหน้าจอไม่ใช่เนื้อหาไฟล์ แต่คือ คำค้นหาปัจจุบัน ของ Vim
  • วิดีโอผลลัพธ์ถูกจำกัดไว้ที่ความละเอียด 120x90
    • เพราะขนาดหน้าจอทำให้ขยายใหญ่กว่านี้ได้ยาก

การดึงเฟรมและแปลงเป็นภาพไบนารี

  • ใช้วิดีโอและคำแนะนำคำสั่ง ffmpeg จาก Felixoofed's badapple-frames repository เพื่อให้ได้ เฟรม PNG ราว 6,500 เฟรม
  • ใช้โค้ด Python ปรับขนาด PNG แต่ละภาพเป็น 120x90 และแปลงเป็นขาวดำ จากนั้นถือว่าค่าพิกเซลที่น้อยกว่า 10 เป็น 1
    • 1 หมายถึงพิกเซลดำ
    • 0 หมายถึงพิกเซลสว่าง
  • วิดีโอต้นฉบับมีความละเอียด 480x360 แต่หลังวัดขนาดเทอร์มินัลแล้วจึงลดลงเป็น 120x90
  • ฟังก์ชัน text_preview ใช้พิมพ์ 0 เป็น . และ 1 เป็น # เพื่อตรวจสอบผลการแปลง

ทำให้อักขระในเทอร์มินัลดูเหมือนพิกเซล

  • สร้างกริดข้อความในไฟล์ของ Vim แล้วค้นหาอักขระบางตัว จากนั้นการไฮไลต์ผลการค้นหาก็สามารถดูเหมือนภาพได้
  • การไฮไลต์การค้นหาเริ่มต้นเป็นสีน้ำเงินซึ่งไม่คมชัดพอ จึงใช้การตั้งค่า hi Search cterm=NONE ctermfg=grey ctermbg=grey
    • ทำให้สีตัวอักษรและสีพื้นหลังของอักขระที่ถูกค้นหาตรงกันเป็นสีเทาเดียวกัน เพื่อให้ดูเหมือนบล็อก
  • ฟอนต์ทั่วไปมีตัวอักษรที่สูงในแนวตั้ง ทำให้พิกเซลดูเป็นสี่เหลี่ยมผืนผ้า
  • ใช้ฟอนต์ Square เพื่อทำให้อักขระในเทอร์มินัลใกล้เคียงกับสี่เหลี่ยมจัตุรัสมากขึ้น และทำให้กริดดูเป็นธรรมชาติกว่าเดิม

วาดสี่เหลี่ยมด้วยแพตเทิร์นค้นหา

  • การค้นหาใน Vim สามารถจับคู่โดยอิงจาก หมายเลขแถว และ หมายเลขคอลัมน์ ที่กำหนดได้
  • ตัวอย่างแพตเทิร์น \%>5c\%<15c\%>4l\%<9l จะจับคู่สี่เหลี่ยมระหว่างคอลัมน์ 5~15 และแถว 4~9
  • สี่เหลี่ยมหลายชุดสามารถเชื่อมด้วย \| แบบ OR เพื่อจับคู่พร้อมกันในสตริงค้นหาเดียว
  • ด้วยความสามารถนี้ ปัญหาจึงเปลี่ยนเป็นการแยกพิกเซลดำของแต่ละเฟรมออกเป็น ชุดของสี่เหลี่ยมหลายชุด

อัลกอริทึมสำหรับย่อเฟรมเป็นสี่เหลี่ยม

  • กริด 90x120 มีประมาณ 10,000 พิกเซล ดังนั้นถ้าสร้างแพตเทิร์นระดับพิกเซล สตริงค้นหาอาจยาวถึงหลายหมื่นตัวอักษร
  • จากการทดสอบพื้นฐานพบว่าการค้นหาของ Vim เองทำงานได้เร็ว แต่สตริงค้นหาที่ยาวเกินไปทำให้อัตราเฟรมลดลง
  • วิธีแรกที่เขียนขึ้นจะหาแต่ละช่วงของ 1 ที่ต่อเนื่องกันในระดับแถว แล้วถ้ามันทับซ้อนกับช่วงในแถวถัดไปก็รวมเป็นสี่เหลี่ยม
    • หาแต่ละช่วงของ 1 ที่ต่อเนื่องกันจากแถวแรก
    • หาช่วงที่ทับซ้อนกับช่วงของแถวถัดไปและของแถวก่อนหน้า
    • ถ้าพื้นที่ของสี่เหลี่ยมที่รวมกันมากกว่าพื้นที่ของแต่ละแถวแยกกันก็จะรวมเข้าด้วยกัน
    • ถ้าเป็นไปได้ก็จะรวมช่วงใหม่เข้ากับสี่เหลี่ยมเดิมต่อไป
  • วิธีนี้ไม่เหมาะที่สุด เพราะมองไปข้างหน้าได้เพียงหนึ่งแถว
    • จึงพลาดกรณีที่ตอนนี้ดูเหมือนเป็นการรวมที่ไม่ดี แต่เมื่อพิจารณาแถวถัด ๆ ไปแล้วกลับเป็นการรวมที่ดี

วิธีสร้างแพตเทิร์น 3 แบบเพื่อหลีกเลี่ยงคอขวด

  • สตริงค้นหาจำนวนมากยาวประมาณ 500~2,000 ตัวอักษร แต่บางเฟรมสร้างสตริงค้นหาที่ยาวเกิน 10,000 ตัวอักษร
  • สตริงค้นหาที่ยาวทำให้อัตราเฟรมลดจากประมาณ 40 FPS ลงเหลือเลขหลักเดียว
  • ความยาวของสตริงค้นหาไม่ใช่ตัวชี้วัดประสิทธิภาพที่สมบูรณ์แบบ แต่ในกรณีนี้แพตเทิร์นที่มีความยาวใกล้เคียงกันจำนวนมากถูกเชื่อมด้วย OR ทำให้ทั้งจำนวนแพตเทิร์นและเวลาค้นหาเพิ่มขึ้นพร้อมกัน
  • แทนที่จะหาอัลกอริทึมทั่วไปที่ดีที่สุด จึงรันอัลกอริทึมง่าย ๆ ทั้งสามแบบ แล้วเลือกแพตเทิร์นค้นหาที่สั้นที่สุด
    • วิธีรวมบน→ล่าง
    • วิธีรวมซ้าย→ขวา
    • วิธี RLE รายแถว
  • จำนวนครั้งที่ถูกเลือกมีดังนี้
    • วิธีเดิมแบบรวมบน→ล่าง: 1,110 ครั้ง
    • วิธีรวมซ้าย→ขวา: 2,239 ครั้ง
    • RLE แบบแถวเดี่ยว: 3,300 ครั้ง
  • แม้ RLE จะถูกเลือกบ่อยที่สุด แต่ในกรณีแย่มาก ๆ มันอาจแย่มาก จึงหลีกเลี่ยงการใช้เพียงวิธีเดียว

เปลี่ยนเฟรมภายใน Vim

  • หน้าต่างตรงกลางด้านบนของ Vim ใช้เป็น ไฟล์ช่องว่าง ขนาด 90 บรรทัด x 120 คอลัมน์
    • เนื่องจากค้นหาตามแถวและคอลัมน์ จึงไม่จำเป็นต้องมีอักขระจริง
  • ด้านซ้ายและขวาใช้บัฟเฟอร์ว่างเพื่อจัดภาพให้อยู่กึ่งกลาง
  • หน้าต่างด้านล่างเก็บแพตเทิร์นค้นหาประมาณ 6,500 รายการไว้ทีละบรรทัด
  • มาโครจะอ่านแพตเทิร์นค้นหาจากบรรทัดปัจจุบัน ใส่ลงใน search register แล้วเลื่อนไปบรรทัดถัดไป

  • มาโครที่ใช้

    • มาโครมีรูปแบบ "ay$:let @/=@a^M+
    • การทำงานมีดังนี้
    • "a: ใช้รีจิสเตอร์ a
    • y$: คัดลอกตั้งแต่ตำแหน่งปัจจุบันไปจนจบบรรทัด
    • :let @/=@a: ตั้งค่า search register / ให้เป็นเนื้อหาของรีจิสเตอร์ a
    • ^M: รันคำสั่ง
    • +: ย้ายไปต้นบรรทัดถัดไป
    • ถ้าบันทึกมาโครนี้ไว้ในรีจิสเตอร์ q ก็สามารถใช้ 1500@q เพื่อเปลี่ยน 1,500 เฟรมได้เร็วที่สุดเท่าที่ทำได้
    • หากวางคำค้นหายาว ๆ ลงในช่องค้นหาโดยตรง เช่น /^Ra^M ช่องค้นหาจะขยายตามคิวรีที่ยาวหลายพันตัวอักษร ทำให้เกิดการกะพริบและอัตราเฟรมตก
    • การตั้งค่า search register โดยตรงด้วย let @/=@a ช่วยหลีกเลี่ยงปัญหานี้ได้

ข้อจำกัดและโค้ดที่เผยแพร่

  • เนื่องจากใช้ความสามารถค้นหาตามแถวและคอลัมน์ของ Vim จึงอาจมีข้อโต้แย้งว่าไม่ได้ประกอบด้วย regular expression แบบดั้งเดิมล้วน ๆ
  • ไม่มีการจัดการเพื่อรักษาอัตราเฟรมให้คงที่
    • ตลอดทั้งวิดีโอ อัตราเฟรมมีแกว่งอยู่บ้าง
  • ถึงอย่างนั้น ก็ยังได้ผลลัพธ์ที่ใกล้เคียงกับวิธีทั่วไปสำหรับเล่นวิดีโอภายใน Vim ด้วยคำค้นหาเพียงอย่างเดียว
  • โค้ดยังไม่ได้จัดระเบียบ แต่สามารถดูได้ที่ repository vim-badapple

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2025-01-13
ความคิดเห็นบน Hacker News

  • ถ้าเป็น nolen ก็นึกอยู่แล้วว่าต้องรู้วิธีทำอะไรให้ ใหญ่ขึ้น 1000 เท่า ได้ :))) เมื่อก่อนเคยลองเทคนิคคล้าย ๆ กัน แต่ทำแยกกัน และไม่เคยทำเสร็จภายในวันเดียวเลย ถ้าสนใจ:
    Bad Matrix (พิมพ์บล็อกลงเทอร์มินัลด้วย tput): https://www.evalapply.org/posts/bad-matrix/
    Animating Text Art in Javascript (พิมพ์ข้อความลงบนกริดคงที่แล้วทำแอนิเมชันเหมือน flipbook): https://www.evalapply.org/posts/animate-text-art-javascript/...
    oxo (ฟอร์แมตและพิมพ์กระดานทิคแทคโทลงเทอร์มินัล แล้วใช้ regex จับคู่ผลชนะ/แพ้/เสมอ): https://github.com/adityaathalye/oxo/blob/7681e75edaeec5aa1f...
    ถึงอย่างนั้น Bad Apple อันนั้นก็ยังสุดยอดที่สุด

  • เดโมเทคนิคที่ทำให้ผมติด Bad Apple จริง ๆ คือเวอร์ชันที่ รันบน NES
    https://somethingnerdy.com/downloads/
    วิดีโอที่ผมรันบน Everdrive อยู่ตรงนี้
    https://inversethought.com/jordi/video/badapple.mp4
    เสียงก็ออกมาครบสมบูรณ์ด้วย ข้อมูลมีขนาดประมาณ 1GB และนี่ทำบนระบบที่เกมทั่วไปมีขนาดไม่เกินไม่กี่ร้อย KB และ CPU มีแค่ รีจิสเตอร์ 8 บิต 3 ตัว สำหรับการคำนวณ

    • เจ๋งมาก จากมุมมองคนที่เคยลองพัฒนา NES มาบ้าง คงไม่ง่ายเลยที่จะทำให้ประสิทธิภาพกราฟิกพอไหว ปกติแค่มีสไปรต์ไม่กี่ตัวในหนึ่งบรรทัด NES ก็เริ่ม “ละลาย” สไปรต์แล้ว ไม่แน่ใจว่าศัพท์ที่ถูกต้องคืออะไร
      สงสัยว่าเขาใช้ background tile map แทนสไปรต์หรือเปล่า ถ้าใช่ ในแง่แบนด์วิดท์กราฟิกก็น่าประทับใจมากเหมือนกัน
      เห็นเขียนว่า “อัตราการเล่นเสียงทั้งหมด (44.2kHz)” เสียงคมชัดขนาดนั้นก็น่าทึ่ง สงสัยว่าเป็นฟีเจอร์ที่ตลับช่วยขยายให้หรือเปล่า เท่าที่จำได้ ช่อง PCM ของ NES ไปไม่ถึงบิตเรตนั้นเลย และขนาด sample ก็น่าจะเป็น 8 บิต
    • ถ้าชอบจุดไหนเป็นพิเศษ คุณอาจชอบ Bad Apple แบบคล้ายกันที่ทำบน NES เช่นกัน ความยากเพิ่มเติมคือรันผ่าน ACE ของ Super Mario Bros. และสตรีมข้อมูลทั้งหมดผ่านคอนโทรลเลอร์
      https://www.youtube.com/watch?v=lfG8DbxFibY
      มีวิดีโออธิบายที่ทำคู่กันด้วย
      https://www.youtube.com/watch?v=Wa0u1CjGtEQ
    • เจ๋งจริง ๆ ถ้ามี บทความสรุป เกี่ยวกับงานนี้ อยากอ่านมาก

  • ส่วนที่ทำให้ Vim macro “เล่นซ้ำได้” โดยย้ายไปบรรทัดถัดไปตอนท้าย จริง ๆ แล้วสามารถใช้คำสั่งด้านล่างเพื่อรันแมโคร หนึ่งครั้งต่อแต่ละบรรทัด ได้ด้วย
    :%norm @q

    • โห วันนี้ได้เรียนรู้เลย แปลกใจเหมือนกันที่ไม่รู้ทริกนี้
      เมื่อก่อนตอนเล่น Vim golf ปกติจะทำให้ macro เป็นแบบ recursive คืออัด macro แล้วปิดท้ายด้วย +@q หมายถึงย้ายไปบรรทัดถัดไปแล้วรัน macro อีกครั้ง แบบนั้นพอรัน macro ครั้งเดียวก็จะไล่ครบทุกบรรทัด
      ในแง่จำนวนคีย์ที่กดถือว่ามีประสิทธิภาพมาก แต่ในทางปฏิบัติค่อนข้างคิดยากและไม่ค่อยติดมือ เลยไม่ได้ใช้บ่อยนัก ถึงอย่างนั้นก็เป็นเทคนิคสนุก ๆ สำหรับการ golf

  • เดือนที่แล้ว Govee Curtain Lights อันนี้ลดราคาอยู่
    https://us.govee.com/products/govee-curtain-lights
    เข้าใจว่าสามารถอัปโหลด GIF แอนิเมชันขึ้นไปได้ ผมเลยเพิ่มงานทำ GIF “Bad Apple” ลงในบอร์ดคัมบังแล้ว แต่ยังไม่รู้ว่าหน่วยความจำของอุปกรณ์มีเท่าไร และจะรันได้ดีแค่ไหน
    บางครั้งฉากที่ Remmy Scarlet กางปีกก็ยังทำให้ขนลุกอยู่เลย

    • ผมลองทำแบบนี้กับไฟ Twinkly แล้ว แต่น่าเสียดายที่หน่วยความจำฝั่งไฟไม่พอ เลยรันได้ไม่เกิน ไม่กี่วินาที
    • ผมมี GIF Bad Apple ความละเอียด 64x32 อยู่ ขนาด ต่ำกว่า 1MB นิดหน่อย
      ได้ https://ezgif.com/ ช่วยไว้เยอะมาก

  • Bad Apple ดูไม่เบื่อเลย เป็นของที่ดีที่สุดบนอินเทอร์เน็ต และแทบทุกครั้งที่ดู ก็รู้สึกอิจฉานิด ๆ ว่าทำไมผมไม่นึกไอเดียนั้นได้ก่อน
    ผมชอบ การทำเชิงอรรถ ของบล็อกนี้มากด้วย คิดว่าน่าจะเอาไปใช้

    • เชิงอรรถนั้นเอามาจากเว็บของ Jake เพื่อนผู้มีพรสวรรค์ (https://jakelazaroff.com/) คุณอาจเคยเห็นงานของเขาที่นี่มาก่อน
      บนหน้าจอใหญ่จะแสดงเป็น sidenote ส่วนบนหน้าจอเล็กจะเปลี่ยนเป็นเชิงอรรถแบบ inline ที่คลิกแล้วขยายได้ เอาไปใช้ได้ตามสบาย

  • ในปัญหาการทำให้จำนวนสี่เหลี่ยมผืนผ้าน้อยที่สุด ปัญหาตรงนี้ดูต่างจากที่คุยกันใน StackOverflow เธรดบน SO พูดถึง การแบ่งเป็นสี่เหลี่ยมผืนผ้าที่ไม่ทับซ้อนกัน แต่โปรเจกต์ Vim นี้อนุญาตให้ทับซ้อนกันได้
    ดังนั้นปัญหาการหาคำตอบที่ดีที่สุดอาจง่ายกว่ามากก็ได้

    • จากมุมมองอัลกอริทึม จริง ๆ แล้วตรงกันข้าม ปัญหา minimum cover ที่อนุญาตให้ทับซ้อนกันได้เป็น NP-hard ส่วนปัญหา minimum partition ที่ไม่อนุญาตให้ทับซ้อนกันมีอัลกอริทึมเวลา polynomial ดูบทความปี 1984 ของ Franzblau และ Kleitman “An Algorithm for Covering Polygons with Rectangles”: https://core.ac.uk/download/pdf/82333912.pdf
      แน่นอนว่านี่เป็นแค่เกร็ดเชิงวิชาการ และไม่ได้แปลว่าฝั่งหนึ่งจะง่ายกว่าในทางปฏิบัติจริง ๆ ตอนทำโปรเจกต์ยามบ่ายให้รันได้
    • ชี้ประเด็นได้ดี ใช่เลย ผมพลาดไปสนิทว่า สี่เหลี่ยมผืนผ้าสามารถทับซ้อนกันได้ โปรเจกต์นี้คงจบแถวนี้ และผมก็ค่อนข้างพอใจกับวิธีแก้ปัจจุบัน แต่ก็เห็นด้วยว่าจุดนี้น่าจะทำให้ปัญหาง่ายลงมาก

  • ตัวสร้างคำตอบผู้สมัครแบบขนาน เป็นไอเดียที่ดีจริง ๆ แต่ทุกครั้งกว่าจะตระหนักได้ว่าไม่จำเป็นต้องสร้างอัลกอริทึมที่แข็งแกร่งที่สุดก็ใช้เวลานาน เพราะมักคิดว่าถ้าแก้อีกนิดก็น่าจะได้วิธีที่ใช้ได้กับทุกกรณีแล้ว

    • น่าจะเป็นหนึ่งในเทคนิคที่ผมชอบที่สุดในการทำ prototype ให้เร็วพอ ใช้ได้ทีไรก็สนุกทุกครั้ง
      แต่ก็เห็นด้วยว่ามันยากจริง ๆ ที่จะถอยออกมาหนึ่งก้าวแล้วนึกได้ว่าเราใช้วิธีนี้แทนการเขียนของที่ “สมบูรณ์แบบ” ได้

  • ค่อนข้างเจ๋ง ความคิดสร้างสรรค์ดี เกมต้นทางก็ถือว่าดีทีเดียว และ bullet hell ก็ดูสะกดจิตมาก

  • คนที่รัน Doom หรือ Bad Apple ในรูปแบบที่คาดไม่ถึงนี่สุดยอดจริง ๆ
    มีตัวอย่างน่าสนใจอย่างการรัน Doom บนที่ตรวจครรภ์ด้วย

    • อันนั้นผมคงเห็นด้วยแบบเต็มที่ไม่ได้ จริง ๆ แล้วมันใกล้เคียงกับการใส่ ไมโครคอนโทรลเลอร์ ตามใจชอบเข้าไปในเปลือกที่ตรวจครรภ์แล้วรัน Doom มากกว่า

  • นึกถึงตอนดูฟุตบอลโลกปี 2006 ที่ที่ทำงาน ผม ssh เข้าเซิร์ฟเวอร์ที่บ้านแล้วดู การแข่งขันในเทอร์มินัล ได้
    แบนด์วิดท์ไม่พอจะดูด้วยวิธีอื่น