Wave Function Collapse (WFC): Procedural Generation Explained

Nếu bạn đã từng chơi trò chơi Heroes 3, bạn hẳn đã từng dùng chức năng sinh random map. Có lần, mình tự hỏi làm cách nào mà người ta có thể sinh ra một bản đồ ngẫu nhiên. Trên bản đồ ấy có biển, bờ biển, đồng bằng, rừng và núi. Những địa hình này không thể xuất hiện hoàn toàn tùy tiện. Một khu rừng thường nằm cạnh đồng bằng hoặc núi, bờ biển là vùng chuyển tiếp giữa đất liền và biển... Nếu chỉ sử dụng random để chọn địa hình cho từng ô, kết quả chắc chắn sẽ rất thiếu tự nhiên và phi logic. Vậy có cách nào để chúng ta chỉ cần cung cấp một số quy tắc đơn giản, sau đó để máy tính tự tạo ra một thế giới mới mà vẫn giữ được sự hợp lý trong cách các địa hình kết hợp với nhau?

Một trong những thuật toán thú vị có thể giải quyết bài toán này là Wave Function Collapse (WFC). WFC đơn giản chỉ cần biết những thành phần nào có thể xuất hiện cạnh nhau. Từ những ràng buộc cục bộ ấy, một cấu trúc lớn hơn dần được hình thành.

Một chút lịch sử thuật toán Wave Function Collapse (WFC)

Wave Function Collapse (WFC) được phát triển bởi Maxim Gumin, một nhà phát triển game độc lập, và được công bố trên GitHub vào năm 2016. Ý tưởng ban đầu của thuật toán là tạo ra những hình ảnh mới có cấu trúc cục bộ tương tự một hình ảnh mẫu đầu vào. Chẳng hạn, từ một hình ảnh nhỏ gồm các họa tiết pixel, thuật toán có thể tổng hợp một hình ảnh lớn hơn mà những tổ hợp pixel cục bộ vẫn tuân theo các mẫu đã xuất hiện trong hình ảnh gốc.

Cái tên Wave Function Collapse được lấy cảm hứng từ cơ học lượng tử.

Trong cơ học lượng tử, một hệ có thể tồn tại dưới dạng chồng chập (superposition) của nhiều trạng thái khả dĩ. Khi thực hiện phép đo, hệ được ghi nhận ở một trạng thái xác định — hiện tượng được gọi là wave function collapse. WFC mượn ý tưởng này như một phép ẩn dụ cho quá trình sinh nội dung. Ban đầu, mỗi vị trí trên bản đồ có thể chứa nhiều tile khác nhau. Khi thuật toán lựa chọn một tile tại một vị trí, các khả năng tại đó được thu hẹp về một trạng thái duy nhất. Lựa chọn này tiếp tục tạo ra những ràng buộc, loại bỏ các tile không còn tương thích ở những vị trí lân cận. Quá trình ấy lặp lại, khiến bản đồ dần được xác định từ một tập hợp lớn những khả năng ban đầu.

Tuy nhiên, cần lưu ý rằng WFC không phải là một thuật toán mô phỏng cơ học lượng tử. Chính Maxim Gumin cũng nhấn mạnh rằng đây chỉ là nguồn cảm hứng về mặt ý tưởng, còn thuật toán thực tế hoạt động trên các trạng thái rời rạc và những ràng buộc toán học.

Một điểm thú vị khác là WFC không xuất hiện hoàn toàn tách biệt khỏi những nghiên cứu trước đó. Maxim Gumin cho biết ông chịu ảnh hưởng từ phương pháp Model Synthesis của Paul Merrell, một hướng nghiên cứu về tổng hợp mô hình từ các thành phần rời rạc đã xuất hiện trước đó. Đến năm 2017, Isaac Karth và Adam M. Smith tiếp tục phân tích WFC dưới góc nhìn của bài toán thỏa mãn ràng buộc (Constraint Satisfaction Problem).

Từ một ý tưởng lấy cảm hứng từ cơ học lượng tử, WFC đã trở thành một công cụ thú vị trong lĩnh vực Procedural Content Generation — sinh nội dung tự động cho game và đồ họa máy tính.

Để hiểu rõ WFC, chúng ta hãy cùng nhau xây dựng một demo sinh ngẫu nhiên một bản đồ 2d.

Một thế giới được tạo ra từ những mảnh ghép

Trước tiên, hãy chia bản đồ thành một lưới gồm nhiều ô vuông. Mỗi ô sẽ chứa một thành phần (tile) trong bộ tileset mà chúng ta chuẩn bị.

Với bản đồ đang xây dựng, chúng ta có thể sử dụng những thành phần sau:

