การสร้าง Raycaster ใน Bash

 (github.com/izabera)
2 คะแนน โดย GN⁺ 2024-12-22 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • เป็นเดโม pseudo-3D บนเทอร์มินัลที่เป็น raycaster ที่สร้างด้วย Bash หมุนและเคลื่อนที่ด้วยปุ่มลูกศร และกด q เพื่อออก
  • การพัฒนาโดยรวมเป็นการพอร์ต บทสอน raycasting ของ Lode Vandevenne และคณิตศาสตร์ทั้งหมดจัดการด้วยการคำนวณจำนวนเต็มที่สเกล 64K โดยไม่ใช้เลขทศนิยม
  • ข้อจำกัดที่ใหญ่ที่สุดคือ ประสิทธิภาพของ Bash เพราะถ้ารันคำสั่งต่อพิกเซล หรือเก็บสถานะหน้าจอไว้เป็นอาร์เรย์/สตริง ก็แสดงผลให้ทันเวลาต่อเฟรมได้ยาก
  • การแสดงผลบนเทอร์มินัลใช้ Unicode half block และสี foreground/background แบบ 24 บิตเพื่อเพิ่มความละเอียดแนวตั้งได้เสมือนเป็นสองเท่า แต่มีข้อจำกัดว่าต้องรู้สีของพิกเซลข้างเคียงไปพร้อมกัน
  • ในโรดแมปปัจจุบัน งานอย่าง fluid movement, decent framerate, parallel rendering, kitty keyboard protocol และต้นแบบแรกเริ่มของ sound ทำเสร็จแล้ว ส่วน textures, sprites, enemies, particles, multiplayer ฯลฯ ยังไม่เสร็จ

Raycaster บนเทอร์มินัลที่สร้างด้วย Bash

  • โปรเจกต์นี้คือ raycaster ที่ทำงานใน Bash และเรนเดอร์ภาพ pseudo-3D ภายในเทอร์มินัล
  • ควบคุมด้วยปุ่มลูกศรเพื่อหมุนและเคลื่อนที่ และกด q เพื่อออก
  • ดูภาพหน้าจอและวิดีโอเพิ่มเติมได้ที่ อัลบั้ม Imgur
  • การพัฒนาโดยรวมเป็นการพอร์ต บทสอน raycasting ของ Lode Vandevenne

ข้อจำกัดที่ทำให้การพัฒนายาก

  • ปัญหาใหญ่ที่สุดคือ Bash ช้า
    • ผู้เขียนระบุว่าแม้ต้องรันเพียงคำสั่งเดียวต่อหนึ่งพิกเซล ก็ยังยากจะได้อัตราเฟรมที่ acceptable
    • แม้จะเก็บสถานะหน้าจอไว้เป็นอาร์เรย์สี การเข้าถึงสมาชิกอาร์เรย์แบบสุ่มก็ยังเป็นเวลาเชิงเส้น จึงเป็นปัญหา
    • แม้จะเก็บสถานะหน้าจอไว้เป็นสตริงยาวเพียงเส้นเดียว การเข้าถึงอักขระลำดับที่ n ก็ยังเป็นเวลาเชิงเส้นแม้ตั้ง LANG=C ดังนั้นแค่อ่านเพื่อดัมป์ลงหน้าจอก็อาจนานเกินกว่าหนึ่งเฟรมได้
  • Bash ไม่รองรับเลขทศนิยม และไม่มีทางเข้าถึงไลบรารีฟังก์ชันคณิตศาสตร์
    • คณิตศาสตร์ทั้งหมดจึงจัดการด้วยจำนวนเต็ม
    • ค่าจำนวนเต็มถูกขยายสเกลเป็น 64K เพื่อใช้คำนวณ
  • ถ้าใช้หนึ่งตัวอักษรบนเทอร์มินัลแทนหนึ่งพิกเซล ภาพจะดูไม่ดี จึงใช้ Unicode half block
    • กำหนดสี foreground และ background ต่างกันเพื่อเพิ่มความละเอียดแนวตั้งได้เสมือนเป็นสองเท่า
    • ไม่มีวิธีอัปเดตเฉพาะสีใดสีหนึ่งจากสองสีภายในหนึ่งเซลล์
    • ไม่มีวิธี query สีของเซลล์ปัจจุบัน และใน Bash การ query แบบนั้นก็ช้าเกินไปอยู่ดี
    • ดังนั้นทุกครั้งที่จะเขียนพิกเซล จึงต้องรู้สีของพิกเซลข้างเคียงด้วย

