This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Generating a Maze" Lesson
[00:00:03]
>> Brian Holt: Okay, so this was a warm up. [LAUGH] And now, we're gonna do the main event, which is generating a maze.
>> Brian Holt: Okay, so I think this is really fun. But I guess I'm kind of warped, so sorry, not sorry. We're gonna go back to working on mazes.
[00:00:29] This is gonna be a slightly different take on mazes, but in theory, you could use the same algorithms that we used to solve the previous maze. Is to solve the mazes that we're about to generate, which I think is kind of cool as well. So the idea is, in this particular case, we just want to generate a maze.
[00:00:49] We're not really generating a beginning or an end to the maze, we just want to design something pretty. [LAUGH] Like some sort of maze looking object. So down here you can see here, this is what we're going to generate, something that looks a bit like this, right? There are lots of ways of doing maze generation.
[00:01:14] And I'm just gonna show you one of them. But there are lots of really fascinating cool ways of doing this. In fact, I'm just gonna pull this up really quick, so you can see. This is an amazing blog post. I don't know who James Buck is, but cool stuff in this particular part of his blog post.
[00:01:31] He goes through and he actually, shows you all the different ways that you can generate mazes. So the one that we're going to do is called recursive backtracking. Which I again, found to be the easiest to teach and it also generates really cool mazes. Which is all I'm all about that, generating cool shit.
[00:01:50] So [LAUGH] I try not to swear during these, and it just never works out. [LAUGH] Anyway, so this is the one we're gonna be running, and it looks something like that. This is showing you, all the various levels of depth. And you can see here, this is what it looks like on a much bigger graph.
[00:02:15] Super, super cool and see you'll end up with mazes that look like that.
>> Brian Holt: But there's a bunch of them. You can run things like this. This one goes rows at a time, which I thought was pretty cool.
>> Brian Holt: That one kind of like random generation.
>> Brian Holt: This one, I thought was very interesting, that it does these.
[00:02:42] Makes quadrants of your graph, and then it divides it. I thought it was really cool. We almost did that one but we didn't [LAUGH]. Hopefully, you can, cuz that must be recursive, right? That has to be recursive, right? That's cuz it is.
>> Brian Holt: Because you're taking a large problem, and you're breaking it down into smaller and smaller and smaller problems.
[00:03:02] Until, it's a problem that you can solve, right? That is recursive, at its most basic definition. Yeah, cool, so it's a bunch of those. You should definitely check them out, super cool. We're gonna be doing recursive backtracking, so as if this course isn't self-referential enough. This is something very similar to what we've done previously.
[00:03:29] So what we're going to do is, we're going to start with some square. In this particular case, we're gonna start at that bottom left square right here. We're gonna call a function that's called randomizedDirections. So this algorithm, it's meant to generate random mazes, right? It's non-deterministic, you call it a bunch of different times.
[00:03:50] It's going to give you a different result every time and that's by design, right? We want it to be a random maze. Otherwise, it's not random, right? We drop the random parts, it's maze. [LAUGH] So you're gonna call randomizeDirection, and it's going to give you back an array of northeast, southwest, right?
[00:04:05] And it's gonna tell you, go do these in this order. So I wrote randomizeDirections for you. The reason why I did that is, so I can unit test, right? Because I need it to be deterministic, so that I can test you, right? But every single time that you call randomizeDirections, it's going to give you the directions that it wants you to go in, right?
[00:04:24] So in this particular case, I got west first, right? Which is left in this particular orientation. So I want you to go left first, which you can't, right? You're at the edge of the graph. You can't go left. So what you're gonna do is, you're gonna try and go north, right?
[00:04:41] So that's what you do here you go north. Now, notice that everything right now has a wall between it. And both this cell right here has a north wall, and this cell right here has a south wall. So when we go north, we're going to basically tunnel. So we're going to eliminate this north wall, and we're going to eliminate this south wall.
[00:05:03] So that's kind of the theme of what we're getting at here, is this tunneling mechanism that we're going to tunnel through various walls, until we've made a maze. So now, we've moved on to processing [1, 0], which is here. Notice that we did north, right? Which is why we went up, but haven't done South and we have not done East yet, right?
[00:05:27] That's because this is recursive, right? Cuz we'll eventually come back, right? Due to the nature of how recursion works, but we have not processed those yet. We're still in this particular level of the recursion, we haven't processed those yet. So now we're here at [1,0]. Also, for this example, I'm flipping on you,
[0,0] is the bottom left.
[00:05:54]
>> Brian Holt: It just worked out so much easier. Believe me, I did you a favor, it's
[0, 0]
>> Brian Holt: Also, did myself a favor, if we're being honest. Okay, so we're now at [1, 0], I'm gonna call randomized directions again, right? So it's gonna give me south first and then, it's gonna look down and see South has been visited before.
[00:06:13] I'm not gonna go there again, right? Cuz you're not going to revisit nodes. That's one of the rules. Recursive backtracking is you don't revisit notes. So I'm not gonna revisit it. It says, west next, west is off the map, so it's not gonna check there either. And then now, it says east, so I'm gonna go east.
[00:06:33] And again, I have not done north yet, I would come back later once we encourage to come back up and do north, right? So we go east, now, we're processing in this one, we can randomized direction, because it is east, which we can go south. You could have gone south, I thought-
[00:06:54]
>> Student: That's not a new method that's the same method as randomized directions, or is that something different?
>> Brian Holt: This is the same randomized method or direction.
>> Student: The text on the two steps is different? One is randomized directions, and one is randomized direction call.
>> Brian Holt: I believe you, but I don't see it.
[00:07:18]
>> Student: It's the one below that.
>> Brian Holt: Yeah, sorry. I'll fix that, thank you. So I did not mess this part up though. So randomize, you go east here and then, the first thing given here is east, which is to the right. Which is why you go here, and then south, and then west.
[00:07:43] And so, we end up here in this kind of dead end, right? So it's gonna try and go right here. Okay, so we've ran out of places to go, so we're going to go back up the tree. So we're gonna go here. This runs out of places to go, right?
[00:07:57] So it goes back up here, and then at this level. It was south north, but we still can go north in this one, right? So we're gonna go north and it's gonna just keep doing that, right? So this one, we'll call randomizeDirection but there's only one place to go, so it'll go here.
[00:08:16] And then now, there's literally no place left to go, so it's just going to go and return all the way back to the beginning and you've completed the algorithm. So by doing this algorithm, you're gonna be guaranteed, to reach every item or every place in the array, right?
[00:08:30] Every place in the graph rather. And the key here is, once you mark something as visited, it's not going to get visited again, right? So even though, if you remember here, we went north first, but we had not yet been east, right? But by the time, this gets all the way back to the origin point, if east will have been visited.
[00:08:53] So it's not going to go east, right? Does that make sense? Despite the fact that it wasn't originally visited by the time, it got back to that point, it had been visited, so it would not visit it. I'm gonna say, visit as many times, as I can. [LAUGH] Any questions about that?
[00:09:14]
>> Brian Holt: So that's the entire gist of it, you're just going to be doing this kind of burrowing. Now, let's talk about what this is similar to before. Well, we're going as far away from the root node as we possibly can, before we come back to it, right? That sounds a whole lot like depth first traversal, and that's because it's exactly what it is, right?
[00:09:36] You're basically going to be treating this cardinal plane, as again, like a tree. And you're just gonna go as deep as you possibly can, until you run out of things to do. And then, you're gonna keep coming up and then going back down, as much as possible, until everything has been visited.
[00:09:50] That's depth first traversal. So that's how you're going to apply it in this particular case.
>> Brian Holt: Questions conceptually, about maze generation?