I Solved The World's Hardest Maze (with Code)

[@DotboT3812]

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

[@AlternateIsopod]

i thought of that too

[@monterrang1]

unironically would make alt maps on it

[@DorusModderman]

A i was just about to comment this

[@yusatelevision]

XD

[@smileyp4535]

Literally exactly my thoughts

[@tiileaf]

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)

[@QWERTIOX]

A* is literally modified dijkstra so it 's weird that he could implement A* and not dijkstra

[@trollsansofficial]

More like di-

[@alger_real]

did bro call gigabyte jigabyte

[@trollsansofficial]

You expect me to NOT pronounce it jigabyte?

[@ThatNerdGuy0]

yeah, and jif clearly

[@diheinfernando1837]

True

[@Boxytablet]

@@trollsansofficialYES I EXPECT YOU TO NOT PRONOUNCE IT THAT WAY

[@golovkaanna8757]

@@trollsansofficial jijabyte

[@DirectalYT]

Wait a second this isn’t code bullet

[@nygeli13168]

I was looking for this comment

[@the_SEAT]

@@nygeli13168mee too

[@_HitDetected_]

yeah i agree....who is this green person?

[@trollsansofficial]

I can't believe it's not code bullet

[@Roaxial]

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

[@raffimolero64]

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?

[@Green-Code]

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

[@muslimgamerrr9479]

how the hell do you make it so small

[@muslimgamerrr9479]

@@Green-Code LMAO ur comment is new

[@Roaxial]

@@muslimgamerrr9479 2 bits per cell storing the right and bottom wall. Cells one the bottom and right edge only store a single bit.

[@alexandratsankova5825]

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

[@mean4276]

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.

[@white_145]

​@@mean4276i believe algorithm used in the video doesnt produce loops like that

[@MarcusMarcus-m8g]

I just start from the end

[@WH40KHero]

A neat thing i noticed is that the wallfollower algorithms create whats essentially a negative of each others routes. This is pretty neat!

[@DqwertyC]

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.

[@BrandonMakesGames_]

Me: I want Code Bullet! Mom: We have Code Bullet at home. Code Bullet at home:

[@leggyjorington3960]

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.

[@Green-Code]

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) :)

[@something-likethis]

"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

[@ViolentCabbage-ym7ko]

This channel needs at least 1 million subs. Great content!

[@MrRaveYard]

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.

[@Austin_Playz27]

someone in the comments got it to 5.29 megabytes

[@scratchthecatqwerty9420]

@@Austin_Playz27 It depends whether there is 1024 or 1000 bytes in a kilobyte

[@Austin_Playz27]

ohhhh that makes sense

[@SpaceVisYT]

​@@scratchthecatqwerty9420 1000 bytes in a kilobyte, 1024 bits in a kilobit

[@Andrew-jh2bn]

​​@@SpaceVisYT 1000 bytes in a kilobyte, 1024 bytes in a kibibyte

[@otter502]

5:19 this only works with these specifc types of mazes whete all of the walls are connected to the edges of the board

[@not_estains]

true

[@ITR]

No, it also works with all mazes where the entrance and exit are on the outer wall

[@eugenekrabs141]

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.

[@AstralrAstralr-mj1tr]

@@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.

[@eugenekrabs141]

@@AstralrAstralr-mj1tr Ok but 99% of mazes are start at border end at different border.

[@dawhoelse]

underrated channel

[@WhyIsJupiterInTheFridge]

Yeah i just subbed

[@Tryh4rd3rr]

Ya

[@rafssoares]

Very cool! 🔥 keep up the consisting uploads

[@YoussefGamerYT]

2:54 "jiggabyte" 💀💀

[@energistixgames]

I love how google translate rewrites it correctly

[@Explosive0]

Is he french or something

[@8083music]

Why do programmer youtubers always pretend their viewers don't want to hear about programming

[@smokyvibes]

cause we don't 💀

[@8083music]

@@smokyvibes speak for yourself

[@245trichlorophenate]

Was excited to see this after seeing that clip of a maze-generation algorithm in the end of the year video!

[@Vniulus]

4:27 BOGO SORT OF MAZE SOLVING LET'S GOOOOOOOOOOOO

