1
00:00:05,240 --> 00:00:10,560
Hi, welcome to this final
week of this course 3.

2
00:00:10,560 --> 00:00:13,820
We are going to be covering
new and final project.

3
00:00:13,820 --> 00:00:15,585
This is going to
be our project 5.

4
00:00:15,585 --> 00:00:17,780
This time around, we're
going to be looking

5
00:00:17,780 --> 00:00:20,320
at the wave function
collapse algorithm.

6
00:00:20,320 --> 00:00:22,360
The wave function
collapse algorithm,

7
00:00:22,360 --> 00:00:24,420
it's a very
interesting algorithm

8
00:00:24,420 --> 00:00:27,160
that is used for
procedural generation.

9
00:00:27,160 --> 00:00:28,980
It's an algorithm
that's actually

10
00:00:28,980 --> 00:00:30,630
inspired in quantum mechanics,

11
00:00:30,630 --> 00:00:32,640
and it's interesting
to note that there's

12
00:00:32,640 --> 00:00:35,800
a few variations out
there of this algorithm.

13
00:00:35,800 --> 00:00:38,320
But we're going to start
with a rather simple version

14
00:00:38,320 --> 00:00:41,240
of it and hopefully you
can expand on that.

15
00:00:41,240 --> 00:00:45,935
The main idea of this algorithm
is that we have a grid,

16
00:00:45,935 --> 00:00:50,170
we're, again using a
grid data structure.

17
00:00:50,170 --> 00:00:52,800
But each one of those tiles in

18
00:00:52,800 --> 00:00:55,500
the grid has possible states.

19
00:00:55,500 --> 00:00:58,220
As you can see, the
number 4 here represents

20
00:00:58,220 --> 00:00:59,680
the possible states in

21
00:00:59,680 --> 00:01:02,100
which each cell in
the grid can be.

22
00:01:02,100 --> 00:01:03,960
What we have down at

23
00:01:03,960 --> 00:01:06,680
the bottom is what we
would call the tile set or

24
00:01:06,680 --> 00:01:11,940
the possible tiles that any
particular cell can be,

25
00:01:11,940 --> 00:01:13,680
and we can define a
much larger number.

26
00:01:13,680 --> 00:01:15,280
We're going to see that we're
going to start with four,

27
00:01:15,280 --> 00:01:16,600
but we're going to move up to

28
00:01:16,600 --> 00:01:20,260
maybe 16 different tiles

29
00:01:20,260 --> 00:01:22,360
that we would offer
each cell to become.

30
00:01:22,360 --> 00:01:24,030
We're going to gradually

31
00:01:24,030 --> 00:01:26,790
reduce something that
is quite uncertain,

32
00:01:26,790 --> 00:01:28,390
meaning like a cell
that actually could

33
00:01:28,390 --> 00:01:30,320
be in four possible states,

34
00:01:30,320 --> 00:01:32,530
we're going to collapse
it into one single state.

35
00:01:32,530 --> 00:01:34,690
That's the first step
of this algorithm,

36
00:01:34,690 --> 00:01:36,170
is to collapse a cell.

37
00:01:36,170 --> 00:01:37,890
We're going to pick
a cell at random.

38
00:01:37,890 --> 00:01:40,710
We're going to pick, in this
case, a particular cell,

39
00:01:40,710 --> 00:01:42,350
and we're going to
just pick out of

40
00:01:42,350 --> 00:01:43,950
the tiles in

41
00:01:43,950 --> 00:01:46,090
the possible states in
which this cell could be,

42
00:01:46,090 --> 00:01:48,400
we're going to pick
one at random as well.

43
00:01:48,400 --> 00:01:50,550
We start with quite
a bit of randomness,

44
00:01:50,550 --> 00:01:52,250
but this will gradually see

45
00:01:52,250 --> 00:01:55,270
that the logic of

46
00:01:55,270 --> 00:01:58,550
the algorithm would give us
very consistent results.

47
00:01:58,550 --> 00:02:00,600
We pick one cell at random,

48
00:02:00,600 --> 00:02:03,550
we reduce its
possibilities from four

49
00:02:03,550 --> 00:02:07,040
to one by picking
one single tile,

50
00:02:07,040 --> 00:02:09,615
and basically we've
collapsed that cell.

51
00:02:09,615 --> 00:02:12,075
The first step of the
algorithm is achieved.

52
00:02:12,075 --> 00:02:14,200
The next step it's propagation.