ปัญหาเรื่องเทอร์มินัลและ I/O

  • การรีเฟรชทั้งเทอร์มินัลในครั้งเดียวด้วยภาษาอย่าง Bash ที่ช้า ไม่ใช่เรื่องง่าย
  • เทอร์มินัลส่วนใหญ่ไม่ได้ออกแบบมาสำหรับวิดีโอเกม จึงไม่สามารถทดสอบสถานะของปุ่มที่กำลังกดอยู่ได้
    • ปกติจะได้เพียงอินพุตจากปุ่มเดี่ยวที่กำลังกดค้างอยู่
    • การทำ input repeat ถูก debounce ค่อนข้างช้า และมีขีดจำกัดของอินพุตต่อเนื่องต่ำ จนอาจได้เพียงราว 5–6 ตัวอักษรต่อวินาที
    • การรับหลายปุ่มพร้อมกันที่ไม่ใช่ modifier ก็ทำได้ยาก
    • ผู้เขียนระบุว่า kitty keyboard protocol ช่วยแก้ปัญหานี้
  • การเติมสีเต็มเทอร์มินัลต้องใช้ข้อมูลจำนวนมาก
    • ที่ขนาดฟอนต์ปกติของผู้เขียน จะเกิด I/O ราว 10MB ต่อวินาที
  • Bash จะไม่ใช้ syscall เดียวเมื่อพิมพ์สตริงที่มีตัวขึ้นบรรทัดใหม่หลายตัว
    • โปรเจกต์นี้จึงไม่พิมพ์ \n แต่ย้ายเคอร์เซอร์ด้วยวิธีอื่นแทน

FAQ และเงื่อนไขการรัน

  • ถ้าปรับขนาดหน้าต่างแล้วภาพพัง กะพริบมาก หรือดูไม่ดีในบางเทอร์มินัล ผู้เขียนขอให้เปิด issue
  • ถ้า CPU ร้อนมากหรือคอมพิวเตอร์เก่าทำงานช้าลง แนะนำให้ลดความละเอียด หรือตั้งตัวแปรแวดล้อม FPS ให้ต่ำกว่า 30
    • เป็นที่ทราบกันว่า Microsoft Defender ทำให้ประสิทธิภาพลดลงมาก จึงแนะนำให้ปิด
  • ผู้เขียนตอบว่า ต่ำกว่า Bash 5.2 ใช้งานไม่ได้
  • โค้ดนี้ไม่ได้เป็น Bash ล้วนทั้งหมด
    • ตอนเริ่มจะเรียก stty หนึ่งครั้งเพื่อปิด echo
    • ตอนจบจะเรียก stty หนึ่งครั้งเพื่อเปิด echo กลับ
    • หลังจบการทำงาน สถิติบางส่วนจะเก็บด้วยเครื่องมืออื่น