[@AavyanTiwari]

2:34 As soon as he said ''What's happening'', 0.001 seconds later, I got an ad

[@BandNerd6000]

Same . They're scheduled

[@saumyamenon896]

Same lol

[@watermelon_cat_skateboard]

the thumbnail alone made me know that this video would be good. Subscribed :D

[@analyzers9335]

How is A* or Dijkstra not faster? Are you using a priority heap or just tossing everything into an array ?

[@nitsum8874]

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

[@A.R.-mk1lq]

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]

@@A.R.-mk1lq yes, greedy best-first search is faster, but does not guarantee the shortest path.

[@A.R.-mk1lq]

@@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.

[@A.R.-mk1lq]

@@Someoneyes-y7l Not true in this scenario.

[@VisualTickle]

"just go right bro" also the maze i have to go though hugging the wall:

[@louizysalah5553]

the "Coding is hard..man" resonated with me on a deep level

[@swaystar1235]

You were printing every step while running the algos? That probably significantly slowed the algos down right?

[@Green-Code]

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 :)

[@Kity3]

Next video: I solved the worlds hardest maze in 0.00072748826254284921 seconds with code

[@FredChop1234]

THIS is the worlds hardest made. Harder than this maze, this maze AND THIS MAZE! no duh

[@asailijhijr]

If you're in an image-editing program, the flood-fill (paint bucket) tool will highlight the solution.

[@NStripleseven]

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.

[@yusatelevision]

8:40 you can generate a world map by this

[@kiryonnakira7566]

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.

[@mattmmilli8287]

That’s the first one pretty much he showed. It’s the least optimal way for sure

[@ameyasonyoutube]

“One fricking jigabyte!” - Green Code

[@block7059]

Dijkstra in computer class was such a pain

[@NotNonamelol]

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

[@starrekt2037]

1:20 bro said i dont fking care in 1942750301264920202 different langauges

[@brunomachado7183]

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

[@Golden_Official100]

Such a banger of a first view! 10/10

[@gogorilla803]

who needs a robot when you can stick to the right side of the wall

[@iaminfinityiq7182]

0:24 ORIGIN SHIFT BY CAPTAIN LUMA

[@KushagrKumar-n1c]

HOW DID U ANIMATE THIS???? LOVE U GREENCODE 💚

[@DarkRedman31]

Actually no Google Maps doesn't use A*, it would be so long, it uses more advanced algorithm that are far more efficient.

[@fredtrentini6791]

I don't get why this only has 13k views wtf, this is like code bullet tier, really well done

[@drdilyor]

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

[@A.R.-mk1lq]

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.

[@OmarRida10]

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!

[@redcarnotaurus323]

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

[@xeridea]

Just find the nearest airport

[@rusytop4910]

please tell me how to make such animations. what is used to animate walking through the maze

[@SkydivingSquid]

This brings me back to my junior year of software engineering lol

[@leocarrico8569]

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

[@thijsdekabouter9198]

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?

[@lobotomiepraktikant1128]

Dijkstra is not specifically made for mazes, it works much better on complex graphs with weights on the edges.

[@cv-p1l]

it’s effectively breadth first search. So its as good as any solution other than A* that simply biases with a heuristic.

[@karimalramlawi7228]

I feel like this is a code bullet secret channel

[@Furkan-yv5ew]

If you start in a middle of the maze then right wall algorith would not work

[@Arch-mv5te]

what library did you use to display the maze? also great video, really enjoyed it!

[@clixis]

underrated ahh youtuber i love code youtubers

[@MichaelUrocyon]

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.

[@_JL27]

"THE FINAL RACE"😂

[@justdopemusicsounds]

U should implement dijiktrasa algorithm using heaps to reduce time complexity

[@the_big_cheez]

roblox click to move

[@dptp201]

Haha so true 😂

[@mazocca]

underrated coment

[@Lampe2020]

2:56 Giggabyyyyte!

[@FelanLP]

"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.

[@sacredcat3222]

What module do you use to visualize or show the process and of the algo?

[@g45h96]

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.

[@diegocamassa1296]

Make a circular maze

[@firecreeper928]

No floodfill is a crime

[@GuillemBassets]

