If you are in a hurry and like to clone code, you can use almost *the same algorithm* as this generator, and *replace the random direction part with exploration test.* But you'd better use *_double-ends-A_** algorithm instead. Feel free to prove me wrong, or to call me to work together on *amazing* 2D, 3D, nD maze generators and solvers.
I found a new use for this algorithm! It's really good at generating oceans/continents. Visited cells are water cells, unvisited are land cells. If the algorithm stops after visiting about 60% of the cells you can get smaller and larger islands, continents, even some rivers! Really cool stuff 👍
@@Noone-rc9wf I can tell you it isn't the same guy... My coding sucks ass.... if I make a asterisk bounce round the screen I start dancing around the room.... I'm just a nice person giving someone positive feedback...
Cheers Konstrukt! I'm not very good at promoting the channel. Sure I'd love more views, but I'm not monetising so there's little incentive for UA-cam to promote the channel either. As long as people engage with the content - I'm happy! No "Hey Guys! What is up?" dodgy thumbnail click-bait rubbish from me..
I absolutely love your coding style! So clean and understandable, without unnecessary complications. I'll try to learn from you, thank you for all your content!
I found this channel while I was looking for how a game coder works - not a video with visual impressive graphical presentation, but the "ugly" unspectacular hard part of coding thousends of lines and how it is possible to keep an overview. Then stuck to your channel because the quality of your videos especially the content (programs and explanations) is excellent and I learned much here (for example the use of the modulo operator and many other "tricks") I like how you concentrate on what matters - the ideas and algorithms and how smart you code. Today I finished my own (primitive) maze program with the 15 unicode chars 0x2554, 0x2557 and so on, without using one of your game engines but with parts of your code and ideas. It creates the maze in one tick so it is not as good for visualisation as yours but it shows me that I really understood your code. To repeat all calculations in every single frame (OnUserUpdate function) is very time consuming and only possible in that ultrafast C/C++ language (or maybe assembler if one is capable of coding in this). Greetings from Germany and I wish you many good ideas for more programs to show.
A couple of years ago, this video of yours inspired me to writing my first Python/Tkinter application: my idea of coding something useful for practice and keeping my grandchildren quietly entertained. Little did I know that after all this time, a discussion in redditt's r/learnpython thread led me to tell the world about it. The response was amazing, and I have felt compelled to use Github for the first time to make available my first clumsy effort. The code starts with a couple of sentences where I told this story and show my indebtedness to your original presentation; coupled with a proviso that you are not responsible for the 'quality' of the coding. Thank you so much.
Yeah it is. Breadth First Searches like this are a staple computer algorithm that have been around since the dawn of programming. By eliminating the need to recurse, it also removes all the problems associated with recursion too.
this was our final project for "introduction to computer science 2" in college; we used both a dfs/stack and bfs/queue (and we had to make the stack and queue). we also had to find the shortest path from the entrance to the exit. ours used ncurses in a gnu/linux terminal! if you have been programming for a couple months, i'd strongly recommend trying that out, it taught me a ton about a programming.
Never ceases to impress me how you can take a advanced concept and break it down to very simple terminology. In just the first five minutes you've broken the method by which the algorithm operates down enough for me to understand how to implement it programmaticly.
I once made a 4D maze. At every location of the maze, you could go up, down, left, right, backward, or forward, but you could also warp to an alternate maze and continue from there. Very easy to design with this algorithm, but very confusing to solve, especially since the display was only 2D.
The way you‘re using bitwise operations has somewhat opened my eyes. I knew about bitwise operations and I also knew about using sums of powers of 2 to store information (e.g. in chmod commands), but I never thought about using it to essentially store several booleans in a single value. Thank you for this video!
Yep, bit flags are very useful, especially for passing a single argument to a function that toggles several different modes of operation. Modern C++ also has bit fields: struct something { int a:1; int b:2; int c:3;} etc. a is basically a boolean, but c:3 could have a value from 0-7. If you need very small integer values you can pack them into a single byte or the smallest integer type that will fit them all. You can't pass pointers or references to them though, only by value.
Thanks. Really good information. I don't understand some of the newer C++ syntax, but that's ok. I understand the algorithm, thanks to your video. I decided to make this algorithm work on the old color computer from Radio Shack in basic with 64k. But only 32k is available. I wanted to make a maze of grid size 127x95 in a resolution of 256x192. I needed a array of 12065 bytes to hold the grid. Then another 24k for the stack. That is roughly 36K. Way over the amount I have to work with. I came up with a different way to save space .So instead of using a stack to hold x and y locations of cell, I decided to use 2 bits in the cell array data to hold a number between 0-3. Those numbers would represent the direction that the cell came from. Now, each byte in cell array has 4 bits for the walls, 1 bit for visited or not.1 bit for backtrack or not and 2 bits for direction cell came from. Some crazy reason, it worked. :) Anyway, I thought I would share my algorithm modification info in case anyone else ran into memory constraints on old retro computers. I was able to cut memory usage from 36K to 12K.
Personally I also did this but instead of keeping which direction each cell came from I actually while generating the maze have all walls built, meaning it's just a grid of squares and each time I move to a cell I break the wall in the direction I went, that way I do not need to store any direction but instead just perform it instantly.
Just something small I noticed. You don't need to keep a count of the number of cells visited. If you reach the bottom of the stack and there are no neighbors, then you know the maze is done. Upon further reflection, I think reaching the bottom of the stack will always leave you with no neighbors. Say everywhere in the maze is filled in, except one cell directly neighboring the start cell. As the stack pops, it will encounter a different neighbor of that cell before returning to the start cell, and this different neighbor will generate the path instead. Similarly for any larger empty region, we must fill it in before we can pop the stack to the bottom.
If you got a stack of 2000 cells, you repeat the same code till your stack is empty, using a count variable would automatically stop the algorithm when it's done
*Stacks of tiles are fun* because they make generating mazes look like solving mazes, but otherwise I don't see the point of *wasting computation time and energy* using them for maze generation. 1. You could link new tiles to the existing graph in *any fucking (or even non-fucking) arbitrary order,* including random and discontinuous, as long as you *mark each tile's branch* well, which can be done in a single step each time a tile is added. 2. Even if you want to go through the graph in a particular order for whatever reason of controlling the maze's properties (e.g. limiting the length of straight corridors, or the number of consecutive turns on the same side, or the distance between two branches, etc.), backtracking is *extremely quicker from one **_branching_** node to the next, than from any one tile to the next.* Feel free to prove me wrong, or to call me to work together on *amazing* 2D, 3D, nD maze generators and solvers.
ah, such fun! I coded something very similar when I was a little kid, and I still like to watch you make algorithms like this. more, we want more! ;-) subscribed.
thanks to this video I learned bitwise operations and better understood hex numbers, thank you!) First two days I only understood the general operation of the code while struggling to figure out what |= and & means in the particular case but on the third day I finally figured out everything Had to spend some time with pen and notebook studying code symbol by symbol. I am very grateful for your videos and the fealing of satisfaction after understanding everything!
Saw 8bits of C++ first, ehh, then this one, subbed... might be a good idea to close any unused toolbox and explorer windows, to get more code on screen, as well as roll back the zoom a bit, and hide the main menu... great video, thanks!
I take that back, 8 bits was second - I watched "What is Assembly Language?" first. Inspired me to start using OneNote again... now that I have a Surface. I gave up on C++ years ago, in favor of VBA, Ruby, and other "scripting" type languages, that satisfied my impatient nature to, "do stuff now", vs getting lost in what seemed to be an endless pit of dependencies, includes, and compiler settings... it was like learning how to build the the tools and the toolbox they go in, when I just wanted to tighten a bolt, but I had to make the bolt too.
16:19 when loops look like that (with math indexed arrays) is usually when I get lost xD 20:10 that's a new one (to me, a lot has happen apparently since I programmed), a function inside a function... Funception!
I really like the way you explain things. Always clean and simple (from a programmer perspective, should I say). Have you ever consider teaching ? Good work, by the way.
I'm really enjoying following along with your projects, which helps to refresh C++. Quick question about your naming convention: why do you put "m_" in front of your variables? What does it stand for?
Thanks! I use an old school technique called hungarian notation, where i include type information in the variable name. In this case "m_" means class member variable. I dont always do this, it depends on the size of the project.
No, but that would be awesome!! I don't know how to do that tho... I just saved a maze as static image and set it as my desktop background... Is there a way to do that automatically?
# include SystemParametersInfo(SPI_SETDESKWALLPAPER, 0, "maze.bmp", 0); Bitmaps are super easy to work with, you can just dump a raw array into a file basically. BITMAPFILEHEADER and BITMAPINFOHEADER are the windows structs for bitmap files, just populate them and dump the memory out to a file, then the pixels, and you're all set. docs.microsoft.com/en-us/windows/win32/gdi/bitmaps
While I agree that this channel should have more than 10 million subscribers, I realize that maybe there are simply not that many smart people in the whole world. It would require something like more than 10 mega smart people.
If anyone runs into an issue with the Windows SDK headers and "byte ambiguity" while attempting to compile this code, or other code that calls on the Windows headers, the issue is that you are using C++17 and the 'std' namespace now defines 'byte', while the Windows headers helpfully also define a symbol called 'byte'. A simple fix that should work for anyone just following along with Javid is to move the 'using namespace std;' statement to be after any '#include' statement that brings in a header that relies on the Windows SDk headers. A more ambitious solution, but potentially problematic, is to "fix" the Windows headers (rename the 'byte' declaration to avoid ambiguity, e.g. BYTE or win_byte, etc). Problematic because they're not your headers, and you're basically creating a non-standard fork of them. And a sidestep to the issue is to make sure you use C++14, instead. This pre-dates the introduction of 'byte' to the 'std' namespace (and is why this issue did not surface earlier). In VS you do this by setting the project properties to the appropriate language variant (and globally defaulting to it, if you like).
I have implemented this algorithm in x86 assembly in tasm and it works wonderfuly! One problem I was having is that if the tracker runs into a backend and as soon as it is out of it it runs into a new dead end immediatly it will back track to the end of the dead end before it. Now it happens of course because it is the last cell being "discovered" as the last ones were just tracking back. while it does not interrupt the algorithm to make a wonderful maze. It does indeed interrupt other algorithms I would like to use with them. I would be happy for your advice or if I have done something wrong. Thank you!
2 mins to create a maze that would take him longer than 1 minute to solve. I see your a Christopher Nolan fan. :) Great video and content. I love how you explain these algorithms. I hope you plan on doing more algorithms.
Your videos are so clean and calm. Regarding this video I have one question, it is supposed to generate a random maze, because no matter how much I run it, it will print the same maze everytime.
Thanks Pengu, you will need to seed your random function. Random is never random on a computer, so you would normally seed the random number generator with a variable that changes such as "time()" to give true pseudo randomness
Thanks for the answer, I've played around with the code and this is what I realised: in your github code you indeed "randomised" the starting spot but it still run the same version everytime. It started to be "random" after I moved the srand(clock()); from the main function to the onUserCreate; Now, I have 2 more questions: - what is the difference between srand(clock()); and srand((unsigned)time(NULL));? - will it make any difference if I reset the seed before choosing a random neighbour? Thanks again for your time and for your work :)
1) nothing really, srand just needs a "random" set of bits to get started. Any function which can provide something you cant easily predict will do. 2) If you reset srand to the same value each time, it will always choose the same number next time you call rand(). resetting srand with a time based function, may have a negligible increase on the quality of the random number, but probably not worth bothering with.
Very cool :-) If I remember correctly I think that you can actually use a queue instead of a stack. Using a queue generates a maze using breath-first traversal, whereas the stack uses depth-first traversal. I would you have liked to see how different the maze looks with a queue instead of a stack :-)
std::list can push and pull from front or back, so you can use it as either a LIFO or a FIFO. Fork the repo and try it out. ;) Although, you might need additional state for each direction on each cell, because the history will be consumed after you take the first branch. I'm sure there are plenty of articles about doing something like that.
Hi. I find your channel very useful to start learning the C++ language. I am having problems with the console windows generation, I am using the olcConsoleGameEngine.h file, but when I create the console with the line "game.ConstructConsole(160, 80, 8, 8);", it shows a window console stretched on the height. And second, I am noticing that the framerate FPS goes very slow on my computer, like 6.00 FPS, when I see that on your computer you have more than 1000 FPS, and I have a good computer. What could be the problem?
Hi Oscar, there could be many things different here, I would suggest using the olcPixelGameEngine instead, its cross platform, and has consistency across compilers
this solution has a many long street without '+' type (cross) branching... I suppose that after 10-12 step randomly open new paralel counting thread :) And randomly open just reached dead end connecting with a neighbour cell... (so make a circuit path). :)
Is there a way to divide larger mazes so that the stack works on chunks of the maze, rather than having a stack equal to the entire maze? As an example, let's say I'm generating an absurdly large 10,000x10,000 cell maze. The cell data array must persist in memory (or be paged from disk as needed), but the stack is temporary. How could I rewrite the algorithm to generate a *perfect maze*
Thanks Andrei, the algorithm is completely unconstrained so you cant specify an end point. However you can specify a start, in my case its top left i think, and because it guaranteed all cells are reachable from all other cells, you can simply nominate a cell as your exit after the maze is generated.
Hey there! Enjoying your vids! I'm having trouble with deriving classes from your code. I downloaded the olcPixelGameEngine, but it looks like that isn't what you're using here. I am guessing you probably get this question a lot, so if you could point me in the right direction I would really appreciate it. Thanks!
@@javidx9 If I remember correctly, I was having trouble with the data types. They are different in this vid than the parameters called for in your function.
all your stuff is very good and enjoyable to follow ^^. it would be very helpful for this vid if when you use your console drawing lib that you put a link-mark to a short vid of how to structure this draw from std::cout ^^ for those who are just trying to get the alg in ^^ (took me longer than i want to admit to restructure for cout output approach, but didn't want to do draws etc. and wanted it to be something where i could just create a 1d-array for usage and send to another module which then figures out what graphic is needed where etc ^^)
I don't see where the need for the "visited" tick list comes from. Couldn't you simply implement the algorithm such that it will iterate until the stack is empty? That would imply that the maze can't be expanded anymore and that all squares have been visited.
Can you please make a video using recursive division and also with this same algorithm DFS but biasing it so that you can, for example, get longer pathways both horizontal and vertical?? Thanks.
Lol Carlos, thats a veeeeeery specific video. You can of course bias the direction by biasing the random number generator. If you want East & West for example, attribute a higher probability to those when choosing
My first thought would have been to store visited/not-visited as a vector and use the indices of the bools as (row, column) to refer to position. Is your convention the more customary one? I want to use an approach that conforms to whatever informal "standards" are commonly used.
Thanks, missing pdb files are an entirely normal output for visual studio projects. They are not errors. It is likely something else that means it doesn't run. It could be your console is too big for your display. Try halving the fontw and fonth values in construct console function.
I know this is an old video, so I'm not sure if I can expect a response or not, but here goes anyways! I've been playing around with the srand() at the end, and no matter what I do it generates the exact same maze and has the exact same starting cell every time. Any advice? Thank you!
your videos are great. Sometimes I spend some time coding along with your videos and concepts just click. But truthfully, i'm currently confused about the third nested for loop in the onuserupdate() function dealing with the walls for the maze.
You mean the drawing code at 15:34? That's looping all the console characters in a single cell, so it fills in the whole cell instead of just one "pixel" of it.
I can do some things very quickly with bits, such as set or unset multiple bits at once, I can check if all the bits are set or none of the bits are set quickly too. I can also exploit mathematical tricks using the binary representation of numbers to speed up decisions and implement complex decision trees. Lots of reasons!
Do you think you will ever create tutorials for creating games with more advanced graphics? Such as SDL, OpenGL or DirectX? :) Let's say you want to create a nice-looking 3D RPG. Also, a tutorial for a simple strategy game might be fun!
Yes probably, but I would not focus on "how to do a directx game" for example. The console is nice because I dont have to explain about how to set anything up, using advanced libraries starts making the video about the advanced library, and not the techniques used in the algorithms and games. I can say there is a strategy game in the works! and a 2D RPG game, and some console based 3D graphics too! A lot of projects fail because there is initial excitement about making it look pretty and doing fun things like sprites and models, but then the dev has no idea what to do with the pretty things - I'm just as guilty of this than anyone else! :D
If you were to draw a full grid, you can produce the maze by deleting walls wherever there is a link from one cell to another. What I like to do is create a binary array containing the what it would look like if there was just a left wall (3 way intersection). Rotate that array 3 times to produce the other walls (multiply by a rotation matrix). Then using binary AND operations, you can produce combinations of the 4 walls to make every possible cell that can occur in the maze. If you represent each one with 4 bits, the bits can tell you which walls to draw where. For example, 1111 would mean draw the Up, Down, Left, and Right walls. 0101 could mean draw the Down and Right walls, but not the Up or Left walls. If you store all of the possible 2d binary arrays to define the walls in numerical order with this binary encoding, you can define how to draw the walls easily. Create a 2d array to store the binary drawing array for every cell in your maze. Start off with 0 (no walls drawn anywhere). For each node in the maze making algorithm, AND together the walls that shouldn't be there. So if there's a connection to the node above and below, but not left or right, you AND together 1000 and 0100 to get 1100. Now the final step is to apply the NOT operation to every cell in your array (the easiest way is to do 15 - val for each cell, though this isn't the most efficient way). The final result is a map telling you which set of walls to draw in every cell. Now just refer to your binary arrays for the wall configurations and actually draw the walls. Hopefully this helps.
Wow! That’s cool you are very good at making mazes I will try it right Now! Thank you For the video! Like this comment if You guys want to see me make a soccer game on scratch or anything you want Ok guys!!!!!!
Or, you could just use the "maze equation": www.desmos.com/calculator/pth16uwlqp (not sure if the link shows though). Anyway, just kidding. These are excellent videos! I've been on and off C++ for... let's say some time :) But I never really advanced from cout lol. And here you are making interesting stuff with basically just that! This makes me want to re- (re- re- re-) visit C++ (well I do use it for Arduino's sometimes, so there's that even if I'm not that advanced with C++. Yet).
Whaaaaaaaat? That function is crazy! Now I'm playing with it to see what changes. Looks like the exponent of 10 is like the seed (307 is where floating point precision breaks down), the last number is the wall thickness, the first inequality right side is the horizontal/vertical bias (-1..1). I didn't know desmos could do half of that stuff, I think I just leveled up. Thanks for sharing XD
Great entertainment! All of yours videos! :-) One question perhaps someone could help me with: I want to store a randomly generated maze in a sort of data structure and use it for a game which will be played over websockets.. How to build a maze (or let build) i kinda figured out by myself after i ve seen a video from the "coding train" years ago. But i never managed to save the maze. :( Any ideas?
Deep Dreamer it would appear you might be including the header file more than once. Check your project structure to see if this is the case. For example are you using precompiled headers?
Now the man makes an algorithm to solve your maze in under 1 minute. The everlasting competition of coders.
If you are in a hurry and like to clone code, you can use almost *the same algorithm* as this generator, and *replace the random direction part with exploration test.*
But you'd better use *_double-ends-A_** algorithm instead.
Feel free to prove me wrong, or to call me to work together on *amazing* 2D, 3D, nD maze generators and solvers.
I found a new use for this algorithm! It's really good at generating oceans/continents. Visited cells are water cells, unvisited are land cells. If the algorithm stops after visiting about 60% of the cells you can get smaller and larger islands, continents, even some rivers! Really cool stuff 👍
just discovered your channel today... Don't normally write in comments sections... but.. really enjoying your videos. please continue the good work.
Hey thanks Mark. Comments like that make it worthwhile.
You cannot tell me this isn't the same guy talking to himself
About two years later, I discovered it today. Same impression, love it.
Very true. This is, for example, the first time I saw a comment of yours.
@@Noone-rc9wf I can tell you it isn't the same guy... My coding sucks ass.... if I make a asterisk bounce round the screen I start dancing around the room....
I'm just a nice person giving someone positive feedback...
This video is a mazing.
haha such dad humor :P
This video is indeed a maze thing.
You little...
☹️
Listen here you little sh..
As always, i cant believe this video has "only" 300 views. Keep up the awesome work!
Cheers Konstrukt! I'm not very good at promoting the channel. Sure I'd love more views, but I'm not monetising so there's little incentive for UA-cam to promote the channel either. As long as people engage with the content - I'm happy! No "Hey Guys! What is up?" dodgy thumbnail click-bait rubbish from me..
Thanks Riptide! :")
Too few people like programming and understanding old algorithms. Actually, many programmers like "not to re-invent the wheel". sad...
2,810 views... this is a good "code along" video.
Great videos indeed. wish yt suggested the channel sooner
I absolutely love your coding style! So clean and understandable, without unnecessary complications.
I'll try to learn from you, thank you for all your content!
This is the greatest UA-cam channel that I have had the pleasure to stumble upon.
I found this channel while I was looking for how a game coder works - not a video with visual impressive graphical presentation, but the "ugly" unspectacular hard part of coding thousends of lines and how it is possible to keep an overview. Then stuck to your channel because the quality of your videos especially the content (programs and explanations) is excellent and I learned much here (for example the use of the modulo operator and many other "tricks") I like how you concentrate on what matters - the ideas and algorithms and how smart you code. Today I finished my own (primitive) maze program with the 15 unicode chars 0x2554, 0x2557 and so on, without using one of your game engines but with parts of your code and ideas. It creates the maze in one tick so it is not as good for visualisation as yours but it shows me that I really understood your code. To repeat all calculations in every single frame (OnUserUpdate function) is very time consuming and only possible in that ultrafast C/C++ language (or maybe assembler if one is capable of coding in this). Greetings from Germany and I wish you many good ideas for more programs to show.
A couple of years ago, this video of yours inspired me to writing my first Python/Tkinter application: my idea of coding something useful for practice and keeping my grandchildren quietly entertained.
Little did I know that after all this time, a discussion in redditt's r/learnpython thread led me to tell the world about it. The response was amazing, and I have felt compelled to use Github for the first time to make available my first clumsy effort.
The code starts with a couple of sentences where I told this story and show my indebtedness to your original presentation; coupled with a proviso that you are not responsible for the 'quality' of the coding. Thank you so much.
Hey that's great Vasco, well done!
"Two minutes to create a maze that would take one minutes to solve" ? That's a line from Inception !
Yes.
using the stack to pop back the path, whilst keeping tracking of total visited cells is a very nice elegant algorithm. thanks for this! 🙏🏻
Yeah it is. Breadth First Searches like this are a staple computer algorithm that have been around since the dawn of programming. By eliminating the need to recurse, it also removes all the problems associated with recursion too.
this was our final project for "introduction to computer science 2" in college; we used both a dfs/stack and bfs/queue (and we had to make the stack and queue). we also had to find the shortest path from the entrance to the exit. ours used ncurses in a gnu/linux terminal! if you have been programming for a couple months, i'd strongly recommend trying that out, it taught me a ton about a programming.
Never ceases to impress me how you can take a advanced concept and break it down to very simple terminology. In just the first five minutes you've broken the method by which the algorithm operates down enough for me to understand how to implement it programmaticly.
One of my more favorite videos I have seen. Subscribed a while ago, just a really enjoyable view, everyone of these !
Hey thanks Shane!
I dont believe you did that in two minutes.
The algorithm runs in two minutes and creates the maze for you.
Of course he did, then he slow down to explain it to us mortals
Salu omnidentidade The only thing limiting him is the speed of light lol.
Damm why this channel has so little subs and views. Good work man!
Hey thanks Emajl, glad you find some of it interesting! You've stumbled across our secret society. Welcome to the club!
I once made a 4D maze. At every location of the maze, you could go up, down, left, right, backward, or forward, but you could also warp to an alternate maze and continue from there. Very easy to design with this algorithm, but very confusing to solve, especially since the display was only 2D.
Errrrr. Yeah now my brain hurts. Thanks! XD
Hahaha, you strike me as an evil genius. You're operating on a higher plane #GodLike
But can you create your own kernel from scratch?
The way you‘re using bitwise operations has somewhat opened my eyes. I knew about bitwise operations and I also knew about using sums of powers of 2 to store information (e.g. in chmod commands), but I never thought about using it to essentially store several booleans in a single value. Thank you for this video!
Yep, bit flags are very useful, especially for passing a single argument to a function that toggles several different modes of operation. Modern C++ also has bit fields:
struct something { int a:1; int b:2; int c:3;} etc. a is basically a boolean, but c:3 could have a value from 0-7. If you need very small integer values you can pack them into a single byte or the smallest integer type that will fit them all. You can't pass pointers or references to them though, only by value.
@@DFPercush bit fields aren't modern C++, bit fields existed in C since it was created in the 70's
Thanks. Really good information. I don't understand some of the newer C++ syntax, but that's ok. I understand the algorithm, thanks to your video. I decided to make this algorithm work on the old color computer from Radio Shack in basic with 64k. But only 32k is available. I wanted to make a maze of grid size 127x95 in a resolution of 256x192. I needed a array of 12065 bytes to hold the grid. Then another 24k for the stack. That is roughly 36K. Way over the amount I have to work with. I came up with a different way to save space .So instead of using a stack to hold x and y locations of cell, I decided to use 2 bits in the cell array data to hold a number between 0-3. Those numbers would represent the direction that the cell came from. Now, each byte in cell array has 4 bits for the walls, 1 bit for visited or not.1 bit for backtrack or not and 2 bits for direction cell came from. Some crazy reason, it worked. :) Anyway, I thought I would share my algorithm modification info in case anyone else ran into memory constraints on old retro computers. I was able to cut memory usage from 36K to 12K.
Personally I also did this but instead of keeping which direction each cell came from I actually while generating the maze have all walls built, meaning it's just a grid of squares and each time I move to a cell I break the wall in the direction I went, that way I do not need to store any direction but instead just perform it instantly.
Just something small I noticed. You don't need to keep a count of the number of cells visited. If you reach the bottom of the stack and there are no neighbors, then you know the maze is done.
Upon further reflection, I think reaching the bottom of the stack will always leave you with no neighbors. Say everywhere in the maze is filled in, except one cell directly neighboring the start cell. As the stack pops, it will encounter a different neighbor of that cell before returning to the start cell, and this different neighbor will generate the path instead. Similarly for any larger empty region, we must fill it in before we can pop the stack to the bottom.
If you got a stack of 2000 cells, you repeat the same code till your stack is empty, using a count variable would automatically stop the algorithm when it's done
1:57 into this video and im already convinced that this is awesome.
*Stacks of tiles are fun* because they make generating mazes look like solving mazes, but otherwise I don't see the point of *wasting computation time and energy* using them for maze generation.
1. You could link new tiles to the existing graph in *any fucking (or even non-fucking) arbitrary order,* including random and discontinuous, as long as you *mark each tile's branch* well, which can be done in a single step each time a tile is added.
2. Even if you want to go through the graph in a particular order for whatever reason of controlling the maze's properties (e.g. limiting the length of straight corridors, or the number of consecutive turns on the same side, or the distance between two branches, etc.), backtracking is *extremely quicker from one **_branching_** node to the next, than from any one tile to the next.*
Feel free to prove me wrong, or to call me to work together on *amazing* 2D, 3D, nD maze generators and solvers.
"rarely the programs did actually work" - can confirm this. Good times!
ah, such fun! I coded something very similar when I was a little kid, and I still like to watch you make algorithms like this. more, we want more! ;-) subscribed.
Glad you enjoyed it, thanks!
thanks to this video I learned bitwise operations and better understood hex numbers, thank you!)
First two days I only understood the general operation of the code while struggling to figure out what |= and & means in the particular case but on the third day I finally figured out everything
Had to spend some time with pen and notebook studying code symbol by symbol.
I am very grateful for your videos and the fealing of satisfaction after understanding everything!
that algorithm is pretty ingenious
Really enjoying these videos. Time to dust of my programming head and have a play.
Hi Bob. Thanks for the great response. Comments like that make it all worth while!
This is a amazing video, it has been a while since I was looking for. Thank you for your great work.
Saw 8bits of C++ first, ehh, then this one, subbed... might be a good idea to close any unused toolbox and explorer windows, to get more code on screen, as well as roll back the zoom a bit, and hide the main menu... great video, thanks!
Cheers, yeah, I was still finding my feet with the whole making videos back then (still am to be fair!) Thanks!
I take that back, 8 bits was second - I watched "What is Assembly Language?" first. Inspired me to start using OneNote again... now that I have a Surface. I gave up on C++ years ago, in favor of VBA, Ruby, and other "scripting" type languages, that satisfied my impatient nature to, "do stuff now", vs getting lost in what seemed to be an endless pit of dependencies, includes, and compiler settings... it was like learning how to build the the tools and the toolbox they go in, when I just wanted to tighten a bolt, but I had to make the bolt too.
16:19 when loops look like that (with math indexed arrays) is usually when I get lost xD
20:10 that's a new one (to me, a lot has happen apparently since I programmed), a function inside a function... Funception!
This guy is the greates teacher I have ever met.
I really like the way you explain things. Always clean and simple (from a programmer perspective, should I say). Have you ever consider teaching ? Good work, by the way.
Thanks Alexandre! I have taught in the past, but decided to leave academia.
This is the absolute best channel on the internet
I realized the maze is the same every time. is there any way to fix this?
Yes Scott, you can seed the random number generator, add something along the lines of srand(time()) to OnUserCreate.
I'm really enjoying following along with your projects, which helps to refresh C++.
Quick question about your naming convention: why do you put "m_" in front of your variables? What does it stand for?
Thanks! I use an old school technique called hungarian notation, where i include type information in the variable name. In this case "m_" means class member variable. I dont always do this, it depends on the size of the project.
I just built this in processing and my desktop background is now a maze :D
Hi thats cool Nicolai, do you get new mazes each time you start up?
No, but that would be awesome!! I don't know how to do that tho... I just saved a maze as static image and set it as my desktop background... Is there a way to do that automatically?
# include
SystemParametersInfo(SPI_SETDESKWALLPAPER, 0, "maze.bmp", 0);
Bitmaps are super easy to work with, you can just dump a raw array into a file basically. BITMAPFILEHEADER and BITMAPINFOHEADER are the windows structs for bitmap files, just populate them and dump the memory out to a file, then the pixels, and you're all set. docs.microsoft.com/en-us/windows/win32/gdi/bitmaps
@@DFPercush Thanks, I might try that!
I can't tell if you're faking going outside or being a programmer... Whichever it is, you are a good, my friend.
This channel deserves more subscribers
Giant Panda Thanks!
While I agree that this channel should have more than 10 million subscribers, I realize that maybe there are simply not that many smart people in the whole world. It would require something like more than 10 mega smart people.
If anyone runs into an issue with the Windows SDK headers and "byte ambiguity" while attempting to compile this code, or other code that calls on the Windows headers, the issue is that you are using C++17 and the 'std' namespace now defines 'byte', while the Windows headers helpfully also define a symbol called 'byte'.
A simple fix that should work for anyone just following along with Javid is to move the 'using namespace std;' statement to be after any '#include' statement that brings in a header that relies on the Windows SDk headers.
A more ambitious solution, but potentially problematic, is to "fix" the Windows headers (rename the 'byte' declaration to avoid ambiguity, e.g. BYTE or win_byte, etc). Problematic because they're not your headers, and you're basically creating a non-standard fork of them.
And a sidestep to the issue is to make sure you use C++14, instead. This pre-dates the introduction of 'byte' to the 'std' namespace (and is why this issue did not surface earlier). In VS you do this by setting the project properties to the appropriate language variant (and globally defaulting to it, if you like).
My first maze was done on a RadioShack model 1. I used a string variable as the stack. Back in 1980
I have implemented this algorithm in x86 assembly in tasm and it works wonderfuly! One problem I was having is that if the tracker runs into a backend and as soon as it is out of it it runs into a new dead end immediatly it will back track to the end of the dead end before it. Now it happens of course because it is the last cell being "discovered" as the last ones were just tracking back. while it does not interrupt the algorithm to make a wonderful maze. It does indeed interrupt other algorithms I would like to use with them. I would be happy for your advice or if I have done something wrong. Thank you!
2 mins to create a maze that would take him longer than 1 minute to solve. I see your a Christopher Nolan fan. :) Great video and content. I love how you explain these algorithms. I hope you plan on doing more algorithms.
Your videos are so clean and calm. Regarding this video I have one question, it is supposed to generate a random maze, because no matter how much I run it, it will print the same maze everytime.
Thanks Pengu, you will need to seed your random function. Random is never random on a computer, so you would normally seed the random number generator with a variable that changes such as "time()" to give true pseudo randomness
Thanks for the answer, I've played around with the code and this is what I realised: in your github code you indeed "randomised" the starting spot but it still run the same version everytime. It started to be "random" after I moved the srand(clock()); from the main function to the onUserCreate;
Now, I have 2 more questions:
- what is the difference between srand(clock()); and srand((unsigned)time(NULL));?
- will it make any difference if I reset the seed before choosing a random neighbour?
Thanks again for your time and for your work :)
1) nothing really, srand just needs a "random" set of bits to get started. Any function which can provide something you cant easily predict will do.
2) If you reset srand to the same value each time, it will always choose the same number next time you call rand(). resetting srand with a time based function, may have a negligible increase on the quality of the random number, but probably not worth bothering with.
I learned about random number generators from a maze generating game on a DOS computer when I was 5
wow, this video helped me out so much, thank you!
"The old pen and paper"... Like many others before you, your work will only be really appreciated when you stop. Until then. Thanks...
How about a 3D version of one of those table top mazes that you have a ball bearing that you need to move through and not allowed to drop in a hole?
Very cool :-) If I remember correctly I think that you can actually use a queue instead of a stack. Using a queue generates a maze using breath-first traversal, whereas the stack uses depth-first traversal.
I would you have liked to see how different the maze looks with a queue instead of a stack :-)
std::list can push and pull from front or back, so you can use it as either a LIFO or a FIFO. Fork the repo and try it out. ;)
Although, you might need additional state for each direction on each cell, because the history will be consumed after you take the first branch. I'm sure there are plenty of articles about doing something like that.
Very useful video implementing this into my game
Thank you for this wonderful video.
Hey Thanks First Mill, my pleasure!
Interesting adaptation of depth first search, would think to use it here.
This is the DFS algorithm :)
Depth first search for those not binging maze videos rn
Good explained!
Your videos are very well made. Keep it up! :-)
Thanks Daniel!
Hi. I find your channel very useful to start learning the C++ language. I am having problems with the console windows generation, I am using the olcConsoleGameEngine.h file, but when I create the console with the line "game.ConstructConsole(160, 80, 8, 8);", it shows a window console stretched on the height. And second, I am noticing that the framerate FPS goes very slow on my computer, like 6.00 FPS, when I see that on your computer you have more than 1000 FPS, and I have a good computer. What could be the problem?
Hi Oscar, there could be many things different here, I would suggest using the olcPixelGameEngine instead, its cross platform, and has consistency across compilers
you are the best!!! Thank you for realeasing such great content
this solution has a many long street without '+' type (cross) branching... I suppose that after 10-12 step randomly open new paralel counting thread :) And randomly open just reached dead end connecting with a neighbour cell... (so make a circuit path). :)
Is there a way to divide larger mazes so that the stack works on chunks of the maze, rather than having a stack equal to the entire maze?
As an example, let's say I'm generating an absurdly large 10,000x10,000 cell maze. The cell data array must persist in memory (or be paged from disk as needed), but the stack is temporary. How could I rewrite the algorithm to generate a *perfect maze*
loving these videos
Thanks Revi09!
Great maze! Could you explain ORing the lambda? That. Was. Awesome.
Thanks Sky, I looked through the code and could not find a case where I am ORing the lambda function, could you clarify what you mean?
Maybe 4 ghosts from the other side and you control a yellow character with a mouth.
In 11:14, could malloc or calloc be used instaed of new kwyword? Would't them initalise everything to 0?
Hi JW, according to spec, malloc does not initialise memory www.cplusplus.com/reference/cstdlib/malloc/ calloc however does
Thanks, I didn't know that about malloc
Thank you for your fascinating video, it inspired me. 👍😃
The last maze runner
Hi javidx9, great video with great topics but what I don't understand, is where can I find the starting point and the exit of the maze?
Thanks Andrei, the algorithm is completely unconstrained so you cant specify an end point. However you can specify a start, in my case its top left i think, and because it guaranteed all cells are reachable from all other cells, you can simply nominate a cell as your exit after the maze is generated.
basically stack is the way that magic effects resolve in magic the gathering
please can someone explain how the enumerate function works applied to this?
Hey there! Enjoying your vids! I'm having trouble with deriving classes from your code. I downloaded the olcPixelGameEngine, but it looks like that isn't what you're using here. I am guessing you probably get this question a lot, so if you could point me in the right direction I would really appreciate it. Thanks!
nvm I figured it out. Looks like you just changed some names. ctrl-f for the win. Funny how I always seem to find a solution after I've asked for help
Hey, at least you got there! 🙂
Okay I am lost again. What do I do with Fill()? FillRect() has completely different params...
Fillrect takes top left position on screen, and width and height, along with a colour
@@javidx9 If I remember correctly, I was having trouble with the data types. They are different in this vid than the parameters called for in your function.
Your brain is substantially better than mine.
all your stuff is very good and enjoyable to follow ^^.
it would be very helpful for this vid if when you use your console drawing lib that you put a link-mark to a short vid of how to structure this draw from std::cout ^^
for those who are just trying to get the alg in ^^
(took me longer than i want to admit to restructure for cout output approach, but didn't want to do draws etc. and wanted it to be something where i could just create a 1d-array for usage and send to another module which then figures out what graphic is needed where etc ^^)
I don't see where the need for the "visited" tick list comes from. Couldn't you simply implement the algorithm such that it will iterate until the stack is empty? That would imply that the maze can't be expanded anymore and that all squares have been visited.
isn't it used to render the maze? (12:20).
@@rastaarmando7058 That makes sense, thank you.
Excellent video, loved it!
W guy, W video. LETS GOOOOOOOOOO
Can you please make a video using recursive division and also with this same algorithm DFS but biasing it so that you can, for example, get longer pathways both horizontal and vertical?? Thanks.
Lol Carlos, thats a veeeeeery specific video. You can of course bias the direction by biasing the random number generator. If you want East & West for example, attribute a higher probability to those when choosing
My first thought would have been to store visited/not-visited as a vector and use the indices of the bools as (row, column) to refer to position. Is your convention the more customary one? I want to use an approach that conforms to whatever informal "standards" are commonly used.
How are there no inception comments close to the top?
you are fantastic!
Beautiful
Thank you for your video! But still I've got a problem related to pdb files which are impossible to find, that's why program doesn't work properly :(
Thanks, missing pdb files are an entirely normal output for visual studio projects. They are not errors. It is likely something else that means it doesn't run. It could be your console is too big for your display. Try halving the fontw and fonth values in construct console function.
@@javidx9,that's it! thank You! When I was exploring your game engine it came up that proper program flow depended on height of the console!
I know this is an old video, so I'm not sure if I can expect a response or not, but here goes anyways! I've been playing around with the srand() at the end, and no matter what I do it generates the exact same maze and has the exact same starting cell every time. Any advice? Thank you!
Sure, it's important to call srand just once, and confusingly srand is thread local. So setting srand needs to be done once in OnUserCreate.
That console window reminds me of the old maze game xd
can you tell me what is implimantation of creating maze or how did you do it on consol
okay, sorry I got it... I did not see the Github first, great work man, thanks
Great video
When you are checking EAST or WEST, how are you handling 'wrap-around' to the next/previous row when on an "edge" (far right or far left of the row)?
your videos are great. Sometimes I spend some time coding along with your videos and concepts just click. But truthfully, i'm currently confused about the third nested for loop in the onuserupdate() function dealing with the walls for the maze.
You mean the drawing code at 15:34? That's looping all the console characters in a single cell, so it fills in the whole cell instead of just one "pixel" of it.
Very nice!
excellent video!
Thanks OxygenMagnet!
Ik push(), pop(), but what is EOP?!
How come you're using bits, and bit operations?
I can do some things very quickly with bits, such as set or unset multiple bits at once, I can check if all the bits are set or none of the bits are set quickly too. I can also exploit mathematical tricks using the binary representation of numbers to speed up decisions and implement complex decision trees. Lots of reasons!
@@javidx9 So the performance gains are significant enough to make up for the loss in readability?
By some margin yes. Also, if you ever encounter any serious embedded programming or assembly language, bitwise operations are pretty much all you get!
Amazing channel!
Yes it is Kalleskit, Thanks! ;)
Do you think you will ever create tutorials for creating games with more advanced graphics? Such as SDL, OpenGL or DirectX? :) Let's say you want to create a nice-looking 3D RPG.
Also, a tutorial for a simple strategy game might be fun!
Yes probably, but I would not focus on "how to do a directx game" for example. The console is nice because I dont have to explain about how to set anything up, using advanced libraries starts making the video about the advanced library, and not the techniques used in the algorithms and games. I can say there is a strategy game in the works! and a 2D RPG game, and some console based 3D graphics too! A lot of projects fail because there is initial excitement about making it look pretty and doing fun things like sprites and models, but then the dev has no idea what to do with the pretty things - I'm just as guilty of this than anyone else! :D
I understand!
Where should I go if I want to learn how to make a game engine? :)
can you explain to me the part where you add walls to yours program ? please.
If you were to draw a full grid, you can produce the maze by deleting walls wherever there is a link from one cell to another. What I like to do is create a binary array containing the what it would look like if there was just a left wall (3 way intersection). Rotate that array 3 times to produce the other walls (multiply by a rotation matrix). Then using binary AND operations, you can produce combinations of the 4 walls to make every possible cell that can occur in the maze. If you represent each one with 4 bits, the bits can tell you which walls to draw where. For example, 1111 would mean draw the Up, Down, Left, and Right walls. 0101 could mean draw the Down and Right walls, but not the Up or Left walls. If you store all of the possible 2d binary arrays to define the walls in numerical order with this binary encoding, you can define how to draw the walls easily. Create a 2d array to store the binary drawing array for every cell in your maze. Start off with 0 (no walls drawn anywhere). For each node in the maze making algorithm, AND together the walls that shouldn't be there. So if there's a connection to the node above and below, but not left or right, you AND together 1000 and 0100 to get 1100. Now the final step is to apply the NOT operation to every cell in your array (the easiest way is to do 15 - val for each cell, though this isn't the most efficient way). The final result is a map telling you which set of walls to draw in every cell. Now just refer to your binary arrays for the wall configurations and actually draw the walls.
Hopefully this helps.
Why aren't you visualizing backtracking? At least color the cell back to blue when popping the stack.
This was entertaining
(m_maze[offset(0, -1)] & CELL_VISITED) == 0
can anyone explain the meaning of "&" in this code? Thanks
It's a bitwise logic AND. See my NES emulator part 1 for an introduction to bitwise operations.
@@javidx9 precious ,sir
Wow! That’s cool you are very good at making mazes I will try it right Now! Thank you For the video! Like this comment if You guys want to see me make a soccer game on scratch or anything you want Ok guys!!!!!!
Or, you could just use the "maze equation": www.desmos.com/calculator/pth16uwlqp
(not sure if the link shows though). Anyway, just kidding. These are excellent videos! I've been on and off C++ for... let's say some time :) But I never really advanced from cout lol. And here you are making interesting stuff with basically just that! This makes me want to re- (re- re- re-) visit C++ (well I do use it for Arduino's sometimes, so there's that even if I'm not that advanced with C++. Yet).
Whaaaaaaaat? That function is crazy! Now I'm playing with it to see what changes. Looks like the exponent of 10 is like the seed (307 is where floating point precision breaks down), the last number is the wall thickness, the first inequality right side is the horizontal/vertical bias (-1..1). I didn't know desmos could do half of that stuff, I think I just leveled up. Thanks for sharing XD
Great entertainment! All of yours videos! :-)
One question perhaps someone could help me with: I want to store a randomly generated maze in a sort of data structure and use it for a game which will be played over websockets..
How to build a maze (or let build) i kinda figured out by myself after i ve seen a video from the "coding train" years ago. But i never managed to save the maze. :(
Any ideas?
There are some LNK 2005 errors with the olcConsoleGameEngine that i don't know how to fix, can you help me out ?
Which compiler are you using? What's thw nature of the errors?
VS compiler and here are the errors: prnt.sc/jep5hp
Deep Dreamer it would appear you might be including the header file more than once. Check your project structure to see if this is the case. For example are you using precompiled headers?
Can it play Wolfenstein? (Sorry, I can't come up with a better comment) :D
Brek Martin hey it's good enough. I did originally think of tacking on my first person shooter code. congrats on busting 700 btw.
I LOVE U