สร้างแผนที่หกเหลี่ยมแบบ procedural ด้วย Wave Function Collapse

• โปรเจ็กต์สร้าง แผนที่เกาะสไตล์ยุคกลาง แบบอัตโนมัติด้วยอัลกอริทึม Wave Function Collapse (WFC) ซึ่งประกอบด้วยไทล์หกเหลี่ยมราว 4,100 ชิ้น
• แต่ละไทล์มีข้อมูลภูมิประเทศ เช่น ถนน, แม่น้ำ, ชายฝั่ง, หน้าผา, ป่า, หมู่บ้าน และสร้างเสร็จภายในราว 20 วินาที ด้วย Three.js WebGPU และ TSL shader
• เพื่อแก้ปัญหาความล้มเหลวที่เกิดขึ้นในกริดขนาดใหญ่ จึงแบ่งเป็น ซับกริดหกเหลี่ยม 19 ชุด และใช้ backtracking กับระบบกู้คืนแบบ local-WFC จนได้อัตราความสำเร็จเกิน 86%
• ด้านภาพใช้ PBR material, shader บน WebGPU, เอฟเฟกต์สะท้อนผิวน้ำและคลื่น, post-processing (แสง, ระยะชัดลึก, grain) เพื่อเพิ่มมิติความลึก
• ใช้ BatchedMesh rendering และ การแชร์ material เดียวกัน เพื่อเรนเดอร์ไทล์นับพันที่ 60fps แสดงให้เห็นศักยภาพของการผสาน procedural generation เข้ากับกราฟิกแบบเรียลไทม์

---

ภาพรวมของการสร้างแผนที่แบบ procedural

• โปรเจ็กต์นี้ได้แรงบันดาลใจจาก วิธีสร้างด้วยลูกเต๋าใน AD&D dungeon โดยอยู่ในรูปแบบที่ อัลกอริทึมประกอบโลกขึ้นมาเอง โดยไม่ต้องให้ผู้ใช้วางแผนด้วยตนเอง
• แผนที่ที่สร้างขึ้นเป็นเกาะสไตล์ยุคกลางที่มี ถนน, แม่น้ำ, แนวชายฝั่ง, หน้าผา, ป่า, หมู่บ้าน และประกอบด้วยเซลล์หกเหลี่ยมราว 4,100 เซลล์
• ใช้ Three.js WebGPU และ TSL shader เพื่อสร้างแผนที่ทั้งผืนเสร็จภายในประมาณ 20 วินาที

อัลกอริทึม Wave Function Collapse (WFC)

• WFC สร้างภูมิประเทศโดยอิงข้อจำกัดที่ว่า ขอบ (edge) ของไทล์ที่อยู่ติดกันต้องสอดคล้องกัน
• ไทล์หกเหลี่ยมมีขอบ 6 ด้าน จึงมี เงื่อนไขข้อจำกัดมากกว่าสี่เหลี่ยม 50%
• แต่ละไทล์กำหนดประเภทขอบทั้ง 6 ทิศทางและค่าน้ำหนัก (weight) เช่น จุดตัดถนนสามทางจะสลับระหว่างขอบถนนกับขอบหญ้า
• อัลกอริทึมทำงานดังนี้
  1. กำหนดให้ทุกเซลล์เริ่มต้นอยู่ในทุกสถานะที่เป็นไปได้
  2. เลือกเซลล์ที่ถูกจำกัดมากที่สุดแล้วทำให้ “collapse” เหลือสถานะเดียว
  3. แพร่ข้อจำกัดไปยังเซลล์ข้างเคียงโดยลบสถานะที่เป็นไปไม่ได้ออก
  4. ทำซ้ำจนกว่าทุกเซลล์จะถูกแก้ครบ

กริดขนาดใหญ่และการแก้แบบโมดูลาร์

