Maze start/end
Closed this issue · 4 comments
Great project. Thanks for making it.
I am trying to use it to auto-generate levels in a love game, and it would be helpful to be able to get start/end so I know where to spawn the player and what is "success". Is this built in?
Hey! Thanks for the warm feedback :)
Tbh, I've made this module ages ago, I don't even remember all of the implementation detail. I have even forgotten most of Lua by this point 😅
What I do remember is that every algo generates a "perfect" maze, which means that there's a way to get from every point in the maze to every other point. So the easiest way to define enter and exit is to just choose two random points on the opposite sides of the maze.
PS: I also should set up some notification for my projects, I stumbled upon this issue by pure chance and waaaay to late. Sorry for the huge delay!
Sorry for the huge delay!
No prob! we're all very busy, and I totally understand. I have since switched to godot, just because it supports other things in my game much easier. I find it much faster to get my game ideas into a playable form than I did with love.
I originally intended to port all these great algos to godot, but ended up being fine with just 1 (recursive-backtracker) as it was easy to implement, and seemed to make decent mazes for my purposes. Here is the maze-engine I am working with. The short answer I came up with is to pick a random start-point, then consider the last filled-in space as "end" it's not perfect, but as you say, they all seem to connect, so it seems to work out fine. I will try your "pick any point" method though, as that is pretty cool!
Yes, Love2D makes it really easy to start with something simple yet functional but finishing a project is different case entirely. Here more comprehensive engines like Godot do shine.
About algos, they have the same output theoretically, that is they all produce perfect mazes. But the typical topology of the maze differs quite a lot. If I remember correctly, I myself liked the recursive-backtracker the best because it was pretty simple implementation wise but also tended to make more windy and interesting mazes.
"Pick any point" is a good start, however for the final version you'll probably want to pick two points that have some minimal distance between them, so the experience would be somewhat consistent. Deciding on a random distance in [min, max] and then flood-filling the maze to find all points that are distance away from the start and then choosing a random one from the list might work well.
Just random thoughts from the top of my head :)
I'll consider this issue closed, feel free to re-open it though if you still have some questions on the topic :)
Great discussion! I will keep this in mind for godot. For fun, I might come back to implementing the rest of the algos in godot. For all the perfect-mazes, it might be good to just have a general "find a start and end that are open and far away from each other", whcih might be good for this lib, too. Implementing the algo actually helped in other areas, like just learning how to write gdscript. For now, this totally resolves my original question, though. Thanks!