Pathfinding a Maze using Lists

[@noot_noot843]

This guy has everything you need for a perfect scratch project!

[@pottabatullamanjula912]

Ya your right

[@ussystems8202]

True!

[@MTSyntho]

Yes

[@SamFromSpaceOfficial]

Could not be truer

[@ussystems8202]

@@SamFromSpaceOfficial No, Griffpatch is very honest.

[@ian-qo8fq]

I admire you, for being able to creat such algorthms in such a limited engine

[@duccofantastico]

I have long gone from the scratch community but this dude is still impressive.

[@kosuken]

You know it’s gonna be a good project when Griffpatch tells you to make the “try move,dx,dy” block

[@idiotic_idiots]

So True

[@Yazanbakr-p7u]

@@idiotic_idiots Yup

[@rAIGMIBU]

There are some griffpatch projects that don't use "try move (dx) (dy)," and this comment implies they are not good, but, as we all know, all griffpatch projects are good, which means that this comment is false.

[@kosuken]

@@rAIGMIBU if all thumbs are fingers then all fingers are thumbs is the above statement true or false? just because I'm saying that use of the move dx dy helps a project be good doesent mean a project withought it will be bad use your brain before posting a comment, child

[@rAIGMIBU]

@@kosuken Yeah, you're right, sorry

[@chiroyce]

Yes, it's here, the long awaited, Pathfinding with Lists!!!!

[@chirantan11-976]

I have seen you. You are a great scratcher!

[@chiroyce]

@@chirantan11-976 Thank you!

[@maaz4354]

This is so cool!! I was trying to put the first pathfinding script in my scrolling rpg, unforunatly, it didn't work. BUT with this tutorial you helped me with that, and it worked! Thanks!

[@Gaming32i]

For those of you who don't know this term: The Scratch "To-do List" stuff, is an example of something known as asynchronous programming. Scratch is heavily async.

[@bibihussain7108]

so true!

[@rohansachdeva4952]

Griffpatch in 2050: Welcome to another one of my epic scratch tutorials, and today we will be learning how to make a tile-based scrolling game with 2 grid lists, one for tiles and one for pathfinding for some off-screen squishable floor-hugging goombas and a self-driving car with proper car physics trying to ram into you. You will get mystery objects such as guns in mystery boxes and also you will get bonus score if you shoot lemons and appels and easter eggs randomly appearing on the level and will get camera shake with flashes and sound effects, with half-tiles, slopes and cliffs.

[@griffpatch]

lol

[@drrenwtfrick]

lol

[@pottabatullamanjula912]

Lol

[@VeryCrazyDude]

lol

[@krazykousins3448]

griffpatch in 20999: welcome to a jetpack making tutorial ( no punctuation)

[@Drachenbauer]

I have another idea fot the place, where the moving directions are stored in the gridlist: at the end of "try moving in all directions", where dir is changed by 90, directly under this block place an "if" and check for and insidt this new "if" change "dir" to -90 this has 2 effects: 1. it now sets the directions the same way, you will find them, if you use the circle-control, that pops up at clicking the input-slot of a [point in direction (value)°]-block. pointing to the left on this circle sets to the value -90 2. it already prevents from storing values higher than 180 in the gridlist, so you don´t need to mod the value at replacing a "?" in the gridlist any more

[@whwhwhhwhhhwhdldkjdsnsjsks6544]

Nice, a lot simpler than I actually imagined it, now something employing a system like this is actually possible for me :)

[@chipm0nk]

I love that, in the intro, you have Appel in the center of the maze instead of an apple to show that the project is more complex :) (can't believe I'm posting a comment that you actually have a chance of seeing lol)

[@griffpatch]

He he

[@blurrysquire6671]

instead of some youtubers that show you it, you explain it which i like because then i don't have to keep coming back to the same video! Keep up the great work!

[@griffpatch]

Glad I could help - Although I would also like you to keep coming back hehe - to watch all my ads so I can make more videos lol. Guess I'll have to keep making new videos!

