Coding Challenge #10.1: Maze Generator with p5.js - Part 1

Подписаться 1,7 млн

Просмотров 393 тыс.

50% 1

Choo choo! In this multi-part coding challenge, I create a maze generator using a depth-first search algorithm with recursive backtracking. The idea is to walk through a grid of cells, removing walls as we go to build a maze. Code: thecodingtrain.com/challenges...
🕹️ p5.js Web Editor Sketch: editor.p5js.org/codingtrain/s...
Other Parts of this Challenge:
📺 Part 2: Visiting Neighboring Cells: • Coding Challenge #10.2...
📺 Part 3: Removing Walls: • Coding Challenge #10.3...
📺 Part 4: Backtracking: • Coding Challenge #10.4...
🎥 Previous video: • Coding Challenge #9: S...
🎥 Next video: • Coding Challenge 11: 3...
🎥 All videos: • Coding Challenges
References:
🌐 Maze Generation Algorithm: en.wikipedia.org/wiki/Maze_ge...
Videos:
🔴 Live Stream Archive: • Coding Train Live 35: ...
Related Coding Challenges:
🚂 #51 A* Pathfinding Algorithm: • A* Pathfinding Algorit...
🚂 #76 10Print: • Coding Challenge #76: ...
🚂 #171 Wave Function Collapse: • Coding Challenge 171: ...
Timestamps:
00:00 Introduction
01:15 What are we Building?
03:18 Create a Grid of Cells
08:10 Draw the 4 Walls Separately
11:03 The Anal Retentive Coder
12:30 Store the State of Walls for each Cell
15:07 Recap, See You in Part 2!
Editing by Mathieu Blanchette
Animations by Jason Heglund
Music from Epidemic Sound
🚂 Website: thecodingtrain.com/
👾 Share Your Creation! thecodingtrain.com/guides/pas...
🚩 Suggest Topics: github.com/CodingTrain/Sugges...
💡 GitHub: github.com/CodingTrain
💬 Discord: / discord
💖 Membership: ru-vid.comjoin
🛒 Store: standard.tv/codingtrain
🖋️ Twitter: / thecodingtrain
📸 Instagram: / the.coding.train
🎥 Coding Challenges: • Coding Challenges
🎥 Intro to Programming: • Start learning here!
🔗 p5.js: p5js.org
🔗 p5.js Web Editor: editor.p5js.org/
🔗 Processing: processing.org
📄 Code of Conduct: github.com/CodingTrain/Code-o...
This description was auto-generated. If you see a problem, please open an issue: github.com/CodingTrain/thecod...
#maze #recursion #backtracking #depthfirstsearch #p5js #javascript

Опубликовано:

1 июн 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 232

@DePistolero 7 лет назад

5 seconds into the video, liked, 6 seconds, subscribed, 7 seconds noticed the amount of the videos suggested on the right... Where have you been all my life :) ?? Thank you.

@schneeekind 7 лет назад

DePistolero yea same here

@muhammaduzair2863 2 года назад

From the future here! This is f**ing good man! Honestly your way of teaching is fabulous.

@Danicker 7 лет назад

16 minutes and he creates a gird... Jks it would take me 16 minutes to get the line to be white. You are very talented!

@TheCodingTrain 7 лет назад

haha, thank you!

@ImMimicute 7 лет назад

Danicker I think I'd give up and pull out a crayon before I made it to 16 minutes

@tcchan14 6 лет назад

1 hour and he finish the challenge. For me, I use about two days

@calebsherman886 6 лет назад

I would take 2 days, and about 30 times referencing this video.

@RedsBoneStuff 7 лет назад

I really like the fact that you generate a maze where with actual walls for walls, rather than one with squares for walls.

@LucasOliveira-dj6gg 5 лет назад

THE BOB ROSS OF CODING

@martinnieva8484 5 лет назад

That's called "Bisqwit"

@porx 5 лет назад

let human = bobRoss; function bobRossToCodingTrain(input) { input -= afro; input += glasses; input.beard *= 0.5; return input; } human = bobRossToCodingTrain(human);