Grass: Trảng cỏ xanh, tạo nên phần nền chính của bản đồ.
Road: Các đoạn đường thẳng, góc cua, ngã ba và ngã tư.
River: Những đoạn sông thẳng, sông uốn cong và các đoạn bờ sông.
Bridge: Cầu bắc qua sông, cho phép con đường tiếp tục đi qua.
Tree: Cây xanh có thể xuất hiện rải rác trên những vùng cỏ.

Điểm quan trọng là các thành phần này không thể xuất hiện hoàn toàn tùy tiện. Chẳng hạn:

Một đoạn đường thẳng phải tiếp nối được với một đoạn đường khác.
Một đoạn sông phải có thể nối với những đoạn sông kế tiếp.
Cây cầu phải nằm trên dòng sông và có đường đi băng qua.
Cây xanh không nên xuất hiện chắn ngang con đường.
Những đoạn bờ sông phải tạo thành vùng chuyển tiếp hợp lý giữa nước và đất.

Chúng ta có thể biểu diễn những quy tắc này bằng một tập hợp các ràng buộc (constraints). Ví dụ, nếu một ô chứa đoạn đường mở về phía Đông, thì ô ngay bên phải nó phải có một kết nối đường tương ứng ở phía Tây. Tương tự, nếu một ô chứa dòng sông chảy theo hướng Bắc - Nam, thì những ô nằm phía Bắc và phía Nam phải có khả năng tiếp nối dòng sông. Như vậy, thay vì chỉ định chính xác vị trí của từng con đường, cây cầu hay dòng sông, chúng ta chỉ cần mô tả những cách kết hợp nào được phép và những cách kết hợp nào không được phép. Đó chính là nền tảng của Wave Function Collapse.

Superposition: Mỗi ô chứa nhiều khả năng

Hãy xét một ô bất kỳ trên bản đồ. Ban đầu, chúng ta chưa biết ô đó sẽ là cỏ, cây, đường hay một phần của dòng sông. Thay vì chọn ngay một thành phần, ta giữ lại tất cả những khả năng có thể xảy ra. Giả sử tập hợp tile của chúng ta là:

T={Grass,Tree,Road,River,Bridge,\ldots}

Khi khởi tạo, một ô có thể chứa toàn bộ những tile hợp lệ:

C_{i,j}=T

Tuy nhiên, không phải mọi tile đều có thể xuất hiện ở mọi vị trí. Chẳng hạn, một tile có kết nối đường hướng Bắc không thể xuất hiện ở hàng trên cùng nếu kết nối đó vượt ra ngoài bản đồ. Vì vậy, tập hợp ban đầu của mỗi ô có thể đã được giới hạn bởi một số ràng buộc về biên. Trong thuật toán WFC, trạng thái mà một ô còn nhiều khả năng được gọi là superposition.

Khái niệm này được lấy cảm hứng từ cơ học lượng tử, một hệ có thể được mô tả bằng sự chồng chập của nhiều trạng thái. Tuy nhiên, WFC không thực hiện phép tính cơ học lượng tử thực sự. Đây chỉ là một phép tương tự về mặt ý tưởng.

Ở thời điểm ban đầu, toàn bộ bản đồ đều tồn tại dưới dạng những tập hợp khả năng như vậy.

Entropy: Chúng ta nên quyết định ô nào trước?

Giả sử có hai ô:

Ô A có 2 tile khả thi.
Ô B có 5 tile khả thi.

Rõ ràng, ô A có ít lựa chọn hơn. Chúng ta đã biết nhiều thông tin hơn về ô này so với ô B. WFC sử dụng một đại lượng gọi là entropy để đo mức độ không chắc chắn của mỗi ô. Với một tập hợp các trạng thái có xác suất $p_1,p_2,\ldots,p_n$ , theo lý thuyết thông tin (Shannon) entropy được định nghĩa là:

H(X)=-\sum_{i=1}^{n}p_i\log p_i

Nếu các trạng thái có xác suất bằng nhau, công thức có thể đơn giản hóa thành:

H(X)=\log n

Trong ví dụ trên: $H(A)=\log 2$ và $H(B)=\log 5$ , do đó: $H(A) \lt H(B)$ . WFC ưu tiên chọn ô có entropy thấp nhất để thực hiện bước tiếp theo. Một cách trực giác, chúng ta sẽ giải quyết những vị trí có ít lựa chọn nhất trước, thay vì quyết định một vị trí còn quá nhiều khả năng.

Nếu sử dụng trọng số cho từng tile, công thức entropy tổng quát hơn sẽ là:

H(X)=-\sum_i p_i\log p_i

Trong đó, xác suất $p_i$ được tính từ trọng số của tile tương ứng $\displaystyle p_i=\frac{w_i}{\sum_j w_j}$ . Những tile có trọng số lớn hơn sẽ có xác suất được chọn cao hơn.

Observation: Collapse một trạng thái

