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.