@bobingstern4448 3 года назад

@@porx yes

@ImJiom 2 месяца назад

more like the richard simmons of coding

@KDChenStudio 7 лет назад

Man, i feel so much fun following the way how you approach the solution.

@badnessofhour 6 лет назад

this is a mazing video. =)

@TheCodingTrain 6 лет назад

😂

@blinzi69 6 лет назад

that comment is highly undertated! :-)

@lowbunny7 5 лет назад

Ugh... puns will be the end (not really) of me!

@WoodyPembs 6 лет назад

Your video (its the first one I've seen) is really helping wake up my 'programming brain'. I used to write code pretty much as easily as writing a shopping list, but that was thirty years ago! I've set myself the task of creating a dungeon game and been thinking about maze generation. Books are fine but your clear presentation style (particularly the shared thought processes) are getting my head back into gear better than hours of reading have done. Thanks!

@TheCodingTrain 6 лет назад

Love hearing this thank you!

@Insanesurf 7 лет назад

Haha I almost died when you went "top, middle, right, wait...", despite having done the silly song trying to remember the correct order xD. Great videos BTW, subscribed.

@smileforworldmotivationcha7144 2 года назад

I love the way you are too excited to explain things. Thanks so much

@BlueDayReborn 7 лет назад

Subbed, you sir are the most amazing programming mentor! Thanks!

@khineaindray 5 лет назад

Your video did really help me. I wish I would have watched this first before finding in somewhere else. And the way you explain was amazing and it's easy to understand. Thank you so much.

@TheMinecraftMan11100 7 лет назад

While I primarily code in Java, I've been drawn to these because you're just so energetic! You always describe what you're doing so well, but I was wondering if you could do a series on Java programming? I'm inexperienced with coding in general, and I've been using your videos to learn. Thank you!

@TheCodingTrain 7 лет назад

Check out all my Processing + Nature of Code videos, those are all processing.org which is Java.

@RifqiPriyo 8 лет назад

"top, right, bottom, left" is what you'll use in CSS shorthands (like padding, border, and margin). 😁

@TheCodingTrain 8 лет назад

+Muhammad Rifqi Priyo Susanto aha! Good point!!

@LegendaryFartMaster 5 лет назад

@@TheCodingTrain I like to remember it as NESW, Never Eat Sea Weed

@flamingowrangler 2 года назад

@@LegendaryFartMaster 1984

@DavidBauer38 2 года назад

The “top right bottom left” seemed to be giving him a bit of TRouBLe!

@SkyenNovaA 4 года назад

A simple and fun way to explain maze generation, thanks!

@ScienceGuides 5 лет назад

Returning to this video long after seeing it the first time. :-) I really enjoy your library of videos. It helps being creative with programming, to see your examples, and in this case, I actually needed a way to generate mazes. THANK YOU! Best regards - Søren

@ResetBox15 7 лет назад

You're exactly what I look for. Explain only what to explain and quickly, without mince words

@yashashav_dk3766 5 лет назад

Mr Coding Train, I love your enthusiasm.

@jorensminats5605 7 лет назад

I love these Coding Challenges, I don't know how to code, but It's still very fun to watch!

@up4life108 7 лет назад

Just begin !

@milkyroad9593 7 лет назад

Hey Daniel. Greetings from Germany. I love your videos. Programming + humor. "We're getting somewhere - eventually" hahaha. Keep doing your videos please.

@toxicsnails 5 лет назад

I’ve always taught my students to remember TROUBLE when writing top, right, bottom, left (TRBL)

@mightyleguan1451 7 лет назад

I really love your videos and I am currently following along the Intelligence and Learning playlist. The only thing I am afraid of is that by watching more of your videos I might start making the *this.* mistake more often. :D

@cyral_u 7 лет назад

Your problem solving skills are mind blowing

@chrisgermann7414 7 лет назад

Daniel your videos are just awesome. You are the reason i switched from electrical engineering to computer science. Love you man, keep up the good work :).