• ในกริดขนาดเล็กระบบทำงานได้เสถียร แต่เมื่อเกิน 4,000 เซลล์ ความน่าจะเป็นที่จะล้มเหลวจะเพิ่มสูงขึ้นมาก
• วิธีแก้คือแบ่งออกเป็น ซับกริดหกเหลี่ยม 19 ชุด แล้วแก้แต่ละกริดอย่างอิสระ โดย ตรึงไทล์ขอบ ไว้เป็นข้อจำกัดคงที่
• หากข้อจำกัดที่ขอบชนกัน ก็ไม่สามารถแก้ได้ด้วย backtracking เพียงอย่างเดียว

Backtracking และระบบกู้คืน

• Backtracking คือการย้อนการเลือกที่ผิดแล้วลองไทล์แบบอื่น โดยทำได้สูงสุด 500 ครั้ง
• แต่ความขัดแย้งระหว่างกริดจะจัดการด้วยระบบกู้คืนแยกต่างหาก
  • ขั้นที่ 1: Unfixing — เปลี่ยนเซลล์ที่ชนกันให้กลับเป็นสถานะแปรผัน แล้วตั้งเซลล์รอบข้างเป็นข้อจำกัดใหม่
  • ขั้นที่ 2: Local-WFC — แก้พื้นที่รัศมี 2 เซลล์ (19 เซลล์) ใหม่เพื่อให้เข้ากันได้กับขอบ โดยลองได้สูงสุด 5 ครั้ง
  • ขั้นที่ 3: Drop & Hide — หากยังล้มเหลว ให้ลบเซลล์นั้นออกแล้วปิดทับด้วย ไทล์ภูเขา เพื่อให้ดูเป็นธรรมชาติ
• การกู้คืนหลายชั้นนี้ทำให้อัตราความสำเร็จในการสร้างแผนที่ทั้งผืนอยู่ที่ประมาณ 86%

การจัดการความสูงแบบสามมิติ

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

ระบบพิกัดหกเหลี่ยม

• โครงสร้างหกทิศทางของหกเหลี่ยมทำให้การคำนวณเพื่อนบ้านซับซ้อนหากใช้พิกัด 2D แบบธรรมดา
• จึงใช้ ระบบพิกัดลูกบาศก์ (q, r, s) เพื่อทำให้การค้นหาเพื่อนบ้านง่ายขึ้น
• WFC มุ่งเน้นที่ โครงสร้างกราฟการจับคู่ขอบ มากกว่ารูปทรงเรขาคณิตจริง ดังนั้นระบบพิกัดจึงถูกใช้หลัก ๆ ในการเรนเดอร์และการวางหลายกริด

การวางต้นไม้และอาคาร

• WFC เหมาะกับ แพตเทิร์นระดับเฉพาะจุด แต่ไม่เหมาะกับ การกระจายตัวในสเกลใหญ่
• ความหนาแน่นของต้นไม้และอาคารจึงกำหนดด้วย Perlin noise field เพื่อให้เกิดการจับกลุ่มตามธรรมชาติของป่าและหมู่บ้าน
• มีลอจิกเพิ่มเติมให้ปลายถนนมีอาคาร ชายฝั่งมีท่าเรือหรือกังหันลม และเนินเขามีวงหิน (henge)

การทำเอฟเฟกต์ผิวน้ำ

• ทะเลไม่ได้เป็นเพียงพื้นระนาบเรียบ แต่มีทั้ง ประกายแสงและคลื่นชายฝั่ง
• ประกายแสง (Sparkles) สร้างด้วย เท็กซ์เจอร์เลื่อนขนาดเล็ก + noise mask แทน Voronoi noise เพื่อลดภาระ GPU
• คลื่นชายฝั่ง (Coast Waves) ใช้มาสก์ชายฝั่งที่ผ่านการ blur เพื่อสร้างแถบคลื่นไซน์ตามระยะทาง
• ในปัญหา อ่าว (Cove) การคำนวณระยะด้วย blur ไม่แม่นพอ จึงให้ CPU ตรวจเซลล์รอบข้างเพื่อสร้าง มาสก์พื้นที่ที่ต้องทำให้คลื่นบางลง