Sau khi chọn được ô có entropy thấp nhất, thuật toán sẽ chọn một trong những tile khả thi của ô đó. Ví dụ, giả sử một ô đang có tập hợp: $C_{i,j}={Grass,Tree,Road}$ . Sau bước collapse, thuật toán chọn được tile Grass $ $C_{i,j}={Grass}$ . Ô này đã được xác định và không còn trạng thái nào khác có thể xuất hiện tại vị trí đó. Việc lựa chọn thường được thực hiện bằng weighted random selection. Điều này giúp những tile có trọng số lớn xuất hiện thường xuyên hơn. Ví dụ, nếu chúng ta muốn bản đồ có nhiều trảng cỏ và cây xanh hơn là đường và cầu, ta có thể thiết lập trọng số tương ứng. Tuy nhiên, việc lựa chọn một tile không chỉ ảnh hưởng đến chính ô đó. Nó còn làm thay đổi những khả năng có thể xuất hiện ở các ô lân cận. Đó chính là phần quan trọng tiếp theo của thuật toán.

Propagation: Một quyết định ảnh hưởng đến những ô xung quanh

Giả sử chúng ta vừa collapse một ô thành tile Road, với kết nối đường hướng Đông và Tây. Khi đó, ô nằm bên trái và bên phải nó bắt buộc phải có khả năng tiếp nối con đường tương ứng. Những tile không đáp ứng điều kiện này sẽ bị loại bỏ khỏi tập khả năng của các ô lân cận. Ví dụ, một ô bên phải ban đầu có:

C_{i+1,j}= {Grass,Tree,Road,Bridge}

Nếu chỉ có Road và Bridge có kết nối đường ở phía Tây, tập hợp mới sẽ là:

C_{i+1,j}= {Road,Bridge}

Như vậy, một quyết định đã làm giảm số lượng khả năng của ô kế bên. Quá trình này không chỉ dừng lại ở một ô. Khi tập hợp khả năng của một ô thay đổi, nó có thể tiếp tục tạo ra những ràng buộc mới cho các ô khác. Những ràng buộc này lại tiếp tục lan truyền cho đến khi không còn thay đổi nào nữa. Quá trình này được gọi là constraint propagation. Sau khi propagation hoàn tất, thuật toán quay lại bước Observation, chọn một ô có entropy thấp nhất và tiếp tục collapse.

Toàn bộ quy trình có thể tóm tắt như sau:

Khởi tạo tất cả các ô với những tile có thể xuất hiện.
Chọn ô có entropy thấp nhất.
Collapse ô đó thành một tile cụ thể.
Propagate các ràng buộc sang những ô lân cận.
Lặp lại cho đến khi tất cả các ô được xác định.

Nếu một ô không còn tile nào hợp lệ, thuật toán gặp phải một tình huống gọi là contradiction. Ví dụ, một ô cần phải có kết nối đường ở phía Tây nhưng tất cả những tile còn lại đều không có kết nối này. Khi đó, cấu hình hiện tại không thể tiếp tục. Chúng ta có thể khởi động lại quá trình hoặc sử dụng backtracking để quay lại những lựa chọn trước đó.

Làm thế nào để xác định hai tile có thể đứng cạnh nhau?

Đây là phần cốt lõi khi xây dựng WFC cho bản đồ của chúng ta. Thay vì chỉ quan tâm đến tên của tile, chúng ta cần mô tả những đặc điểm ở các cạnh của nó. Ví dụ, một tile Road có thể có kết nối ở hai phía Đông và Tây:

Road_{EW}

Một tile Road khác có thể có kết nối ở phía Bắc và Đông:

Road_{NE}

Tương tự, dòng sông cũng có những hướng kết nối riêng:

River_{NS}

Với cây cầu, chúng ta cần một cách biểu diễn đặc biệt hơn. Một cây cầu bắc qua dòng sông có thể được mô tả bằng hai lớp kết nối độc lập:

Lớp Road: kết nối theo hướng Đông - Tây.
Lớp River: kết nối theo hướng Bắc - Nam.

Ta có thể biểu diễn tile cầu bằng:

Bridge=(Road_{EW},River_{NS})

Như vậy, một tile cầu vừa tiếp tục con đường, vừa tiếp tục dòng sông. Đây là một điểm quan trọng trong thiết kế tileset: một tile không nhất thiết chỉ chứa một loại thông tin. Nó có thể đại diện cho nhiều lớp cấu trúc cùng tồn tại trên một vị trí. Về mặt tổng quát, ta có thể biểu diễn các kết nối của một tile bằng một tập hợp các thuộc tính:

Tile=(Terrain,Road,River)

Khi hai tile nằm cạnh nhau, chúng phải tương thích ở tất cả các lớp kết nối liên quan. Ví dụ, hai tile $A$ và $B$ nằm cạnh nhau theo hướng Đông - Tây phải thỏa mãn:

