Whilst recently on my holidays, I met a strange man, and he told me I had two minutes to create a maze that would take him longer than one minute to solve.

So I did this and send sold that though, Ugo.

And if you haven't guessed already, this video is about mazes, but more specifically it's about algorithms.

And this isn't out with them that I've loved since I was a child.

I first encountered it in the BBC Micro magazines.

When you have to type in the program's yourself from acres and acres of source listing, rarely did the programs actually work.

But this one always stuck with me because it's a fantastic out with them and it's perfect and it's complete, and we'll look at the details of it later.

And I think is a great example of programming and computer science at its absolute best.

Just in case you're wondering today I am living proof that programmers and code is actually go outside.

So there we go.

Now, before we get stuck into the code, I'm just gonna provide a quick primer for the uninitiated, and that is what is a stack because this is fundamentally a stack based algorithm and a stack can also be known as a life Oh, which stands for last in first out.

Some people may also call it the file.

Oh, it's the same thing.

And the idea is, I wanted to imagine a box like this on if we put some data into this box, it sits at the bottom.

And then if we put in some more data into the box, it sits on top.

But we can't access this data at the bottom anymore.

We can only take off the last bit of data that was put on.

There's a little bit of terminology.

We always push items onto the stack and we pop items from the stack on the top of the stack is always the most recent item that was pushed onto it now because this is a video primarily about algorithms, I'm not gonna go into the implementation of the stack.

There are many ways to do it.

Suffice it to say that if your system or your code uses a stack, it will behave like this.

Now the algorithm I'm going to talk about for developing a maze is known as the recursive backtracking on one sure of the origins of this algorithm, but it has been around for a very long time and has some fantastic properties.

But whenever you want to write code that involves a more complex algorithm than normal, it's always good to get the pen and paper out first, make sure you understand it.

So I'm going to go through it by hand here on this very simple mate.

And it's four by four.

And along the top here along my X axis, I've got four cell 0123 and I've got my y axis going down.

My plan is to fill this four by four array with the maze.

And I'm going to start by arming my stack with some data, and I'm gonna arm it with starting coordinate, which in this case, is going to be 00 So that's zero along and zero down on the mark, that cell as being visited.

So any cells that have a blue blob in the middle are going to be visited on.

I'm going to get a tick here, and I'll know when to stop my algorithm because I should have visited all of the cells at the end on out, therefore half 16 ticks.

Now I'm not going to make you sit through all of this.

I will speed up parts of it.

But it's a nice visual example of how the algorithm is put together.

Don't forget that even though there's only one item in my stack, the top of my stack is 00 on the algorithm goes like this from my current position, which is the top of the stack.

I've got to choose one of my neighbors randomly.

So from position 00 here, I've got a choice off this neighbor 10 or this neighbor zero warm.

I roll the dice, create a random number, and I select 01 So I set that cell to be visited, and I create a link update my visited count, and I've pushed the new location onto the top off my stack.

So now I repeat, I look at my immediate neighbors and choose one of them randomly that I've not already visited.

So my immediate neighbors consist of 00110 too.

Well, 00 doesn't count because I've already visited it.

After rolling my dice, I've decided that I'm going to move east.

I create a link to it.

Push the new cell onto the top of my stack.

Martin's cell is visited.

So one more time with commentary for completeness.

I take the top of my stack.

I choose a random, direct neighbor.

So in this case, I've got 10 21 01 and 12 I can't use this neighbor because I've already visited randomly choosing.

I'm going to go again to the east, push the new coordinates, the top of my stack and update my visited count.

So now I've let the algorithm run for a few alterations and we've hit a problem.

I now need to choose a neighbor.

There's not been visited before.

So my immediate neighbors air, of course.

Now 00 11 and 20 However, they've all been visited.

So I have no neighbors which haven't been visited.

I've now got to backtrack.

And this is where the stack became useful.

The stack contains a history of all the locations that I visited.

So the top of my stack is my current location.

And if I pop the top of the stack, I can move back one But note I don't remove anything from the visited column on here or face the same situation.

All of my neighbors are visited before, so I've got to move back one by popping off the top of the stack.

Now I'm back at this location.

This is the first cell as we're backtracking.

That's got a neighbor that I can actually plot into, which in this case is three to all of the other neighbors are not available.

They've already been visited, so I got little choice.

I've got to go here.

This is a new cell, so it becomes visited.

We pop the location onto the stack.

Now we'll let the algorithm continue again.

But now if it's a dead end again, as we can see, I've got no neighbors which have not previously visited.

So I've got to backtrack, and I do that by popping the top off the stack and using the top of the stack to set my current position.

And when I get to this location, I do have one neighbor I've not already visited, and it's the only one I can choose.

And so here I've now got 16 ticks, which is the number of cells that I visited.

This album is really nice because it guarantees completeness.

It doesn't matter how big my mazes it will fill all of the cells, and it guarantees that every cell can touch every other cell.

So it doesn't matter where you start in the maze, you guaranteed to get to the objective location within the maze.

Unlike all perfect algorithms, it's completely scalable, not just in terms of dimensions of the maze, but in how you apply.

In this case, I've got a single cell where I can visit my immediate neighbors north, south, east and west.

But it needn't be the case.

I could have many neighbors and applied the same algorithm and get a perfectly complete maze out of it.

Once you visited all the cells, it's up to your rendering algorithm to then try and draw the maze.

So in this case, I'm going to fill in wherever I haven't got a link between two cells.

So I'm going to draw a line here on here on here.

