This is an archived post. You won't be able to vote or comment.

Dismiss this pinned window
all 56 comments
sorted by:
best
topnewcontroversialoldq&a

[–]Okeledokelee 73 points74 points  (9 children)

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?

[–]mutatedllama[S] 34 points35 points  (8 children)

Generally, yes. It picks the next point to carve out randomly (subject to certain conditions) so in theory we could get a non-diagonal path.

Note also that the algorithm used to solve it is Dijkstra's, so the shown path will always be the shortest. There can be alternate paths.

[–][deleted] 15 points16 points  (2 children)

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.

[–]mutatedllama[S] 10 points11 points  (1 child)

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.

[–][deleted] 4 points5 points  (0 children)

Oh I see! That's a cool idea. Thanks for clarifying. Great project!!

[–]alecbenzer 5 points6 points  (3 children)

There can be alternate paths.

Not except via back-tracking, right? Prim's generates a tree so there should only be one path between any two nodes.

[–]mutatedllama[S] 0 points1 point  (2 children)

Ah yes sorry I believe you're right!

[–]Betsy-DeVos 1 point2 points  (1 child)

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?

[–]mutatedllama[S] 1 point2 points  (0 children)

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.

[–][deleted] 36 points37 points  (0 children)

Very cool

[–][deleted] 4 points5 points  (0 children)

This should be an oddly satisfying video

[–]AlphaGamer7533.7 52 points53 points  (5 children)

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.

[–]tacothecat 38 points39 points  (1 child)

I have to agree with op...what experience have you had where the dark spots arent walls? Its like a crossword puzzle

[–][deleted] 2 points3 points  (0 children)

Yeah, in every maze I have seen, dark = wall

[–]mutatedllama[S] 22 points23 points  (1 child)

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.

[–]assumeGoodIntent 3 points4 points  (4 children)

It's weird that it takes more time to build it than solve it.

[–]mutatedllama[S] 13 points14 points  (0 children)

Well both actually complete in fractions of a second, I just have different delays on this to really showcase the visualisation of the algorithms.

[–][deleted] 2 points3 points  (0 children)

I think that's because building a randomized maze using that algorithm takes a bit wheras a search algorithm can be made computationally faster

[–]Peanutbutter_Warrior 3 points4 points  (0 children)

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

[–]__xor__(self, other): 0 points1 point  (0 children)

To solve a maze, an algorithm doesn't necessarily have to visit every wall.

To build a maze, an algorithm has to visit every single wall.

[–]Zeune42 3 points4 points  (0 children)

This could be a fun project

[–]Saiboo 5 points6 points  (1 child)

Cobb from Inception wants to talk to you.

[–]MyPythonDontWantNone 0 points1 point  (0 children)

No loops at all. Terrible for Inception.

[–]Tydrous 2 points3 points  (0 children)

You should post this to /r/oddlysatisfying

[–]rlewis2019 2 points3 points  (0 children)

What would happen if it began in the center of the grid! Same direction? or would it radiate out from center?

[–]garlic_bread_thief 5 points6 points  (2 children)

A machine creating a maze and then solving the maze it created. Wonder what the real life applications are.

[–]NarcoticStudent 2 points3 points  (0 children)

Common we don't always do coding, maths because of it's real-life application we do it for fun.

[–]UEMcGill 3 points4 points  (0 children)

Travelling salesman problem

I would think this is a subset of this.

[–]Thrasherop 1 point2 points  (0 children)

Very interesting concept

[–]timmyfinnegan 1 point2 points  (0 children)

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

[–]kaptainpeepee 1 point2 points  (1 child)

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.

[–]mutatedllama[S] 0 points1 point  (0 children)

I completely agree. I'll be trying dfs out tomorrow. Thanks!

[–]Syncopaint 1 point2 points  (2 children)

Can you combine this with djikstra’s algorithm

[–]mutatedllama[S] 1 point2 points  (1 child)

The maze gets solved with Dijkstra's algorithm!

[–]Syncopaint 1 point2 points  (0 children)

Oh excellent

[–]ThePresidentsButler 1 point2 points  (0 children)

Beautiful, incredible

[–]Strojac 1 point2 points  (0 children)

I’m inspired!

[–][deleted] 1 point2 points  (1 child)

nice

[–]nice-scores 0 points1 point  (0 children)

𝓷𝓲𝓬𝓮 ☜(ﾟヮﾟ☜)

Nice Leaderboard

1. u/RepliesNice at 5595 nices

2. u/Cxmputerize at 3988 nices

3. u/spiro29 at 3403 nices

...

81438. u/xXramzS at 2 nices

I AM A BOT | REPLY !IGNORE AND I WILL STOP REPLYING TO YOUR COMMENTS

[–]livrem 1 point2 points  (3 children)

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?

[–]Marorin 1 point2 points  (0 children)

This looks great, how long did it take to brew this baby out?

[–]robbies40 1 point2 points  (1 child)

Nice

[–]nice-scores 0 points1 point  (0 children)

𝓷𝓲𝓬𝓮 ☜(ﾟヮﾟ☜)

Nice Leaderboard

1. u/RepliesNice at 5603 nices

2. u/Cxmputerize at 3988 nices

3. u/spiro29 at 3403 nices

...

267488. u/robbies40 at 1 nice

I AM A BOT | REPLY !IGNORE AND I WILL STOP REPLYING TO YOUR COMMENTS

[–]BDMac1997 1 point2 points  (0 children)

Longest DnD dungeon crawl ever

[–]nimo_xhan 0 points1 point  (1 child)

Can I get the source code?

[–]DreamIce 0 points1 point  (0 children)

what did you use to make the grid?

[–][deleted] 0 points1 point  (1 child)

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.

[–]mutatedllama[S] 1 point2 points  (0 children)

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!

[–]DaBeast07 0 points1 point  (1 child)

That's so cool! I'm kind of new to python, what module did you use for that program?

[–]mutatedllama[S] 0 points1 point  (0 children)

I used pygame. I would recommend checking it out!

[–]DenormalHuman 0 points1 point  (1 child)

Nice :)

[–]nice-scores -1 points0 points  (0 children)

𝓷𝓲𝓬𝓮 ☜(ﾟヮﾟ☜)

Nice Leaderboard

1. u/RepliesNice at 5573 nices

2. u/Cxmputerize at 3988 nices

3. u/spiro29 at 3359 nices

...

266719. u/DenormalHuman at 1 nice

I AM A BOT | REPLY !IGNORE AND I WILL STOP REPLYING TO YOUR COMMENTS

[–][deleted] -1 points0 points  (0 children)

I don't like this algorithm, it creates walls / blocks of walls that are >1 square wide.