@TheCodingTrain 7 лет назад

Thanks for the nice feedback!

@SyemaAilia 5 лет назад

This guy makes me literally laugh out loud

@piyushmajgawali1611 4 года назад

p5 js is so easy to use went to the web editor,followed the video,made sense Thanks

@ihatethesensors 5 лет назад

Dude, your videos are awesome!

@puke1523 5 лет назад

Awesome idea! Remade this in Java, and it also solves itself afterwards, really fun!

@Malik-lo7tw 4 года назад

what algorithm does it use to solve it ? :)

@NicholasWautier 7 лет назад

Commenting your code can help with those memorization issues you're having ;) Seriously though, great video! Thanks for not editing out your mistakes... It helps to see others going through those kind of issues!

@pdsmart 2 года назад

I am SO like you. LOL. I LOVE to have things to line up!! I swear, I need to write my OWN formatter for Visual Studio.

@TheCodingTrain 2 года назад

Hah, thanks for the comment and the support!!

@SarasamirSarasor 22 дня назад

Thank lots , this maze generator related to reinforcement learning (neural network)??plz tell me@@TheCodingTrain

@Josh01363 3 года назад

I’m doing maze generation and pathfinding for my college coursework and ur vids are helping a lot even though I’m doing mine in a different language

@esrako 2 года назад

hey! in which language did you create the maze?

@vbcoachwasi 4 года назад

I love your style!!

@thomasruck4139 5 лет назад

I built a java program in Processing a few months back creating randomized mazes, at this time I wasn't considering algorithms in the code, just breaking the problem down and solving it one step at a time. I am really curious to figure out now what sort of algorithm I have created. All my mazes are solvable. When small a little predictable, when larger totally fun to try and solve.

@brandonmoffett3835 4 года назад

Thank you so much for this man!

@theredstormer8078 4 года назад

Very helpful. I am in the process of making a 3d maze generator for Minecraft to confuse people on a server trying to traverse an underground base and I'm hoping this can be translated into 3d then sliced into various images so I can convert those into schematics in-game.

@ArthurPasqualottoakak 8 лет назад

I just love watching your videos

@TheCodingTrain 8 лет назад

+Arthur Pasqualotto thank you so much!

@bennybrouwer 6 лет назад

After having programmed so many bouncing balls in all the introductory courses, I have the feeling that now the fun begins. Compliments for interesting and challeging lessons.

@Grimlock1979 4 года назад

I always use r and c for loop variables to indicate rows and columns.

@pedro.fontoura 26 дней назад

Using both this and the ray tracing algorithms, I made a 2D micro mouse simulator. Your (first and basic) goal is to program the mouse to wander the maze, avoid hitting the walls and getting stuck. That is NOT a simple task. You can explore many algorithms: maze solving, self-driving (AI, robotics, ...).

@AA-em3lw Год назад

Thanks for another great video, I have OCD too :P

@NeilRoy 5 лет назад

Depth First is nice if you want long passages. I want to use one for a more interesting game with many branching hallways, so I found Prim's Randomized to be the best for that. In one implementation I had my program choose which algorithm at random, and then generate the maze, which was kind of interesting and gave more variety. In my own program I wanted to generate a sort of "3D" Text maze. But an interesting use for these I recently found was generating a random platform game! Which I thought was a very kewl use for maze generation. It's making me think of different uses. I was surprised at how easy these are to understand and implement.

@TheCodingTrain 5 лет назад

Thanks for this feedback!

@av3stube480 6 лет назад

I HAVE this kind of thing, but it's not a problem, it eliminates the possible bugs steaming from nit understanding what you wrote because it was too packed up.

@condor07usa 7 лет назад

altough i am much of a php guy, your videos are helping me learn oop concept which is still a mistery to me. btw you should turn the volume of your vids down little more since i can still barely hear you

@ShowMeSomeCode 7 лет назад

Amazing Daniel! I uploaded a music reactive particle system in my channel inspired on your tutorial! Thank you for sharing knowledge with us.

