เมืองในขวด – ระบบ Raycasting ขนาด 256 ไบต์

• City In A Bottle เป็นเดโม JavaScript ที่บรรจุเอนจิน raycasting และตัวสร้างเมืองไว้ใน HTML ขนาด 256 ไบต์
• การรันเริ่มต้นด้วยเพียง <canvas> และ onclick=setInterval(...) โดยวาดฉากใหม่ทุกเฟรมบนแคนวาสกว้าง 99 พิกเซล
• การเรนเดอร์ทำด้วยพีชคณิตพื้นฐานและ การดำเนินการระดับบิต แทนการใช้ฟังก์ชันตรีโกณมิติ และสร้างเงาโดยไล่ตามรังสีกล้องกับรังสีทิศทางแสงในแต่ละพิกเซล
• รูปทรงเมืองแบ่งความสูงอาคาร ถนน และพื้นที่ว่าง ด้วยพิกัด X, Y, Z และเงื่อนไขอย่าง X/9^Z/8, X%99, Z>32
• ความสว่างสุดท้ายผสมหมอกตามระยะ เงา และเท็กซ์เจอร์ (X&Y&Z)%3/Z เข้าไปในความกว้างของ fillRect ทำให้โค้ดที่เล็กสุดขั้วนี้สร้างได้ทั้งเมือง มุมมองเชิงลึก และพื้นผิว

---

โครงสร้างทั้งหมดใน HTML ขนาด 256 ไบต์

• เดโมนี้ไม่ได้ทำงานเป็นชิ้นส่วน JavaScript แต่เป็น โปรแกรม HTML ที่ถูกต้อง หนึ่งโปรแกรม

<canvas style=width:99% id=c onclick=setInterval('for(c.width=w=99,++t,i=6e3;i--;c.getContext`2d`.fillRect(i%w,i/w|0,1-d*Z/w+s,1))for(a=i%w/50-1,s=b=1-i/4e3,X=t,Y=Z=d=1;++Z<w&(Y<6-(32<Z&27<X%w&&X/9^Z/8)* 8%46||d|(s=(X&Y&Z)%3/Z,a=b=1,d=Z/w));Y-=b)X+=a',t=9)>

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

HTML และลูปการทำงาน

• HTML ประกอบด้วยแคนวาสหนึ่งตัวและอีเวนต์คลิกเท่านั้น

<canvas style=width:99% id=c onclick=setInterval('',t=9)>

• กำหนด id ของ canvas เป็น c เพื่อให้เข้าถึงจาก JavaScript ได้สั้นลง
• style=width:99% ไม่จำเป็น และแม้ไม่มีส่วนนี้ก็ยังทำงานได้
• เรียก setInterval ใน onclick เพื่อเริ่ม ลูปอัปเดต
  • กำหนดช่วงเวลาเป็น 9 มิลลิวินาที
  • ตัวแปรเวลา t ก็ถูกเริ่มค่าเป็น 9 ตรงนี้เพื่อประหยัดพื้นที่
• มี บั๊กเล็ก ๆ คือถ้าคลิกแคนวาสหลายครั้ง interval จะทำงานหลายชุดและทำให้ช้าลง

JavaScript ที่คลี่ให้อ่านง่ายขึ้น

• เพย์โหลด JavaScript ที่รันหลังคลิกมีขนาด 199 ไบต์

for(c.width=w=99,++t,i=6e3;i--;c.getContext`2d`.fillRect(i%w,i/w|0,1-d*Z/w+s,1))for(a=i%w/50-1,s=b=1-i/4e3,X=t,Y=Z=d=1;++Z<w&(Y<6-(32<Z&27<X%w&&X/9^Z/8)* 8%46||d|(s=(X&Y&Z)%3/Z,a=b=1,d=Z/w));Y-=b)X+=a

• หากใส่ช่องว่างและขึ้นบรรทัดใหม่ จะอ่านเป็นลำดับการทำงานได้ดังนี้

