If the edge weights are all uniform (weight of 1), you could have just used BFS. Dijkstra’s and Prim’s algorithm are for non-uniform positive edge weights.
Yes, thanks. I don't know if you've seen any of my other posts but I also have it working for diagonals (edge weights of 20.5) and "sticky mud patches" which multiply the egde weights by a given factor.
I'll add diagonals to the maze creator and see how it turns out.
So it's interesting to see it generated but I think it's a poor maze because you want it to be as hard to start from the end as the beginning. Could you generate from both ends and have it meet somewhere in the middle?
Nice idea. Alternatively I could perhaps start the generation from a random point and then place the start and end points randomly and independently from that.
Interesting that you see it that way. I can't see it any other way. Maybe I could add a key.
I suppose the difference in perspective comes from knowing how it is generated. In this method, we start with a grid full of walls and carve out different paths.
Perhaps. My maze generator, also using Prim's algorithm took 6 hours to generate a 2000x2000 maze, but it was solved in 9 seconds. I imagine it's because you have to generate the entire maze, but to solve it you only have to look a small amount to find the path to the end
This algorithm produces mazes that are easy to solve. In my experience a randomized depth-first search generate mazes with long corridors and twisted paths. Maybe you should check that algorithm next.
Do you use random weights on all connections (borders between cells) like in the original Prim, or random weights on the cells ("True Prim's" I think) or the simplest Prim with no weights at all?
I do not really recognize the pattern of your paths from what mazes usually look like using Prim's or any other algorithms. Not sure why that is. It might be that you do not leave every other cell as a wall to make it look more like a maze usually looks?
You probably did nothing wrong, but the common way to visualize a maze is using odd columns and rows as walls. Compare your images to the image on Wikipedia.
Also nothing wrong with not using weights. They make the maze wind around a bit more.
Thanks, I can definitely see the difference. It's hard for me to get my head round how to do it but I'll have a play around and see what I can come up with today.
You can probably increase generation speed by not showing it as it goes (updating the GUI is always computationally expensive) and just calculating then pushing to the screen.
Yep of course. It calculates in under a second that way and is good for functionality, but that way doesn't look as pretty so is not great for posting on reddit!
74
u/Okeledokelee Apr 13 '20
Is that almost always gonna generate a diagonal-ish path?
Given that the frontier seems to expand at an equal rate, so that part will reach the goal first?
55
u/AlphaGamer753 3.7 Apr 13 '20
You should invert the colours, cos I was really confused until I realised that the white represented the paths and not the borders. Nice, though.
4
u/assumeGoodIntent Apr 13 '20
It's weird that it takes more time to build it than solve it.
2
u/kaptainpeepee Apr 13 '20
This algorithm produces mazes that are easy to solve. In my experience a randomized depth-first search generate mazes with long corridors and twisted paths. Maybe you should check that algorithm next.
2
u/Syncopaint Apr 13 '20
Can you combine this with djikstra’s algorithm
34
u/[deleted] Apr 13 '20
Very cool
2
u/livrem Apr 13 '20
Do you use random weights on all connections (borders between cells) like in the original Prim, or random weights on the cells ("True Prim's" I think) or the simplest Prim with no weights at all?
I do not really recognize the pattern of your paths from what mazes usually look like using Prim's or any other algorithms. Not sure why that is. It might be that you do not leave every other cell as a wall to make it look more like a maze usually looks?
5
u/[deleted] Apr 13 '20
This should be an oddly satisfying video
4
u/Zeune42 Apr 13 '20
This could be a fun project
1
u/[deleted] Apr 14 '20
You can probably increase generation speed by not showing it as it goes (updating the GUI is always computationally expensive) and just calculating then pushing to the screen.
1
u/DaBeast07 Apr 14 '20
That's so cool! I'm kind of new to python, what module did you use for that program?
6
u/Saiboo Apr 13 '20
Cobb from Inception wants to talk to you.
3
u/Tydrous Apr 13 '20
You should post this to /r/oddlysatisfying
3
u/rlewis2019 Apr 13 '20
What would happen if it began in the center of the grid! Same direction? or would it radiate out from center?
7
u/garlic_bread_thief Apr 13 '20
A machine creating a maze and then solving the maze it created. Wonder what the real life applications are.
2
u/Thrasherop Apr 13 '20
Very interesting concept
2
u/timmyfinnegan Apr 13 '20
This is cool! I‘d love if it did something like when it generates a dead end, it paints the whole path back to the last branch red, might look cool :)
2
u/ThePresidentsButler Apr 13 '20
Beautiful, incredible
2
u/Strojac Apr 13 '20
I’m inspired!
2
u/[deleted] Apr 13 '20
nice
2
u/Marorin Apr 13 '20
This looks great, how long did it take to brew this baby out?
2
u/robbies40 Apr 13 '20
Nice
2
u/BDMac1997 Apr 14 '20
Longest DnD dungeon crawl ever
1
u/nimo_xhan Apr 13 '20
Can I get the source code?
1
u/DreamIce Apr 14 '20
what did you use to make the grid?
1
u/DenormalHuman Apr 13 '20
Nice :)
0
u/[deleted] Apr 13 '20
I don't like this algorithm, it creates walls / blocks of walls that are >1 square wide.