Simple Maze Generation Tutorial

[Music] hello fellow scratchers do you like mazes ever wanted to generate your own i'm griff patch and today we are going to learn how to do just that mazes are basically one long twisting corridor from start to finish but with branching corridors with dead ends that confuse those attempting to solve them so the question is how do we get scratch to draw one well we'll begin by deleting this sprite one and since we now have the stage sprite selected let's go into the backdrop background editor and switch to the bitmap mode fill the entire screen with pure black this will be the colour of our walls and we'll carve out the maze from this blank space next we'll create a new sprite naming it bounds the sprite will define the maze bounds we want to draw a non-filled rectangle with a pen width of something like 40. that's quite fat and i'll draw it out such that it sits just inside the drawing canvas border like so once i'm happy with its size i'll just reposition it on the stage by setting both its x and y position to zero now we'll add another new sprite naming it maze this will be responsible for all the maze drawing so what costumes will we need the first we shall name tile and we'll need to be quite accurate drawing these costumes so zoom right in with the plus button such that we can see only a handful of the checkered grid tiles remember each grid tile is 4x4 pixels in size i'm choosing my maze floor tiles to be pastel yellow i'm selecting a transparent pen color though and then we can draw our square that is exactly eight by eight pixels that is two full grid squares wide and tall then to ensure it's centered just drag it until it snaps in place next we will draw the main costume that we need and this is a coverdoor costume we'll duplicate the tile costume and name it corridor now using the selection arrow tool we select the yellow rectangle and then pull out the right hand side to make the rectangle 5 grid squares long that's 5. that will be about 20 pixels wide and eight tall make sure not to center the costume this time round as it wants to be just like this now to help us understand how the maze is being drawn we'll add a thin red border to the corridor costume and also add a small red arrow on the left hand side like this okay now don't do this in your project but let me just copy this rectangle to show you how we are expecting these costumes to fit together in a maze you see the start of one corridor will stamp directly over the end of the previous one like this when in this formation you can see that the length of a single path tile will actually be three grid squares that is 12 pixels wide we'll need that number shortly so remember it 12 pixels i'll just delete these parts to tidy up and we can look at how to actually script this okay move into the code tab and we'll begin by clicking on extensions down here and adding the pen extension we'll need this to draw the maze as we're definitely going to exceed the clone limit drag in the arrays all block this is used to clear the screen of anything we've previously drawn we'll trigger this right away of a when green flag clicked hat block so firstly how big is our maze going to be it'd be nice to have a way of setting this so remove the my variable here and make a new one naming it tile size for all sprites and then set it to 40. that is our tiles are going to be 40 pixels wide that's nice and chunky for starters now bring in a set size 2 block okay so how are we going to size our sprite so that is working at the selected 40 pixel size where this size block expects a percentage hmm tricky but no problem let's do the math setting the size to 100 would mean our tiles are of size what was it 12 pixels remember that's what we said so if we divide 100 by 12 it will be 12 times smaller which would make it one pixel wide rather than 12. good from here it's easy to make it 40 pixels we just simply multiply it by tile size aha we win next let's position the sprite where we want the maze to begin go to x zero y of zero and we'll point in a random direction ah but we only want to point directly up right down or left nothing in between to do this we need the direction to be multiples of 90 degrees so multiply 90 by pick random minus 1 to 2. if i run this script you can see that this gives us the directions minus 90 0 1980 perfect now we want this corridor to build up in length so we'll make a new custom block naming it draw maze for now we'll leave the run without screen refresh clear and we'll drag this new block to the end of the green flag script so we want to draw using a corridor costume so switch to that and then right away we use the pen stamp block so with an imprint of the costume left behind on the stage we can move the sprite forward by tile size like so clicking the draw maze script over and over demonstrates this working what will make it even better is if the corridor had bends so use a turn right block after we move either we turn 90 degrees left or keep straight or 90 degrees right that's just 90 multiplied by random minus 1 to 1. we can test again by clicking the green flag and then repeatedly clicking the draw maze button oh yes this is looking really cool note that because we are stamping only the last corridor costume on the stage is actually a sprite right enough clicking to build up this corridor we need another draw maze block that we can drop in at the end of the existing draw maze script this is now one of those dangerous recursive scripts i've mentioned before since the block is making use of itself be warned if this was running without screen refresh it would reduce your computer to a crawl so don't do that yet what this maze needs first is to respect its bounds we'll stop it in its tracks using an if here around the draw maze to allow it to continue to draw the sprite must not be touching the bound sprite that's the rectangle around the level if i run the project you can see that the corridor does indeed stop when it gets to the edge good now we also do not want the corridor to cross over itself so extend the sensing check with an or and check for touching color and select the corridor color using the color picker but if we run the project we can see that we have a problem the maze now stops right away and why well look if i move the sprite a little out of the way you can see that the corridor is of course already touching the yellow from the previous corridor tile we can't have that we'll need to add a special sensing costume that doesn't overlap the corridor tile we are coming from open the costumes tab and duplicate the corridor costume select the rectangle and carefully drag the left hand edge to the right until the corridor is 2 by 2 grid squares the arrow to the left shows where the previous covered or tile will end this can be deleted and then colour the block red so that we can identify it from the corridor colour we can name this costume detector now click back into the code and we'll switch to the detector costume before we perform the touching sensing in this if i'm going to run the project again now and we find that it's working once more and also there we have reached a point where the corridor has collided with itself just like in the game's snake so obviously we don't actually want to stop when this happens it would be much better if we could try a different direction to turn in instead well at each point there are potentially four directions of travel we can add a repeat 4 around the if sensing condition and we can turn right by 90 degrees as the last script in the repeat loop so if we fail to move forwards we can certainly now turn right and try the next direction let's give that a run oh now what are we seeing here the corridor travels nicely winding around but it still appears to be running into trouble and stopping in a mad spin okay well the reason is simple sometimes the corridor goes head first into a dead end of its own making in this case it doesn't matter how many times we turn around there simply is nowhere else to go so how do we get out of this one the answer is we don't instead we need to back up until we find a place where we can begin drawing again the difficulty is how do we know where to back up to since we randomly were turning left and right as we went okay for this we need some help from a custom block with input variables as unlike normal variables these do not forget their values when we return to them let me show you what i mean make a new custom block naming it try directions from and we'll add a numeric input named start direction we can move the turn right script and everything following it into there and replace with a call to this new tri-directions block but and here is the clever bit we pass in the current direction of the corridor note this is the direction before we have made any random turns the magic of this is that we can point back to the start direction at the end of the script guaranteeing us to be pointing the same way we were when we came in this means we can now safely move backwards by tile width using a subtract block from zero to backtrack us to the previous tile position the magic of this idea is that even when we now reach a dead end and all four turns come back blocked we now reverse the turn that led us here and move back to the previous position this in turn takes us back to the previous tri-direction script and will continue turning around to see if there are any other directions that are yet to be travelled this process is now fully recursive and should leave no turn unchecked which means running the project now yields a rather awesome sight wow just look at that did you see us backing up the pathway and then finding a new possible turn there and that's it the whole screen has been filled and the maze is complete the script ends with the maze sprite back at the beginning where it began and nowhere else to search well x marks the spot right so i'd suggest we swap out the coverdoor costume for a small x here to finish off the effect switch to the costume tab and we'll make a new costume naming it x now draw a sweet little x using a 3 pixel wide line it should be around six to seven pixels in size mine is just over the size of one grid square and i'll select and drag it to ensure it's nicely centered while we're here we might as well click into the cold or sprite and remove the arrow and the red border from the costume now back in the scripts simply switch costume to x after the drawing of the maze we can run the project again now and see a much cleaner maze form and then to finish it off there's the red x right in the center where we began that is awesome so being the naturally curious type of person you are you may have already fiddled with the tile size variable we set up at the beginning well if you haven't now is the time after all the smaller we make the tiles the more maze we can fit on the screen let's change tile size from 40 down to 30. and here we go i can see there's more to the maze and it's working great i have to say though it's taking its time perhaps we can make this run faster by editing the define draw maze block and making it run without screen refresh so how fast will it draw the maze now click the green flag wow did that finish already i'm just clicking the green flag over and over i can't get enough of this no wait i can because now i want to set the tile size down to 20. yikes still fast so a tile size of 10 then we have reached the limit of our sprite costumes now you can play around with changing the costumes to bitmap or adding a transparent rectangle around them but to be honest if you stick with a size no smaller than 12 you'll probably be safest for now however to continue this tutorial let's back up the tile size to 20. interestingly you may have noticed that the maze produced has a rather zigzaggy pattern this is caused by the random turning left and right with every move forward perhaps it would be nice to make corridors that have a preference for straightness here's the script that turns us left or right so if we didn't run this script then the corridor would be completely straight but obviously we need to turn at some point so surround this turn with an if and compare pick random one to ten with one this means there is a one in ten chance for the corridor to change direction okay run the project oh my gosh i think we overdid it these corridors are very long and very spirally i rather like it but let's tone it way back down we'll use a random one to two instead there that's a good balance and it gives you another fun variable to tweak so let's take stock we have a resizable maze and the center is marked off with an x what we lack perhaps is a start to the maze how about we find the longest possible passageway from the center and stick the start there to do that we'll need to keep track of how long each corridor is as we draw it and simply remember the furthest point reached we'll add four new variables to achieve this furthest x for all sprites and furthest y also for all sprites and then furthest distance for this sprite only and distance for this sprite only we can set both furthest distance and distance to zero before drawing the maze as we've yet to travel anywhere it'll be easier to create a custom block to record the distances make a new block naming it record distance then if distance that is the current distance traveled is greater than the furthest distance traveled then we set furthest distance to distance furthermore we also record where we are when we recorded this distance by setting furthest x to x position and setting furthest y to y position good now come over to the draw maze script now every time we move forward we change distance by one and when we move back we change distance by minus one this will keep track of how far we've traveled from the start of the maze and now we can pop in our record distance block just after we increase the distance variable here that means if this is the furthest we have traveled so far then it will record the position in furthest x and y that is all we need to find the furthest point now we just need a way to mark it on the screen so let's add a broadcast to a new event named maze generated after everything else has run in the green flag script create a new sprite named player and i'll draw a costume of a small blue circle mine is seven by seven pixels and it sits nicely within the two by two grid cell i'll make sure it's centered now to the code this is simple when i receive maze generated then using the of block in the sensing category we set size to the size of maze this keeps us the same size as the maze tiles next to position our player sprite at the furthest point from the center of the maze we go to furthest x and furthest y now i'm excited to run this because i love it when a simple script can solve a seemingly difficult problem and there we go we are seeing the blue player dot being positioned at different places on the maze and all looking very good yeah this is really really fun i can feel my eyes trying to trace the route between the start and the end to see if it is the longest path i guess it's this way then here i did it pretty good there well done me okay so it's fun enough using my mouse but it would be even more fun if we could control the player sprite using the keyboard yeah let's gamify this project now this tutorial isn't so much about player movement many of you will have lots of experience doing this part yourselves so don't feel you need to do it the same way as me feel free to use your favorite scripts for player movement but i'll quickly code something up so that we can get the job done i'll start by hiding the player sprite when the green flag is clicked then adding to the when i receive may's generated script i'm going to wait until no keys are being pressed this is to ensure that we don't move at this very start of the game until all the keys are released now we can show the player sprite before starting the game loop repeating until we are touching the maze yeah touching maze gives the wrong impression it doesn't really mean we are touching the maze at all what we are touching is the x in the middle of the maze as that was the last costume the maze sprite was changed to and that's going to be our goal then on touching the mazes x we exit the repeat loop hide the player and broadcast a new message of reset maze next up create a new custom block named move with two inputs of dx and dy run without screen refresh to ensure our player's circular shape doesn't get caught on the edges of the maze we can add a second costume a small centered square naming it square and while i'm here i'm going to name the circle as player we can switch to the square costume and move the player sprite by dx and dy in the x and y directions now check if we are touching the color black and if we are we move back to where we came from using zero subtract dx and the same for dy like so finally set the costume back to the player circle costume good so all we need to do is detect the player key presses right i'm going to do this next bit in a slightly different way to usual but nothing crazy we create a new block named move with speed with an input called speed running without screen refresh and what i'm going to do is rather than detect keys and then move in big steps i'm going to repeat right here once for each pixel i want to move use a ceiling block to round our numbers up to the nearest whole number and then pop speed in here now comes the keypress scripts drop in two calls to the move block the first is for moving left and right and we'll use the trick of key right arrow pressed subtract key left arrow pressed to give us the one for right and minus one for left we can duplicate this and use it for the right hand input of up and down i'll fill in zeros in the other inputs so the trick here is that these moves are small just a pixel at a time but we loop the movements a number of times each frame to allow us to move further we just need to drop a move with speed block into our game loop over here and decide how far we can move each frame it's a good idea to move relative to the size of the level so perhaps we'll move by tile size divided by eight that will mean it takes eight frames to move across each tile of the maze you may want to play around with this value or do things completely different it's up to you wow we are almost done we should just take care of this last broadcast to reset the maze click into the maze sprite and add a when i receive reset maze hat block and then move the entire script from under the green flag into there and we'll pop a broadcast to reset maze to trigger from the green flag and by jove i think we've done it let's click that green flag and give it a test drive okay so the wall collisions are working great i can't pass through them and i'm not getting stuck on the edges or corners i can move right up against the walls and still move around so far so good i don't feel the maze is overly taxing yet but you never know when you might have gone wrong when there are certain choices ah yes uh i have gone wrong hold on let me back up a bit it must have been that turning back there and this oh no no no no this way oh poop no back this way yeah this is looking good ah no um no it's okay here we go oh phew ha we did it and the game resets and we have a new maze to solve wonderful so how about setting tile size down to 12. ah that makes things even more tricky you know what would be really good is perhaps a timer or something well i'll leave that up to you yeah this maze is a lot more hard to predict let me speed this up yay i got there in the end now before we finish this tutorial let me just show you one more cool thing you can do if we click into the bounds sprite and add some shapes to the costume see how the maze shape now is bounded to fit around these shapes that's really cool it's even better in black look we can do circles or perhaps letters yeah i love this i know you guys are gonna have a lot of fun with this too and with that that brings us to the end of this tutorial i hope you've enjoyed following along and have made some excellent mazes of your own if you enjoyed this tutorial then smash the like button and don't forget to subscribe to the channel to avoid missing my next exciting video thanks for watching and scratch on guys you

Channel: griffpatch

Views: 458,833

Keywords: griffpatch, script, labyrinth, maze, coding, how to, pathway, random, generate, generation, create, game, make, scratch3, scratch, programming

Id: 22Dpi5e9uz8

Length: 25min 29sec (1529 seconds)

Published: Mon May 10 2021