Tạo bản đồ lục giác thủ tục bằng Wave Function Collapse

• Dự án tự động tạo bản đồ đảo phong cách trung cổ gồm khoảng 4.100 ô lục giác bằng thuật toán Wave Function Collapse (WFC)
• Mỗi ô chứa thông tin địa hình như đường đi, sông, bờ biển, vách đá, rừng, làng mạc, và được tạo trong khoảng 20 giây bằng Three.js WebGPU cùng shader TSL
• Để xử lý các lỗi xuất hiện trên lưới lớn, dự án chia thành 19 lưới con lục giác và đạt tỷ lệ thành công trên 86% nhờ backtracking và hệ thống phục hồi Local-WFC
• Về mặt hình ảnh, dự án áp dụng vật liệu PBR, shader dựa trên WebGPU, hiệu ứng phản xạ mặt nước và sóng, hậu xử lý (ánh sáng, độ sâu trường ảnh, grain) để tăng cảm giác chiều sâu
• Với rendering bằng BatchedMesh và chia sẻ một material duy nhất, hàng nghìn ô được render ở 60fps, cho thấy tiềm năng kết hợp giữa sinh thủ tục và đồ họa thời gian thực

---

Tổng quan về tạo bản đồ thủ tục

• Dự án lấy cảm hứng từ cách tạo bằng xúc xắc trong AD&D dungeon, theo hướng thuật toán tự xây dựng thế giới mà không cần người dùng thiết kế trực tiếp
• Bản đồ được tạo có dạng đảo trung cổ gồm đường đi, sông, đường bờ biển, vách đá, rừng, làng mạc, với khoảng 4.100 ô lục giác
• Toàn bộ bản đồ được hoàn thành trong khoảng 20 giây bằng Three.js WebGPU và shader TSL

Thuật toán Wave Function Collapse (WFC)

• WFC xây dựng địa hình dựa trên ràng buộc rằng các cạnh (edge) của những ô kề nhau phải khớp nhau
• Vì ô lục giác có 6 cạnh nên có nhiều ràng buộc hơn 50% so với ô vuông
• Mỗi ô định nghĩa kiểu cạnh theo 6 hướng và trọng số (weight); ví dụ, một nút giao đường ba hướng sẽ xen kẽ cạnh đường và cạnh cỏ
• Thuật toán hoạt động như sau
  1. Khởi tạo mọi ô với tất cả các trạng thái có thể
  2. Chọn ô bị ràng buộc nhiều nhất và “collapse” nó về một trạng thái
  3. Lan truyền bằng cách loại bỏ các trạng thái không còn khả thi ở các ô lân cận
  4. Lặp lại cho đến khi toàn bộ ô được giải xong

Lưới lớn và cách giải mô-đun

• Hệ thống hoạt động ổn định trên lưới nhỏ, nhưng xác suất thất bại tăng mạnh khi vượt quá 4.000 ô
• Để khắc phục, bản đồ được chia thành 19 lưới con lục giác; mỗi lưới được giải độc lập nhưng vẫn giữ các ô biên như ràng buộc cố định
• Nếu các ràng buộc ở biên xung đột với nhau thì chỉ backtracking thôi là không thể xử lý được

Backtracking và hệ thống phục hồi

• Backtracking là cách hoàn tác lựa chọn sai để thử một ô khác, với tối đa 500 lần thử
• Tuy nhiên, xung đột giữa các lưới được xử lý bằng một hệ thống phục hồi riêng
  • Bước 1: Unfixing — chuyển các ô xung đột trở lại trạng thái biến đổi được và đặt các ô xung quanh làm ràng buộc mới
  • Bước 2: Local-WFC — giải lại vùng bán kính 2 ô (19 ô) để đảm bảo tương thích ở biên, thử tối đa 5 lần
  • Bước 3: Drop & Hide — nếu vẫn thất bại thì loại bỏ ô đó và phủ bằng ô địa hình núi để xử lý tự nhiên hơn
• Nhờ cơ chế phục hồi nhiều lớp này, tỷ lệ tạo thành công toàn bộ bản đồ đạt khoảng 86%

Xử lý độ cao 3D

• Bản đồ có 5 mức cao độ, trong đó các ô sườn dốc và vách đá kết nối những mức trên và dưới
• Nếu nối sai, có thể phát sinh lỗi như đường bị chặn bởi vách đá hoặc sông chảy ngược lên cao
• Thông tin độ cao được mã hóa vào màu instance để shader trộn bảng màu vùng thấp và vùng cao

Hệ tọa độ lục giác

• Do cấu trúc 6 hướng, ô lục giác khiến việc tính láng giềng trở nên phức tạp nếu chỉ dùng hệ tọa độ 2D đơn giản
• Dự án dùng hệ tọa độ cube (q, r, s) để đơn giản hóa việc duyệt ô kề nhau
• Vì WFC tập trung vào cấu trúc đồ thị khớp cạnh hơn là hình học thực tế, hệ tọa độ chủ yếu được dùng cho rendering và bố trí nhiều lưới

Bố trí cây và công trình