@DrSpooglemon 3 года назад

If you make local 'w' and 'h' variables then you can pass those in as line argumants and it make it look neater without the need for whitespace; line(x, y, w, y); line(x, h, w, h); line(x, y, x, h); line(w, y, w, h);

@kevnar 6 лет назад

You only need to draw the Top and Left line. If the line of the next cell over is true, the line will be there. Then, when the walls are all done, draw a box around the whole thing, minus any exits. Also, I used an integer for the walls. if the 1 bit is on, the north wall is there. 2 is for the east. 4 is for south, and 8 is for west. If the walls integer is 15, that means all walls are there. If it's 5, only the north and south walls are there. Simple binary math. To knock down a wall, just subtract the correct number for that direction. So 15 - 8 removes the west wall, 15 - 1 removes the north wall... and so on. Later when you're solving the maze, to check if a wall is present, you just say: this.isWall = function(intWalls, dir) { return (intWall & dir) != 0; } Where intWalls is the integer for which walls are up, and dir is the direction you want to go in, 1,2,4, or 8. The bitwise & returns 0 if the path is clear. And if it's not equal to 0, then the wall is there, and the function returns true. It's quicker than four different if/thens for each wall.

@tzq33tdq 7 лет назад

I'd use vars for each corner like tl (top left), br (bottom right)

@caljohn1475 Год назад

Thanks!

@TheCodingTrain Год назад

Thank you for the support!

@7Argeus 7 лет назад

Hi you're videos are great and im going through every single one just seeing how you approach these problems and what kind of stuff you can do with code, i was wondering if you would be able to suggest a good program to download for free preferably or a program to buy if i must do so, if so i would greatly appreciate it, and also do you have any recommendations for beginners? Like a good starting point, im doing engineering now at the moment and i love my C++ program im doing, we currently use eclipse in class, will that work for this sort of stuff or no? Also would you be able to do a video on creating a game of chess maybe? thanks again keep up the great videos

@DowzerWTP72 5 лет назад

Just been set the MicroMouse Challenge for second year Robotics at University. We haven't been given any rules yet, nor do we know the groups, but I have decided to begin the software for the bot. Because the maze we will solve will be random, but of known dimensions, I am going to creat my own maze generator, then once that is done, somehow create an algorithm which maps the maze in memory, then finds the fastest route to the goal (which is the centre), and produces a path. I think once I have the maze generator done, I am going to remove it's graphical side, and just have it generate in the 'setup()' function, then have the path creation run afterwards, then finally draw it all to the canvas once complete. We have to do it in C, but I think for developing the theoretical code for the bot, this is a good idea. Plus if all else fails, at least I'll have an awesome simulation!

@rainbowcemetery 7 лет назад

i made an olde timey random maze game a while back, though i only gave cells the potential for a south and east wall. if that's better or worse that having all 4 i don't really know :o

@robdallachiesa 6 лет назад

I like this topic

@InsectInPixel 8 лет назад

Hi Daniel,I LOVE the way you teach code! You make it fun. You should teach kids. I have a quick question. Each Square has four lines. So looking at the grid, there are two lines because squares are connected to one another. correct? ( with the exception of the squares around the perimeter of the grid ) You will probably go over details in the next video.

@TheCodingTrain 8 лет назад

+InsectInPixel If I understand correctly, yes that is right! Even though each cell as 4 lines associated with it, each line overlaps exactly with the lines of its neighbors and therefore you just see what appears to be a grid.

@Jono_1987 7 лет назад

I did the song and dance with you now I feel great!

@TheCodingTrain 7 лет назад

Yay!

@ibrahim47 5 лет назад

the spaces part killed me XD

@ACS20596 4 года назад

I am interested in creating a first person maze survival app, and would appreciate any advice towards that goal!

@stanislavyankovskiy1374 5 лет назад

great

@ritikkhatri 6 лет назад

13:23 is my favourite part of the video

@iceboy5418 7 лет назад