[@blurrysquire6671]

sometimes i do rewatch these videos when i am bored. and i remake the project that i did before and i try and challenge myself to think of what you are going to do next!

[@turtleblox1826]

I am currently making a game that requires enemies to pathfind, and the tutorial was amazing, but I found one problem. I don't want all of my enemies following each other in a line, and I think the reason this is happening is because it takes priority of some directions over others, meaning that other directions that still cause the same speed to get to the object are excluded. I would like to make it so it records places that have two or even three directions that would cause the speed, and use a random number generator to decide which one to use. I would love if you could help figure out how to record when two directions would cause the same time to reach the goal. If you have any questions for elaboration please ask. Thank you so much in advance, I love using scratch and your tutorials are amazing.

[@04tmoodyscratch24]

Wow that one cat solving the maze at the end just blew my mind even knowing how it all works. Just so beautiful!

[@griffpatch]

Yeah he he - I love watching him trundle around :)

[@scratchcatcreator2012]

34:03 I think he's rocking out to the outro song LOL

[@scratchcatcreator2012]

@@Daydarkness0 yes

[@EHMM]

Because he used the sin and cos operators

[@9e39shauryalalsahu7]

I love how he merges both the different projects! :)

[@mrg4melover]

Remember back on that maze generation tutorial, I asked how to use a pathfinder for it, and you said with lists? I had no idea how to do that, but this video REALLY helped! Thank you so much!

[@jakel1977]

Definitely the best Scratcher to follow. Thank you for all your work

[@intheheatofjuly]

niceee! i was waiting for this sequel! great job!

[@tronche2cake]

Finally! I've been waiting for months for this episode to come

[@pixelbee42314]

it's a good thing I saw the pathfinding and grid list tutorials when they came out and made projects with them.

[@griffpatch]

Yay!

[@EpicVideos2]

Great video - I liked the explanation of it's stack based single threading runtime loop.

[@Borutpahorbjmachine]

I am gratefull for the fact that you even make videos, thanks

[@griffpatch]

My pleasure!

[@Borutpahorbjmachine]

@@griffpatch ✌️

[@jacob7538]

This will be really helpful for my RTS game I am making! Thanks!

[@TeleKiwi]

Nice! I was really excited for a sequel to the last part!

[@griffpatch]

Hope you enjoyed it!

[@Myalnyblth0]

I added this path finding script to enemies in my ray-casting project and it works much better than just point to player and move so thanks

[@strategy2128]

Griffpatch: these two videos together could be really powerful Me: *hurriedly opens procedural maze generation project*

[@chumbucket3475]

Minotaur time

[@codeiscool3622]

same

[@coolgameriguess]

lol

[@Drachenbauer]

I combined them to a fully automatic maze solving simulator (just click green flag and watch) But I also have another maze project, that is controllable by arrow keys.

[@jer8036]

Next up: combining the 2 videos and the videos about making a 3d game

[@evanlamb1595]

I'm going to use this and the maze project we did to make an awesome game!

[@InverseOfficial]

been wanting to make a tower defence game similar to field runners, this is perfect!

[@griffpatch]

Ha - interestingly enough, that is exactly the game that inspired this project in the first place :)

[@MoreThanJustGabe]

@@griffpatch what a coincidence

[@matyera2508]

This is perfectly what I needed!

[@spawnnumber2126]

I would love to combine this with the maze generator stuff. this is so amazing

[@Drachenbauer]

I combined them to a fully automatic maze solving simulator (just click green flag and watch) But I also have another maze project, that is controllable by arrow keys.

[@JanDuckworth]

@@DrachenbauerHave you shared it? I'd love to have look!

[@SparrowTutorialsFun]

Wow the path finding is amazing!!

[@rohansachdeva4952]

Happiness be like: "Grid List Pathfinding" No Sarcasm intended, and I am dead serious again

[@jensenx08]

you write this in every video.

[@th1v5]

@@jensenx08 because it's true

[@MrCrompz]

again

[@jensenx08]