• WFC mạnh trong việc tạo mẫu cục bộ, nhưng không phù hợp với phân bố quy mô lớn
• Mật độ cây và nhà được quyết định bằng trường nhiễu Perlin để tạo cụm rừng và làng tự nhiên hơn
• Logic bổ sung còn đặt công trình ở cuối đường, cảng và cối xay gió ven biển, cùng các vòng đá henge trên đồi

Triển khai hiệu ứng mặt nước

• Biển không chỉ là một mặt phẳng đơn giản mà còn có độ lấp lánh và sóng ven bờ
• Hiệu ứng lấp lánh (Sparkles) được triển khai bằng texture cuộn nhỏ + mặt nạ nhiễu thay vì nhiễu Voronoi để giảm tải GPU
• Sóng ven bờ (Coast Waves) được tạo bằng cách blur mặt nạ bờ biển để sinh ra các dải sóng sin theo khoảng cách
• Với vấn đề vịnh nhỏ (Cove), cách tính khoảng cách dựa trên blur không đủ chính xác, nên CPU sẽ kiểm tra các ô lân cận để tạo mặt nạ vùng cần làm sóng mỏng hơn

Tạo và căn chỉnh tile

• Mô hình cơ bản dùng KayKit Medieval Hexagon Pack, còn các ô kết nối bị thiếu như sông dốc hay biến thể vách đá thì được tự làm bằng Blender
• Mọi ô đều được thống nhất ở chiều rộng 2 đơn vị; nếu có lỗi căn chỉnh UV thì đường nối sẽ lộ rõ, nên cần mapping thật chính xác

Hiệu ứng hình ảnh và rendering

• Dự án được triển khai bằng Three.js WebGPU + shader TSL, dùng shader dạng node thay cho GLSL
• Stack hậu xử lý
  1. GTAO để tăng nhấn mạnh đổ bóng
  2. Depth of Field để tạo hiệu ứng mô hình thu nhỏ
  3. Vignetting và film grain để mang lại chất cảm analog
• Shadow map động được điều chỉnh lại theo khung nhìn camera ở mỗi frame để vẫn giữ bóng sắc nét khi phóng to

Tối ưu hiệu năng

• BatchedMesh gộp tile và vật trang trí của từng lưới để render bằng một draw call
• Tất cả mesh cùng chia sẻ một material duy nhất để giảm tối đa việc chuyển trạng thái shader
• Kết quả là đạt 38 BatchedMesh, hơn 4.100 ô, và rendering ở 60fps

Các con số chính và stack công nghệ

• 30 loại tile, 19 lưới, ~4.100 ô, 500 lần backtracking, 5 lần thử Local-WFC, 20 giây tạo, tỷ lệ thành công 100% (500 lần thử nghiệm)
• Sử dụng Three.js r183, shader TSL, Web Workers, Vite build, BatchedMesh, Seeded RNG

Trải nghiệm và mã nguồn

• Có thể mở rộng bản đồ và tạo toàn bộ bản đồ tại demo trực tiếp
• Mã nguồn GitHub được công khai; có thể tinh chỉnh ánh sáng, màu sắc, mặt nước và thiết lập WFC bằng hơn 50 tham số

Tóm tắt

• Trải nghiệm này cho phép thuật toán tạo ra thế giới thay vì xúc xắc, và mỗi lần đều có thể khám phá địa hình, đường đi và kết nối sông khác nhau
• Đây là một thử nghiệm tạo bản đồ dựa trên WebGPU kết hợp sinh thủ tục, tối ưu đồ họa và công nghệ shader

[GN⁺]

Ý kiến trên Hacker News

• Bài viết nói rằng backtracking chỉ đơn giản bị giới hạn ở 500 bước, nhưng trên thực tế, lập trình ràng buộc là một lĩnh vực rất thú vị và phức tạp
  Nếu dùng Algorithm X của Knuth và dancing links, có vẻ sẽ giải được vùng "Layer 2" được nhắc trong bài với tỷ lệ thành công cao hơn 86%
  Ngoài ra, nếu áp dụng nhiều heuristic khác nhau thì có thể tìm kiếm nhanh hơn brute force đơn thuần rất nhiều. Ai từng làm Sudoku solver chắc đều biết brute force chậm đến mức nào

  • Với kiểu bài toán tối ưu tổ hợp dựa trên ràng buộc này, đã có sẵn nhiều solver chuyên dụng hoặc ngôn ngữ mô hình hóa cấp cao
    Ví dụ, MiniZinc cung cấp một ngôn ngữ mô hình hóa cấp cao hỗ trợ nhiều backend solver
    Thay vì tự viết thuật toán, sẽ hiệu quả hơn nếu dùng các solver cấp công nghiệp này để mô hình hóa bài toán và để solver tìm lời giải bằng tìm kiếm ngẫu nhiên hoặc toàn diện
    Như vậy, thay vì tốn thời gian viết solver, bạn có thể tập trung điều chỉnh định nghĩa bài toán để tạo ra bản đồ thú vị hơn

