Pathfinding a Maze using Lists

Key Takeaways

[Music] hello fellow scratchers i'm griff patch and today we are looking again at our exciting pathfinding project in scratch and since last time we've been set quite a challenge to pathfind our way through this detailed vector maze seriously wow i love it this is going to be fun our previous pathfinding tutorial had us tracing the shortest routes to a level using these coloured arrow clones the reward for using clones was simpler scripts but due to the 300 clone limit it meant we couldn't make our levels any more complex than you are already seeing here also because we use the colour of the tiles to direct the scratch cats through the maze we also ran into other problems where are these cats going the cats could cover up the coloured tiles so that they didn't know where to go oh no disaster but if we don't use clones how else can we keep track of the pathways luckily if you've been following my recent tutorials then you'll also have seen an episode on grid lists this technique allows us to scan a level at high resolution into scratch lists and once there we can ditch using clones and sensing blocks for the pathfinding and switch to using the grid lists alone yes these two tutorial projects brought together could make a truly powerful combination so before you can try to tackle this project yourselves make sure you have watched the two previous videos we will need the completed projects available to us before we can tackle today's challenge together you'll find a link to the first pathfinding and the gridless tutorials below this video guys let's get scratching i'm going to bring up my grid lists project first i just want to point out that the grid sprite is the one that does all the work here is a level sprite this is the costume being scanned to a list if i run the project oh yeah look at the detail on that i cannot wait to get that into the pathfinding project all we need to do is open up the backpack and drag in the entire grid sprite next up load up the simple pathfinding tutorial project i'll just confirm that the project is all working yep perfect i have to say that the color arrows although not practical in a real game do look really nice now i don't want to destroy this previous project and i advise you to do the same so go to the file menu and save the project as a copy now give it a new name like pathfinding with grid lists yeah so before we begin bringing our projects together let's have a quick recap of the sprites and code starting with the stage two scripts in here the first spawns new cats with the space bar useful the second was a simple hack we tried to use it to hide the pathway clones it worked to some extent but we are going to do things better this time round so just delete that now next we have the cat sprite basically there are two forever loops in here that run for each cat clone the first moves the cat forward looks at the colour of the arrow below its feet and turns the cat accordingly the second forever loop is waiting for the cat to touch the apple before despawning it now the apple sprite this is just looking for mouse clicks in case the apple is moved then it broadcasts that we need to recalculate the shortest routes through the level the may sprite yeah this is my favorite kind of sprite it really doesn't do anything less to explain right however remember that our grid list project is scanning a sprite named level let's rename the sprite to match that level good and lastly the path sprite this is where the magic happens right from the first green flag click the first path sprite is positioned at the apple the target of the pathfinding and then the sprite tried to clone itself in all four immediate directions upright down and left this is only done though where no collision with the level occurs so as this process repeats the pathway flows outwards filling every reachable point and leaving behind a followable trail of arrows back to where they started the apple nice we are ready to bring in the grid scanning sprite but just while we are here in the path sprite separate off with me the find path block from the when green flag clicked we are going to want the new scanning scripts to run first so open the backpack and drag in the grid sprite right there are a few things we need to check and update the set tile width here is setting how large each tile in our tile grid is in pixels the current pathway code uses 32 pixel tiles for now then let's set this to 16 that will effectively quadruple the number of tiles in use an impressive start next i want to double check in the define scan script that the touching block indeed is set to scan the correct level costume just as we have set it in this project yeah that's good it has to be exactly the same capital letters and all just change it here if it's not okay then let's run the project and check the initial scan works there yes the scan is picking up the level walls nicely and you can see right off that the detail is looking a lot better if i move the apple around you can see that the pathway tiles created are much bigger so what did this level scan do the drawing of the purple tiles is not the purpose no that's just so that we can see that the process worked the important thing is that the level has been encoded into the grid list we have hashes representing walls and blank rows for empty space what i am thinking is that going forward we not only store the level walls in this list but we might also store the coloured pathways in here too these blank rows could easily be used to store the directions a cat needs to move in to reach their target apple that would then remove the need for the clones and the colour sensing and keeping everything neatly in the grid list i'm excited to try this idea but to make things easier for our pathfinding going forward we need to make one tweak you may remember that in a grid list if you move across the grid and off one side mathematically you end up wrapping around and appearing on the opposite side just one row up well to fix this i'm going to add an extra column full of walls up the right hand side of the grid level this will stop anything wrapping around while we try to pathfind later on so add 1 to the grid columns variable that's our extra column then come down to here where we're scanning the level we don't want to scan that last new row so subtract 1 from the grid columns no we want to always add a hash for the last column so add a hash to grid just before we move to the next row with a change y okay give the project a quick test there should be no visible change after that as the new wall is off screen to the right yeah good now back in the code i'm just looking at this second green flag script in the grid sprite this was added to allow us to draw new tiles into the grid using the mouse we won't be needing that this time so i'll separate it off from the hat block to stop it running what else do we have in here ah get tile at x y it's amazingly useful given a position on the screen x and y it gives us back the index that is the row number in the grid list that represents that tile so it also gives us the value of the tile itself super useful equally useful is the position at index idx script this does the opposite taking idx a row number in the grid list and setting the current sprite to be positioned at where that row represents on the screen we are going to need these in our updated pathfinding sprite so let's drag them both into the path sprite now so lastly once our scan is complete and the grid list populated we add in a broadcast for a new event named begin this will trigger the pathfinding scripts to begin and it's time to get to work click into the path sprite straight off we need to move the two new custom blocks into some free space we'll make use of these shortly okay so we separated off the green flag script earlier let's replace this now with a when i receive begin event hat block and reattach the find path block this will now run once the level has been scanned right costume sizes if we check out the costumes you can see our original pathfinding tiles were 32 by 32 pixels in size with a small gap between tiles but our new grid scanning sprite uses a variable named tile width to store the desired width of our tiles in pixels we should therefore resize the costume from 32 pixels to match this new size so set size to 100 that's the full size divided by 32 that reduces our size down to one pixel wide and multiply by tile width to bring it back to the size we want cool so let's follow through the scripts and see what we need to change to make a safe transition from sprite sensing with clones to grid lists find path is the first script that runs positioning itself at the apple and here we have a touching block this is the first sensing block used and is here to prevent our pathways being traced if the apple starts over a wall instead of using the touching block we must use our very handy new custom block get tile at x y and feed it the x position and y position of this sprite let me pull up what this script does over here you can see it sets the tile variable to the item found in the grid list at the given screen location so instead of the touching level block we can now replace it with an if tile equals hash remember hashes represent walls in this case we don't want to continue so i'm going to hide the sprite and stop this script however if not then we can begin plotting our pathway through the level yay see that's a pretty straightforward change isn't it our get tired xy is like a go to xy and comparing tile to hash is like the touching level block only it runs way faster in scratch which is rather handy and a good reason why advanced scratchers use lists so much and now to understand the following changes to our code we are going to need to understand a little bit more scratch type theory did you know that scratch never runs two scripts at once nope scratch is what we would refer to as single threaded you can ask it to run lots of scripts apparently running simultaneously across many sprites and clones using hat blocks broadcast receivers and loops so how can it be scratch only runs one at a time that can't be right the answer is that scratch is just really good at running scripts in the right order one after the other and it keeps track of what to run when in its own internal to-do list whenever a broadcast is made a key is pressed or a clone is created scratch takes note of what scripts will need to be run where and adds them to the bottom of its to-do list this means that when scratch does get around to choosing its next script to run it will simply take the one from the top of the to-do list and off it goes this way scripts are always run in the order they were requested this is exactly the process that makes our original pathfinding scripts work with the clones as the order in which the when i start as clones run it's the same order in which the clones were originally created that is each new clone created has its when i start as a clone script added to the to-do list ready to run but it won't run until all the other when i start as clone scripts above it on the list have run first this behavior is exactly what makes the pathfinding scripts work therefore to replicate this behavior without clones we will make our own to-do list make a new list naming it to do indexes for this sprite only okay we only just put this script back but actually delete it for now what we really need to do before starting down this thrilling new road is to first clean up the grid list why is that well our pathfinding scripts will be stuffing all the path directions into this grid list so when the apple is later moved and we want to recalculate pathways again we will need to remove all the directions from the list leaving only the walls the hashes so get out your broom and create a new custom block named clean the grid list run without screen refresh we'll begin by erasing all the stamped costumes from the pen canvas next we'll delete all of our new to do index list yeah we're going to clean things up nicely so to keep track of things as we clean the grid list create a new variable naming it next index for this sprite only set it to zero and begin a repeat loop this loop wants to run over the entire grid list that would be grid columns multiplied by grid rows although i could have just used the length of grid now i think about it now change next index by one this will allow us to work our way through the entire grid list one row at a time so we need to check whether the next grid item is a wall if item next index of grid is not equal to a hash not a wall then we are going to replace the same item with a question mark we'll use question marks to mean tiles that are not walls that are yet to be visited by the pathfinding script there after this is finished the entire grid list will be filled with only hashes and question marks so that's the cleaning scripts done so come back to the define find path script and pop in the clean grid block we just made so we are ready to take our first step in a new path find we'll mark the spot in the grid list by replacing item index of grid with zero remember index has already been set when we use the get tile at x y just above so it's the position of the apple in the grid list we record a direction of zero it doesn't matter which direction we start with as we've already reached the target and now because we've updated the grid tile we also add index to our to-do indexes list wait what so this is the fun part where we are saying we want to come back and process this tile at our next convenience but because it's added to the bottom of the to-do list everything above it in the list will be actioned first i think we can safely run our project here and when i do we can see an item get added to the to-do list that's a good sign that things are working also if i move the apple and run the project again i can see the index changes as would be expected okay make sure you are still in the path sprite what we need to do next is start working through our to-do list yeah it's only got a single item in it at the moment but very soon that is going to grow so repeat until the length of to-do indexes equals zero that will keep us looping there until there is no items left to be actioned after which we can just hide this sprite what do we do inside the repeat loop we put back the try moving in directions block excellent so now we have a loop that works its way through all the tiles that are waiting to be processed we therefore no longer need these scripts triggering the same thing when starting as a clone so delete that we also don't need this when i receive reset path again we don't have any clones to delete oh and this when i receive hide path that's trash 2. right back to our define try moving in all directions script as you might expect things have got to change separate off the entire script and keep it for reference let's begin with the costumes themselves these are 100 cosmetic now they are not used for anything but to let us know the pathway is working correctly let's simplify things by changing the first costume to be a simple large arrow head since the tiles will be much smaller we need a bigger arrow to be able to see it clearly now delete the following three costumes as i said the color will mean nothing from now on back to our code begin by making a new variable named current index for this sprite only and set it to item 1 of to do indexes that's the item that was added first to our to-do list once we have the value we can delete item one of the to-do list to indicate we have actioned it now let's find out what direction was recorded at the position in the grid list make a new variable named der dir for direction and set it to item current index of grid if you remember we just put a zero at this location so at first duh will be zero but as the script run this will be whatever direction the pathway was last moving in right to be able to see whether this is working we're still drawing the pathway to the screen to do this we use the position at index block with the current index that we are actioning then point in direction der the direction we are facing and simply stamp great and now we can test that the first pathway step is being placed move the apple to a free space on the level and then click the green flag look behind it and the pathway arrow is stamped there press the green flag again and once again the stamp is correctly positioned success click back into the path sprite and we can hide the to-do list now so we know we are in the right location the next step is to replicate the previous scripts that did the pathfinding firstly we need to loop around four times once for each possible direction now the next step was to move forward by one tile okay so that's a little bit more complex when we are working in a grid list to move left or right we add or subtract one from the index and to move up and down we add or subtract a full number of columns however we always start at the current index so set next index to current index plus we'll do left and right movement first we know the direction we are facing it's stored in the direction der do you remember me talking about the maths of sine and cos operators before these can be used to move the x and y replicating what a move in direction can do for that reason we can add sine der to the index to move it left or right by one tile then up and down we change next index by this time we need to multiply and change by grid columns multiplied by because that's how you move up and down in a grid list multiplied by cos of der did that make any sense at all to you it kind of blows my mind when i think too hard about it with the movement done we should check whether the grid item is empty or not as we only want to move into empty grid cells if item next index of grid is a question mark ah right question mark that's right we filled all the non-wall cells with these so a question mark means we are good to move into that direction so we replace item next index of grid with okay we could just put der in here but if we did this number will just keep getting bigger and bigger so let's constrain it to be a number from zero to 360 by using de mod 360. that way it'll wrap around back to zero again now do you remember how we ensure this new pathway will get processed in future yeah we add next index to to-do indexes finally the last script in this repeat loop change dir by 90. can you see why i did this using clones in the first tutorial it's way more complex to understand when written like this but hey we're all learning scratches here so it's good to push ourselves to understand new things and that's all the pathfinding scripts written aha well i am stoked shall we give it a test go full screen and hit the green flag wowzers that's pink but it's good pink look at all the arrows they are facing the right directions and there are a lot more of them than we had in our first pathfinder tutorial that's a real point of success do you think we can move the apple oh yeah that is cool and it's also pretty smooth i'm dead pleased with that i wonder what scratchcat thinks of it let's find out hit the space ah it appears he doesn't think much of it yet no neither do his pals they are still expecting to see colours on the screen to tell them where to go and they don't have a clue how to read the grid list oh my what made that little fellow so special okay click into the cat sprite so if i scroll over here to find the define get next direction custom block you can see this is where colors make prizes well they tell us which way to turn anyhow we need to transition from using colors to grid lists how can we find out what grid item is under the cat sprite we need to turn back to our useful custom blocks click into the grid sprite and we'll copy the define get tile xy into the cat sprite great now back in the cat sprite move the custom block into some free space we'll get the tile at the x position and y position of the cat sprite and then we can check whether the tile returned was greater than minus one it turns out that this will be false for a hash so this works well all directions are greater than minus one so it's a directional right so set next direction to tile plus 180 we add 180 because the directions recorded in the grid lists are actually flowing away from the apple not towards it adding 180 reverses that direction so we will travel towards the goal delete the rest of this old scripts and we are good to run the project again let me spawn a new cat oh my that is sensational i'm so pleased that that change was so easy compared to the rest i can move the apple oh hang on the cat still all despawned when i moved the apple that's anticlimactical and completely unrequired now in the cat sprite find the when i receive reset path and we can just delete this script run the project again spawn some cats and now moving the apple around yay we have success this was not possible in our clone based pathfinding engine we can now have a moving target and all the cats follow us changing routes as the target changes i could play with this for ages but i can spot a problem did you see those cats walking through the wall this is not any fault of our pathfinding this is down to the simple nature of our cat's simple movement scripts look here all we do is move the cat forward and then turn left or right never stopping if we actually hit a wall perhaps we can address that before we look at making the maze any more complex move into some free space and make a new block named try move with a numeric input of dx and another of dy run without screen refresh we're going to check what is in the grid cell if we move the cat by dx and dy so get tile at x position plus dx and y position plus d y now we can check again if tile is greater than -1 if it is then this is not a wall so we can move into that space change x by dx and change y by d y next come back to the define follow path custom block we're wanting to replace this move two steps block again we will change this move into two separate move x and move y's using sine and cos so use two try moves we split it into two so that if moving in the x or y direction fails we can still succeed with the other direction this helps smooth out movement in a grid system our x movement will be 2 multiplied by the sine of direction and the y movement will be 2 multiplied by the cos of direction the twos here are the speed of movement just as we originally were moving forward by two steps just before testing we can scroll down to the when i starters clone that contains the wait until touching apple or edge script i want to replace this now with a wait until distance to apple is less than tile width the reason is that as we work with more detailed maps i don't want scratch cat to be able to touch the apple through walls and we can test again a few cats is not really enough to tell if this is working let me spawn more oh now i'm not a fan of these stuck cats we'll need to bug fix that first as they are making it hard to see the cats in question are simply ones that are spawned on top of a wall in the cat sprite find that when i start as a clone and look for the get next direction block if we spawn on top of a block then at this point tile will be a hash so if tile equals hash simply delete this clone and off we go again and let's play i'm going to spawn loads of cats notice they are no longer spawning on walls so that is great and now let's move the apple around and see if we can see any naughty kitties and the answer is no i cannot it's working flawlessly what an achievement oh yes this is great and that brings us back to our original challenge can we navigate this high-res circular maze costume what makes this so much more complex is that curves do not fit well into tile grids to get enough detail we'll have to up the grid size considerably click into the level sprite and the costume editor tab i'm going to import a new costume this maze svg if you want the costume then you can find a link to it under this video move the apple to the middle of the maze now switch to the grid sprite so that we can set things up just for a moment separate off the broadcast begin that will let us check the scan was successful run the project ah problem the tile size is far too large to capture the detail of this maze how about we set the tile width to 8 pixels test again yes this is better we are starting to see a difference between corridors and walls but we are really some way off the detail required how about a tile width of just 4 pixels test this is looking good but something is not right and i think it's not the tile size as much as the size of the scanned costumes this is due to scratch not allowing our sprite to shrink down as small as 4 pixels in width well just as there's a trick to getting sprites to become super big there is a similar trick to getting them to go super small click into the grid sprites costume and make a new costume naming it big draw a large rectangle now back to the code find the define scan custom block and here is where we are setting the costume size switch costume to big before setting the size that will allow the size to go much smaller and then switch back to costume one after the size is set and the small size is retained okay and we test wow yeah i was right that made all the difference we can now see how small the tiles really are now at 4 pixels they are tiny if i hide the level sprite for a moment you can see how detailed this scan really is i can't wait to give the pathfinding a test but before we can make the level visible again and then back in the grid sprite we put back the broadcast begin and we've run the project holy moly look at the tiny arrows perhaps we've gone a little over the top to achieve this goal but it's only because the maze i'm trying to solve is so opie any normal level would have its walls snapped beautifully with the tile grid and our tiles would be much bigger so these arrows are really annoying it's time to lose them for good in the path sprite locate the define try moving in all direction script and remove these three blocks the position at index point in direction and stamp they are not needed and since we are working with such a small tile size i'm going to click on the cat sprite and set its size to just 17 here and let's give it a run release the scratch cat and they're off trundling around the maze gosh it's a long way to get to the prize let me speed this up and they did it of course to complete this challenge we just need to ensure that they can navigate this maze no matter where the apple is i'm moving it outside the maze now and then spawning not one not two but all of the cats well okay not all of them but a good many of them and they just love this maze wow let's try moving the apple oh it's a bit laggy but that's to be expected on this silly tile size poor scratch doesn't know what has hit it don't forget this pathfinding is designed for more than just maze solving it's for finding the shortest pathways through levels with many possible routes anyhow i think with that we can say mission accomplished and if you want to see this working with different level layouts then here you are if you want to know where i got my circular maze i've put a link to a website under the video that lets us generate svg mazes it's really cool yeah so here's another maze [Music] i can pop it in size and rotate it and give it a test so good now don't think that this pathfinding is limited to mazes or even that you need to use the sprite scanning to create your level grid these scripts can be adapted to work with tile-based games scrolling games or almost any kind of game now this is scratch so do experiment have fun push your own limits and see what is possible share your success in the comments below the video and in the pathfinding studio also linked under the video and with that we have come to the end of another episode i hope you enjoyed this video and if you did then slap that like button if you haven't already then please do consider subscribing to my channel that way you won't miss any future videos and can be in the early to view gang so if it feels like i'm not talking much on the community tab at the moment sadly it's still broken and youtube support are hopefully on the case lastly as summer progresses for us here in the uk i've got some holidays booked so we may not get a video every monday but rest assured i'll make as many as the time allows all the more reason for you guys to subscribe not to miss them when they land so thanks for watching and scratch on guys you