2
\$\begingroup\$

I have a set of items and a data structure that describes where and how those items may be dropped. I'm looking to implement a roguelike/randomizer element to the game and want to include the special items that control progression.* Ensuring the game remains completable is an absolute requirement but I'm having trouble handling all the different constraints that mixing up the progression item locations brings.

I'm looking for a way to model the requirements that isn't just hard-wiring them into the randomizer logic and hoping I got it right. Preferably some kind of DSL that is processed and kicks out a partial drop table that at least guarantees completion is possible that I can slot less important items into afterwards. Does this kind of modeling tool exist?

*: for reference the game is a Metroidvania-style platformer, so progression items are things that unlock traversal abilities like a double-jump, swimming, immunity to lava, etc. They are not necessarily acquired in order though many are locked behind others in the vanilla game.


Detailed explanation of specific problem:

Let A,B,C,... be special progression items.

Each location in the drop table has a boolean constraint describing what items are necessary to access that location. For example A | (B & C) would imply two possible paths: get A, or get B and C.

Early-stage locations are easy to model because they generally have no or very short constraints. Later-stage locations become very complex as the boolean expression must expand to cover every possible progression path and very quickly become something like (A | B | C) | (D & (E ^ F)) | ... with another 4-5 terms following after. Getting these constraints wrong means it's possible to generate an impossible-to-complete game.

Trying to handle the constraints in code quickly become intractable and very difficult to debug. Thus the search for a better way to model the constraints.

In the end it's a kind of recursive boolean satisfiability problem. In theory I could build a giant expression for the entire game complete-able state and repeatedly run it through a SAT solver until completion is achieved or it stalls. Food for thought in case anyone else has this same problem.

\$\endgroup\$
  • \$\begingroup\$ I don't think you'll find an out-of-the-box tool that just does this. Every game I've ever worked on has such different concepts of how they structure their loot tables or prerequisites that generalizing such a tool to work across multiple games would be impractical. Moreover, tools requests aren't on-topic here. But we can help you solve this problem for your specific game. Have you read up on how this problem has been solved in existing games? How have you tried applying this to your game so far, and how can we help? \$\endgroup\$ – DMGregory Aug 24 at 13:20
  • \$\begingroup\$ I've read that post but the approach isn't well-suited to multiple progression paths. Because of the large number of drop locations only having one path hasn't playtested well when players miss a single important chest. Though I may be able to enumerate a large number of paths, select a few, then apply more traditional techniques. \$\endgroup\$ – thegreatunclean Aug 24 at 19:02
  • \$\begingroup\$ The method at the link is not restricted to one progression path. Can you walk us through how you've tried to apply it to multiple progression paths and gotten stuck? We may be able to help you find a solution. \$\endgroup\$ – DMGregory Aug 24 at 19:06
  • \$\begingroup\$ Can you add more detail on what a "location in a drop table" is? Generally I'm used to seeing items in drop tables, so I get the impression that you're using this term in a different sense. \$\endgroup\$ – DMGregory Aug 24 at 21:26
  • \$\begingroup\$ By 'location' I just mean 'entry in the drop table structure' to be a generic container. So a chest would have one entry with (potentially) multiple items that it could contain, each monster has their own entry for (potentially) multiple items to drop, etc. \$\endgroup\$ – thegreatunclean Aug 24 at 23:22
1
\$\begingroup\$

I'm still not fully sure I understand the way your generator works, producing / using these constraints, but I'll walk through one possibility and we can use that as a starting point for clarifications & corrections.

Let's say we've already generated a map that requires specific items/unlockable abilities to access various regions. We want to populate that map with pseudo-random rewards, so that the player is guaranteed to be able to get the items they need to access region X without already passing through region X, so that the map remains solvable.

Let's start by fixing a sequence of the key items to be collected. Note that when we do this, we're not forcing the game to be linear, nor mandating that the player will collect them in this order. All we're doing is ensuring there is at least one viable solution order - and other orderings may also be possible.

This choice to focus on ensuring one guaranteed solution path, rather than modelling every possible path, cuts the complex boolean satisfiability problem of multiple routes down to comparing indices in a single route. We still get alternative paths as a side effect, but they're no longer necessary to evaluate in aggregate in order to guarantee solvablity.

We could approach this in one of two ways:

  • Pick the sequence of items first, then generate the map so that barriers that need early items occur early in the map. (It doesn't benefit the player to get the fire resistance boots if there's no fire in the part of the map they can reach so far, so they won't be able to see immediate benefit)

    The Lenna's Inverse strategy works this way, growing the map as a tree with nodes labelled by the number of key items collected before reaching that point, which only increase as we grow the tree outward. Then cross-links are added for non-linearity, and barriers requiring key item X are added to any link where Max(items required by room A, items required by room B) == X

  • Generate the map first, then do a breadth-first search through it, passing through only barriers we already have the items to cross, and noting which uncrossable barriers we've encountered. When we run out of reachable regions, add an item that will pass one of the uncrossable barriers we've met so far to the end of our sequence, and resume our search with these barriers as the frontier.

Either way we go, we now have two related sequences:

  1. A sequence in which the key items can be obtained

  2. An expanding sequence of "tiers" of the map, accessible once the player has all of the first X items from the item sequence. Tier 0 is the area around the starting location that is accessible without passing through any barriers at all. Tier 1 is the area the player can reach with only the first item, etc.

    Note that each tier includes the tiers before it, rather than only the new addition - we'll use this to allow multiple solution paths.

Now we can place our items. For each item i, enumerate all the opportunities in map tier i-1 where it could drop. (Say if the fire resistance boots can only drop from a fire-type enemy or a red chest, count up all the fire enemies/red chests) You can do this without explicitly coding constraints in advance: just search the drop table to see if item i appears in it.

If you ever encounter an item that has no opportunities to drop in the preceding tier, then it's time to locally modify the map to put at least one opportunity somewhere. You can often do this without re-generating the whole map. Or, to avoid this possibility, you could start by stamping some spot in every tier with one opportunity for the next item, before you populate the rest of the region's contents to match this seeded bit.

Because tier 2 includes tier 1, which includes tier 0, it's possible that the first two items are both accessible in the starting area - that the player may get item 2 before they get item 1. So they might be able to access regions in a different order than our tier list. That's how we can get multiple solution paths/non-linearity, even though we only rigidly guaranteed a solution path with item 1 first.

This doesn't break our solvability guarantee, though it can allow opportunities for sequence breaks, where the player finds a way to beat the level without getting one of the items. This can be controlled for if it's not a desirable outcome.

Now you have two choices: you can either fix one of the opportunities in each tier as the one that will give the next item, or make it stochastic during play:

Each time the player hits one of these opportunities, in the preceding tier and it doesn't award the key item, decrement your count of remaining opportunities for this item. You can skew your loot probability so that it reaches 100% drop rate when the player is down to their last opportunity, or shape it to typically drop 3/4 of the way through, etc.

In pseudo-code, that might look like this:

foreach(keyItem in guaranteedSolutionSequence) {
    if(rewardSource.CanContain(keyItem)) {
        probability = 1f / keyItem.remainingOpportunities;

        if(random() < probability)
            reward.Add(keyItem);
        else if (GetTierIndex(rewardSource.position) <= keyItem.index)
            keyItem.remainingOpportunities--;
    }
}

Here I allow one opportunity to drop multiple key items, so even if there's only one chest in the first 3 tiers you can still make progress. But you can ensure your generator drops opportunties in every tier so that this isn't necessary.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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