การสร้างและจัดแนวไทล์

• โมเดลพื้นฐานใช้ KayKit Medieval Hexagon Pack แต่ไทล์เชื่อมต่อที่ขาดไป เช่น แม่น้ำบนทางลาดหรือหน้าผาแบบแปรผัน ถูกสร้างเพิ่มเองด้วย Blender
• ไทล์ทั้งหมดถูกทำให้มีความกว้าง 2 ยูนิตเท่ากัน และหาก การจัดแนว UV คลาดเคลื่อน จะเห็นรอยต่อที่ขอบ จึงต้องทำ mapping อย่างแม่นยำ

เอฟเฟกต์ภาพและการเรนเดอร์

• สร้างด้วย Three.js WebGPU + TSL shader โดยใช้ shader แบบ node-based แทน GLSL
• สแตก post-processing
  1. GTAO เพื่อเน้นเงา
  2. Depth of Field เพื่อให้เอฟเฟกต์เหมือนโมเดลจิ๋ว
  3. Vignetting·Film Grain เพื่อเพิ่มพื้นผิวแบบอนาล็อก
• dynamic shadow map จะถูกปรับใหม่ทุกเฟรมให้สอดคล้องกับมุมกล้อง จึงยังคงเงาคมชัดแม้ซูมเข้า

การปรับแต่งประสิทธิภาพ

• ใช้ BatchedMesh รวมไทล์และของตกแต่งในแต่ละกริดเข้าด้วยกัน เพื่อเรนเดอร์ด้วย draw call เดียว
• ทุก mesh ใช้ material เดียวกัน เพื่อลดการสลับสถานะของ shader ให้เหลือน้อยที่สุด
• ผลลัพธ์คือเรนเดอร์ได้ด้วย BatchedMesh 38 ชุด, 4,100+ เซลล์, ที่ 60fps

ตัวเลขสำคัญและเทคโนโลยีสแตก

• ไทล์ 30 แบบ, 19 กริด, ~4,100 เซลล์, backtracking 500 ครั้ง, ลอง Local-WFC 5 ครั้ง, สร้างเสร็จใน 20 วินาที, อัตราความสำเร็จ 100% (ทดสอบ 500 ครั้ง)
• ใช้ Three.js r183, TSL shader, Web Workers, Vite build, BatchedMesh, Seeded RNG

ทดลองใช้และซอร์สโค้ด

• สามารถขยายแผนที่และสร้างใหม่ทั้งผืนได้ที่ ไลฟ์เดโม
• มี ซอร์สโค้ดบน GitHub และปรับพารามิเตอร์ได้มากกว่า 50 ค่า เช่น แสง สี น้ำ และการตั้งค่า WFC

สรุป

• มอบประสบการณ์ที่ให้อัลกอริทึมสร้างโลกแทนลูกเต๋า และสามารถสำรวจภูมิประเทศรวมถึงการเชื่อมต่อของถนนและแม่น้ำที่ต่างกันในแต่ละครั้งได้
• เป็น การทดลองสร้างแผนที่บน WebGPU ที่ผสาน procedural generation, การปรับแต่งกราฟิก, และเทคนิค shader เข้าด้วยกัน

[GN⁺]

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

