Doom แบบไม่ใช่ยูคลิด: จะเกิดอะไรขึ้นกับเกมเมื่อ pi ไม่ใช่ 3.14159 (2022) [วิดีโอ]

 (media.ccc.de)
3 คะแนน โดย GN⁺ 2024-05-18 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • เริ่มจาก ค่า pi ที่ผิด ในซอร์สโค้ดของ Doom แล้วสำรวจว่าเมื่อจงใจทำให้ค่าคงที่ทางคณิตศาสตร์คลาดเคลื่อนมากขึ้น การเรนเดอร์และความรู้สึกต่อพื้นที่ในเกมยิงมุมมองบุคคลที่หนึ่งจะเปลี่ยนไปอย่างไร
  • กราฟิกเกมไม่ได้พึ่งพาแค่ pi แต่ยังพึ่งพา ตรีโกณมิติ และเทคนิคทางคณิตศาสตร์หลายอย่าง ดังนั้นการเปลี่ยนแปลงทางคณิตศาสตร์เพียงเล็กน้อยก็อาจส่งผลต่อวิธีที่เรามองโลกและเคลื่อนที่ในโลกนั้นได้
  • Doom เป็นเกม FPS คลาสสิกที่ เปิดเผยซอร์สโค้ดภายใต้ GPL ในปี 1999 จึงสามารถนำมาใช้เป็นเป้าหมายทดลองสำหรับการเปลี่ยนค่า pi รวมถึงฟังก์ชันตรีโกณมิติและค่าคงที่ต่าง ๆ ได้
  • การทดลองยังกล่าวถึง เทคนิคการปรับแต่งประสิทธิภาพ ที่ทำให้ Doom ทำงานได้ดีบนฮาร์ดแวร์ในยุคนั้น และให้คำแนะนำสำหรับการคอมไพล์เวอร์ชันที่ใช้คณิตศาสตร์ผิดพลาดด้วยตนเอง
  • สำรวจว่าเรขาคณิตแบบไม่ใช่ยูคลิดจะสร้างประสบการณ์พื้นที่แบบใหม่ภายในเกมได้หรือไม่ พร้อมเชื่อมโยงไปยังเกมอื่นที่ใช้ค่า pi ผิด และคลังซอร์สโค้ดแบบเปิดเผยด้วย

การจงใจทำให้คณิตศาสตร์ของ Doom คลาดเคลื่อน

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

ซอร์สของ Doom และขอบเขตการทดลอง

  • Doom เป็น เกมยิงมุมมองบุคคลที่หนึ่ง คลาสสิกที่เป็นที่รู้จักกันดี
  • ซอร์สโค้ดของ Doom ถูกเปิดเผยภายใต้ GPL ในปี 1999
  • สิ่งที่ทดลองรวมถึง
    • เปลี่ยนค่า pi ให้เป็นค่าที่ผิดมากขึ้น
    • เปลี่ยน ฟังก์ชันตรีโกณมิติ อื่น ๆ ให้เป็นค่าที่ผิด
    • เปลี่ยนค่าคงที่ทางคณิตศาสตร์ที่เกี่ยวข้องให้ไม่แม่นยำ

ความเป็นไปได้ของเกมแบบไม่ใช่ยูคลิด

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

การปรับแต่งประสิทธิภาพและการรันด้วยตนเอง

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

