Hi, welcome to this final
week of this course 3. We are going to be covering
new and final project. This is going to
be our project 5. This time around, we're
going to be looking at the wave function
collapse algorithm. The wave function
collapse algorithm, it's a very
interesting algorithm that is used for
procedural generation. It's an algorithm
that's actually inspired in quantum mechanics, and it's interesting
to note that there's a few variations out
there of this algorithm. But we're going to start
with a rather simple version of it and hopefully you
can expand on that. The main idea of this algorithm
is that we have a grid, we're, again using a
grid data structure. But each one of those tiles in the grid has possible states. As you can see, the
number 4 here represents the possible states in which each cell in
the grid can be. What we have down at the bottom is what we
would call the tile set or the possible tiles that any
particular cell can be, and we can define a
much larger number. We're going to see that we're
going to start with four, but we're going to move up to maybe 16 different tiles that we would offer
each cell to become. We're going to gradually reduce something that
is quite uncertain, meaning like a cell
that actually could be in four possible states, we're going to collapse
it into one single state. That's the first step
of this algorithm, is to collapse a cell. We're going to pick
a cell at random. We're going to pick, in this
case, a particular cell, and we're going to
just pick out of the tiles in the possible states in
which this cell could be, we're going to pick
one at random as well. We start with quite
a bit of randomness, but this will gradually see that the logic of the algorithm would give us
very consistent results. We pick one cell at random, we reduce its
possibilities from four to one by picking
one single tile, and basically we've
collapsed that cell. The first step of the
algorithm is achieved. The next step it's propagation. That cell would actually
look around it, will actually look at the adjacent tiles around it
and it will determine due to a logic of synergy or a logic of
compatibility between tiles, we're actually using
these colors black and white to demonstrate
certain connectivity. If you imagine that
this white line represents something
like a road, or represents a logic of
connectivity and you might want to have always that
connectivity working, you'll see that the
tile above the cell we collapsed it has only
one possible choice. There's only one
possible tiles out of the four tiles that
we've defined that could actually match and work in this
connectivity principle. The tile on the right
will have three options, the tile below will
have three options. The tile on the left actually
doesn't have any options. We'll see that
that's not an error, but something that we will
have to avoid just because the algorithm won't
be able to resolve that condition or otherwise we'll have some inconsistencies. But the algorithm
would actually pick the tile or out of
the adjacent tiles, the one that has the
least amount of options, but yet achievable options
in this case would be one, and we're going to process that tile again and collapse it. We basically do this two step process,
collapsing a cell, checking its neighbors
and its compatibility, and then collapsing one
of those neighbors. At that point, we
repeat the process. We expand the search to the adjacent neighbors
of that new tile, we collapse the new
tile and so on. We're going to be
going very gradually looking at how we can actually
construct this set up, construct the grid
and the tile set. Also, how we go gradually and understanding the
collapse function, the propagation function, and also the
compatibility function. How do we make tiles
that are adjacent to one another understand that they're in fact compatible
with one another. A lot of interesting things to cover throughout this week. I'll see you in the
next video where we're going to get
started. See you then.