1

I want to make a randomizer for the items in the game La-Mulana. However, some arrangements of items would mean that the game cannot be completed. Sometimes there's only one group of items required to pass an obstacle, other times, there are multiple groups of items which can pass an obstacle.

For example, to reach the Chamber of Birth, you need to have the Feather, Grapple Claw, Hermes' Boots, and Plane Model, or have the Isis Pendant and Hermes' Boots, or kill the fifth boss and have the Plane Model. This means that anything that puts the Hermes' Boots and the Plane Model in the Chamber of Birth makes the game impossible to complete.

Effectively, I'm trying to put a list in random order where some items can never be within a range of indices and some items can only be within a range of indices if others are within a second range of indices. Is there a better way of doing this than to reject and re-generate illegal configurations?

Improve this question
5
  • 2
    Do you care about all valid states having the same probability of being generated? Commented Mar 3, 2017 at 17:17
  • 1
    It would be nice, but if that's expensive, then not really. Commented Mar 3, 2017 at 18:10
  • 2
    Can you indicate roughly what percentage of the possible configurations is invalid and if it is a cheap or expensive operation to check if a given configuration is valid? That would greatly affect the best way to generate a random valid configuration. Commented Mar 4, 2017 at 9:02
  • @BartvanIngenSchenau I can't, no. I haven't mapped out the requirements yet. Commented Mar 4, 2017 at 18:27
  • Do you experience any downside with using rejection-sampling? While there might be smarter solutions, rejection-sampling is simple, and there is fairly little risk of introducing biases. Commented Dec 6, 2021 at 10:26

3 Answers 3

Reset to default
2

Sometimes the best way to generate a valid configuration is to make valid configurations and incrementally build larger ones.

I'm not familiar with La-Mulana. The first time I heard about it was around sixty seconds ago while reading your question. I'm going to assume the locations are linearly visited but we can perhaps generalize the below algorithm.

Assuming the locations are ordered A, B, C, and so forth, and for each X location we know that it requires items X1, X2 etc...:

  1. Put all the items in location A (metaphorically speaking)
  2. For the next location, figure out any items in the previous locations that could be moved to it (i.e. the items that are not needed before the present location). Randomly distribute those items between this location and the previous locations. (Random could mean 'to even out the levels', 'totally randomly' etc...)
  3. Repeat (2) until you are at the last location

Depending on the particulars of La-Mulana, the above algorithm will need to be tweaked.

Improve this answer
3
  • Oh, sorry, no, the game isn't entirely linear; you can backtrack easily and there are branching paths. Progression typically involves solving puzzles or killing a boss to find new items/go to new places which allow you to solve further puzzles. Commented Mar 3, 2017 at 19:45
  • 1
    Could you model it as a directed acyclic graph? If so, the above algorithm can be modified for that purpose. Commented Mar 3, 2017 at 19:52
  • Yes, I can. At the moment I do plan on using this algorithm. Commented Mar 3, 2017 at 20:06
0

One approach that might work here is to create a mapping from integers to legal configurations. That is, 0 would be the first legal configuration, 1 would be the second legal configuration. Then it's simply a matter of generating a random number in a range and expanding that to a legal configuration.

The function that maps from a number to a configuration is the trick, of course. I'm not familiar with the rules of the game in question so it's not clear to me that this is a possible solution here or if it's worth the effort. A lot depends on how probable it is to generate an illegal configuration using the brute force method. If you provide a little more detail on the shape of the problem, more concrete advice should follow.

Improve this answer
2
  • 1
    I can't enumerate all the possible ways that make the game possible to complete; there are 107 items. Commented Mar 3, 2017 at 18:40
  • 2
    @Smurfton You wouldn't need to. You'd just need a way of mapping the Nth logical item to that configuration. For example, if you have a lock that has 5 digits and you choose 4 numbers then you know that 57th combination would be 2-1-0-2 (that's just 57 in base 5) and you wouldn't need to actually generate the 56 combinations that came before it. You just need to come up with a good algorithm to determine "the Nth possible valid state of the game". Commented Mar 3, 2017 at 19:40
-2

A Genetic Programming approach might work.

  1. Choose a scoring function. (A simple score might be number of constraints failed; you might give harder constraints to satisfy a higher value.)

  2. Generate a series of random permutations.

  3. Choose the permutation with the lowest score.

  4. If that score is zero, stop. You have a solvable game.

  5. Create a number of "mutations" of your permutation. For example, make 50 copies, then on each copy, make 1-3 random swaps.

  6. Go to step 3.

Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.