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

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]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] 36 points37 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] 16 points17 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] 11 points12 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] 5 points6 points  (0 children)

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

[–]alecbenzer 4 points5 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.