แหล่งข้อมูลที่เกี่ยวข้อง

  • มีลิงก์ไปยังเกมอื่นที่ใช้ค่า pi ผิด และ คลังซอร์สโค้ดแบบเปิดเผย ด้วย
  • วิดีโอการบรรยายให้บริการเป็นคอนเทนต์ MCH2022 บน media.ccc.de

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

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

 
GN⁺ 2024-05-18
ความคิดเห็นจาก Hacker News

  • ในเกมคลาสสิก Duke Nukem 3D ก็มีตัวอย่างแบบนี้อยู่เหมือนกัน เป็นด่าน ‘Lunatic Fringe’ ที่ Richard “Levelord” Gray สร้างขึ้น
    https://dukenukem.fandom.com/wiki/Lunatic_Fringe
    ด่านนี้มีทางเดินวงกลมด้านนอก ซึ่งวนครบสองรอบโดยไม่ตัดกัน และใช้ความสามารถของ Build engine ที่ล้ำสมัยในตอนนั้นในการแบ่งพื้นที่ด้วยการเชื่อมห้องเข้าด้วยกัน ความสามารถนั้นยังถูกใช้กับเทคนิค ‘ห้องซ้อนห้อง’ ด้วย
    เล่นแบบมัลติเพลเยอร์แล้วสนุก และภาพลวงตาก็ยังคงความสมจริงได้ค่อนข้างดี ถ้าจำไม่ผิด ห้องตรงกลางมีทางเข้าออก 4 ทาง แต่ทุกครั้งที่เดินวนด้านนอกหนึ่งรอบจะเจอแค่ 2 ทางเท่านั้น
    ตอนทดลองเอนจิน ผมเคยลองทำด่านเล่น ๆ ด้วยเทคนิคนี้เพื่อไขปริศนา “เชื่อมบ้าน 3 หลังกับสาธารณูปโภค 3 อย่างโดยไม่ให้เส้นตัดกัน” ด้วย

    • ไม่แน่ใจว่า Duke Nukem เป็น “ตัวอย่างของสิ่งนี้” ในความหมายไหน ฝั่ง Duke เป็นการทำงานของโปรแกรมที่สอดคล้องกันภายใน ส่วนอันนี้ใกล้เคียงกับ ข้อผิดพลาดแบบสุ่ม ที่เกิดจากการแก้ซอร์สโค้ดตามอำเภอใจมากกว่า
      Duke อาจเป็นอะไรสักอย่างคล้ายเรขาคณิตนอกแบบยุคลิด แต่การเปลี่ยนค่า pi ใน Doom นี้ไม่ค่อยเกี่ยวกับเรขาคณิต และดูใกล้กับ “ใส่ขยะเข้าไปก็ได้ขยะออกมา” มากกว่า
    • ถ้าพูดถึง “เทคนิค ‘ห้องซ้อนห้อง’ ที่ล้ำสมัยในตอนนั้น” Marathon ของ Bungie ในปี 1994 ก็ทำได้แล้ว และแสดงให้เห็นในแผนที่เดธแมตช์ 5-D Space[1]
      โดยพื้นฐานแล้ว มีแค่ Doom เท่านั้นที่พังเมื่อมีเซกเตอร์ซ้อนทับกัน
      [1] https://www.lhowon.org/level/marathon/30
    • นานมาแล้วผมเคยสร้างเอนจินเล็ก ๆ ที่มีฟีเจอร์แบบนี้ ตอนนั้นยังไม่รู้จัก Build engine และแทนที่จะแบ่งโลกเป็น เซกเตอร์นูน แล้วไล่ตามต้นไม้ BSP ก็อนุญาตให้มีลิงก์อิสระ หรือก็คือพอร์ทัล การเรนเดอร์ทำจากหน้าไปหลังและตัดที่ขอบพอร์ทัล
      ถ้าราสเตอร์ไรซ์ภายในรูปทรงนูนได้ ก็สามารถราสเตอร์ไรซ์โลกแบบเซกเตอร์-พอร์ทัลได้โดยทำเครื่องหมายพื้นผิวบางด้านเป็นพอร์ทัล ตั้งพื้นที่ที่ด้านนั้นจะมองเห็นเป็นคลิปปิงรีเจียนหรือสเตนซิลบัฟเฟอร์ แล้วใช้ทรานส์ฟอร์มที่เหมาะสมในข้อมูลพอร์ทัลกับ ID ของเซกเตอร์อีกฝั่งเพื่อเรนเดอร์เซกเตอร์ด้านหลัง
      การจัดการการชน ผ่านพอร์ทัลยากกว่าการเรนเดอร์สิ่งที่อยู่หลังพอร์ทัลมาก
    • ห้องซ้อนห้อง ที่เกม Build รุ่นหลัง ๆ ทำโดยทั่วไปไม่จำเป็นต้องให้เซกเตอร์ซ้อนทับกันแบบนี้ มันเป็นการต่อยอดจากวิธีทำให้น้ำที่ว่ายได้ โดยเอนจินเรนเดอร์เซกเตอร์อื่นแทนพื้นหรือเพดาน
      Lunatic Fringe เป็นตัวอย่างที่แสดงเรขาคณิตที่เป็นไปไม่ได้ใน Build แบบตรง ๆ แต่ในแผนที่ Duke3D มีเรขาคณิตที่ตัดกันอยู่มากกว่านั้นอีกมาก ใน Doom ไม่สามารถสร้างต้นไม้ BSP สำหรับโครงสร้างแบบนั้นได้ และผู้เล่นหรือมอนสเตอร์ก็เก็บตำแหน่งแค่พิกัด X/Y ดังนั้นจึงเป็นไปไม่ได้อยู่แล้ว
    • มีเกม VR ที่น่าสนใจชื่อ Tea For God อยู่ มันสร้างทางเดินและห้องใหม่ ๆ อย่างแยบยลทุกครั้งที่คุณเลี้ยวหัวมุมหรือนั่งลิฟต์ภายในพื้นที่เล่นจริง ทำให้เกิดภาพลวงตาว่าอยู่ในสถานที่ขนาดใหญ่ ทั้งที่ไม่ได้ออกจากห้องเดิมเลย ทำได้โดยไม่ใช้จอยสติ๊กหรือการเทเลพอร์ต

  • พอดีกำลังอ่านนิยายคลาสสิกของ Poul Anderson เรื่อง Operation Chaos อยู่
    https://en.wikipedia.org/wiki/Operation_Chaos_(novel)
    เรื่องอยู่ในโลกคู่ขนานที่เวทมนตร์มีอยู่จริงและพัฒนาอย่างรวดเร็วควบคู่กับวิทยาศาสตร์ เช่น Edwin Land ประดิษฐ์อุปกรณ์ที่ใช้โพลาไรเซชันเพื่อทำให้มนุษย์หมาป่าแปลงร่างได้โดยไม่ต้องมีแสงจันทร์
    ลูกของตัวเอกถูกลักพาตัวและพาไปนรก และพวกเขาได้ยินว่ากองทัพเคยพยายามสำรวจนรกเมื่อ 20 ปีก่อน แต่ทุกคนเสียสติไปหมด ศัตรูหลุดเบาะแสออกมาว่าเรขาคณิตของกาลอวกาศในนรกต่างจากของเรา จึงสามารถย้อนกลับไปยังขณะที่เด็กไปถึงและพากลับมาได้
    นักวิทยาศาสตร์ใช้แค่เบาะแสนั้นก็รู้ได้ว่าเรขาคณิตของนรกเป็น เรขาคณิตนอกแบบยุคลิด และคำนวณคาถาสำหรับเข้าไปอย่างปลอดภัย ทนอยู่ได้ และกลับออกมาได้ เพื่อหาทาง พวกเขาสวดภาวนาให้ได้รับความช่วยเหลือจากนักเรขาคณิตศตวรรษที่ 19 สองคน，其中หนึ่งเป็นนักบุญ

    • เรขาคณิตของกาลอวกาศในโลกเราก็ไม่ใช่แบบยุคลิด และกระทั่งไม่ใช่ เรขาคณิตรีมันน์ ด้วย Operation Chaos ดูจะวุ่นวายมากกว่าจะเป็นวิทยาศาสตร์
      ผลงานของ Poul Anderson ที่ผมเคยอ่าน เช่น High Crusade ที่ยอดเยี่ยม ก็เป็นแบบนั้น เขาชอบเดินหน้าลุยแบบดิบ ๆ โดยไม่ค่อยใส่ใจฉากหน้าทางวิทยาศาสตร์นัก
      ผลงานอีกเรื่องที่พูดถึงเรขาคณิตนอกแบบยุคลิดและผมจำได้ดีคือ Inverted World ของ Christopher Priest
    • อาจฟังดูซ้ำซาก และจริง ๆ ก็อาจเป็นอย่างนั้น แต่ทุกวันนี้ผมไม่รู้ว่าทำไม นิยายที่สร้างสรรค์ แบบนี้ถึงไม่ค่อยมีออกมา
    • รวมเรื่องสั้นยอดเยี่ยมของ Jack Vance เรื่อง Tales of the Dying Earth ก็น่าอ่าน มีทั้งเวทมนตร์/วิทยาศาสตร์และมิติของปีศาจ
    • ผมชอบ Operation Chaos แต่ภาคต่อที่ออกมาทีหลังมาก ๆ น่าผิดหวัง

  • John Carmack อาจจะจำหลักที่ 10 ของ pi ผิดก็ได้ แต่ทุกคนควรลองค้นหา 84,600 ใน codebase แล้วดูว่ามีใครพิมพ์จำนวนวินาทีในหนึ่งวันผิดหรือไม่
    เรื่องนี้พบได้บ่อยกว่าที่คิด และเป็นบทเรียนว่าควรพิมพ์ค่าคงที่ลงในโปรแกรมเอง หรือควรใช้ค่าที่มีอยู่แล้วใน standard library ของภาษาโปรแกรม

    • เป็นเรื่องจริงด้วย ดูเหมือนว่าแม้แต่โปรเจกต์ใหญ่ ๆ อย่าง MySQL หรือ Textmate ก็อาจมีข้อผิดพลาดนี้อยู่ใน codebase
      https://github.com/search?type=code&auto_enroll=true&q=84600
      https://github.com/mysql/mysql-server/blob/824e2b4064053f7da...
      https://github.com/textmate/textmate/blob/346b52b108b387462d...
    • เคยเสียเวลาน่าอายไปมากกับการดีบักว่าทำไม โค้ดรีเฟรชโทเค็น ที่ควรรันทุก 15 นาทีถึงไม่ทำงาน สุดท้ายพอพิมพ์ค่าตัวแปรทั้งหมดออกมาดูถึงพบว่ากำหนด 15 นาทีเป็น 15 * 60 * 60
    • พูดให้แม่นคือ มันคือจำนวนวินาทีของ “วันส่วนใหญ่”

  • ในความเป็นจริง กราฟิกและการเคลื่อนที่จะเริ่มแปลกไป แล้วสุดท้ายก็เล่นไม่ได้ เรียกสิ่งนี้ว่า Doom แบบ non-Euclidean คงไม่ค่อยตรงนัก น่าจะเรียกว่า “ผลลัพธ์จากการไปยุ่งกับค่าคงที่ของจักรวาล” มากกว่า
    ถ้าเป็น Doom แบบ non-Euclidean จริง ๆ ผมคาดหวังว่าจะหน้าตาแบบนี้: https://youtu.be/kEB11PQ9Eo8?si=0HNlpGFBii2AIK1n

    • ถ้าจะจู้จี้สักหน่อย วิดีโอนั้นก็ใช้คำว่า non-Euclidean ผิดเหมือนกัน ฝั่งคนทำ HyperRogue เคยทำวิดีโอหลายตัวที่แสดงเรขาคณิต non-Euclidean จริง ๆ
      https://youtu.be/yqUv2JO2BCs?si=AutaqS5unvT7cDjw
      พอดูเอฟเฟกต์เรขาคณิตแปลก ๆ ในวิดีโอ Doom อย่างเวลาขยับไปข้างหน้าแล้ววัตถุดูเหมือนเลื่อนไปด้านข้าง ก็พอจะบอกได้ว่าการเรียก Doom ตัวนี้ว่า non-Euclidean ก็มีเหตุผลอยู่บ้าง
    • นั่นก็ยังไม่ใช่ความหมายของ non-Euclidean อยู่ดี มันเป็นแค่โลก 3D ทั่วไปที่มี พอร์ทัล ในยุคนั้นเอนจินเกมยิงมุมมองบุคคลที่หนึ่งมักเอาห้องมาต่อกันผ่านช่องประตู หรือก็คือพอร์ทัล เพื่อใช้ตัดส่วนที่ถูกบังออก
      มันสามารถแสดงเรขาคณิตปกติได้ แต่เรขาคณิตไม่จำเป็นต้องสมเหตุสมผลในเชิงใด ๆ และอนุญาตให้เชื่อมห้องเข้าหากันแบบตามใจได้ด้วย ไม่ได้ตั้งใจจะจับผิด แต่เป็นความเข้าใจผิดที่พบได้บ่อย
      ถ้าสนใจ non-Euclidean จริง ๆ แนะนำงานของ ZenoRogue เช่น เกมง่าย ๆ ที่ใช้เรขาคณิต Nil[1], บอสไฟต์ขนาดใหญ่ใน roguelike โลก non-Euclidean[2], และความพิสดารทางเรขาคณิตโดยรวม[3] เป็นต้น หรือจะดูงานไหนของพวกเขาก็ได้
      [1] https://m.youtube.com/watch?v=gejRg_q70EA&pp=ygUJemVub3JvZ3V...
      [2] https://m.youtube.com/watch?v=jcnXI8IArRI&pp=ygUJemVub3JvZ3V...
      [3] https://m.youtube.com/watch?v=yqUv2JO2BCs&pp=ygUJemVub3JvZ3V...
    • แปลกใจที่ยังไม่มีใครพูดถึง Antichamber เป็นเกมที่ยอดเยี่ยมซึ่งเอาแนวคิดคล้าย ๆ กันมาสร้างเป็นปริศนาจริง ๆ
      คิดดูแล้วก็ผ่านมานานพอสมควร น่าจะกลับไปเล่นอีกครั้งแล้วยังสนุกอยู่
    • อันนี้ดูเหมือนพอร์ทัล เกมยิงมุมมองบุคคลที่หนึ่งสมัยนั้นโดยพื้นฐานแล้วเอาห้องมาต่อกันผ่านช่องประตู หรือก็คือ พอร์ทัล เพื่อทำการตัดส่วนที่ถูกบังออก
      การแสดงเรขาคณิตปกติไม่มีปัญหา แต่ไม่มีเงื่อนไขว่าเรขาคณิตต้องสมเหตุสมผลเสมอ และสามารถเชื่อมห้องเข้าหากันแบบตามใจได้
    • ผมก็คาดหวังแบบนั้นเป๊ะ ๆ นี่คือการทำ non-Euclidean อีกแบบหนึ่งที่มีไอเดียใหม่อื่น ๆ ใส่เข้ามาด้วย
      https://www.youtube.com/watch?v=tl40xidKF-4

  • Doom ไม่ใช่ simulation ดังนั้นการเปลี่ยนค่าคงที่เพียงตัวเดียวจึงไม่ได้เป็นตัวอย่างที่ดีของอะไรนัก
    มันใกล้เคียงกับการทำให้ routine บางส่วนพังมากกว่า และนั่นทำให้ผลลัพธ์จากการเปลี่ยนส่วนใหญ่เล่นไม่ได้

    • ไม่ค่อยเข้าใจว่าทำไมเรื่องนี้ถึงน่าสนใจ ถ้าเปลี่ยนค่าคงที่เป็นตัวเลขผิด ๆ ก็ย่อมเกิดพฤติกรรมแปลก ๆ หรือ error อยู่แล้ว แล้วมันจะเป็นอย่างอื่นได้ยังไง? พฤติกรรมแปลก ๆ ก็ไม่ได้ดูพิเศษอะไร ผมพลาดอะไรไปหรือเปล่า

  • ลองเอาซอร์สโค้ดของ console emulator ที่คุณชอบมาใส่ ข้อผิดพลาดแบบ floating-point แบบสุ่ม หรือกลับความหมายของ branch instruction บางตัวก็ได้ ยิ่งเกมเก่าเท่าไร ก็ยิ่งมีโอกาสที่ยังรันต่อได้สูง และยิ่งมีโอกาสที่จะดูเหมือนทริปหลอนแย่ ๆ มากขึ้น

    • นานมาแล้วเคยมีเครื่องมือสำหรับ N64 emulator ที่ทำแบบนี้ได้ ลองใช้แล้วก็สนุกอยู่พักหนึ่ง แต่ก็ crash บ่อยตามคาด
      เคยมีโปรเจกต์ glitch art ที่ทำลายบางช่วงของไฟล์ภาพและวิดีโอชื่อดังเพื่อสร้างสิ่งใหม่ด้วย อยากหาเจออีกทั้งสองอย่าง แต่หาไม่เจอแล้ว

  • Marathon 1 (1994) รองรับพื้นที่แบบนอกยุคลิด แต่ถูกใช้น้อยมาก ระหว่างเล่นเกมทั้งเกมที่ประกอบด้วยหลายเลเวลพร้อมแผนที่ จะมีพื้นที่ที่เป็นไปไม่ได้โผล่มาแค่ในหนึ่งหรือสองเลเวลเท่านั้น และเกมก็ไม่ได้เตือนหรือบอกว่ามีอะไรแบบนั้นเป็นไปได้
    ดังนั้นมันอาจเป็นตำแหน่งอีสเตอร์เอ้กที่ดีที่สุดที่ค้นพบในเกมก็ได้
    เจอวิดีโอสาธิตด้วย: https://www.reddit.com/r/Marathon/comments/vclu55/probably_n...

  • คำถามสุดท้ายคือ “ค่าสูงสุดของ pi ที่ยังเล่นได้และไม่แครชคือเท่าไร” เหตุผลที่เกิด segmentation fault เมื่อ pi เท่ากับ 4 น่าจะเป็นเพราะการเข้าถึง lookup table บางส่วนเลยท้ายตารางออกไป และถ้าเป็นเช่นนั้น ค่าสูงสุดที่ยังเล่นได้ก็น่าจะมากกว่า pi เองเพียงเล็กน้อยเท่านั้น

  • อยากให้วิดีโอนี้ลงลึกเรื่องกลไกของเกม และอธิบายว่าทำไม การเปลี่ยนค่า Pi ถึงทำให้เกิดปัญหาในลักษณะนั้นมากกว่านี้

  • สงสัยว่าในการทดลองนี้กับ Doom แบบ ray tracing ที่ถูกอ้างถึง ผลลัพธ์จะน่าสนใจกว่านี้ไหม ผลจากการแฮ็กค่าคงที่ในเทคนิค rasterization แทบจะเป็นไปตามที่คาดไว้ แต่ถ้าเป็น ray tracing อาจได้ผลลัพธ์ที่น่าสนใจกว่านั้น