Hi, welcome to this new video. We are going to continue
working on our project, which is the wave function
collapse algorithm. And we have been covering
a series of functions. We are almost ready to conclude the loop,
or one loop, of what the whole algorithm would actually
do and iterate over a whole grid. But we are at the point where we need
to calculate the lowest entropy. Let's understand what that means. Calculating the lowest entropy. As we are collapsing a cell and we start updating the neighbors
around that cell, we'll realize that suddenly the grid no longer has
the same number of entropy values. Entropy in this case refers
to the uncertainty or the number of choices that
are available for each cell, right? So as you can see in the example here, there's three cells that
have been collapsed, and there's a few adjacent cells around
that that have a possibility space of 8. And there's one specific
one that has four options. So that would be, in fact,
the lowest entropy. So we want to find that cell, right? We want to loop through the cells and
make sure that we are picking the lowest entropy cell to move and apply
the collapse function to that one and then move on to the adjacent tiles and
kind of start looping, right? But what happens in this calculation if we
have a series of cells that are tied for the lowest entropy value? So we're going to have to write something
that we have written already before, which is finding the lowest point,
let's say, or the closest distance. We've written algorithms like that, but
we're going to write it in such a way that we will also account for what
happens if there are multiple cells that are tied to the lowest value,
which is something that will happen often, because we will actually be evaluating
cells that has discrete numbers. Some of them will have eight,
four, two options. And it's likely that we're going to
have many cells that are tied for the lowest number. So we're going to collect those in a list,
and it's going to refer to the cells that have the lowest entropy, and
they could be multiple, right? The algorithm will pick one random,
one of those. It doesn't really matter which one. At this point, we just need to choose one. But we need to account for the algorithm
to know that there's in fact many cells that are tied for the lowest value. So we're going to continue
where we left off. We are working within, this is our grid
script, which we are calling environment, and tile, right. Basically the same thing that we have so
far. Let's look into the grid at this point. I would like to write a few
functions that are going to be, let's just comment them out here. First, I would like to write
the find lowest entropy. And I would also like to
display the lowest entropy. Just as the graphics that we're
showing in some of the slides, it would be nice to have a very clear
representation of which is the tile that is being evaluated, right? So we're going to do a little highlight
that would display the next value. So those functions,
we're going to write them here, I'm writing them as kind of comments so
far. So we're going to write
those functions first and then we're going to basically come back
and activate them in the run, right? So let's just write one of them here. So let's define, let's give ourselves
a little bit of space to work here. So let's call this find lowest entropy. And we are just going to,
for lowest entropy cell. We're looking for a cell, right? Self, right. And usually what we do with
the kind of closest point or smaller distance calculation,
we start with a very high number. So we do lowest entropy
would be something like, something quite large, right. And then we're going to say cell_x and
cell_y, because we're looking at the x index and
the y index of that cell, we're going to to say none and
none, right? So this is a way of describing
two variables in one line. And we're also going to start a list here, which is something that
we haven't done before. Several lowest,
it's going to be an empty list. So now we loop through all
these cells in the system. So for x in range(self.columns) and for y in range(self.rows) let's calculate the entropy here. The entropy is the length, remember that the entropy is
the number of possibilities. So we're going to check the cell x and y. Cells x and y, right? And the length of that list, right, because we know that each cell
refers to a list of possible states. In a way the length of that in
this case would be probably four. That would be the entropy, right? So now we can say, well, if it's bigger than one and smaller than the lowest entropy, right. So we're doing inline checking
that it's in fact bigger than one, which is the collapsed state, right? And smaller than the lowest entropy,
which is a very high number. We can agree that we're going to update. We will, we're going to reset the list. When I reset the list, the lowest entropy, It's going to become, The entropy, right? We're basically saying if we're below
the lowest entropy, let's just assign. I did that twice, sorry. Lowest entropy = entropy, right? We're assigning the lowest entropy to be
the current entropy that we're looping through. And the index of x and y,
It's going to become x and y, right? From the loop, right? And the several lowest.append, we're going to pass on a tuple, x,y The several lowest is going to contain
a tuple of the x and y index, right? Let me correct a little bit. I've been writing a little bit fast here,
so I'm going to correct my spelling, several. And I think here,
let me see if there's another one. Several, I think that's fine, right? This is the case in which the entropy is
in fact smaller than the lowest entropy, right? We want to write a second statement
that is going to be if it's tied, right? I'm going to explain this line,
which I didn't explain too much. Why are we resetting
the several lowest list, right? We're going to do a second statement,
which is the elif statement here Here, which is what happens if
the entropy is equal to the lowest_entropy, Right? This is the case in which we
found the lowest_entropy. Let's say the lowest_entropy initially was
10,000 and then we reduce it to 8, right, and now we're finding more than
one cell that has that number 8. So if our entropy is equal
to the lowest_entropy, all right, so we have a second cell
that matches that lowest number. Well, at that point, we want to
store that value because any time that we encounter more than one
entity with that lowest entropy, we're going to be storing it in
this several_lowest list, right? There we go, right? So we append to this list. If we, in fact, let's say we're
collecting all the entropies number 8, but we suddenly find a number 4. Well, that becomes the new lowest_entropy,
and we reset the list, right? If we had like three or
four entries tied to the number 8 and that list already contained
a few elements, but then we find the number four,
we want to reset the list, right, and start storing new entities in
this new created list, right? So in this way,
the several_lowest will always contain the most updated lowest and
it will only contain either one or more entries that are tied
to that lowest value, right? So there we have it. We've looped through the grid. So let's just find,
now let's check if the length of this, whoops, several_lowest. So this list, so we can check,
is this bigger than 1? And if it's bigger than 1,
it means that we have several tied lowest. And we could say that the cell, let's pick a random choice from the several_lowest. So pick one of them is what
we spoke about before. And here what we're going to be
updating with this function, which is finding the lowest_entropy. If you remember, we created all the way to
the top of the script these two entries, which is the next cell, and we use
those to start the algorithm, right? We started them here,
we say the next cell, it's going to be based
on this information. So what we're going to be
doing all the way down here, we're going to be updating this next cell,
and we're not going to be using this kind of
arbitrary numbers that we used before. We're going to be using the cells or,
sorry, the selected cell from this random. The first entry of that is the index,
the x, right, because we're looping through
the tuple of indices, right? The 0 and the 1, right? And then return a cell[0] and cell[1], else, so this is the case if there's more than 1, right? But if it's only 1,
we can just do something slightly, it's kind of similar than this exit or
this return. Just write it here and
then do some changes. So the next cell would be a cell_x, cell_y. And you might be wondering
what are these values? Where are we getting these from? Let's just double-check that in a minute. So these have been declared at the very
beginning of this function, right? So if we go here, these values all the way at the beginning
of the function were defined as none. But as we loop through the list,
we assign those, right? If we only find one entropy cell, those are already assigned to the tuple
x and y, sorry, to the x and y index. So we can use those straight away. So that's the function of
finding the lowest_entropy. We mostly use it to update
the next cell value, right? So we start with an arbitrary
number that is 15 and 7. And as we loop through the algorithm,
we find the lowest entropy point. So let's just call this algorithm
because this is not currently called. So here we could say self.lowest_entropy, Like that, right? And at this point, if this runs,
we could have a loop. We're going to see that there's some
errors and there's some kind of exceptions that we might run into, but
let's see what we have at this moment. So we run the algorithm and
it starts looping and it crashes. That's totally fine. Let's understand what's going on. So the algorithm will kind of gradually
go from cell to cell, each frame, right? Each frame, it's going to collapse a cell within
this kind of wave_function_collapse, propagate a search,
update the entropy of the neighbors, and then move down the line to the
find_lowest_entropy and then start over. And it's going to repeat this
sequence over and over and over. The problem is because we have
a system that has only four tiles, it is possible that the algorithm
doesn't run into a solution, that it kind of runs into errors, right? So we're going to expand these tiles
to all the possible states that this system can actually have so that we in fact find a solution to
the whole configuration, right? But we're going to do
that in the next video. Let's first conclude by
writing this display entropy. I would like to have
a highlight of which is the cell that is being
evaluated at a time, right? So let's just do a simple
visualization for that, right? So I'm going to call it
display lowest entropy. I'm going to write it all
the way to the bottom. So we have display_grid somewhere here,
but we're starting to operate
within the display_grid, here we can use a function to
display the lowest_entropy, right? So display, display_lowest_entropy(self, x, y), right? So what we're going to do is that
we're going to pass an x and y coordinate for that cell,
and let's do some exceptions. We're making sure that if x is not None, it might happen that at some
point the algorithm concludes and we reach a point where we cannot
run this visualization anymore. So I like having some measures. So the tile size could be
calculated by a float number, which is the self, .world x divided by the columns, right? And then let's just define the stroke. I'm going to do a red color with
noFill just to make it a highlight. And a strokeweight of 3 or, sorry, 3, r? I think that should be enough. And then we pushMatrix. We translate in x times the tile size,
right? Again, we're drawing
a rectangle on top of and y times the tile size. Let's define the rectangle
rectMode to be CORNER. And let's draw that rectangle at 0, 0, tile size, tile size, right? Because we're using it to translate
the coordinate we can use 0, 0 because we're using push and
push and pop matrix, right? And now we pop the matrix. If you like this to be shorter, you can actually type the coordinates
of the position of the rectangle and avoid the whole kind of
push popMatrix situation. But this would allow you to expand on
that visualization if you want, right? And then we go back I
would like to kind of, whenever I change the strokeweight,
I like to return the strokeweight because we hadn't been manipulating
the strokeweight anywhere else, right? So if I kind of change it to 3, I don't want the whole drawing
to become strokeweight of 3. I'm going to return it to 1, right? So we have this function that
would draw the lowest entropy. Let's see if this has any errors or
it's working. So let's just see here. So we're going to use self.display
lowest entropy, right? And we have to provide some arguments,
right? We have to provide the x and the y, right? And what is the x and
the y for this highlight? Well, we can use these global values, these values that we have for
the next cell x and next cell y. This is going to be at all times the cell
that would be evaluated next, right? So let's see if this visualization now,
it's actually showing us. Well, we're running into the same
problem of crashing at some point due to the possibilities, right? But we do have a highlight, right? So let's just run that a couple of times. Because of the randomness, it might be
that we run it a few more iterations. You see, like different times, we run
it more or less, but we often will find ourselves in a position of not finding
a solution to continuing the algorithm, right? So we're going to have to
provide more tile options for the algorithm to really
resolve this equation. If you run this algorithm at this point, you see that it runs pretty
quickly until it crashes, right? One of the things that I like
doing is trying to slow down the algorithm to the point in
which we could actually click and execute a loop or kind of a frame, right? I would like to implement that now. It's actually a really simple technique,
but it allows us to have some kind of control. So in the draw,
let's just create a global count and a t count and we're going to say if the count is smaller than the t count, I'm going to write this and explain what I'm doing in a minute. We are going to run the environment,
right? So this is the loop that is happening,
right? Let's comment out this background for
a moment, right? And, If we press a key, let's just create a bit of space here. Let's use keyReleased. So if we release a key
we advance the t count. So, So what we're saying here is that
let's just use the keyboard. So the algorithm by itself,
it's not going to start, right? Actually, let's just
start these values here. count=0 and t count=0, right? So let's understand what we're doing here. We're saying we're starting both at 0,
right? If we press the key,
we advance the t count so that will go from 0 to 1. At that point this algorithm will run and
execute, right? Or will start executing. What we want at this point is also make
sure that after we execute one loop, we say count +=1, right? So at this point the count
will match the t count. So every time we press a key, we give it an extra possible
step to move forward, right? And in such a way we will actually
be able to control with our keys, with the keyboard or you can use the mouse
or anything else changing a little bit the function to control how the flow
of the algorithm is executing, right? So you'll see that nothing happens,
but if we press once, you'll see, we collapse the cell and we find
the lowest entropy point, we press again, we collapse the cell and we find the
lowest entropy point and so forth, right? So we could actually kind of start
looping through until we crash it, right? So this is a way of like slowing down
the execution of the algorithm and allows us to debug a little bit
more clearly what's going on. So we're going to leave it here and
I'll see you in the next video where we're going to kind of continue expanding and
adding more tiles to the system. We'll see you then.