1. icon for News
  2. icon for TCHOW

News

Tuesday, July 30, 2013

Rktcr World Generation Cleanups

In Rktcr, you play in one of many randomly generated worlds. (Or you play challenge levels, but that part of the game is already pretty much sorted out.) Worlds come in three sizes: 3-gem, 7-gem, and 14-gem. Worlds are assembled by selecting zones from a pool of possible zones and connecting together portals in those zones.

Today, I spent a bit of time patching this world-generation process to make it faster to build new worlds. Here are a few of the results, as displayed by my debug viewer:

The Old Process

The old world generation process for a world with N gems:

  1. Select (at random, without replacement) N zones that contain gems.
  2. Select (at random, without replacement) N zones without gems.
  3. Shuffle the selected zones, then move a zone without a gem and with at least three exits to the start of the list.
  4. Connect a random portal in each zone to a random unconnected portal in some previous zone. (In the first zone, connect to the start portal.)
  5. Make a list of all unconnected portals, shuffle it, and connect adjacent pairs of portals in the list (if the list is odd-length, connect the last portal to itself).

For every generated world, wrapper code then checks, based on the claims contained in each zone, if a path collecting all gems and returning to the start exists. If so, the world is stored. If not, another world is generated.

A few notes:

Step 3 moves a zone with several exits to the beginning because I want players to have a choice immediately upon starting. This helps to indicate that world mode isn't like challenge mode.

Step 4 makes sure that all the zones are at least connected -- a necessary (but not sufficient) condition for the world to be solvable.

The Update

Today I replaced steps 1-4 with a variation that makes it more likely the updated world is solvable:

  1. Keep a list of reachable, unconnected portals (and world states). Add the start portal to the list.
  2. Pick a reachable portal, world state pair -- r,w -- at random and an un-added zone at random (pick the first zone from those without gems and with at least three portals; for the remaining, alternate picking zones with and without gems).
  3. Pick a portal p in this selected zone so that there are some claims with p as the starting portal and a world state consistent with w. If the zone has gems, these claims must get the gems.
  4. Add the selected zone to the list of zones in the world. Add a connection from r to p. Update the list of reachable, unconnected portals.
  5. If more gems are required, go to step 2.
  6. Connect remaining portals as per step 5 above.

In essence, the new procedure makes sure that added zones (and gems) aren't just connected, but are also reachable. This makes it more likely that the generated world is solvable.

Of course, it can still happen that worlds generated this way aren't solvable -- for instance, the gems can all be reachable, but there might be no way back to the start portal. However, the yield is much greater.

Conclusion

Previously, it took 8 cores overnight to generate about 20 large-sized worlds. With this new code, a single thread managed to crank out 100 of the large-sized worlds in about an hour.

This is especially good news if I start writing scripts to curate the generated worlds; e.g., by balancing appearances of each zone. It also means that generating a new pool of worlds after adding zones should be relatively quick.

2 comments:

  1. Doesn't the new method make it more likely zones without gems won't need to be traversed in the winning path?

    ReplyDelete
    Replies
    1. I think you might be correct. Certainly that's something I'm interested in measuring (and mitigating) with world curation scripts. I suspect that things are actually biased more by the shape of the zones themselves (e.g. zones with only two exits are probably less likely to be on the solution path); but I won't really know until I actually run some scripts.

      Ideally, of course, I'd like every zone to appear in about the same number of worlds, and I'd like most of the zones in a given world to be relevant to the solution. Also, I'd like the appearance of any given zone to be conditionally independent of the appearance of the others. (And, probably, a similar property on zone-zone connections should hold -- any portal should connect to any other portal with about equal probability.)

      It will be interesting to see how many of these properties I can enforce while still getting a decent yield on generated zones.

      Delete