53
00:02:14,200 --> 00:02:16,500
That cell would actually
look around it,

54
00:02:16,500 --> 00:02:17,720
will actually look at

55
00:02:17,720 --> 00:02:21,560
the adjacent tiles around it
and it will determine due

56
00:02:21,560 --> 00:02:23,500
to a logic of

57
00:02:23,500 --> 00:02:27,060
synergy or a logic of
compatibility between tiles,

58
00:02:27,060 --> 00:02:29,800
we're actually using
these colors black and

59
00:02:29,800 --> 00:02:32,880
white to demonstrate
certain connectivity.

60
00:02:32,880 --> 00:02:36,460
If you imagine that
this white line

61
00:02:36,460 --> 00:02:38,380
represents something
like a road,

62
00:02:38,380 --> 00:02:42,130
or represents a logic of
connectivity and you might

63
00:02:42,130 --> 00:02:45,940
want to have always that
connectivity working,

64
00:02:45,940 --> 00:02:48,275
you'll see that the
tile above the cell we

65
00:02:48,275 --> 00:02:51,255
collapsed it has only
one possible choice.

66
00:02:51,255 --> 00:02:53,130
There's only one
possible tiles out of

67
00:02:53,130 --> 00:02:55,250
the four tiles that
we've defined that

68
00:02:55,250 --> 00:02:57,850
could actually match and

69
00:02:57,850 --> 00:02:59,900
work in this
connectivity principle.

70
00:02:59,900 --> 00:03:02,060
The tile on the right
will have three options,

71
00:03:02,060 --> 00:03:03,990
the tile below will
have three options.

72
00:03:03,990 --> 00:03:06,310
The tile on the left actually
doesn't have any options.

73
00:03:06,310 --> 00:03:08,490
We'll see that
that's not an error,

74
00:03:08,490 --> 00:03:12,190
but something that we will
have to avoid just because

75
00:03:12,190 --> 00:03:13,750
the algorithm won't
be able to resolve

76
00:03:13,750 --> 00:03:14,820
that condition or otherwise

77
00:03:14,820 --> 00:03:16,545
we'll have some inconsistencies.

78
00:03:16,545 --> 00:03:19,355
But the algorithm
would actually pick

79
00:03:19,355 --> 00:03:23,380
the tile or out of
the adjacent tiles,

80
00:03:23,380 --> 00:03:26,080
the one that has the
least amount of options,

81
00:03:26,080 --> 00:03:29,710
but yet achievable options
in this case would be one,

82
00:03:29,710 --> 00:03:30,820
and we're going to process

83
00:03:30,820 --> 00:03:32,480
that tile again and collapse it.

84
00:03:32,480 --> 00:03:33,740
We basically do

85
00:03:33,740 --> 00:03:36,120
this two step process,
collapsing a cell,

86
00:03:36,120 --> 00:03:38,600
checking its neighbors
and its compatibility,

87
00:03:38,600 --> 00:03:40,890
and then collapsing one
of those neighbors.

88
00:03:40,890 --> 00:03:42,860
At that point, we
repeat the process.

89
00:03:42,860 --> 00:03:45,760
We expand the search

90
00:03:45,760 --> 00:03:49,245
to the adjacent neighbors
of that new tile,

91
00:03:49,245 --> 00:03:52,005
we collapse the new
tile and so on.

92
00:03:52,005 --> 00:03:54,960
We're going to be
going very gradually

93
00:03:54,960 --> 00:03:57,770
looking at how we can actually
construct this set up,

94
00:03:57,770 --> 00:04:00,820
construct the grid
and the tile set.

95
00:04:00,820 --> 00:04:02,480
Also, how we go gradually and

96
00:04:02,480 --> 00:04:04,340
understanding the
collapse function,

97
00:04:04,340 --> 00:04:06,180
the propagation function,

98
00:04:06,180 --> 00:04:08,000
and also the
compatibility function.

99
00:04:08,000 --> 00:04:10,560
How do we make tiles
that are adjacent to one

100
00:04:10,560 --> 00:04:11,980
another understand that they're

101
00:04:11,980 --> 00:04:13,990
in fact compatible
with one another.

102
00:04:13,990 --> 00:04:15,840
A lot of interesting things

103
00:04:15,840 --> 00:04:18,040
to cover throughout this week.

104
00:04:18,110 --> 00:04:20,520
I'll see you in the
next video where

105
00:04:20,520 --> 00:04:23,170
we're going to get
started. See you then.