c.width = w = 99
++t
for (i = 6e3; i--;)
{
  a = i%w/50 - 1
  s = b = 1 - i/4e3
  X = t
  Y = Z = d = 1
  for(; ++Z<w &
    (Y < 6 - (32<Z & 27<X%w && X/9^Z/8)*8%46 ||
    d | (s = (X&Y&Z)%3/Z, a = b = 1, d = Z/w));)
  {
    X += a
    Y -= b
  }
  c.getContext`2d`.fillRect(i%w, i/w|0, 1 - d*Z/w + s, 1)
}

• c.width = w = 99 ล้างแคนวาสและตั้งค่าความกว้างเป็น 99 พิกเซล พร้อมเก็บค่าเดียวกันไว้ใน w เพื่อใช้ซ้ำ
• ความสูงเริ่มต้นของแคนวาสคือ 150 และพื้นที่ด้านล่างจากนั้นจะว่างเปล่า
• ++t เพิ่มค่าเวลาทุกเฟรมเพื่อทำให้ฉากเป็นแอนิเมชัน
• for (i = 6e3; i--;) เป็นลูปภายนอกที่กำหนดความสว่างรายพิกเซล

การคำนวณรังสีกล้อง

• แต่ละพิกเซลถูกประมวลผลเป็น รังสี หนึ่งเส้นที่ออกจากกล้อง
• องค์ประกอบแนวนอนถูกเก็บใน a

a = i % w / 50 - 1

• ใช้ i % w เพื่อหาตำแหน่งแนวนอนของพิกเซลปัจจุบัน หารด้วย 50 แล้วลบ 1 เพื่อปรับสเกลให้อยู่ราว ๆ ระหว่าง -1 ถึง 1
• องค์ประกอบแนวตั้งถูกเก็บใน b และค่าเดียวกันยังใส่ใน s สำหรับการเฟดฉากหลังด้วย

b = s = 1 - i / 4e3

• ลดขนาดโค้ดโดยใช้ i / 4e3 แทนการคำนวณอัตราส่วนแนวตั้งที่แม่นยำ
• การลดรูปนี้ทำให้เกิด ความเอียง ที่แทบสังเกตไม่เห็น แต่ช่วยประหยัดไบต์
• ค่า 4e3 ถูกเลือกเพื่อเลื่อนเส้นขอบฟ้าให้ต่ำกว่ากึ่งกลาง
• ตำแหน่งเริ่มต้นของกล้องใช้ค่าเวลา เพื่อสร้างฉากที่เคลื่อนที่ไปทางขวา

X = t
Y = Z = d = 1

• Y, Z และ d ที่ใช้กับหมอกตามระยะ ล้วนเริ่มค่าเป็น 1

การสร้างเมืองและการตรวจจับการชน

• ลูปภายในคือหัวใจของระบบ raycasting โดยเพิ่ม Z ไปข้างหน้าจนกว่าจะชนอะไรบางอย่าง

