Simple Pathfinding Tutorial

hello fellow scratchers ever wondered how that enemy ai manages to move through a level navigating around corners skipping dead ends and finding that shortest route to the player i'm griff patch and today we will be delving into the world of enemy ai pathfinding you may be interested to know that the same pathfinding scripts that we're about to learn about are also used for calculating things like light flow in paper minecraft i wonder after you've watched this video whether you'll be able to tell me how they are linked drop me a comment if you know the answer i really love this project it looks so complex so how on earth do we go about creating it we'll begin with a blank new project and we're going to keep scratch cat this time they will be pleased we need him much smaller though so enter the value 30 into their size box and we'll also change the sprite name to cat next add a new sprite from the library i'll go for an apple and this will be our goal since scratchcat loves them so much set its size to 60 now the next step requires a little more creativity create a new sprite naming it maze and now we need to draw make sure your pen color is set to pure black for any walls and set the pen width to nice and chunky perhaps a width of now start by drawing a large rectangle around the border of the costume next draw a chunky maze leaving plenty of space around for the cat to navigate keeping the lines pure black now a device for starters making the maze similar size to the one i'm drawing here while we are working on our scripts the more complex maze i showed earlier will have to wait so with your simple maze drawn click into the code tab and add a when green flag clicked go to x y of zero by zero to center the maze on the stage so we want to find the shortest route between scratch cat and the apple we could start trundling off around the maze handling wall collisions and taking a stab at the best direction to turn at each point but bearing in mind that there are potential dead ends and worse looping corridors it would be best to plan our desired route in advance so create a new sprite and we'll name it path we are going to split the maze up into small square regions draw a 30 by 30 pixel tile just less than 8 large grid squares in width and height we can use the selection tool to drag it so it snaps to the center i've colored it a light pastel red with a saturation of around 10. next we draw an arrow pointing to the right make sure this is also pure black in color we're going to use this sprite to make a visual route or pathway through the maze in the code tab when green flag clicked show the arrow tile so have you ever noticed how it can be so much easier to solve a maze by starting at the end and working backwards this is exactly what we are going to do now so we start by going to apple point in direction zero which is up and go to back layer i'll just make sure scratch cat and the apple sprites are in good positions and then we'll run the project the tile should appear behind apple a good start to begin drawing a path we want to try and place a tile above the existing one so move forward by 32 steps that's one whole tile now we create a clone of ourselves and then quickly leaving the clone where it is we move ourselves back by minus 32 steps to where we started if i click that script we can see the new clone has appeared we want to do the same for all four possible directions around us the simplest way to do this is to add a turn clockwise by 90 degrees turn right and then run the same move script four times in a row this leaves us facing upwards once more having traveled full circle and has left a rather attractive diamond pattern around the apple with the arrows all pointing outwards in the direction of travel so let's wrap the moving script in a repeat for loop and we'll make a new custom block named try moving in all directions so mouthful and run without screen refresh that will contain this loop script to ensure all four clones get created together i'll drop a call to this custom block at the end of the green flag script so it runs when the project runs just test that to confirm it's still making the same pattern what we want to do now is continue these arrows outwards from the apple until they reach scratch cat over here but what about the maze walls if i place the apple next to a wall and run the script see how this arrow has appeared right over the wall well that's not right our paths should never cross a wall we can stop this by placing an if around the crate clone block here and ensure we are not touching black and only then create clone of myself running the project again confirms that this has worked as the offending arrow has been removed super okay now it's magic time i just know you're going to love this bit we've successfully coded a script that moves outwards checking for collisions so what if each new clone were to continue to do the same thing and each tried to spread out to their surrounding tiles and then those spread out again like the ripples on water moving outwards from the apple well let's find out drop a when i start as a clone block this will trigger for all four of the new tiles we just created so for now add in a wait one second this is just so that we can watch things happen you may actually want to use a smaller value than this and then simply add a try moving in all directions block to finish it off now look at this it's important can you see how running this script will create a clone and creating a clone will again run this script what we have created here is a recursive loop without anything to stop them recursive loops can run forever and they will really lag out your project but we'll come back to this in a second i've held off long enough i'm dying to run the project and see what we have created oh yes this is exactly what we wanted the tiles are now cloning themselves and spreading all around the maze flowing outwards from apple and even navigating around corners at some point they will certainly find scratch cat and just like solving a maze backwards we can then reverse the root and find our way back to the apple in fact i have an idea come into the costume editor and flip this arrow around to point left i can hold down shift as i rotate it to ensure it snaps to 45 degree increments there look with the arrows reversed the map suddenly reveals its true purpose if i want to take scratch cat from any place on this map to the apple the arrows show me the way to go let me move the apple and run the project again each time the map is generated it shows me the shortest route to get to the apple from any point on the map this is really useful it allows all the enemies on a level to seek you out using the same map okay i'm getting carried away i had a word of warning about this recursive loop so this script creates clones and the new clones in return run this script this could run forever and then wow super lag but we have two protections against this one scratch will not create more than 300 clones before it refuses to create any more and two we specifically don't create a clone if we are touching black which brings me to another really important point in our design remember how the arrows on our path tiles are also coloured black this was purposeful because it means that not only do we stop the tiles being placed on a maze wall but also a tile will not be placed down when another tile is already there otherwise they would just be stacking on top of each other and the script wouldn't get very far but the black color stops them black walls black arrows okay there's another little problem we need to solve here where the tiles are getting misaligned at the borders of the screen this is just down to scratch's sprite fencing we can fix it by setting the size to 300 before we move and then setting it back to 100 afterwards this allows them to go off screen and come back on again in exactly the same place i'll just confirm that that worked yes that's much better while we're addressing potential issues let's also add in an if around the initial try move script under the green flag here and make sure we are also not touching black we don't want to begin tracing roots if the apple starts in a bad place finally we should remove this weight one how fast do you think this map will generate without it here wow really fast is all i can say in fact it's pretty instantaneous exciting stuff however this is all nice and good but how do we get scratch cat to follow these arrows hmm well the simplest way that i could think of is to color code our arrows go into the costume tab and rename the first costume to up i'm happy to keep this one's color the same now duplicate the costume naming it right and change the color to be green a color value of 35 will do then do the same for down with a color of blue around 55 and left with a color of purple around 80. you can choose whatever colors you want of course now back in the scripts switch costume to up after we point in direction zero and then use a next costume after turning 90 degrees to the right this will cycle through the costumes as we rotate by 90 degrees run the project now and we are greeted by a lovely display of coloured tiles quite beautiful really i like it and what's more i just know scratchcat will love it too let's teach him to read it click into the scratchcat sprite in the costume editor create a new costume named mask and draw a filled square perfectly centered in the painting area mine is around 48 by 48 pixels the size of 12 by 12 grid squares now remember also we shrunk scratch cap by 30 percent so this square will also be shrunk down if you are using a different size sprite you'll need to size the square accordingly now back in the scripts we want to be able to track what color is under this little square mask and turn scratch cat accordingly so create a new custom block named get next direction and switch right away to the mask costume now check if with an if else it is touching color with the project running we can click the color swatch and pick the color from any tile pointing upwards now we could use a point in direction block here but instead let's make a new variable named next du for this sprite only and set that to direction zero instead that's up duplicate the if else block three more times and we'll check for the right color with a direction of 90. down with 180 and left with minus 90. all four of these colors must match the up right down and left colors if we take this new block add it to a point in direction of nextdir and then a switch costume back to costume 1 then we can click the script to run it and we should find that our cat ends up pointing in the same direction as whatever arrow tile is behind them super i'll just do this a few more times to check cool let's get scratch cat moving make another block named follow path leave the run without screen refresh clear as this script will keep running while the cat is moving around so to start our cat's journey in a forever loop move forward by two steps and then after that place the get next direction point in direction and switch costume scripts we just created underneath lastly we want a when green flag clicked to kick off the follow path script great let's run the project and see what we have made and off trundle scratch cat this is working surprisingly well ha things go a little wrong once he reaches the apple oops more on that later let's add a key to reposition scratch cat add in a when space key pressed go to mouse pointer now i can just tap the spacebar and have them appear at my mouse and he immediately sets off in the direction of the apple once more that's neat where this project has room for improvement is in our cat's turning you see at present how he turns so quickly that he often walks down the edge of a tile and this can lead to him looking like he's overlapping the walls too how about we kill two birds with one stone and smooth out his turning i've scripted many ways of allowing sprites to turn smoothly in my years on scratch but while working on this tutorial i stumbled upon a clever trick that does it really simply in just a couple of blocks we start with a sprite pointing in direction a say 90 degrees in my example and b is the direction we want to face minus 160 degrees but we want a the cat to turn towards b smoothly and the problem is we don't want to end up rotating the long way round a clever trick is to rotate the entire problem so that b is pointing upwards we can do this by turning left by the value of b minus 160. this leaves us with a much simpler problem to solve the cat is now facing in the direction minus 110 and we can see that we want to turn to face upwards well that's easy we just need to turn right by 110 that's just the inverse of the new value a which is the current direction of scratch cat to turn smoothly in that direction we just divide this number up into smaller chunks let's see if we can implement that start by creating a new custom block named turn towards with a numeric input of direction a label with smoothing followed by another input named smooth we turn left by the input direction we want to point in that's the red one then we must turn back right by the same input direction again so that we are pointing back towards a after all this is where we are turning from and then we subtract the current sprites direction reporter that's the blue one but divide it by smooth so that we only move a fraction towards the goal direction and that my friend is it what a neat little solution i really like that just be careful to use the right direction variables here let's use this script simply replace the point in direction with our new turn towards block and use a smoothing value of six run the project now and bask in the beauty of that smooth rotation how very clever all this pressing space makes me think it would be better if each press created its own scratchcat clone we should be able to do that pretty easily click into the stage sprite and add a when space key pressed create clone of cat triggering from the stage avoids accidentally creating clones from other clones now back into our cat sprite we bring in a when i start as clone and move the go to mouse pointer block into there instead we can delete the old when space key pressed from here now then lastly we make use of the follow path block once more for this clone run the project and now with each press of the space key a fresh new cat spawns happily trundling off towards the apple yeah lucky that that apple is so large there's plenty to go round i have to say that these cats are rather building up around the apple now i'd like to do something about that perhaps we can just fade them out once they reach their goal add a hide block to the when green flag clicked and delete the follow path block we'll only use the clones from now on to represent the moving cats now come down to the when i start as clone receiver and we'll duplicate this so that we have two events triggering off the start of each clone remove the follow path from the first receiver and replace with a show block then we'll wait until either we are touching apple or touching the edge of the screen the touching edge is just a sanity check in case we lose a cat off the beaten track then once it's reached the end of the goal we repeat 10 and change ghost effect by 10 to fade the cat away finally delete this clone for the second when i start as clone just remove the go to mouse pointer we only want to keep the follow path script nothing else by having these scripts separate we can keep the cat moving while we'll simultaneously fade them out let's give it a test smack the space key and watch the cats gracefully fading away when they reach their target excellent work now just because it's extra fun let me show you how we can trigger a change of goal when the apple is moved click into the apple's sprite add a when green flag clicked and set drag mode to draggable that's in the sensing category we'll then loop forever but right away we want to wait until the mouse is down then we broadcast a new message reset path followed by another broadcast to find path let's hook up those events click into the cat sprite little note try to ignore those apple x and y variables that have appeared on the stage i was trying something else and decided against it you won't need them we are going to add a when i receive reset path and then simply delete this clone this keeps things running smoothly in the demo by cleaning up the old cats now click into the path sprite again we add a when i receive reset path and simply delete this clone to take away the previous pathways next add a when i receive find path make a new custom block named find path run without screen refresh and move all the scripts from when the green flag was clicked hat block into there ensuring to add the find path script back under the when green flag clicked and also under the new when i receive find path receiver now then this is a really fun test you're going to love this now run the project in full screen mode and grab the apple and drag it around the maze how awesome is this the pathfinding is calculating in real time and all the arrows are updating dynamically to show the best route oh my gosh that is so cool then i can still press the space bar and drop some cats wow what an awesome little project this is turning out to be now you may ask how could i use this in a game okay so i created this project the way it is to avoid the technicalities of working with lists and 2d grid systems but in practice lists and grids would be the way to go to support larger or more detailed mazes and off-screen enemies too it would also run even faster than it does now importantly it would also mean that these arrow tiles would not have to be visible that would be nice however we can't do that this time but i do have one trick up my sleeve that will at least allow us to hide the arrows so if you want to try it then go into the path sprite and add a when i receive hide path and hide the sprite then under the when i start as a clone add a forever loop and show this gets in really quickly before most other scripts run in a game frame lastly click into the stage bright and add when green flag clicked or ever broadcast hide path that's it run the project and voila the pathway has gone and yet you can see the cats are still behaving as if the colored pathway is still there that's because to them it is still there we are showing the pathway at the start of the frame and then hiding it again using a broadcast from the stage this will trigger after the cats have moved but before the screen is updated for us to see a neat trick that at least gets us to where we might want to be and this is where i leave you if you fancy seeing how far you can go with upgrading your maze then you can try to draw one lined up with the grid which lets you create something as cool as this note i have also set the cat script to point in the right direction as soon as they clone to do this just add a weight zero to the beginning of both the when i start as clones in the cat sprite and then check next direction and point in direction next door before beginning to wait until touching here and that's it well i hope you've enjoyed this tutorial if you have then please do smash the like button and leave a comment don't forget to subscribe to the channel to avoid missing my next exciting video but until that time thanks for watching and scratch on guys

Channel: griffpatch

Views: 315,380

Keywords:

Id: 0faPPgOT--E

Length: 23min 36sec (1416 seconds)

Published: Mon Apr 26 2021