• แม้ในบทความจะบอกว่าแค่จำกัด backtracking ไว้ที่ 500 ขั้น แต่ในความเป็นจริง การเขียนโปรแกรมเชิงข้อจำกัดเป็นสาขาที่น่าสนใจและซับซ้อนมาก
  ถ้าใช้ Algorithm X ของ Knuth กับ dancing links ก็น่าจะช่วยแก้พื้นที่ "Layer 2" ที่กล่าวถึงในบทความได้ด้วยอัตราความสำเร็จสูงกว่า 86%
  นอกจากนี้ หากใช้ heuristics หลากหลายแบบ ก็จะค้นหาได้เร็วกว่า brute force แบบตรงไปตรงมามาก คนที่เคยทำตัวแก้ Sudoku น่าจะรู้ดีว่า brute force ช้าลงขนาดไหน

  • สำหรับปัญหา การหาค่าเหมาะที่สุดเชิงผสมภายใต้ข้อจำกัด แบบนี้ มีทั้งตัวแก้เฉพาะทางและภาษาสำหรับสร้างโมเดลระดับสูงอยู่แล้วมากมาย
    ตัวอย่างเช่น MiniZinc เป็นภาษาสร้างโมเดลระดับสูงที่รองรับ solver backend ได้หลายแบบ
    แทนที่จะเขียนอัลกอริทึมเอง การสร้างโมเดลปัญหาแล้วใช้ solver ระดับอุตสาหกรรมให้หาคำตอบแบบสุ่มหรือแบบสำรวจครบถ้วนจะมีประสิทธิภาพกว่า
    แบบนั้นก็จะได้ไม่ต้องเสียเวลากับการเขียน solver และไปโฟกัสที่ การปรับนิยามของปัญหาเพื่อสร้างแผนที่ที่น่าสนใจกว่าเดิม ได้มากขึ้น

• บนโน้ตบุ๊กของฉัน (Core i5 เจเนอเรชัน 11, Iris Xe, Chrome เวอร์ชันล่าสุด) เดโมรันได้แค่ 5 FPS ดูเหมือน GPU จะเป็นคอขวด
  ในบทความบอกว่ามันรันได้ 60 FPS บนมือถือ ก็เลยคิดว่าน่าจะมีประสิทธิภาพกว่านี้
  แผนที่สวยมาก แต่ด้วย ข้อจำกัดระดับไทล์ ของ WFC มันเลยให้ผลลัพธ์ที่ดูไม่เป็นธรรมชาติ เพราะสะท้อนอิทธิพลแบบไม่เฉพาะที่ (non-local influence) ได้ยาก
  สำหรับเกมที่สำรวจทีละไทล์อาจโอเค แต่ไม่ค่อยเหมาะกับการสร้างแผนที่ทั้งผืน
  แนวทางที่อิง noise ของ Red Blob Games ให้ผลลัพธ์ที่ดีกว่า แม่น้ำใช้การติดตามความชื้น ส่วนถนนหรือสะพานก็จัดการในอีกพาสหนึ่งแยกต่างหากได้ ทำให้เร็วและทนทานกว่า
  ถึงอย่างนั้น WFC ก็ยังเป็นโจทย์เขียนโปรแกรมที่น่าสนุก ดังนั้นการลงมือทำก็คงเพลิดเพลินไม่น้อย โดยรวมแล้วเป็นบทความที่ยอดเยี่ยมและเดโมก็น่าประทับใจมาก

  • ไม่ทราบว่าคุณรันบน Windows หรือ Linux หรือว่ากำลังใช้ CPU rendering อยู่หรือเปล่า
  • บนมือถือของฉันทำงานได้ดี เลยสงสัยว่าคุณวัด FPS ยังไง เพราะในเว็บไม่เห็นมีแสดงไว้ หรือว่าดูผ่าน Chrome Dev Tools?

• Oskar Stålberg ใช้ Wave Function Collapse (WFC) ในหลายเกม โดยตัวอย่างที่เด่นที่สุดคือ Townscaper
  ดูวิดีโอพูดเกี่ยวกับเรื่องนี้ได้ที่ SGC21 - Beyond Townscapers

• ทำให้นึกถึง Unity tutorial ของ Jasper Flick อย่าง Hex Terrain
  โปรเจกต์นี้ใช้ไทล์ที่เตรียมไว้ล่วงหน้าแล้วจับให้ตรงตามข้อจำกัด ขณะที่บทเรียนของ Jasper จะ สร้างขอบเขตของไทล์แบบไดนามิก
  ทั้งสองแนวทางน่าสนใจและอ่านสนุกเหมือนกัน

