To test djikstra on the large maze, use uniform cost search. Same algorithm, same results, but it doesn't load the entirety of the maze in memory at the start which is why your implementation wouldn't work for the large maze. Similar concept to how A* has a limited search frontier (the set possible choices for the algorithm to explore next)
When you showed that your maze file was >1GB I was so enraged that I decided to reimplement the maze generator and rewrite the part that exports to a file so that it would be smaller and I managed to get it down to about 5.29MB
2 bits per cell, right? Checks out. Hell, the file could be as small as just a seed + the maze generator itself if it wasn't too slow. You got a Git repository somewhere?
I think if you want your video to have high quality available right when it comes out, you can just upload it, but schedule it to release sometime in the future. That way youtube will have time to process higher quality.
Yeah I should have done that. The problem was I wanted to get the video out as soon as possible (but didn't realized that the HD quality hadn't finished processing) :)
I believe legt and right wall followers can be changed to give you the most optimal path, if the cells (when the algorithm backtracks) are removed from the path
Imagine a maze like this where it goes from ! to # (Don't mind the small gaps) ________________ ! | | | | | | | | | | | | | ____+______#_____ The optimised right wall follower you said would go down, up, down and to the hashtag while A* would got right then down to the hashtag which is shorter.
The dead-end filling algorithm is fun because it can be set up as a cellular automata. Make the walls thicker so they're the same size as the passages, then define the the maze so that passages are "living" cells and walls are "dead" cells. The automata only really needs one rule - if a living cell has fewer than 2 living neighbors, it dies. If you set it up with a loop of living cells around the outside of the maze (to keep the entrance and exit always alive), eventually all of cells that make up the dead ends will "die," leaving you with just the solution alive.
Your video is well produced, but 4600x4600 worth of cells can fit into about 5.4MB of memory if you only use 1 bit of information to store if a wall exists or not.
"even thought a* completed 2nd rank and not aat all faster than RH WF, i declare that A* wins the race because it is one of my favourites" worst scam of all time
No, any maze can be completed by following the wall since the point of a maze is to enter and exit from 2 different points. Its not like your gonna be leaving from the middle.
@@eugenekrabs141 imagine.. - someone drop you somewhere in underground maze and you need to find the ladder in the middle. - start at random, end at border: someone drug you and you loop around middle square wall - start at border, end at random: you entrance the maze building and find the stairs to next floor - scifi portal or fantasy Harry Potter like except they call it something else instead of maze, I'm not sure.
why don't use just run... bfs... it will always find the best solution... and dijkstra is useless because its only useful when edges have weihgts. if the weights are all 1, bfs gets the job done
BFS of course will find the (only) solution, but it visits more nodes than A*. Dijkstra/Uniform cost search is also relatively useless in such an unweighted graph. Greedy best-first search is better.
Had a good time watching. But, a glaring issue with your methodology (and claim to hardest maze ever): There were no looping paths, which have a very, very good chance of rendering Wall-follower methods completely useless.
The underlying graph of such a maze is just an unweighted (spanning) tree. A* is better than Dijkstra because it expands fewer nodes, but "greedy best-first search" is even better.
@@Someoneyes-y7l For "perfect mazes", which are just trees, it of course finds the "shortest" path because there exists a unique path between any pair of nodes.
Djikstra’s alg is better when you have weighted edges iirc, whereas here you’re just looking at the same distance between each tile, so it’s basically just BFS.
Nah I wasn't printing every step, just sometimes. For the Final Race, I didn't printing anything as it would take way too much time. I just did it for debugging purposes. Hope that answers your question :)
sad you didn't implement the human algorithm: - just try to follow the direction toward the exit, - if it doesn't work out, just backtrack until you have another way that seems to lead towards that direction. - Repeat until you get to the exit.
"How to solve the worlds most dificult maze?" One words: Water. I can think of 3 methods. Method 1: Water presure Assuming the world of the maze only has two dimensions and no gravity (or gravity but into the thrid dimensions direction means it wouldn't really matter here), just connect a water pipe to one end and pump water through it. The only path it can take is the path (or paths) to the other end, since all other routs are dead ends and due to water presure it can't go in there. Method 2: flowing water Just connect a (large enough, or invinite for a simulation) water source to one end and let it fill the maze. The water will flow into all paths but stop at ends. So it if water comes out the other end, you can follow the path like its a river. Method 3: Water and gravity Just hang the maze on the wall, connect a (again, large enought) water source to the top and let it run through the maze. Since the only way to diplace the air in the maze is by pusing it hrough the other end it can only fully take the routes towards the other end since all other paths will get clogged by the water. I don't know how good fluid physics engines are though. Maybe all methods might work in simulations, maybe just one, maybe non at all.
How do you do such animated videos? I really want to know how to build things like your character, the maze generation, and pretty much everything. I love them so much!
A good way to measure efficiency in maze solvers is by the number of steps they took to find a solution. Wall followers are quick to process, but they take way more steps to find a path than A*. The dead end filling algorithm is neat, but it needs to explore so much of the map. I'm disappointed you didn't give the random mouse a chance. You should always give random algorithms a chance just in case it solves it first try; you want that shit to be on camera.
I‘m writing a paper on this topic (I coded the mazes in Ruby) and I‘d like to give a shoutout to my boy the Aldous-Broder Algorithm for giving me an absolute headache with how long it takes to generate
it would cool to calculate how much time a human would take to finish this maze, considering that they would always go for the right and need to stop to eat and sleep
Google doesnt use that algorithm, its not computable on a global scale road network, google uses a variation of the heat method, and yes the heat method can solve this problem a lot faster
I wonder if the maze creation algorithm has some kind of creation bias that allows the wall follower algorithm to perform more efficiently than the other algorithms
3:00 There is NO WAY that is a separate OBJECT PER CELL of the maze- Python takes 24 bytes per integer (not even objects, just integers) so 192 bits, possibly even more than that (I've heard of 200+ bits), when you only need 2 bits per maze cell under optimal circumstances. You have 2 bits of useful memory for every 192 bits that you spend. No wonder you ran out of memory XD A decent way to compress this is to use Python's bytearray() so you can create and manipulate individual bytes. Then, using bitwise operations, you can store 4 cells per byte, maximizing your memory.
or, you could use that python has no problem with really large ints, and let you use bitwise operations on it, and use an int to store everything. if you want to prunt it, i recommend hexadecimal
i used large integers on an space limited microcontroller, for printing letters (2 bytes per letter, to know which loght to activate * 40 characters or so) (the lib only supported fixed length characters, but needed that few pixel (display is 4(width)*5 (hight) pixel (max size for a symbol is 3*5 pixel)
so at 0:55 you explain the Iterative implementation (with stack). and then a few seconds later, you implement a recursive implementation of the maze gen?? mistake?
I hadn't come across anyone creating content like yours before, so I started following you a year ago, and I absolutely love your entertaining content. However, if you stop posting videos for a long time (again), I'll be come to your house and kick your ass. 😅
just by peeking at your code at 9:23, i can see that your implementation works in O(n^2 logn), you are sorting the list of unvisited vertices every iteration of the algorithm, so you are doing an O(n logn) each time you run the algorithm, when you could run dijkstra in O(n log n) lol. that's why it's usually implemented with a priority queue im using n loosely as the number of cells and edges, both of which are O(w*h) in any case, you are better off doing a simple bfs because the weight of each edge is 1, so ignore my previous comment
Right hand and Left hand is my favorite because it looks like a country border, and i like maps oh yea and also that's (i think one of but i forgot) the first tips i got to solve a maze (i didnt use it tho)
What if Because the wall followers were pretty quick, but non optimized. What if you ran a code that only looked at where both wall followers went on the same path, which only should be the optimized path unless there are multiple ways to the end...
im currently studying maze generation, and im seeking for algorithms that are really flexible and that can be added troug a lot of different render variations, shapes, or wall width and height, and i wonder what is the best architecture, i thought about doing it with one class that represent the cell, and one that represent the wall, each cells are in an array and reference their walls, the walls would just serve as "link" between two cells and say if they are pathable or not, is this the structure you made ? or did i miss something here ?
You definitely did something wrong if A* is not the fastest. Maybe wrong heuristic or you used a list instead of a heap. Btw. For optimal performance on really big mazes we normally use a Fibonacci heap but these are petty complicated to code
A noob question but what framwork do you use to visualize these mazes and solving of them...... like for example in cpp we can use SFML for that purpose....??
jsut wanted to know, do you make a lot of money, im asking bcasue you seem to know a lot about coding, so im interested to know how much money someone of your coding experience can make ?
![[#2024MAMA] G-DRAGON - 무제(Untitled, 2014)+POWER+HOME SWEET HOME+뱅뱅뱅+FANTASTIC BABY | Mnet 241123 방송](http://i.ytimg.com/vi/Ox29z5Nf1Uk/mqdefault.jpg)
i love how the wall followers just made maps of europe, i can just imagine using the path as land and non paths as water for a fantasy setting
i thought of that too
unironically would make alt maps on it
A i was just about to comment this
XD
Literally exactly my thoughts
To test djikstra on the large maze, use uniform cost search. Same algorithm, same results, but it doesn't load the entirety of the maze in memory at the start which is why your implementation wouldn't work for the large maze. Similar concept to how A* has a limited search frontier (the set possible choices for the algorithm to explore next)
A* is literally modified dijkstra so it 's weird that he could implement A* and not dijkstra
did bro call gigabyte jigabyte
You expect me to NOT pronounce it jigabyte?
yeah, and jif clearly
True
@@trollsansofficialYES I EXPECT YOU TO NOT PRONOUNCE IT THAT WAY
@@trollsansofficial jijabyte
When you showed that your maze file was >1GB I was so enraged that I decided to reimplement the maze generator and rewrite the part that exports to a file so that it would be smaller and I managed to get it down to about 5.29MB
2 bits per cell, right? Checks out.
Hell, the file could be as small as just a seed + the maze generator itself if it wasn't too slow. You got a Git repository somewhere?
That's pretty sick. Yeah I used to pickle to store the object, and got a really large file. Couldn't be asked to figure out why
how the hell do you make it so small
@@Green-Code LMAO ur comment is new
@@muslimgamerrr9479 2 bits per cell storing the right and bottom wall. Cells one the bottom and right edge only store a single bit.
I think if you want your video to have high quality available right when it comes out, you can just upload it, but schedule it to release sometime in the future. That way youtube will have time to process higher quality.
Yeah I should have done that. The problem was I wanted to get the video out as soon as possible (but didn't realized that the HD quality hadn't finished processing) :)
Wait a second this isn’t code bullet
I was looking for this comment
@@nygeli13168mee too
yeah i agree....who is this green person?
A neat thing i noticed is that the wallfollower algorithms create whats essentially a negative of each others routes. This is pretty neat!
I believe legt and right wall followers can be changed to give you the most optimal path, if the cells (when the algorithm backtracks) are removed from the path
Imagine a maze like this where it goes from ! to # (Don't mind the small gaps)
________________
! |
| | | |
| | | |
| | |
| ____+______#_____
The optimised right wall follower you said would go down, up, down and to the hashtag while A* would got right then down to the hashtag which is shorter.
@@mean4276i believe algorithm used in the video doesnt produce loops like that
I just start from the end
The dead-end filling algorithm is fun because it can be set up as a cellular automata. Make the walls thicker so they're the same size as the passages, then define the the maze so that passages are "living" cells and walls are "dead" cells. The automata only really needs one rule - if a living cell has fewer than 2 living neighbors, it dies. If you set it up with a loop of living cells around the outside of the maze (to keep the entrance and exit always alive), eventually all of cells that make up the dead ends will "die," leaving you with just the solution alive.
Me: I want Code Bullet!
Mom: We have Code Bullet at home.
Code Bullet at home:
Your video is well produced, but 4600x4600 worth of cells can fit into about 5.4MB of memory if you only use 1 bit of information to store if a wall exists or not.
someone in the comments got it to 5.29 megabytes
@@Austin_Playz27 It depends whether there is 1024 or 1000 bytes in a kilobyte
ohhhh that makes sense
@@scratchthecatqwerty9420 1000 bytes in a kilobyte, 1024 bits in a kilobit
@@SpaceVisYT 1000 bytes in a kilobyte, 1024 bytes in a kibibyte
"even thought a* completed 2nd rank and not aat all faster than RH WF, i declare that A* wins the race because it is one of my favourites"
worst scam of all time
This channel needs at least 1 million subs. Great content!
2:34 As soon as he said ''What's happening'', 0.001 seconds later, I got an ad
Same . They're scheduled
5:19 this only works with these specifc types of mazes whete all of the walls are connected to the edges of the board
true
No, it also works with all mazes where the entrance and exit are on the outer wall
No, any maze can be completed by following the wall since the point of a maze is to enter and exit from 2 different points. Its not like your gonna be leaving from the middle.
@@eugenekrabs141 imagine..
- someone drop you somewhere in underground maze and you need to find the ladder in the middle.
- start at random, end at border: someone drug you and you loop around middle square wall
- start at border, end at random: you entrance the maze building and find the stairs to next floor
- scifi portal or fantasy Harry Potter like
except they call it something else instead of maze, I'm not sure.
@@AstralrAstralr-mj1tr Ok but 99% of mazes are start at border end at different border.
underrated channel
Yeah i just subbed
Ya
why don't use just run... bfs... it will always find the best solution... and dijkstra is useless because its only useful when edges have weihgts. if the weights are all 1, bfs gets the job done
BFS of course will find the (only) solution, but it visits more nodes than A*. Dijkstra/Uniform cost search is also relatively useless in such an unweighted graph. Greedy best-first search is better.
2:54 "jiggabyte" 💀💀
I love how google translate rewrites it correctly
Is he french or something
1:20 bro said i dont fking care in 1942750301264920202 different langauges
Had a good time watching. But, a glaring issue with your methodology (and claim to hardest maze ever): There were no looping paths, which have a very, very good chance of rendering Wall-follower methods completely useless.
If you're in an image-editing program, the flood-fill (paint bucket) tool will highlight the solution.
8:40 you can generate a world map by this
4:27 BOGO SORT OF MAZE SOLVING LET'S GOOOOOOOOOOOO
How is A* or Dijkstra not faster? Are you using a priority heap or just tossing everything into an array ?
Because they are looking not juste for a path, but the shortest while the wall follower just needs to find 1 path no matter which one
The underlying graph of such a maze is just an unweighted (spanning) tree. A* is better than Dijkstra because it expands fewer nodes, but "greedy best-first search" is even better.
@@A.R.-mk1lq yes, greedy best-first search is faster, but does not guarantee the shortest path.
@@Someoneyes-y7l For "perfect mazes", which are just trees, it of course finds the "shortest" path because there exists a unique path between any pair of nodes.
@@Someoneyes-y7l Not true in this scenario.
Was excited to see this after seeing that clip of a maze-generation algorithm in the end of the year video!
Very cool! 🔥 keep up the consisting uploads
“One fricking jigabyte!”
- Green Code
Why do programmer youtubers always pretend their viewers don't want to hear about programming
cause we don't 💀
@@smokyvibes speak for yourself
Djikstra’s alg is better when you have weighted edges iirc, whereas here you’re just looking at the same distance between each tile, so it’s basically just BFS.
You were printing every step while running the algos? That probably significantly slowed the algos down right?
Nah I wasn't printing every step, just sometimes. For the Final Race, I didn't printing anything as it would take way too much time.
I just did it for debugging purposes.
Hope that answers your question :)
sad you didn't implement the human algorithm:
- just try to follow the direction toward the exit,
- if it doesn't work out, just backtrack until you have another way that seems to lead towards that direction.
- Repeat until you get to the exit.
That’s the first one pretty much he showed. It’s the least optimal way for sure
the "Coding is hard..man" resonated with me on a deep level
I feel like this is a code bullet secret channel
"How to solve the worlds most dificult maze?" One words: Water. I can think of 3 methods.
Method 1: Water presure
Assuming the world of the maze only has two dimensions and no gravity (or gravity but into the thrid dimensions direction means it wouldn't really matter here), just connect a water pipe to one end and pump water through it. The only path it can take is the path (or paths) to the other end, since all other routs are dead ends and due to water presure it can't go in there.
Method 2: flowing water
Just connect a (large enough, or invinite for a simulation) water source to one end and let it fill the maze. The water will flow into all paths but stop at ends. So it if water comes out the other end, you can follow the path like its a river.
Method 3: Water and gravity
Just hang the maze on the wall, connect a (again, large enought) water source to the top and let it run through the maze. Since the only way to diplace the air in the maze is by pusing it hrough the other end it can only fully take the routes towards the other end since all other paths will get clogged by the water.
I don't know how good fluid physics engines are though. Maybe all methods might work in simulations, maybe just one, maybe non at all.
How do you do such animated videos? I really want to know how to build things like your character, the maze generation, and pretty much everything. I love them so much!
If you start in a middle of the maze then right wall algorith would not work
the thumbnail alone made me know that this video would be good. Subscribed :D
"just go right bro"
also the maze i have to go though hugging the wall:
Next video: I solved the worlds hardest maze in 0.00072748826254284921 seconds with code
THIS is the worlds hardest made. Harder than this maze, this maze AND THIS MAZE! no duh
A good way to measure efficiency in maze solvers is by the number of steps they took to find a solution. Wall followers are quick to process, but they take way more steps to find a path than A*. The dead end filling algorithm is neat, but it needs to explore so much of the map.
I'm disappointed you didn't give the random mouse a chance. You should always give random algorithms a chance just in case it solves it first try; you want that shit to be on camera.
if i was stuck in a maze twice the size of paris i would want to solve the maze as fast as possible rather than develop the fastest path then get out
I‘m writing a paper on this topic (I coded the mazes in Ruby) and I‘d like to give a shoutout to my boy the Aldous-Broder Algorithm for giving me an absolute headache with how long it takes to generate
Dijkstra is not specifically made for mazes, it works much better on complex graphs with weights on the edges.
it’s effectively breadth first search. So its as good as any solution other than A* that simply biases with a heuristic.
Dijkstra in computer class was such a pain
who needs a robot when you can stick to the right side of the wall
This brings me back to my junior year of software engineering lol
roblox click to move
Haha so true 😂
underrated coment
what library did you use to display the maze? also great video, really enjoyed it!
it would cool to calculate how much
time a human would take to finish this maze, considering that they would always go for the right and need to stop to eat and sleep
Google doesnt use that algorithm, its not computable on a global scale road network, google uses a variation of the heat method, and yes the heat method can solve this problem a lot faster
what’s the heat method and could ya list a source i could use to read up on it coz i couldn’t find it with a google search. Thanks
I wonder if the maze creation algorithm has some kind of creation bias that allows the wall follower algorithm to perform more efficiently than the other algorithms
3:00 There is NO WAY that is a separate OBJECT PER CELL of the maze-
Python takes 24 bytes per integer (not even objects, just integers) so 192 bits, possibly even more than that (I've heard of 200+ bits), when you only need 2 bits per maze cell under optimal circumstances. You have 2 bits of useful memory for every 192 bits that you spend. No wonder you ran out of memory XD
A decent way to compress this is to use Python's bytearray() so you can create and manipulate individual bytes. Then, using bitwise operations, you can store 4 cells per byte, maximizing your memory.
Yeah I don't know, I just used the pickle library and somehow I got a really really large file. Couldn't be asked to figure out why 😅
or, you could use that python has no problem with really large ints, and let you use bitwise operations on it, and use an int to store everything. if you want to prunt it, i recommend hexadecimal
i used large integers on an space limited microcontroller, for printing letters (2 bytes per letter, to know which loght to activate * 40 characters or so)
(the lib only supported fixed length characters, but needed that few pixel (display is 4(width)*5 (hight) pixel (max size for a symbol is 3*5 pixel)
Make a circular maze
POV: Your dad's screensaver
I don't get why this only has 13k views wtf, this is like code bullet tier, really well done
You should try implementing bidirectional versions of theses algorithms
so at 0:55 you explain the Iterative implementation (with stack). and then a few seconds later, you implement a recursive implementation of the maze gen?? mistake?
Such a banger of a first view!
10/10
I hadn't come across anyone creating content like yours before, so I started following you a year ago, and I absolutely love your entertaining content. However, if you stop posting videos for a long time (again), I'll be come to your house and kick your ass. 😅
Thank you for the kind words! I'll make sure to keep uploading videos (i'm afraid now)
If you like my type of content make sure to check out Code Bullet, he's been my main inspiration for my videos :)
@@Green-Code I love both of you guys! Glad to see a new video!
WallFollower L and R always move one tile. A* cheats by teleporting anywhere in the whole maze
just by peeking at your code at 9:23, i can see that your implementation works in O(n^2 logn), you are sorting the list of unvisited vertices every iteration of the algorithm, so you are doing an O(n logn) each time you run the algorithm, when you could run dijkstra in O(n log n) lol. that's why it's usually implemented with a priority queue
im using n loosely as the number of cells and edges, both of which are O(w*h)
in any case, you are better off doing a simple bfs because the weight of each edge is 1, so ignore my previous comment
wall followers will give most optimal solution as well if you discard backtracking paths
it depends/dont have to
No floodfill is a crime
BTW Wall follower is not the best algorithm as it is not reliable when the maze have loops
Right hand and Left hand is my favorite because it looks like a country border, and i like maps
oh yea and also that's (i think one of but i forgot) the first tips i got to solve a maze (i didnt use it tho)
7:30 WHY
*a mobile maze game player that reached lvl 300*: too small
If you do an and gate on the two wall follower paths, I think it would get the optimized solution.
Definitely close to as much effort as code bullet, which is saying a lot.
What if
Because the wall followers were pretty quick, but non optimized.
What if you ran a code that only looked at where both wall followers went on the same path, which only should be the optimized path unless there are multiple ways to the end...
dont add print statements if you want code to run fast
learnt that the hard way when making a 3d renderer
2:56 Giggabyyyyte!
What module do you use to visualize or show the process and of the algo?
8:31 lmao it looks like fantasy world’s map
underrated ahh youtuber
i love code youtubers
im currently studying maze generation, and im seeking for algorithms that are really flexible and that can be added troug a lot of different render variations, shapes, or wall width and height, and i wonder what is the best architecture, i thought about doing it with one class that represent the cell, and one that represent the wall, each cells are in an array and reference their walls, the walls would just serve as "link" between two cells and say if they are pathable or not, is this the structure you made ? or did i miss something here ?
a whole jiggabite 🥶🥶🥶
HOW DID U ANIMATE THIS???? LOVE U GREENCODE 💚
The new animations are so cool man
Thank you Guillem! 😉
Code bullet's voice is weird on this one
Hey! Just a question, Do you use hackintosh? (Please answer honestly)
please tell me how to make such animations.
what is used to animate walking through the maze
How long did it take to generate that maze, python is not a fast language.
You definitely did something wrong if A* is not the fastest. Maybe wrong heuristic or you used a list instead of a heap. Btw. For optimal performance on really big mazes we normally use a Fibonacci heap but these are petty complicated to code
I thought A* is going to dominate
A noob question but what framwork do you use to visualize these mazes and solving of them...... like for example in cpp we can use SFML for that purpose....??
This isn't the biggest maze! considering technically you could consider the earth to be a maze with the streets and turns!
You are the best. Thanks !!!!
if you combined the L-hand and R-hand algorithms, would they fill every cell of the maze?
don't have to, but depends on the map (/map generator)
Theoretically, there can be an unreachable part of the maze
I'd love to try running these on my computer. Any chance you'll post your code?
You can! I'm uploading all my code today to Patreon :) (and all my code from all my previous projects)
jsut wanted to know, do you make a lot of money, im asking bcasue you seem to know a lot about coding, so im interested to know how much money someone of your coding experience can make ?
"THE FINAL RACE"😂
The maze program Daedalus has maze that's about 1 billon by 1 billon. Good luck beating that one lel
Correction: It has one billion paths to a side, and one quintillion cells total.
pretty interesting video, i sure hope there isn't any ai-generated imagery in it!
ok i just got to 2:32 and i have bad news
Dude everything I did myself. I just couldn't be asked to draw a circus :)
I was cheering for algs that i know myself, they weren't so effective ngl😕. Why only 15k subs?! I thought at least 250k, content quality is so high!
bro make your own algorithm which work like water and water is most good maze solver in world
0:12 he meant dumb as in not the mainframe
0:24 ORIGIN SHIFT BY CAPTAIN LUMA
How did you represent the maze in memory? Adjacency matrix or list?
I hope neither of them but one large bit set.
best ml channel on youtube by far!!!!