• Trên laptop của tôi (Core i5 thế hệ 11, Iris Xe, Chrome bản mới nhất), bản demo chạy ở 5 FPS. Có vẻ GPU là nút thắt cổ chai
  Bài viết nói nó chạy 60 FPS trên di động nên tôi đã nghĩ nó sẽ hiệu quả hơn
  Bản đồ rất đẹp, nhưng do ràng buộc ở cấp độ tile của WFC nên tạo ra các kết quả thiếu tự nhiên. Nguyên nhân là khó phản ánh ảnh hưởng không cục bộ (non-local influence)
  Nó ổn với game khám phá từng tile, nhưng không phù hợp để tạo cả bản đồ
  Cách tiếp cận dựa trên noise của Red Blob Games cho kết quả tốt hơn. Sông có thể xử lý bằng theo dõi độ ẩm, còn đường hoặc cầu thì xử lý bằng pass riêng sẽ nhanh và vững hơn
  Dù vậy WFC vẫn là một bài toán lập trình thú vị, nên chắc hẳn việc triển khai nó cũng rất vui. Nhìn chung đây là một bài viết hay và bản demo rất ấn tượng

  • Không biết bạn chạy trên Windows hay Linux, hay là đang dùng CPU rendering?
  • Trên di động của tôi nó hoạt động tốt. Không rõ bạn đo FPS bằng cách nào. Tôi không thấy hiển thị trên trang, có phải bạn xem bằng Chrome Dev Tools không?

• Oskar Stålberg đã dùng Wave Function Collapse (WFC) trong nhiều game. Tiêu biểu nhất là Townscaper
  Có thể xem video thuyết trình liên quan tại SGC21 - Beyond Townscapers

• Tôi nhớ đến tutorial Unity Hex Terrain của Jasper Flick
  Dự án này ghép các tile dựng sẵn theo điều kiện ràng buộc, trong khi tutorial của Jasper thì tạo biên tile một cách động
  Cả hai cách tiếp cận đều thú vị và rất đáng đọc

• Đây thực sự là một dự án rất hay
  Nhân tiện, nếu tác giả có đọc được thì tôi muốn hỏi liệu bạn đã cân nhắc biểu diễn trạng thái superposition của tile (tập các lựa chọn khả dĩ) bằng bitfield chưa
  Trước đây khi tôi triển khai WFC, chỉ cần chuyển sang bitfield là tốc độ tăng lên cực kỳ nhiều. Thậm chí tính lại cả chunk còn nhanh hơn backtracking

  • Tôi cũng có trải nghiệm tương tự. Bot WFC của tôi tạo bản đồ Carcassonne, và hiệu năng cải thiện đáng kể sau khi dùng thư viện bitset
    Nó hoạt động bằng cách lưu trạng thái vào stack theo chu kỳ, rồi nếu bị kẹt thì quay lại trạng thái gần nhất
    Nhìn tên biến tenper khiến tôi hơi oán trách bản thân trong quá khứ

• Có vẻ phần khó nhất là tìm ra một cách sắp xếp thỏa mãn các ràng buộc
  Tôi tự hỏi liệu có phương án thay thế dùng SAT solver không. Tuy nhiên nếu làm vậy thì có thể lúc nào cũng chỉ tìm được các nghiệm ‘dễ’, làm giảm tính ngẫu nhiên
  Một số SAT solver có thể gán ngẫu nhiên giá trị ban đầu cho biến, nhưng điều đó không đồng nghĩa với việc cho ra lời giải ngẫu nhiên. Không biết có ai từng thử cách tương tự chưa

  • SAT solver cũng có vấn đề là độ phức tạp tính toán cao, và với những người chưa học formal methods thì khá khó hiểu
    Trong khi đó WFC là một cách brute force đơn giản nên dễ triển khai, và nếu không gặp quá nhiều ngõ cụt thì chi phí tính toán thấp
    Trong game, kết quả ‘đủ tốt’ thường thực tế hơn một lời giải hoàn hảo, nên WFC có thể là lựa chọn thiết thực hơn

• Đây là một dự án truyền cảm hứng. Tài liệu tham khảo rất tốt và mã nguồn cũng được công khai
  Nếu kết hợp thêm phong cách hình ảnh của Here Dragons Abound thì có lẽ sẽ rất tuyệt

• Có thể OP đã biết rồi, nhưng trang toán học về Hexagon của Red Blob Games có rất nhiều ví dụ và mã nguồn hay

  • Bài viết cũng đã liên kết đến trang đó rồi

• Thật thú vị khi thấy WFC được khám phá trên lưới không vuông (non-square)
  Có vẻ độ phức tạp của lan truyền ràng buộc sẽ cao hơn nhiều so với các ví dụ thông thường
  Trong kiểu topo phức tạp này, tôi nghĩ các solver ràng buộc khác như Constraint Logic Programming có thể có lợi thế hơn về khả năng biểu đạt và hiệu năng

• Tôi nhớ đến Dorfromantik. Liên kết Steam

  • Nó dựa trên board game cùng tên. Xem trang BoardGameGeek