7
$\begingroup$

I'm trying to come up with a maze generation algorithm that satisfies the following requirements, but I end up with fairly "boring" linear grids that take a long time to generate.

The requirements are:

  • The result is a NxM grid. Each cell may be either a wall, represented by 0, or a number [1, P], which represent a floor "type".
  • The input is the size of the maze (It is safe to assume N*M < 700), the number of floor types, and a list of entries and exits.
  • Each entry-exit couple also includes a list of requirements:
    • The set of allowed floor types in a path (i.e. There must be a path from A to B that only goes through specific floor types)
    • The set of required floor types in a path (i.e. There must not be a path from A to B that does not go through specific floor types)

Extra credit:

  • The input may also a list of required position-value pairs, that must exist in the final result. (e.g. the value at 2, 6 must be 4)

Not sure how to adapt an existing "generic" algorithm to these requirements, any ideas or solutions?

Improve this question
$\endgroup$
6
  • $\begingroup$ Your second requirement list: do you mean that there must not be a minimal path, or could a back-tracking path that goes off on a dead end just to touch a missing floor type be acceptable? $\endgroup$
    – Ian MacDonald
    Mar 27, 2017 at 16:34
  • $\begingroup$ @Ian MacDonald; Let's say we have points A and B, and the set for the first requirement is {1, 2}, and the set for the second requirement is {2}. It means that there must be a path that only goes through floor types {1, 2}, and that must not be a path that only goes through floor types {1}. This means that (assuming P=2) all paths from A to B goes through a 2-tile. I hope that answers the question. $\endgroup$
    – LIJI
    Mar 27, 2017 at 17:14
  • $\begingroup$ Yes, the "all paths" bit clarifies. Thanks. $\endgroup$
    – Ian MacDonald
    Mar 27, 2017 at 17:32
  • $\begingroup$ From the player's point of view, what are the floor types for? Does the player have to collect things? Are there trapdoors and such? Or are they just decorative elements? $\endgroup$
    – BaSzAt
    Apr 2, 2017 at 8:35
  • $\begingroup$ They're used for several things, both decorative and functional. (For example, the player should only be able to go through floors of type 3 if certain conditions are met) $\endgroup$
    – LIJI
    Apr 4, 2017 at 11:47

1 Answer 1

Reset to default
1
$\begingroup$

I think a good general approach is some kind of genetic algorithm.

First, use some sort of maze solving algorithm to test whether your requirements are met (dijkstra or similar). You probably want try to solve it twice. Once with the complete list of allowed floors, to check that it's possible and what the shortest route length is. Second, with the list excluding the required floors to ensure that this is not possible. Whatever the details, this will allow you to have a score for a randomly generated grid. Perhaps a 0 if any entry-exit pair is not satisfied and a number showing the shortest route, if that's what you want to maximize.

Second generate a number of different random mazes and score them. Depending on your restrictions, you may get a bunch of zeros. Then you might need to think of something cleverer than random generation and ensures at least some solutions.

Third, think about a way (or ways) to randomly mutate your best candidates. It may be possible to mix some of the best candidates, taking values from each. This stuff can be all kinds of different things, and depends on what you're trying to do. But if you imagine that you have a population of 100 mazes and then generate 1000 offspring or something like that.

Fourth, score the offspring, take the best 100 (or whatever) and repeat.

Improve this answer
$\endgroup$
4
  • $\begingroup$ This is more or less the solution I tried, but it took very look time to generate (~15 minutes) and the results ended up hardly containing any walls. I should probably think of better generation functions. $\endgroup$
    – LIJI
    Mar 28, 2017 at 16:33
  • $\begingroup$ Well, if it's walls you want, then you need to put that into the score! So have your solver find a solution, and then look along the path and count the walls and add that into your score. $\endgroup$
    – Dr Xorile
    Mar 28, 2017 at 16:48
  • $\begingroup$ That's true, but adding more parameters to the scoring functions will make solving even longer, possibly an unreasonable amount of time. $\endgroup$
    – LIJI
    Mar 28, 2017 at 21:28
  • $\begingroup$ Not really. The art of genetic algorithms is pretty much all in the scoring function. But in this case, you are going to find the shortest path (say using dijkstra), and then run through the path looking for walls. I doubt the walls part will add even 0.1 to a dijkstra. The key is to know what you want and score for it. I didn't see your request to make the paths have walls in your question. Maybe you can fill out a little more in your question what you are actually trying to achieve here... $\endgroup$
    – Dr Xorile
    Mar 29, 2017 at 0:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.