@Gary Lenoie LOL

[@funraven659]

Griffpatch is my no. 1 fav utuber I luv him so so much

[@griffpatch]

You are too kind :)

[@yezpastaisdrawing8677]

Griffpatch, I just want to say you something. You're amazing

[@griffpatch]

:) - You are too kind!

[@yezpastaisdrawing8677]

@@griffpatch 🥰Aw! Thank you!

[@Lyminary]

Could you show us how something similar with a platformer so that it automatically completes itself in the fastest time possible? Could you do it for a scrolling platformer too? Ai building would be cool in so many applications here on scratch.

[@theelegantcoder9963]

Appel in the start made my day!!

[@cookiecatmustapic1058]

My arrows are only updating when I move the apple and then click the screen do you know what is happening?

[@irmizatopek4468]

Thanks alot. This is gonnna be the base for a point and click adventure I am currently working on :)

[@PeterbroMC]

I have an idea for a new pathfinding algorithm in scratch. We can use A* algorithm. Basically the pathfinding sprite moves in all 4 directions with each movement having a serialized Xposition|Yposition|Direction|Distance in a list(Distance = Distance From Target). When the orginal spirte comes back to its previous location, it serializes its Xposition|Yposition|Direction|Distance|Used. This |Used| Serial will server as a condition when a different Custom block is checking for the Serial Number with the lowest distance on the list. Then a different block will determine the X and Y position of the serial number with the lowest distance on the list. The Pathfinding Sprite will then go to the X and Y positon and do the same procedure. Note: Ensure that the 4-way split of the original sprite has stage collision detection, to stop serialization of the collided block. Hope this idea is of help to you.

[@b9k-e7f]

Hello, Griffpatch! I have been working on some code in the Tile Scrolling Platformer for partial blocks, like slopes, but with more flexibility than one slope. It works kind of like a tile grid for each block. It isn't fully finished, but I think it's enough to build off of. If I could share my code with you so you could see if it would be helpful for the tutorial series, that would be great. I have been using your series to develop my own game, so I thought by making some code I could possibly help others like you helped me. Thanks for your time! -Uboiscratch

[@sdbadik]

Woah, looks like something he would use in his RPG tutorial. Did you do those tile pins or quarter tiles? I'm interested

[@terracoon9882]

i am now using javascript after years of scratch but this is stil so helpfull!! thank you

[@jorgeluizbanhos3747]

Finally, a Update for our pathfinding! Yay!!!

[@OE-yu9co]

finally, i love your vids

[@cat_awry]

Mixing this with the maze generator video can make a cool game

[@flowocode]

Griffpatch:"Lets go scraching" Me: Yea scraching my head how is this possible

[@jamesscrivens6308]

just letting you know you forgot the 't' in scratching

[@morveman_yt9567]

I love it and I will combine the maze generator and the grid list pathfinders lol

[@FeniteFr]

OMG this tutorial is awesome 🤯🤩 !!!! I have wait a long tome for this 🌟🌟🌟🌠🍋🍋 I hope you can write posts again soon 😊👍

[@griffpatch]

Oh sob... My posts!

[@kidustefera7734]

You know a video is going to be good when the username is Griffpatch

[@repplayz65]

Amazing followup!

[@gamesgg3896]

Hey so I want to make a online racing game but I don't know how to could you help

[@ThatGeometryDude]

He said 'So, get our your brooms... 13:14 ' And I immediately thought of Harry Potter

[@josephjustin4124]

Wow, this looks good

[@cst1229]

I wonder if TurboWarp can make the tiny tiles pathfinding run smoother...

[@stormer4859]

Scratch Addons with 60fps mod

[@cst1229]

@@stormer4859 That still doesn't compile the project which is the main source of the speed

[@stormer4859]

@@cst1229 griffpatch: set it to 240 fps other people: griffpatch computer is very good

[@jensenx08]

holidays? you can go? 33:47 well u are lucky! for me here i can't even get out of the house... and that's why everyday i comment on griffpatch's videos.