• เป็นโปรเจกต์ที่เจ๋งมากจริง ๆ
  เผื่อผู้เขียนผ่านมาเห็น อยากรู้ว่าเคยพิจารณาแทนสถานะ superposition ของไทล์ (ชุดตัวเลือกที่เป็นไปได้) ด้วย bitfield หรือไม่
  ตอนที่ฉันเคยทำ WFC การเปลี่ยนไปใช้ bitfield ทำให้ ความเร็วเพิ่มขึ้น แบบมหาศาล จนการคำนวณทั้งชังก์ใหม่หมดเร็วกว่า backtracking เสียอีก

  • ฉันก็มีประสบการณ์คล้ายกัน WFC bot ของฉันสร้าง แผนที่ Carcassonne และประสิทธิภาพดีขึ้นมากหลังใช้ ไลบรารี bitset
    มันทำงานโดยบันทึกสถานะลงสแตกเป็นช่วง ๆ แล้วถ้าตันก็ย้อนกลับไปสถานะล่าสุด
    พอเห็นว่าตั้งชื่อตัวแปรว่า tenper ก็อดแอบโทษตัวเองในอดีตนิด ๆ ไม่ได้

• ดูเหมือนว่าส่วนที่ยากที่สุดคือการหาอาร์เรย์ที่ตรงตามข้อจำกัด
  เลยสงสัยว่ามีทางเลือกอย่างการใช้ SAT solver ไหม แต่ถ้าใช้แบบนั้นก็อาจเจอแต่คำตอบที่ ‘ง่าย’ อยู่เสมอ และความสุ่มจะลดลง
  SAT solver บางตัวตั้งค่าเริ่มต้นของตัวแปรแบบสุ่มได้ แต่ก็ไม่ได้หมายความว่าจะได้คำตอบแบบสุ่มเสมอไป เลยอยากรู้ว่ามีใครเคยลองแนวนี้ไหม

  • SAT solver มีปัญหาว่าความซับซ้อนในการคำนวณสูง และสำหรับคนที่ไม่เคยเรียน formal methods มาก็เข้าใจได้ยาก
    ขณะที่ WFC เป็นแนว brute force ที่เรียบง่าย จึงนำไปใช้ได้ง่าย และถ้าไม่เจอทางตันบ่อยเกินไป ต้นทุนการคำนวณก็ต่ำ
    ในเกมนั้นไม่จำเป็นต้องได้คำตอบที่สมบูรณ์แบบ แค่ ‘ดีพอ’ ก็พอแล้ว ดังนั้น WFC อาจใช้งานจริงได้มากกว่า

• เป็นโปรเจกต์ที่ให้แรงบันดาลใจมาก แหล่งอ้างอิงก็ดี และยังเปิดซอร์สโค้ดไว้ด้วย
  ถ้านำ สไตล์ภาพ จาก Here Dragons Abound มาผสมด้วยก็น่าจะยอดเยี่ยม

• OP อาจรู้อยู่แล้ว แต่หน้า คณิตศาสตร์ Hexagon ของ Red Blob Games มีทั้งตัวอย่างและโค้ดดี ๆ เยอะมาก

  • ในบทความก็ลิงก์ไปที่เว็บนั้นอยู่แล้ว

• การสำรวจ WFC บน กริดที่ไม่ใช่สี่เหลี่ยมจัตุรัส (non-square) น่าสนใจมาก
  ความซับซ้อนของการแพร่กระจายข้อจำกัดน่าจะสูงกว่าตัวอย่างทั่วไปมาก
  บนโทโพโลยีที่ซับซ้อนแบบนี้ ตัวแก้ข้อจำกัดแบบอื่นอย่าง Constraint Logic Programming อาจได้เปรียบทั้งด้านความสามารถในการแสดงออกและประสิทธิภาพ

• ทำให้นึกถึง Dorfromantik ลิงก์ Steam

  • เกมนั้นสร้างจาก บอร์ดเกม ชื่อเดียวกัน ดูได้ที่ หน้า BoardGameGeek