Coding Challenge #10.1: Maze Generator with p5.js - Part 1
ฝัง
- เผยแพร่เมื่อ 15 มิ.ย. 2024
- 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: th-cam.com/users/thecodingtrainjoin
🛒 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
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.
DePistolero yea same here
From the future here!
This is f**ing good man!
Honestly your way of teaching is fabulous.
I really like the fact that you generate a maze where with actual walls for walls, rather than one with squares for walls.
THE BOB ROSS OF CODING
That's called "Bisqwit"
let human = bobRoss;
function bobRossToCodingTrain(input) {
input -= afro;
input += glasses;
input.beard *= 0.5;
return input;
}
human = bobRossToCodingTrain(human);
@@porx yes
more like the richard simmons of coding
Man, i feel so much fun following the way how you approach the solution.
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!
Love hearing this thank you!
this is a mazing video. =)
😂
that comment is highly undertated! :-)
Ugh... puns will be the end (not really) of me!
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!
haha, thank you!
Danicker I think I'd give up and pull out a crayon before I made it to 16 minutes
1 hour and he finish the challenge. For me, I use about two days
I would take 2 days, and about 30 times referencing this video.
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.
I love the way you are too excited to explain things. Thanks so much
Subbed, you sir are the most amazing programming mentor! Thanks!
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.
I’ve always taught my students to remember TROUBLE when writing top, right, bottom, left (TRBL)
A simple and fun way to explain maze generation, thanks!
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!
Check out all my Processing + Nature of Code videos, those are all processing.org which is Java.
I love these Coding Challenges, I don't know how to code, but It's still very fun to watch!
Just begin !
You're exactly what I look for. Explain only what to explain and quickly, without mince words
Mr Coding Train, I love your enthusiasm.
This guy makes me literally laugh out loud
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
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 :).
Thanks for the nice feedback!
"top, right, bottom, left" is what you'll use in CSS shorthands (like padding, border, and margin). 😁
+Muhammad Rifqi Priyo Susanto aha! Good point!!
@@TheCodingTrain I like to remember it as NESW, Never Eat Sea Weed
@@LegendaryFartMaster 1984
The “top right bottom left” seemed to be giving him a bit of TRouBLe!
Your problem solving skills are mind blowing
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
Hey Daniel. Greetings from Germany. I love your videos. Programming + humor. "We're getting somewhere - eventually" hahaha. Keep doing your videos please.
p5 js is so easy to use
went to the web editor,followed the video,made sense
Thanks
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!
Dude, your videos are awesome!
Thank you so much for this man!
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
hey! in which language did you create the maze?
I love your style!!
Awesome idea! Remade this in Java, and it also solves itself afterwards, really fun!
what algorithm does it use to solve it ? :)
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.
Hah, thanks for the comment and the support!!
Thank lots , this maze generator related to reinforcement learning (neural network)??plz tell me@@TheCodingTrain
I just love watching your videos
+Arthur Pasqualotto thank you so much!
I always use r and c for loop variables to indicate rows and columns.
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, ...).
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.
Thanks for another great video, I have OCD too :P
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.
Amazing Daniel!
I uploaded a music reactive particle system in my channel inspired on your tutorial! Thank you for sharing knowledge with us.
the spaces part killed me XD
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.
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.
I'd use vars for each corner like tl (top left), br (bottom right)
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.
I like this topic
Thanks!
Thank you for the support!
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.
Thanks for this feedback!
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!
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
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
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
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);
I did the song and dance with you now I feel great!
Yay!
great
I am interested in creating a first person maze survival app, and would appreciate any advice towards that goal!
How I found you? I don't know
How much I love your vids? Very much
"Being very careful to center the tape on the bag"
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
}
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.
+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.
13:23 is my favourite part of the video
12:10 nope, I like my identation the way you have it as well.
"uncaught referenceError: Cell is not defined (sketch: line 15) [this line var cell = new Cell(i, j); ]what is the error? please help me?
var Cell = new Cell(i,j); you need to capitalize the first cell or lower case the cell following new.
Not using p5 too, but this kind of work on any browser if you use right logic
Is it possible to create a single for-loop that loops n integers?
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.
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.
you are inspiring
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
top right bottom left is a big trouble to remember so just remember trouble as in trbl ... top right bottom left
Clockwise from top would've made it easier to memorize.
Hey you should do this in processing, please and thank you!!!
Its just giving me serious trouble(TRBL) : Top Right Bottom Left :D
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
11:09 makes me wonder how long you've been brewing up the April Fools 2022 video
You could make the top,right, bottom,left boolean value inside an object instead of array, that would be more readable
Or indexes.
TOP=0, RIGHT=1, BOTTOM=2, LEFT=3.
Then do if(walls[TOP]) {......}
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 ?
12:16 You forgot to align the parentheses! Ahahah
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.
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.
How can you make it so that there are square walls?
make the maze then make an A* program to find the shortest path out of it?
Ever considered coding one that can generate circular/hexagonal mazes?
Great idea!
10:57 mental breakdown ;D
i can understand the struggle...
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
so...top right bottom left?
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]
Thanks a lot for this !! Can you please tell how to solve this maze ?
You can use the A* algorythm He Made a Video abou it
floor() is not working for me... any ideas why?
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. :/
TeRriBLe - mnemonic for Top-Right-Bottom-Left
editor = atom.io/
Hi Daniel, the github repository link is broken. cheers
15:59 ahahha
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?
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
.
Do you show somewhere how you set up Atom for these coding challenges?
A little bit here: th-cam.com/video/d3OcFexe9Ik/w-d-xo.html
Awesome! Great videos btw.
For mine, both 'grid' and 'this' are not red. Could that be why my screen isnt showing what you have?
nevermind! Thanks for the lesson
4:25, sketch.js, line 10
Where are the width and height variables come from? We've never defined them, yet we use them.
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"
@@lbgstzockt8493 thank you
p5.js
Make a video on different Sorting Algorithms with visualization.
You might wanna check out Sound of Sorting. I’m not sure that it’s a tutorial, but it is a visualization of many different sorting algorithms
I am still saying top right bottom left... When should I stop? It's getting really awkward...