[@griffpatch]

IKR... We are not going out much here... We'll just be visiting family which will be super nice.

[@jaecheokkim99]

Scratch Cat: i'm lazy i don't want to move Griffpatch: that's okay i can bug fix that Scratch Cat: NOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO!!!!!!!! Griffpatch: Bug Fixed! Scratch Cat: Well... Back to work...

[@vevericac3294]

I KNEW THIS WAS GONNA POP UP!!! IT WAS A MEMBER ONLY IN THE PLAYLIST! :D

[@sbfshadoe9918]

How did you know if ur not a member?

[@vevericac3294]

@@sbfshadoe9918 the playlist shows everything in it, even the member only videos

[@foxyolk]

0:52 that last cat that went the right direction...

[@FireyDeath4]

This is why you make radial pathfinders. imagine a big 3D game engine like Unity or Unreal just going all the way across the map where the furthest objects are and just breaking the whole screen into little cubes

[@cuttamOWU]

Would you mind giving me a rundown of how those work? I wanna see if this kind of thing can be translated into scratch and whether it would be more efficient than this method. This method is still on the basic side as it's meant to be understandable by newer scratchers so there are limitations in terms of speed and more advanced movement like diagonals. I want to see if this method fixes or at least make less of the problems.

[@FireyDeath4]