Road_E(A)=Road_W(B)

và:

\int_0^\infty x^2 dx

Các điều kiện này giúp tránh tình trạng đường hoặc sông bị đứt đoạn tại ranh giới giữa hai tile. Trong thực tế, chúng ta có thể sử dụng một tập hợp các tile được thiết kế sẵn, sau đó tự động tạo các biến thể bằng cách xoay chúng theo những hướng khác nhau.

Nhờ vậy, chỉ cần thiết kế một số tile cơ bản, chúng ta đã có thể tạo ra nhiều cách kết hợp khác nhau.

Xây dựng một World Map Generator bằng JavaScript

Bây giờ chúng ta có thể áp dụng những kiến thức vừa tìm hiểu để xây dựng một demo nhỏ.

Bản đồ sẽ bao gồm năm thành phần chính:

Trảng cỏ xanh làm nền.
Cây xanh xuất hiện rải rác.
Con đường với các đoạn thẳng, góc cua và giao lộ.
Dòng sông với những đoạn thẳng và đoạn uốn cong.
Cầu để con đường có thể băng qua sông.

Demo sẽ có một số chức năng:

Điều chỉnh kích thước bản đồ.
Generate để tạo một thế giới mới.
Play/Pause để quan sát quá trình WFC.
Step để thực hiện từng bước collapse.
Hiển thị những tile còn khả thi tại mỗi ô.
Hiển thị entropy để quan sát mức độ không chắc chắn.
Điều chỉnh trọng số xuất hiện của các loại tile.

Chúng ta không chỉ nhìn thấy bản đồ cuối cùng, mà còn có thể quan sát cách nó dần được hình thành. Một quyết định đặt con đường ở một vị trí có thể khiến các ô xung quanh phải thay đổi. Một đoạn sông được xác định có thể loại bỏ hàng loạt tile không phù hợp ở những vị trí kế tiếp.

Những giới hạn của Wave Function Collapse

Mặc dù khá mạnh mẽ, WFC không phải là một thuật toán có thể tạo ra mọi cấu trúc mong muốn. Một trong những giới hạn quan trọng nhất là WFC chủ yếu xử lý các ràng buộc cục bộ (local constraints). Ví dụ, việc đảm bảo rằng hai đoạn đường liền kề luôn tương thích không đồng nghĩa với việc toàn bộ hệ thống đường sẽ tạo thành một mạng lưới có thể đi từ đầu này đến đầu kia. Tương tự, việc đảm bảo các đoạn sông tiếp nối nhau không tự động đảm bảo rằng dòng sông sẽ bắt nguồn từ một vùng cao và chảy ra khỏi bản đồ. Đây là sự khác biệt giữa local constraints và global constraints.

Với bản đồ của chúng ta, có thể xuất hiện những tình huống như:

Một con đường hoàn toàn hợp lệ ở từng ô nhưng kết thúc thành một ngõ cụt ngoài ý muốn.
Một dòng sông liên tục nhưng không có điểm bắt đầu hoặc kết thúc hợp lý.
Một cây cầu có đầy đủ các kết nối cục bộ nhưng không thực sự cần thiết trong cấu trúc tổng thể.

Để giải quyết những vấn đề này, chúng ta có thể kết hợp WFC với các kỹ thuật khác:

Graph algorithms để kiểm tra tính liên thông của hệ thống đường.
BFS hoặc A* để kiểm tra khả năng di chuyển giữa các vị trí.
Noise functions để định hướng những vùng địa hình lớn.
Mask constraints để giới hạn những vị trí mà một số tile được phép xuất hiện.
Backtracking để xử lý những tình huống contradiction.

Nói cách khác, WFC rất tốt trong việc tạo ra một cấu trúc có tính nhất quán cục bộ, nhưng không nhất thiết hiểu được mục đích tổng thể của thế giới mà chúng ta đang xây dựng.

Kết luận

Wave Function Collapse là thuật toán xây dựng một hệ thống có thể hình thành một cấu trúc phức tạp từ những quy tắc tương đối đơn giản. Chúng ta không cần chỉ định chính xác vị trí của từng cái cây, con đường, cây cầu hay dòng sông. Chúng ta chỉ cần mô tả những gì có thể và không thể xảy ra khi các thành phần đứng cạnh nhau. Từ những ràng buộc cục bộ ấy, thuật toán dần thu hẹp không gian khả năng cho đến khi tạo ra một cấu trúc hoàn chỉnh. Đây cũng là một ví dụ thú vị về Constraint Satisfaction Problem (CSP), một bài toán có thể được thực hiện bằng cách liên tục loại bỏ những khả năng không còn hợp lệ.

Wave Function Collapse - Sinh bản đồ ngẫu nhiên