for(; ++Z<w &

• Z เพิ่มขึ้นจนกว่าจะน้อยกว่า w หรือก็คือ 99
• อาคาร ตรอก และพื้นที่ว่างฝั่งชายทะเลของเมืองถูกสร้างจากเงื่อนไขต่อไปนี้

Y < 6 - (32<Z & 27<X%w && X/9^Z/8)*8%46

• ตรวจว่ารังสีอยู่ต่ำกว่าความสูงของตำแหน่งนั้นหรือไม่ เพื่อพิจารณา การชน
• 6 - มีหน้าที่ลดผลลัพธ์ความสูงลงใต้กึ่งกลาง และกลับทิศให้พื้นอยู่ด้านล่าง
• เงื่อนไขในวงเล็บกำหนดรูปทรงของเมือง
  • 32<Z เว้นระยะระหว่างกล้องกับแนวอาคารแถวแรก
  • 27<X%w สร้างพื้นที่ว่างเป็นคาบเพื่อแบ่งบล็อกเมืองเหมือนถนน
  • ในค่าติดลบจะเป็น false เสมอ ทำให้เกิดพื้นที่ว่างคล้ายทะเล
  • X/9^Z/8 ใช้ bitwise XOR เพื่อสร้างการกระจายความสูงอาคารที่ดูคล้ายสุ่ม
  • ค่าที่ใช้หารด้วย 9 และ 8 ควบคุมความกว้างและความลึกของอาคาร
  • X/9 หารลงตัวด้วย 9 ร่วมกับตัวเลขที่เกี่ยวกับความกว้างถนน จึงป้องกันไม่ให้เกิดอาคารที่บางมากตรงขอบ
• ผลลัพธ์ในวงเล็บถูกคูณด้วย 8 แล้วนำไป modulo ด้วย 46 เพื่อสร้างช่วงความสูงสูงสุด
• ค่า 8 และ 46 ถูกเลือกจากการทดลองเพื่อให้ได้ความสูงอาคารที่หลากหลาย

เงา เท็กซ์เจอร์ และหมอกตามระยะ

• เมื่อเกิดการชน ลูปภายในเดิมจะรับบทบาทที่สอง คือทำ การตรวจสอบทิศทางแสง

d | (s = (X&Y&Z)%3/Z, a = b = 1, d = Z/w)

• d | ใช้แยกว่ารังสีปัจจุบันเป็นรังสีที่ออกจากกล้อง หรือเป็นรังสีที่ตรวจเงาไปตามทิศทางแสง
• ตอนแรก d = 1 จึงทำงานเป็นรังสีกล้อง
• หลังชนแล้ว d = Z/w จะกลายเป็นค่าที่น้อยกว่า 1 และผลการประเมิน bitwise OR เปลี่ยนไป ทำให้ลูปกลับมารันอีกครั้งและเริ่มตรวจเงา
• หากชนอีกครั้งระหว่างตรวจเงา ลูปจะออกและวาดพิกเซลนั้นเป็นเงา
• ค่าเท็กซ์เจอร์ s สร้างจากสมการต่อไปนี้

s = (X&Y&Z)%3/Z

• ใช้ bitwise AND กับ X, Y, Z แล้วนำเศษจากการหารด้วย 3 มาใช้สร้างเท็กซ์เจอร์สีเทาที่ดูเหมือนหน้าต่าง
• จากนั้นหารด้วย Z อีกครั้งเพื่อให้เท็กซ์เจอร์ที่อยู่ไกลจางลง
• ตั้งทั้ง a และ b เป็น 1 เพื่อส่งรังสีไปยังแหล่งกำเนิดแสงแบบมีทิศทางคล้ายดวงอาทิตย์
• d = Z/w คือค่าหมอกตามระยะ และใช้ทำให้อาคารไกล ๆ สว่างขึ้น

การวาดพิกเซลและการแสดงความสว่าง

• แต่ละพิกเซลถูกวาดด้วย fillRect

c.getContext`2d`.fillRect(i%w, i/w|0, 1 - d*Z/w + s, 1)

• i%w สร้างพิกัด x และ i/w|0 สร้างพิกัด y
• ความสว่างแสดงด้วยการลดความกว้างของพิกเซล ซึ่งเป็นเทคนิคหลักในการสร้างภาพ grayscale ด้วยโค้ดขนาดเล็ก
• 1 เทียบเท่าพิกเซลสีดำ ดังนั้นสมการสุดท้ายจึงลบค่าออกจาก 1 เพื่อสร้างความสว่างของภาพ
• d * Z/w รวมเอาเงาและเอฟเฟกต์ระยะทางเข้าด้วยกัน
  • ถ้าไม่ใช่เงา รังสีจะเดินทางจนถึงระยะสูงสุด w ทำให้ Z/w เป็น 1
  • ในเงา Z จะน้อยกว่า w จึงดูมืดกว่า
  • ยิ่งวัตถุที่บังแสงอยู่ใกล้ เงาก็ยิ่งมืด ทำให้เหลือเอฟเฟกต์คล้าย ambient occlusion
• สุดท้ายบวก s เพื่อผสมเท็กซ์เจอร์อาคารเข้ากับความสว่างสุดท้าย

เดโมต่อยอดและเครื่องมือทดลอง

• ถูกส่งเข้าร่วม Revision 2022 demo party และดูได้บน Pouet
• ตอนนั้นถูกส่งผิดหมวดหมู่ จึงไม่สามารถขึ้นอันดับสูงได้
• หลังจากนั้น Xor และโค้ดเดอร์คนอื่น ๆ ได้สร้าง shader ขนาด 256 ไบต์ บน Shadertoy ที่จำลองเวอร์ชัน JavaScript ขึ้นมา
  • เดโม Shadertoy รันที่ 60fps ใน HD
• Daniel Darabos สร้างเครื่องมือ Observable ที่สามารถปรับองค์ประกอบหลายอย่างของโปรแกรมได้แบบเรียลไทม์
  • Decoding A City In A Bottle
• โค้ดสามารถรีมิกซ์ได้บน Dwitter และทดลองได้บน CapJS

[GN⁺]

ความคิดเห็นจาก Hacker News

• มีข้อมูลที่เกี่ยวข้องคือวิธีจัดโครงสร้างโลกของ Pitfall สำหรับ Atari 2600: https://evoniuk.github.io/posts/pitfall.html
  การสร้างแบบ procedural ของเกม 8 บิตยุคแรก Elite: https://procedural-generation.tumblr.com/post/112509130817/e...
  เอกสารทั่วไปเกี่ยวกับการสร้างแบบ procedural: https://en.wikipedia.org/wiki/Procedural_generation
  แนวคิดที่เกี่ยวข้องอยู่บ้างคือ lazy evaluation ในภาษาโปรแกรมเชิงฟังก์ชัน: https://en.wikipedia.org/wiki/Lazy_evaluation
  ถ้าอัลกอริทึม ray tracing บางแบบประเมินเฉพาะจุดที่มองเห็นเมื่อสร้างภาพ 2D จากข้อมูล 3D ก็ดูคล้ายกับแนวคิด lazy evaluation ที่ว่า “เลื่อนการประเมินนิพจน์ออกไปจนกว่าจะต้องใช้ค่า”: https://en.wikipedia.org/wiki/Ray_tracing_(graphics)
  ถ้าขยายความไปอีก ก็ให้ความรู้สึกว่าพอจะเชื่อมโยงคร่าว ๆ กับแนวคิด “การสังเกตทำให้ฟังก์ชันคลื่นยุบตัว” ได้ด้วย: https://en.wikipedia.org/wiki/Wave_function_collapse
• ยังมี 1K Pinball Game in JavaScript จากผู้เขียนคนเดียวกันด้วย: https://frankforce.com/lu1ky-pinball-code-deep-dive/
• Remnants ของ Alcatraz ก็เป็น เดโม MS-DOS ขนาด 256 ไบต์ ที่คล้ายกัน และมีลิงก์ YouTube รวมอยู่ด้วย: https://www.pouet.net/prod.php
  แต่ผลงานนี้น่าประทับใจกว่าตรงที่ทำด้วย JavaScript เพราะโดยทั่วไป JavaScript มักมีความหนาแน่นของโค้ดแย่กว่าโค้ดเครื่อง x86 แบบ 16 บิต
  • ลิงก์ที่ถูกต้องน่าจะเป็นอันนี้: https://www.pouet.net/prod.php?which=96536
    มีซอร์สโค้ดรวมอยู่ด้วย
  • Spongy ทำสิ่งที่คล้ายกันได้ใน 128 ไบต์ หรือเล็กลงครึ่งหนึ่ง: https://www.pouet.net/prod.php?which=53871
    http://www.youtube.com/watch?v=36BPql6Nl_U
    ชื่อนี้มาจากแฟร็กทัล Menger sponge ที่ใช้เป็นพื้นฐาน: https://en.wikipedia.org/wiki/Menger_sponge
  • ไม่จำเป็นว่า JavaScript จะมีความหนาแน่นของโค้ดแย่กว่าเสมอไป ตัวแปรใช้ชื่อ 1 ไบต์ได้ แต่คำสั่งโหลดของ x86 โดยปกติมีอย่างน้อย 2 ไบต์ และมักเป็น 3 ไบต์
    จุดที่ JavaScript ได้เปรียบมากในที่นี้คือ ไลบรารีมาตรฐาน dweet มีฟังก์ชันอย่าง sin/cos/fill/line ให้ใช้ ในขณะที่ x86 BIOS ช่วยได้แค่ประมาณ “เปลี่ยนโหมด” จากนั้นก็ต้องจัดการอาร์เรย์พิกเซลเองโดยตรง
• สุดยอดจริง ๆ ความหนาแน่นของข้อมูล ที่เรารู้สึกได้จากโค้ดเพียงน้อยนิดขนาดนี้สูงจนน่าเหลือเชื่อ
  เลยทำให้คิดว่าโมเดลภาษาขนาดใหญ่อาจไม่ใช่วิธีที่ดีที่สุดในการจำลองโลกก็ได้
  • โค้ดที่ทำให้อ่านยาก ซึ่งอัด shortcut ไว้เต็มไปหมด ก็น่าจะไม่ใช่วิธีที่ดีที่สุดในการจำลองโลกเหมือนกัน ถึงอย่างนั้น นี่ก็เป็นความสำเร็จที่น่าประทับใจอย่างแน่นอน
    ถ้าเป็นผม แค่ทำได้ในสัก 256 บรรทัดก็คงพอใจแล้ว และในความเป็นจริงอาจต้องใช้มากกว่านั้นมาก
    สิ่งที่มองเห็นได้ ไม่ว่าจะเป็นสิ่งประดิษฐ์หรือสิ่งธรรมชาติ ในหลายกรณีก็เป็นไปตามแพตเทิร์น ถ้าไม่เป็นอย่างนั้นก็คงยากจะจำแนกได้ตั้งแต่แรก จึงมีอะไรให้ใช้ประโยชน์ทางคณิตศาสตร์ได้มาก สำหรับ height texture สามารถใช้ noise หรือแพตเทิร์นได้หลายชนิด แฟร็กทัลก็ใช้ได้อย่างน่าสนใจ สำหรับพืชพรรณและต้นไม้ใช้ฟีโบนัชชี/อัตราส่วนทองคำได้ ส่วนองค์ประกอบโครงกระดูกและกระดูกต่าง ๆ ก็ใช้อัตราส่วนขนาดได้ เรื่องพวกนี้ไม่จำเป็นต้องใช้เครื่องทำนายมหัศจรรย์อะไร
  • ทำไมถึงคิดว่าโมเดลภาษาขนาดใหญ่เป็นวิธีที่ดีที่สุดล่ะ?
• เท่มากก็จริง แต่ระหว่างอ่านบทความก็เสียดายนิดหน่อยที่ ลูปทำงานต่อเนื่อง จนแล็ปท็อปร้อนเกินไป
  • อ้อ มิน่าล่ะ มือถือถึงได้อุ่นผิดปกติตลอดช่วงไม่กี่นาทีที่ผ่านมา!
• ถ้าชอบอะไรแบบนี้ ก็น่าจะชอบ #tweetcart บน Twitter ด้วย
  เป็นโปรแกรมขนาดเท่าทวีตสำหรับคอนโซลเสมือน Pico-8
  • ยังมี https://www.dwitter.net/ ด้วย