​@@cuttamOWU Hoh I...think I kinda get the idea probably not the code however (I hadn't started programming such a thing yet though) Oh well I'll just go through the logical procedures I think For the mapping, I guess you have layers of circles radiating from a point, and then some walls defined as being at certain angles. Now, for now I'm just going to assume you're in a circular maze with straight edges and corners. You should always cling to the shorter side of the arc until it's time to cross over to a corner. When you're approaching a corner outward, you want to aim for it when you're at a tangent on the arc that goes to that corner. When you're approaching a corner inward, just keep clinging to the short arc until you get to the corner. When you're at a "straight" corridor radiating from the circle (the walls are probably slanting toward each other near the middle), just cling to the edge or go the diagonal to the other point you want to go. Yeah I need a diagram to explain it, had to picture it in my head as I wrote it and I don't know if you can do the same but hey, this is how I'd do it If you're just having general blobs and not a strict sense of radial space, just do this method with more and more tangents and maybe use Dijkstra's algorithm if you need to

[@cuttamOWU]

​@@FireyDeath4 Yeah you might need a diagram. Right now my idea for pathfinding is set up a bunch of nodes and find which combination of nodes result in the shortest path using Euclidean Distance. There are manually-placed nodes I place as a checkpoint where the enemy has to pathfind to eventually and computer-placed nodes that the computer places, adjusting for changes in enemy location in the case the enemy or goal are shifted or the current path becomes obstructed. The pathfinding itself is simple but idk how to set up the computer-placed nodes. Right now I'm thinking of using some sort of ray tracing/marching to find the walls and directions it can't go to. Then I could set a minimum distance between the enemy sprite and the obstacles to limit wall-hugging. From there I would move the tracker towards the goal, moving left or right accounting for walls and minimum distance. And then stop after a certain length and repeat the process for as many times as needed. The stopping length is determined relative to the walls as I now have the direction of every wall point as well as the distance of each of those points from source. My ideal code would find the closest wall segment (segments if they are connected in the line of sight), create an arc where moving in a straight line within that arc will collide with a wall, move towards the goal, and move to the points on either side of the wall(s) in the case that the direction to the goal in within the arc, moving the distance the points on each side are from the origin of the tracker. This ideal code falls apart however in a maze where the walls are connected to one another (will see almost every direction as immovable) unless I can find a way to filter out certain wall segments from others. Keep in mind that I'm not using other sprites or clones, I have to figure this one mathematically. I don't want to completely remove the connected wall segment functionality since without it, the code might break (ex. /\ where the left side is the closer wall segment; If I were only to detect the left wall segment, the pathfinding will move itself into the space between the walls and make the right side path always appear longer because of a detour.). There may be other methods for this distance finding made for maze-solving but I don't know how to make them. This problem might not exist though if I'm just being dumb and the ray tracing/marching solves it for me. Idk how efficient this method would be compared to your method or even the method in this video. All this computing may take longer than both of those methods, especially from the ray tracing/marching, depending on how I implement it. Please give me thoughts on the manner since I kinda have no idea what Im talking about for some of this.

[@FireyDeath4]

@@cuttamOWU Yeah I think you need a diagram too I was barely paying attention in fact lol (don't think raytracing is efficient though - pure geometry is better) Well, if you can calculate tangents, I think you can just cling to walls by changing your angle from the middle and use radians or whatever. If the sprite's a certain size you don't want to have _in_ the wall, I guess you could add in the walls, and then calculate a map whose edges are the sprite's diameter apart, the sprite's radius away from the original walls. Basically compensating so you can calculate using only a point. I just proposed you'd sort of code in the maze, based on where the arcs are (how far they are from the middle), the degrees they occupy between gaps, and any straight lines and their angles and lengths. Then use that.

[@cuttamOWU]

@@FireyDeath4 Ray Tracing was just the first thing that came to my mind. I just need some code to figure out the direction of a wall and the distance that wall is from the origin. And I needed the returned data to be a line from the origin's perspective. Even then, the node part is pure speculation since I still feel that there will be problems with my theorized method. Mostly coming from the possibility that the returned paths being suboptimal or being too optimal that the turns are unnaturally sharp. We probably should move this conversation elsewhere where we can express our reasoning in the form of diagrams since words don't seem to cut it.

[@unspeakabletiger4535]

I never knew that Scratch had a to do list! Wow! 😀

[@FeniteFr]

33:43 yes, I was starting to wonder if you weren't an alien to get to make so many videos 👽🤯😂

[@smarf93]

Thanks a ton! I was trying to make sense of this method on the Wiki, but couldn’t work it out 😁

[@confusioned2249]

The apple trying to hide itself in a maze, but still being found and eaten: WAIT WHAT

[@achorjustin9807]

This is so awesome...Very educative but I have a big issue with most of my scratch projects ...Please can you make a tutorial on how you normally go about with increasing frame rates in your games...

[@notthatntg]

he just has a beefy pc and scratch is capped at 30 fps without mods anyway

[@extrem780]

YEAH!!! Now this is exciting!

[@superprobablylevel]

maybe you could perhaps implement this pathfinding into the raycaster for enemies

[@Blob2763]

Enjoy your holidays, Griffpatch! Do send postcards!

[@ti2184]

0:18 i think you mixed apples and appels

[@xaneanian]

Advanced Scratchers in scratch 10.0: testing the newly added 3d mode code

[@Kja211]

Great! I'm gonna try to combine this with your maze generator that I made :)

[@griffpatch]

Sounds great!

[@Drachenbauer]

I combined them to a fully automatic maze solving simulator (just click green flag and watch) But I also have another maze project, that is controllable by arrow keys.

[@Yazanbakr-p7u]

Boids + Pathfinding + Grid list = very good project

[@Opti234]

So I was gone for vacation, and I missed out on the previous 2 videos. The first thing that I did when I came back and took a shower was watch the two videos. Just saying how much we like your videos, griffpatch! P.S. 0:18 nooo why Appel?

[@infinitise636]

Hi Griffpatch, uhh, for your next video can you teach us on how to make a 3D Games like your 3D Laser Tag game for new scratchers.

[@nandolaysyt]

The Start Seems So Excited 😆

[@matelocopoco]

Lets goo exactly what i wanted!

[@Haynster]

oh hey I was just watching your other tutorial today!

[@SierraLeoneballMapping]

I love your tutorials!

[@griffpatch]

Thank you so much!

[@SierraLeoneballMapping]

@@griffpatch You're welcome.

[@kidssmelt6804]

nice tuturial and a good idea

[@grande1900]

You don't have to rename the maze, since in the grid list sprite it's only 1 instance of

[@saadpro1586]

WOW LETS GO AMAZING

[@landnpr3414]

ussally id just use blocks and glide blocks for path finding like maze runners and stuff but i can see problems where itll hit the wall and glide through anyways, Good Tutorial!

[@proffessor4039]

Thanks griffpatch... (Also, try clearing your browser cookies/cache, it might solve your problem with posting)

[@griffpatch]

Thanks for the tip! - It's good advice, but sadly I tried that... many times hehe - It also fails from the KZbin app on my phone... so yeah! D:

[@joshuamanrique8557]

I wonder how powerful the combination of: •Random maze generator •How to use tile grids •Simple pathfinding Will be...

[@griffpatch]

He he - These were designed to be base projects to be built upon :)

[@joshuamanrique8557]

@@griffpatch now that I can talk to you... Can you make a snake game tutorial first with clones, then with grid lists and finally with scrolling?

[@AdelHakim-x7k]

THANK YOU GRIFFPATCH

[@ilyaszan]

Hey! Hello there! i love your videos. but can you create a video where you optimize what you're trying to do at 28:42? For example, I think the tiles can be optimized in such a way that they are not in the X and Y axes, but in the form of walls (also in the form of circles in their directions). In this way, you will have a more optimized project, and since the direction of the tiles is round, the character does not move in a zigzag shape in diagonal places! think about it. good day!

[@joelamaster7200]

Could you somehow make it so that the maze could work with more than one apple? I wish to make a light flow system so instead of apples i make lights.

[@rawr4everPT]

no one: griffpatch: "Draw a rectangle" *Proceeds to draw a square*

[@mahadevan4660]

Hi Sir, will there be episode 15 of tile scrolling platformer? If yes I am very excited to see it!!!!!

[@griffpatch]

There will be, but this Monday will probably not be a video in sorry, not enough time as I am away

[@mahadevan4660]

@@griffpatch It's ok sir. I am very exited to see your video :) can you give a hint what will the next episode cover? :)

[@rotmann2015]

Pathfinding + grid List = advanced pathfinding Advanced pathfinding + maze generator = epic maze game Epic maze game + items, bosses, weapons, inventory, and more = project I’m working on

[@jensenx08]

You need to have guiness world records for all the records you hold in scratch :O

[@griffpatch]

That would be funny

[@jensenx08]

@@griffpatch lol

[@haroonkids3222]

@@griffpatch I bet you could get some if you contacted the world record people lol

[@ameerio157]

i swear this guy is going to teach us how to make a fully functional alexa with lists

[@griffpatch]

lol

[@peak-contextless4861]

My arrows do not want to follow the Apple. Sometimes they get stuck in corner or appear in only certain spots, instead of going throughout the whole maze. I did everything correctly, too.

[@ChathanadathHouse]

Your corridors are too small

[@CBFNetworksArchive]

Maybe a maze generator using gridlist with pathfinding soon?

[@saeedtalpur8380]

Wow I didn’t know this was uploaded early

[@brawldude2656]

Interesting i made A* pathfinding with lists project 3 days ago :O

[@griffpatch]

Nice!!!! That's a fantastic technique

[@brawldude2656]

@@griffpatch Thanks :D

[@gabrijelcoh]

These tutorials are really cool yes, but my question is, how do you know so much about scratch coding? You're so smart man!

[@griffpatch]

It's just practice... you would be amazed how much you can do once you get fluent in coding!

[@shahinma221]

@@griffpatch Yes, even I was like a NOOB now I know a lot about scratch but not scrolling

[@gabrijelcoh]

@@griffpatch How long did it take you to learn all of this?

[@KnightBolt-LBS]

so good i love your tutorials

[@_apehuman]

I am looking for a light flow script and this should work nicely

[@ecodersofficial]

Can you please make a tutorial on how to create a cloud list? Also, can you explain how to make a cloud list encoder and decoder?

[@JackCat101]

Now I have to be unlucky if it not tile scrolling game next week because I like the tile scrolling game toturials