สถานะโรดแมป

  • รายการที่เสร็จแล้ว

    • semi-accurate pseudo 3d

      • fluid movement
      • decent framerate
      • parallel rendering
      • 24 bit colours
      • kitty keyboard protocol
      • framerate-independent speed
      • sound แต่ยังเป็นเพียงต้นแบบระยะเริ่มต้นมาก
      • dynamic wall colours
      • dynamic map ซึ่งตอนนี้ยังไม่มีอีเวนต์มาเปลี่ยน แต่ในทางเทคนิคถือว่าเป็นแบบไดนามิก
      • basic animations effects for walls
      • basic on-screen minimap
      • รายการที่ยังไม่เสร็จ

    • mouse support

      • textures
      • sprites
      • objects/enemies
      • particles
      • better perf
      • multiplayer

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

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

 
GN⁺ 2024-12-22
ความคิดเห็นจาก Hacker News
  • อันนี้ดีมากเลย ก่อนหน้านี้สงสัยว่ามันวาดภาพได้อย่างไรโดยไม่ต้อง echo ทีละพิกเซล วิธีที่ใช้ฉลาดมาก
    เพราะเกมนี้ไม่ใช่ 3D “จริง ๆ” จึงต้อง raycast แค่ครั้งเดียวต่อหนึ่งคอลัมน์ แล้ววาดเพียงไม่กี่บรรทัดที่แทนท้องฟ้า หญ้า และวัตถุจริง
    จากนั้นก็พิมพ์สตริงไปยังเทอร์มินัลด้วยการ ทำซ้ำสตริง ในรูปแบบ “วาดพิกเซลนี้แล้วเลื่อนลงหนึ่งช่อง” ตามจำนวนครั้งที่ต้องการ
    ไม่ได้ทำสำหรับ Bash แต่ฉันเคยคิดจะลองทำ voxel rendering engine ในสภาพแวดล้อมอื่นที่ทรัพยากรคำนวณจำกัด และดูเหมือนที่นี่จะมีอะไรให้นำไปใช้ได้แน่นอน
    • ไฟล์ VoxelCanvas.js ก็น่าสนใจเหมือนกัน เป็นไฟล์ JavaScript และใช้แนวคิด raycasting แบบเดียวกัน: https://github.com/EngineersNeedArt/Mooncraft2000
  • ถ้าเคยสงสัยว่ามี raycaster ที่เขียนด้วย MS Batch ไหม ก็มีอันนี้ด้วย: https://github.com/nTh0rn/batch-raycaster
  • น่าเสียดายที่ stty ต้องมีการ fork โปรเจ็กต์ถัดไปอาจจะเป็นการใช้ Bash กับ rowhammer เพื่อเรียก ioctl ที่ต้องการโดยไม่ต้อง fork ก็ได้
  • ไม่เคยคิดเลยว่าจะทำอะไรแบบนี้ด้วย Bash ได้ เคยคิดว่าตัวเองใช้ Bash ได้ค่อนข้างระดับสูงแล้ว แต่นี่น่าทึ่งจริง ๆ
    ฉันไม่มีความรู้คณิตศาสตร์พอจะเข้าใจ implementation นี้ แต่แค่ดูก็สนุกแล้ว
  • สคริปต์ Bash ของฉันใช้ไป 300 บรรทัดกับการทำ parsing ตัวเลือกบรรทัดคำสั่ง สารพัด แต่จริง ๆ แล้วน่าจะแสดงเกมแบบนี้แทนได้เหมือนกัน :-P
  • ยังไม่เข้าใจอยู่ดีว่าทำไมเรายังติดอยู่กับเชลล์ที่ช้าจนน่าเหลือเชื่อแบบนี้ มันดูเหมือนความบ้าคลั่งล้วน ๆ
    ฉันเข้าใจนะว่าแอปบางตัวต้องการพฤติกรรมประหลาดทุกแบบของ vt100 แต่แอปสัก 90% คงแค่เขียนไปที่ standard output กับ standard error เท่านั้น
    น่าจะมีวิธีส่งข้อความขึ้นจอให้เร็วขึ้นกว่านี้ แล้วให้ที่เหลืออีก 10% อยู่ใน โหมดเข้ากันได้ ได้ไม่ใช่หรือ
    • เชลล์ช้า และ Bash ก็ช้าเป็นพิเศษ แต่ไม่ค่อยเข้าใจว่าประเด็นหลังจากนั้นเชื่อมโยงกันอย่างไร เชลล์ไม่ได้เกี่ยวข้องกับการตีความ terminal escape sequence เลย และเทอร์มินัลสมัยใหม่ก็เร็วพอสมควร
      แม้ในเทอร์มินัลกว้าง 350 คอลัมน์ก็ยังเรนเดอร์แอนิเมชันได้ และเมื่อคำนึงถึงข้อจำกัดแล้วก็ลื่นมาก
      แถมสมมติฐานของโพสต์นี้ก็คือ Bash ไม่ใช่ภาษาที่เหมาะกับ raycasting อยู่แล้ว คล้ายกับการเขียน bubble sort ด้วย CSS
      เรื่อง “ให้ 10% ที่เหลืออยู่ในโหมดเข้ากันได้” ก็ไม่มีอะไรมาห้าม แค่ตรวจสอบว่าสตริงมีแต่ตัวอักษรธรรมดาหรือไม่แล้วใช้ทางลัดที่เร็วกว่าได้
      ปัญหาคือในการเรนเดอร์ข้อความด้วยซอฟต์แวร์นั้น แทบไม่มีทางลัดที่เร็วจริง เพราะยังต้องจัดการเรื่องอย่าง ligature อยู่ดี
  • “bash ช้า”
    นี่จึงเป็นหนึ่งในเหตุผลที่ฉันไม่ใช้ Bash สำหรับงานสคริปต์ และไม่ใช้แบบโต้ตอบด้วย
    บาง Linux distribution ยอดนิยมก็หลีกเลี่ยง Bash ในฐานะ เชลล์สำหรับสคริปต์ เช่นกัน
  • เอาอันนี้ไปรวมกับ implementation ps แบบไม่ต้อง fork ของผู้เขียน ก็น่าจะได้ psDoom แบบไม่ต้อง fork ที่เกือบใช้งานได้
    พูดเล่นนอกเรื่องไปหน่อย แต่มันเจ๋งจริง ๆ
  • แน่นอนว่าต้องกล่าวถึง raycaster ที่เขียนด้วย awk เมื่อ 9 ปีก่อนอย่างสมเกียรติด้วย: https://github.com/TheMozg/awk-raycaster/tree/master