The new animations are so cool man

[@Green-Code]

Thank you Guillem! 😉

[@emrekaram]

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. 😅

[@Green-Code]

Thank you for the kind words! I'll make sure to keep uploading videos (i'm afraid now)

[@Green-Code]

If you like my type of content make sure to check out Code Bullet, he's been my main inspiration for my videos :)

[@ZephyrysBaum]

@@Green-Code I love both of you guys! Glad to see a new video!

[@thekingoffidget52]

Just a question, do you use lazykh’s thing for animating? If yes, cool!

[@divijverma1524]

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....??

[@Starry00wolf]

Family friendly code bullet

[@YoloYester94]

Definitely close to as much effort as code bullet, which is saying a lot.

[@Greentor]

You should try implementing bidirectional versions of theses algorithms

[@LeLeDeLaGeo]

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 ?

[@white_145]

wall followers will give most optimal solution as well if you discard backtracking paths

[@schwingedeshaehers]

it depends/dont have to

[@Seurak1985]

Cool video, but this World's "Hardest" maze isn't quite close, there is start at the border, and ends at the border, which disqualifies it as hard from the very beginning, at most it could be long to solve, because it's solvable by right-left hand algorithm by any person who can follow one wall :) For true test, try it against maze which do have multiple layers, algorithm starts in the middle, and finish is also somewhere in the middle, even 4 times smaller maze with 4 layers and ways up and down (sometimes by one level, sometimes by two levels) is harder, especially if you ensure some multilayered loops, and path which needs to cross at least few times every layer, especially if some ways up or down the layer are one way only. This is by definition unsolvable by algorithms which cheat from upside perspective knowingly fills all dead ends, because they should have only information what is upfront of their pointer. If you up for a challange, feel welcome to try ;)

[@Bacon_Protogen1111]

*a mobile maze game player that reached lvl 300*: too small

[@vlad_cool04]

Is and operation of right wall and left wall algorithm makes path and makes best path?

[@rBoxYT]

POV: Your dad's screensaver

[@corrpendragon]

I'd love to try running these on my computer. Any chance you'll post your code?

[@Green-Code]

You can! I'm uploading all my code today to Patreon :) (and all my code from all my previous projects)

[@GG4_]

a whole jiggabite 🥶🥶🥶

[@spookykitty2327]

WallFollower L and R always move one tile. A* cheats by teleporting anywhere in the whole maze

[@AbdullahAlZawad-m9x]

Hey! Just a question, Do you use hackintosh? (Please answer honestly)

[@Виктор-ы1п3ф]

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!

[@leonszegedy]

If you do an and gate on the two wall follower paths, I think it would get the optimized solution.

[@RichConnerGMN]

pretty interesting video, i sure hope there isn't any ai-generated imagery in it!

[@RichConnerGMN]

ok i just got to 2:32 and i have bad news

[@Green-Code]

Dude everything I did myself. I just couldn't be asked to draw a circus :)

[@smaug9833]

How did you represent the maze in memory? Adjacency matrix or list?

[@A.R.-mk1lq]

I hope neither of them but one large bit set.

[@aoch1461]

You are the best. Thanks !!!!

[@Iyht]

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

[@abd_sh_321]

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

[@raffimolero64]

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.

[@Green-Code]

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 😅

[@schwingedeshaehers]

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

[@schwingedeshaehers]

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)

[@artemsheykin556]

best ml channel on youtube by far!!!!

[@Green-Code]

[@korneldekany6689]

I thought A* is going to dominate

[@zix2421]

8:31 lmao it looks like fantasy world’s map

[@PrabalVerma-iy7yz]

how do you animate these videos

[@HarrisonBorbarrison]

2:56 Jigabyte

[@violetfox4065]

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...

[@miawmiawgary2024]

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)

[@miawmiawgary2024]

7:30 WHY

[@deventerprises2640]

BTW Wall follower is not the best algorithm as it is not reliable when the maze have loops

[@ThomasDeSwert]

This isn't the biggest maze! considering technically you could consider the earth to be a maze with the streets and turns!

[@maxwell6881]

How long did it take to generate that maze, python is not a fast language.

[@RageBird7200]

Just go around the maze!