-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
176 lines (165 loc) · 6.44 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>WFC - Home</title>
<link rel="preconnect" href="https://fonts.googleapis.com" />
<link rel="preconnect" href="https://fonts.gstatic.com" crossorigin />
<link
href="https://fonts.googleapis.com/css2?family=Cantarell:ital,wght@1,700&family=Roboto&display=swap"
rel="stylesheet"
/>
<link rel="stylesheet" type="text/css" href="styles/style.css" />
</head>
<body>
<article>
<h1>Wave Function Collapse</h1>
<hr />
<h3>What is that?</h3>
<p>
I should start by saying I didn't come up with it. I also can't say that
I fully understand all of the thought that went in to it, or some of its
subleties. For the utmost in detail, please check out the original work
<a href="https://github.com/mxgmn/WaveFunctionCollapse" target="_blank">
here</a
>.
</p>
<p>
Wave Function Collapse is an algorithm that alows us to, for example,
generate an image made of a tiling of smaller images with rules for
which images may be adjacent. By guessing where we have to and updating
our neighbors' legal options after each guess, we're able to generate a
reasonable potential image. By identifying and correcting any eventual
mistakes, we can assure the final product is a "legal" image.
</p>
<p>
The algorithm gets its name from Quantum Mechanics, where our cells are
in superposition of multiple states, and by observing our cells we are
able to collapse that superposition, revealing more information about
the state of the cells around us, and eventually leading to the entropic
collapse of the entire system.
</p>
<h3>Uh huh... Yeah, I know some of those words...</h3>
<p>
Err, right. Yeah. This is more of a visual thing. Luckily, I have
visuals! Check these out and we'll keep talking about this after.
</p>
<h4>Tilesets</h4>
<ul id="sketch-buttons">
<li><button class="sketch-button" id="lines">Lines</button></li>
<li><button class="sketch-button" id="polka">Polka</button></li>
<li><button class="sketch-button" id="roads">Roads</button></li>
<li>
<button class="sketch-button" id="train-tracks">Train Tracks</button>
</li>
<li>
<button class="sketch-button" id="circuit-original">
Circuit - Original
</button>
</li>
<li>
<button class="sketch-button" id="circuit-modified">
Circuit - Modified
</button>
</li>
<li>
<button class="sketch-button" id="circuit-custom">
Circuit - Custom
</button>
</li>
</ul>
<iframe
id="demo"
src="demo/circuit-original.html"
scrolling="no"
frameborder="0"
></iframe>
<h3>Okay, I saw what was happening... tell me what that means again?</h3>
<p>So the process goes like this:</p>
<h4>The Setup</h4>
<ol>
<li>
Define a grid that's X units by Y units, called "cells". This will
hold our images eventually.
</li>
<li>
Define a set of possible images for our options called "tiles", as
well as the rules for how these tiles can connect to each other.
</li>
<li>
Tell every cell in the grid that, by default, they are allowed to be
any of the options.
</li>
</ol>
<h4>The Algorithm</h4>
<p>
Now that we've set up our system, we can perform our algorithm over and
over until our system is solved.
</p>
<ol>
<li>
Find the cell with the smallest number of available options.
<ul>
<li>If there's several tied for the lowest, pick one at random.</li>
</ul>
</li>
<li>
"Collapse" the cell by assigning its state to one of its options at
random.
</li>
<li>
Tell all the neighbor cells their list of legal options is now reduced
to those matching this new cell.
<ul>
<li>
If any of those neighbors have their options reduced to zero,
reset that neighbor and all of its neighbors.
</li>
</ul>
</li>
<li>Repeat until all cells have been collapsed!</li>
</ol>
<h3>How do the tiles know what they're alowed to be next to?</h3>
<p>
Great question! You can provide rules for the tiles that explicitly say
which tile edges are allowed to go next to each other. My code checks
the pixels on the edges of the images and stores that to compare against
the other images, so it detects the rules automatically!
</p>
<p>
This doesn't always work: not all tilesets can have their rules
explained perfectly by a single method. Or at least, if there is one
such method, I haven't found it yet. But so long as the edges of each
matched image are identical, this algorithm will understand that as a
rule.
</p>
<h3>
Got it... I think. Is this useful though? It definitely looks cool...
</h3>
<p>
Yes! I mean, maybe not to everyone, but we can definitely find places
where this algorithm could come in handy. One example is creating video
game textures! Maybe you want to have a bunch of backgrounds for your
levels that should be similar, but not the same. Instead of sitting
there arranging all the tiles by hand!
</p>
<p>
Let's come up with a more entertaining example though. What if instead
of watching these images get drawn, we hid the whole process, and before
revealing the image, we rotated some of the tiles and allowed the user
to rotate them back by clicking.
</p>
<p>
Because we're generating the picture according to the tile rules, we can
be sure we'll always have a solvable puzzle as opposed to randomly
placing random tiles in random directions.
</p>
<p>
Oh and look! That game we just talked about is right here!
<a href="#">Not yet implemented</a>
</p>
</article>
<script src="index.js"></script>
</body>
</html>