Once I filled in all the lines, I've effectively just developed the walls from my maze, at which point we no longer need the stack and we can get rid of all of this construction data, which leaves us with a really nice, albeit rather small, maze like structure.

Now let's see how we would do this in code.

I'm going to start with a blank in Maine program, as I always do, and I'm going to pull in the one lone Coder Consul game engine, which you can see in the video marks in the little tab above.

Now, since this is the first video I've done that uses the technology, I'm only going to go over it very briefly because you can look at that other video for the finer details.

But ultimately, I need to derive a class from my counsel game engine, which just handles all of the consoles stuff for me.

If you've seen my other videos, you'll know that all of my programs involved creating a screen buffer and using get a stinky state to emulate some sort of game engine.

I've wrapped that up into a nice, tidy package that I've called the one lone code, a console game engine and their two functions in this on user create, which is where we do all of our definitions and creating of resources and on user update, which is basically a per frame function.

So this is where we put all the fun stuff, and implementing the class couldn't be simpler.

We just create the variable.

We construct the console to the dimensions that we want.

So in this case is 100 60 characters across by 100 wide, and each council character is going to be eight by eight pixels, and then we call the start function.

This is only for Windows.

The construct council function calls things to the Windows operating system that define how the consul's look.

But you shouldn't let that put you off.

If you're a limit to a Mac user, the algorithm is still going to be platform independent Now for my maze algorithm.

I know that it's fundamentally Stack based, so I'm going to include this stack from the Standard Library and in the game class.

I'm going to create some variables that define the maze.

Specifically, my maze has a width ah, height, and I'm going to create an array here dynamically, which stores a value for all the cells, and I'm going to use this value to tell me which neighbors the cell is connected to.

And so to make this a little bit more readable, I'm going to create on enumeration here, where I'm defining some constants.

So for any given cell, I can tell whether it's connected to its neighbors because the inter value that represents that cell will contain the bit set in the appropriate locations.

And if I visited the cell as well, I know that the algorithm also requires me to keep track of how many cells have already visited.

And finally, of course, I'm going to need this stack, and this might use something a bit new to the one long code of videos I'm using.

The pair type A pair allows you to store two things at the same time.

I could create a structure here myself that stores an X and A Y corners, but I'm going to use the pair anyway.

Why not?

It's 60.

And so I have a stack that stores an object which type pair, but the pair is a template ID to store to introduce.

The 1st 1 will be the X coordinate on the 2nd 1 will be the Y coordinates.

Now I'm ready to specify some parameters that define my maze, someone to set the width of the maze to 40 on the heights to 25.

I've already pre determined that this dimension looks quite nice on the screen.

And because I'm I want to play with these numbers later, I'm going to allocate the maze memory dynamically based on the dimensions we've just set.

It's also quite important that we set all of the elements in the Meseret to zero to begin with.

I'm using the memo set command for this.

No need to specify the starting conditions for my maze.

The stock has to have something in it to begin with.

So I'm going to push on to that, a new pair and I'm going to use the make pair function.

We're going to start like I did when I was drawing it by hand in the top left hand corner, which means I also have to set that cell to be visited and conveniently the top left corner off.

My Meseret also happens to have the index zero.

I'm going to use one of the bits that I sat before on because I've already visited one cell I'm going to set my visited cell count 21 As you can see, there is very little required to initialize this algorithm, but it's important either.

Before we get stuck in with the algorithm.

I think it's quite important we have a way to visualize it that way.

We know if we're coding it in the right direction.

So to begin with on the unused update function, I'm going to clear the screen.

And that's involved, basically drawing space to my console in all locations that screen width and screen height from the top left corner.

And as discussed previously, Mei Mei's consists of a two D array off cells.

So I'm going to it straight through each of the cells makes with inmates height and for each cell in the array, I'm going to check.

Does the interview half the cell visited?

Bit set?

In which case, if it does, we draw a white pixel or a white block character to that location on the council or with your blue one.

Let's just have a quick look what that looks like.

Well, it's a blue rectangle with a tiny little white dots.

That's good.

I mean, that indicates that our maze off the dimensions 40 by 25 does have 40 blue characters by 25 blue characters, and the one cell we've already set to visited in the top left has been set.

However, everything looks a bit small and there's a problem.

We don't have anywhere to draw the walls.

I'm going to introduce the notion of a path wit, which will specify how many onscreen consul character cels represent a single cell in my maze.

So, for example, if the width is set to actually occupy a two by two block off cells on the console, which represents one cell in my maze, then I can surround the two sides to the east and the south off that one cell with blocks that represent wall.

Here's my two by two cell Here is a two by two cell, and here is a two by two cell, and we've now got position to at walls.

I only need to concern myself with walls at the east and south side off the cells, because if two cells are linked, then this cell loses its western wall.

In this cell, loses eastern wall.

AII the wall is shared between them and of course.

The same applies for north and South, so this is now cell position 00 on this would become sell 10 on this one would be 01 on 11 But the relationship to the council characters underneath is now the cell coordinate times two to get us to hear, and we always plus one to give us some wall at the end.

And, of course, that happens in both access so we can consider then a whole complete cell with walls and exits, and everything else is a multiple of path width plus one.

It's not another variable to our class.

Pathways on will define this as being three, so our may sell will represent three council characters across on one for the wall.

We then need to modify our drawing algorithm to accept this change in scale, so every position becomes multiplied by path wit plus one.

Let's take a look.

Well, we can now see that it spread out across the whole console, which is good, but it's not filled in the individual cells, which is bad.

Therefore, I need an additional loop inside my maze Li pin that's draws in each cell so for each cell in my maze.