How I found you? I don't know How much I love your vids? Very much

@toxications 5 лет назад

Is it possible to create a single for-loop that loops n integers?

@waltercisneros9535 4 года назад

12:10 nope, I like my identation the way you have it as well.

@aylictal 5 лет назад

why wouldn't you use an object instead of an array for this.walls? that way you wouldn't have to keep remembering which walls correlate to which values. this.walls = { top: true, right: true, bottom: true, left: true } this.show = function(){ if (this.walls.top){ //draw top wall} //etc }

@PhilU2B 7 лет назад

Your version of p5.js has what MS calls intellisense --- shows options as you are entering code based on what is being typed. The windows version I downloaded does not exhibit this action. Is that a separate library that is provided with the Mac version? Where can I download it (and how to install it). I am using your site to get familiar with javascript and java -- your teaching style is informative and entertaining.

@realcygnus 7 лет назад

I asked the same thing several times & never got a response.....found out/eventually realized....hes using atom here for the editor......& its not really like an intellisense.......its just hints/tips (only based on spelling of cached/existing words)....rather then actual available data/members & such......which is surprising cuz there are many 3rd party add-on packages available......but they didn't have such a thing when I checked/installed it.

@mspeir 5 лет назад

I would love to find an iterative method to generate perfect mazes. I have some C++ code that I've optimized and compressed the data structures as far as I can, but the recursion places limits on the size of the mazes through stack memory. I was working on a game in which each level was bigger than the last, with no upper limit. Even with my computer having 16GB of RAM and writing the code to use 64 bit addressing, I couldn't generate mazes past 10,000x10,000 cells. Huge, I know, but still an upper bound. Sadly, the memory requirements are mostly due to the stack. Without it, I could fit a maze about 100x's the size in the same memory.

@MrEliteXXL 3 года назад

12:16 You forgot to align the parentheses! Ahahah

@ambientsoda106 3 года назад

Hey would you do a challenge on creating a program that can create and run a function using ai? Meaning you dont write the function yourself in the definition area

@DodaGarcia Год назад

"Being very careful to center the tape on the bag"

@vishesh8746 7 лет назад

you are inspiring

@Tracy7689 3 года назад

Is there a way to make a 3D maze with this? I’m not so good with coding, but I think if there were 6 walls it might work in 3D.

@vladosononame6376 5 лет назад

Not using p5 too, but this kind of work on any browser if you use right logic

@mementomori5580 7 лет назад

If you want extensive information about mazes and maze algorithms (but basically no code), here is a site that might interest you: www.astrolog.org/labyrnth/algrithm.htm

@juniordev4190 7 лет назад

Its just giving me serious trouble(TRBL) : Top Right Bottom Left :D

@lsddcrew1794 5 лет назад

"uncaught referenceError: Cell is not defined (sketch: line 15) [this line var cell = new Cell(i, j); ]what is the error? please help me?

@bominrahmani9559 5 лет назад

var Cell = new Cell(i,j); you need to capitalize the first cell or lower case the cell following new.

@jasdeepsinghgrover2470 7 лет назад

top right bottom left is a big trouble to remember so just remember trouble as in trbl ... top right bottom left

@benhardsim8629 2 года назад

You could make the top,right, bottom,left boolean value inside an object instead of array, that would be more readable

@mrevson74 Год назад

Or indexes. TOP=0, RIGHT=1, BOTTOM=2, LEFT=3. Then do if(walls[TOP]) {......}

@aryamaangoswamy179 5 лет назад

Clockwise from top would've made it easier to memorize.

@LoPhatKao 2 года назад

11:09 makes me wonder how long you've been brewing up the April Fools 2022 video

@MrMile40 5 лет назад

I just wanted to know... imagine that the labyrinth is finished. How do i do if i want t reset each rectagle fill to noFill ?

@ctbram0627 21 день назад

make the maze then make an A* program to find the shortest path out of it?

@hunterbattles130 7 лет назад

Hey you should do this in processing, please and thank you!!!

@tnsaturday 4 года назад

4:25, sketch.js, line 10 Where are the width and height variables come from? We've never defined them, yet we use them.

@lbgstzockt8493 4 года назад

width and height refer to the dimensions of the canvas in pixels, its not a variable but more of a state, its like asking javascript "yo how wide is my canvas"

@JorgeGonzalez-cs2io 3 года назад

@@lbgstzockt8493 thank you

@angelcaru 2 года назад

p5.js

@atrumluminarium 7 лет назад

Ever considered coding one that can generate circular/hexagonal mazes?

@TheCodingTrain 7 лет назад

Great idea!

@rahulbera454 5 лет назад

Thanks a lot for this !! Can you please tell how to solve this maze ?

@mrmugame 5 лет назад

You can use the A* algorythm He Made a Video abou it

@bobingstern4448 3 года назад

How can you make it so that there are square walls?

@flowfrog101 6 лет назад

10:57 mental breakdown ;D

@sillysock1508 4 года назад

Can u make it like a town layout like a maze with many paths thru it please and like there is more than one exit and entrance if u can try and or do this I would be amazed and so thankful and happy

@brucewernick6542 4 года назад

I followed your maze videos using standard HTML5 and VSCode (not p5). There is a small glitch that is a bit confusing. With my canvas width attribute at 400, I use the following to get the width in my JavaScript: var width = canvas.scrollWidth; But, strangely, the width is 399 (1 pixel less)! The scrollWidth is used in W3Schools and seems to be a common way to get an element width. Even more strange is that my same code gets the correct width of 400 in the W3Schools TryIt editor. What could be happening here?

@brucewernick6542 4 года назад

I did some more searching. Turns out there are many ways to get an element size. scrollWidth getBoundingClientRect() offsetWidth clientWidth Problem is, they are not consistent. I'm leaning towards using offsetWidth .

@erkoriley23 7 лет назад

Do you show somewhere how you set up Atom for these coding challenges?

@TheCodingTrain 7 лет назад

A little bit here: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-d3OcFexe9Ik.html

@erkoriley23 7 лет назад

Awesome! Great videos btw.

@denisschulz3814 6 лет назад

floor() is not working for me... any ideas why?

@PedroCouto1982 2 года назад

13:01 You could have used flags and constants. ``` const TOP_WALL = 1; const RIGHT_WALL = 2; const BOTTOM_WALL = 4; const LEFT_WALL = 8; ... if (walls & TOP_WALL) { ... } ```

@PaulGoux 5 лет назад

If anyone is interested in a hexagonal maze, here is an example based on this code. it has other functionality too such as mouse interaction. Uses multiple tiles to create the maze rather than just one. Can toggle tiles on and off by clicking, or by dragging. Could be useful if you wanted to make a game like civ. editor.p5js.org/paulgoux/sketches/eiY8BkMUm Ps I know you recommended the contributions page, but I don't understand how to share things there. :/

@MrSwift2568 5 лет назад

When you create an array for the sides booleans, you should have immediately written a comment that gives a key for the array // [Top,Right,Bottom,Left]

@whenthingsgetright5351 7 лет назад

i can understand the struggle...

@Andreas_Mann 7 лет назад

you dont need some weird rhythmic song to remember the order. its just clockwise dude ^^ i am starting to work with the SFML lib in c++. will it be sufficient to create this project? if not, what would you recommend? fun video as always!

@guyr989 7 лет назад

so...top right bottom left?

@suxo 7 лет назад

Hi Daniel, the github repository link is broken. cheers

@ACS20596 4 года назад

For mine, both 'grid' and 'this' are not red. Could that be why my screen isnt showing what you have?

@ACS20596 4 года назад

nevermind! Thanks for the lesson

@samuelcoelho5267 7 лет назад

I have gotten to 11:13 in the video, and my code already has an error. I have tried so much to fix it, but I can't find away. For some reasons, the left and the right walls of each cell do not show up. Has something changed in p5.js, or am I just doing it wrong? My code: pastebin.com/RMH6pp5a