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.

TCHOW is Travelling (until August 1st)

This week, TCHOW World Headquarters will be driving up to Portland, Maine (helping a friend move). I expect it to be hard to code in a moving van with a dog sitting on my lap. As such, updates over the upcoming days may be somewhat sporadic and lacking in game progress.

I do have a few things I've been hoping to post about -- perhaps more prose-heavy and tangentially related to Rktcr than the recent slew of posts -- so this news page won't be entirely silent over the coming days. I'm also thinking of trying to write a 7dRTS; but... well, we'll see.

Also, why not give Rktcr Demo 2 a try, and comment/email/tweet at me?

Rktcr Demo2

Next week, I'm going to be on the road helping a friend move. Since this takes me away from my Windows and Linux build machines, it seemed like a good time to do another demo release of Rktcr.

So go get it over here.

What's new?

Well, I did fix a physics glitch, so some paths may be invalidated. Other than that, it's horde of little refinements. Portals now glisten, there are more skins and costumes for vehicles and characters, backgrounds and edge-of-level are handled differently, and some par times have been improved.

I also decided to package all of the basic challenge levels with the demo. This is -- in part -- a stopgap measure that (I hope) will ease the learning curve. It also means that there's an even more ridiculous amount of gameplay in there now.

Oh, and the Linux build is switched to 64-bit. I don't think this should matter, but if it does, please comment.

Note: if you happen to be a journalist or a Let's-Play-er, and I haven't already done so, e-mail me and I'll be happy to link you to the full pre2 build [contains more levels and worlds].

A Dash of Levels and a Pinch of Scrambling

Today, I'm continuing my recent spate of loose-end-tying in Rktcr with some code tweaks, graphics adjustments, and new challenge levels.

Challenge Levels

I finished up a few challenge level ideas I had been playing with. I don't want to say too much about these, lest I clue the solutions, but these are definitely worthy of their "tricky" label.

The flat blue background of the challenges was starting to look ugly, so I added a crumpled paper texture (an actual scan of an actual sheet of my scrap paper, in fact). I don't think it's quite right yet (I should pull some sort of normal map out of that paper photo), but at least it breaks up the monotony of the background a bit.

Car Scrambling

Since there are now five possible car sprites, I decided to add part scrambling. This allows for exponentially more unique vehicle appearances.

Three New Rktcr Vehicles

Today was another day of drawing things for Rktcr. In part, this was because my remote git server was down due to a power outage, so I wanted to stay away from (mysterious prototype) and Rainbow, both of which I had most recently worked with on my laptop. Mostly, though, it was because Rktcr really did need some vehicle variety.

So here's what I got into the game today:

This vehicle skin was inspired by locomotives; the counterweight design in the wheels was to mitigate the "hammering" of the track caused by the drive piston motion. I think I struck a decent balance between ornamentation and staying true to Rktcr's flat style, though the front triangle seems a bit lacking. I might also decide to come back and tint the wheels. I tried a few tints while drawing and nothing looked quite right.

Next, I decided to head to the future. This vehicle was inspired by a whole slew of visual influences, from plates-over-machinery robot design to the circle-segment elements of the Remember Me logo. I think it came out rather well; though I find that the wheels and body can sometimes blend together.

Finally, I tried to channel a sort of present day performance car aesthetic -- some body panels for aerodynamics, but over a light tubular frame. And, of course, ridiculous low-profile tires and custom rims to round out the look. I'm honestly not sure what that exhaust system would be used for, but I liked the asymmetry.

New Rktcr Challenge Level: Shape

Added a Rktcr basic challenge level this morning:

It's not complicated, but playtests have indicated that more not complicated levels might be a very good thing.

Physics Objects on the Boundary of Death

...at least that's what the overly dramatic line in my TODO.txt said.

It's hot today and I'm feeling less than entirely energetic, but I wanted to make at least some progress on Rktcr before taking my laptop off to air-conditioned environs to wait out the afternoon.

So I finally fixed up the level vignetting so that objects falling out of the level border are masked out. (Before is on the left.) The code to do this is a complete hack, but I was feeling lazy and wanted to avoid writing convex/half-plane clipping code, so I ended up opting for a bit of extra overdraw and calling it good enough.

This ticks off another of the myriad little things that need to get done in Rktcr, and brings the game a (tiny) bit closer to release.

Glimmers in Rktcr and Motivation

Recently, I've been making factual posts -- talking a lot about what I'm doing and why I'm doing it from a design or implementation perspective. Today, I'm making a short post to talk about the other side of things: motivation and direction.

I've heard indie developers (also fellow graphics researchers) complain about lack of motivation. This is not a problem for me; I always want to make progress, and I'm almost pathologically optimistic about outcomes. That said, I often feel the crushing weight of the whole TCHOW experiment; of not having a job, of not having any backup (if I don't do things, they don't get done), and of not having any hard deadlines (except when my self-funding runs out in ~13 months).

I know that for some folks out there these all sound like really good things. But, let me tell you, they aren't. They simply add planning time to one's already overburdened schedule.

And that leads to the big problem for me: not motivation, but direction. I start each day with plenty of creative energy, but it's never clear where I should be expending it. Do I work on Rktcr? Rainbow? One of the many prototypes I've been meaning to build? Do I put my effort into code? Art? Sound?

I don't really know the answer to that. So I just try to do something (or several somethings) each day, so that every week Rktcr and Rainbow and TCHOW games in general move closer to being done.

Today, that little thing was some glimmers for the portals in Rktcr, because they are sometimes hard to spot otherwise. It's a little bit of eye-candy, and it addresses a rough spot for new players.

Design Goals for a Board Game Rulebook Langauge

I spent today drawing things for Rktcr, so it's definitely time to unwind with some recreational math. And the problem that has been on my mind recently is how to design a language for describing board games.

But before I get into that, I'd like to take a detour into the problem that got me started thinking about this.

The Motivation: A Cryptographic Primitive for Deck Shuffling

Some time ago, I spent a little bit of time thinking about a relatively basic cryptography design problem: design an protocol that allows a group of agents to collaboratively shuffle a deck of cards, such that no person in the group knows the final ordering, all cheating is detectable, and the ordering will be random as long as at least one person is acting honestly.

I don't remember the full algorithm I came up with at the time, but loosely, it involved each player obscuring (in a Diffie-Hellman-like way) each card, shuffling the cards together, and handing them to the next player. Once all the players have done this, any player wishing to draw a card receives (securely) the information required to un-obscure the top card from the other players, and is thus able to "draw" the card by revealing it to themselves.

Obviously there are some details here that I've glossed over, but they are not germaine.

The Challenge: Extending to General Games

So, while it's interesting to think of this sort of primitive, or other primitives (passing a card, say) in isolation, it seems yet more interesting to try to come up with a complete and nicely composable set of primitives that can be used for general board and card games.

Another name for a nicely composable set of primitives is, of course, a language. So, the goal becomes: design a language that can be used (ideally, by a human without an advanced degree) to express the rules of any board or card game, in such a way that they can be interpreted (by a collection of computers -- one per player) to enforce these rules and play the described game.

If such a language existed, I could write a general board-game app using it; new games would be packages consisting of a rulebook (written in the proposed language), along with some UI scripts (which would handle displaying visible portions of the game state). The core of the app would be a rulebook interpreter, which would handle communicating state updates with other players' devices, and all the crypto to make sure that hidden state stayed appropriately hidden.

Language Features

What would a good language for describing board and card games look like? Well, my first impulse (mostly due to Chris' excellent ideas -- though I can't find the exact write-up I'm thinking of at the moment) is to work in a find-replace/linear logic setting. This means that we view the state of the game as consisting of some universe of things, and actions in the game involve consuming some of those things in order to produce other things.

This works well for basic turn-taking (a player's "ability to take a turn" is a thing that can be consumed by their turn). However, it doesn't always work at a high enough level to obscure the nifty crypto tricks we'd like to effectively "build in." Here's what I think needs to be added, either to the core language or as syntactic sugar:

• Visibility -- tokens should be able to be obscured, either from all players or from some players. They must be able to be revealed to some (or all) players. However, facts about obscured tokens should still persist (e.g. an obscured sapphire card in Scepter of Zavandor has an unknown actual value, but it is known to be a sapphire card).
• Ownership -- tokens should be able to be acted upon only by certain players. This is required to prevent arbitrary players for taking actions for other players. There needs to be a way to transfer ownership of tokens as a result of actions.
• Stacking -- this would just be "nice to have", except for...
• Shuffling -- stacks of obscured tokens should be able to be mixed, drawn from, cards added, etc; just as a real stack of cards (and hearkening to my initial motivation).
• Dice -- basically syntatic sugar on top of shuffling; but a common enough feature in games that it might be good to support it.
• Pattern Matching -- some sort of generalized reasoning so one doesn't have to, e.g., enumerate all possible melds in rummy.
• Integer Math -- gotta count victory points somehow.

One thing that can't be built in, given that I want all games to be able to work in a distributed way, is simultaneous player potential to act in a way that denies other players the ability to take the same action (e.g. calling "set" in Set). This is because collusion between players can mess up any consistent ordering.

What Next?

This is more of a problem statement than any sort of conclusion or proposal of a solution. I think the next step is to actually start to put together a syntax, and start trying to write some rulebooks. From there I can see how it is convenient to express ownership and visibility. Perhaps they are simply predicates that can come into existence through special rules and be consumed by others. Perhaps they involve moving tokens between different domains (with fixed ownership rules).

As always, feedback is welcome; I especially encourage those of you with PL background to cozy your brain up and figure out the language you would want to use to, e.g., write down the rulebook for Agricola.

Rktcouture

I spent today drawing costumes for the characters in Rktcr. There are finally 14 for each character, which is the target count I, somewhat arbitrarily, selected.

As you can see, there are some duplicates with more or less variation among them, some recolorings, and a few wild and crazy outfits for each character. I'm unsure if these are going to be the final costumes or if I will refine or replace some of them. However, just as with a piece of writing, it's good to have a real draft to work from instead of a blank page.

Collision in Rainbow

One of the things I'm revisiting in the C++ port of Rainbow is the way in which the bow fronts collide with level geometry, and how this splits up the fronts.

Splitting fronts is an important part of the game because smaller fronts are more maneuverable. However, in the HTML5 version of rainbow, the only way to split a front was to run it into something in a way that stopped one of the frequency bands. In the C++ port, I wanted to make it so that (with certain level geometry) one could actually split a front nondestructively.

The key to this is to use ray-vs-level tests to determine bow collision and convex-vs-level tests to figure out where to split the front. This way, frequency bands only crash if their centers intersect level geometry, but bow fronts can split gracefully around thin geometry. I finally added convex-convex collision today, so this splitting system is up and running.

Keeping Rktcr Honest

One of the important tenants of Rktcr is that -- while it is very hard -- it isn't impossible. So how do I keep the game possible, given the hundreds of generated worlds and tens of levels? As expected, the answer is extensive (semi-automatic) testing.

The core of this testing revolves around a database of paths -- recordings of player input that take the vehicle from portal [to gem] to portal, under different gravity directions and mirrorings, in each level. As of this writing, there are 1093 paths in the database. That's a lot of gameplay (in fact, it's all the gameplay I think is possible).

These paths have a few functions, but the most important is to make sure that any changes I make to the game don't (unintentionally) change what is possible in the game. I have a helper program test_paths that runs every path in the database and prints a hash of the game states along each path. The output of test_paths gets stored in my main git repository; before releasing a build (and, generally, after any change that I think might have messed with the physics), I run test_paths and compare to the stored output. If there are any differences, I know there is trouble afoot.

Of course, the paths aren't just for testing. They also get converted into par times for the levels; for this I have a pair of utility modes -- rktcr update-claims updates the par times to reflect the current paths database, while rktcr check-claims check the current par times against the paths database to make sure they are consistent (this comes in handy when I change level geometry or physics, invalidating existing paths, as it lets me know what paths I need to recreate).

Aside: why not distribute paths instead of par times? Philosophical reasons, mainly. I prefer that games not know the answers they are asking you to provide.

These par times, in turn, are used by the aptly named world_gen to generate worlds (groups of connected levels). Of course, I want to hedge against the possibility that a world becomes unwinnable owing to new paths and par times. For this, I have yet another utility program, world_test, which loads each world in turn and makes sure that it is solvable in a reasonable time, given the current par times.

And that's how I keep Rktcr honest.

Rktcr: Hunting a Box2D Glitch

I spent the afternoon hunting down the source of an unfortunate physics glitch in Rktcr. I think I've got it figured out, though I will say that the solution isn't entirely satisfactory. In this post I'll go through what I did to find the buggy code, what I think the problem was, and how I fixed it.

Isolating The Problem

This is what the physics glitch looked like in-game:

The problem seems to be collision between the central block (a dynamic body represented as a union of convex polygons) and the level geometry (represented as a chain of edges). Here's my first version of a trimmed-down test case:

The diamond falls, then glitches to the right suddenly. In this picture, and the following, you'll see lots of debug drawing being done. I think very visually, so having relevant data visualized helps.

At this point, I was thinking that the problem must have to do with my convex decomposition code splitting the colliding point of the polygon. However (thankfully) I made an even simpler test case that disproves that hypothesis:

Again, the blue wedge falls, touches the yellow platform, and glitches to the right. After one more test case revision (simplifying further, to a triangle), I was ready to move on.

It's hard to figure out just what the contact visualization is showing (and Box2D may create/destroy contacts during a solution step), so to get a better understanding of what was going on, I hacked a quick "disable all collisions" flag into the b2ContactListener Rktcr uses to filter contacts.

With collision resolution disabled, the reported contacts still looked decidedly odd. I was actually wondering if my visualization was working -- it really shouldn't be the case that the polygon is considered to be deeply penetrating the bottom edge of the yellow wedge. (The red "X" and edge indicates the colliding primitive.)

With this problem in mind, I dug into Box2D's source code. The relevant file turns out to be b2CollideEdge.cpp, which you might want to open in a new tab if you are code-minded.

Reading through the code, I caught a few things that appear to be bugs (or at least not very clean code), but also aren't responsible for the behavior I'm seeing. For sake of completeness (and to convey a bit of how grueling the slog was) I'll complain about them for a moment.

The first bit of sloppy code I noticed is that struct b2EPCollider contains an enum VertexType which is never used, other than as the type of two members -- m_type1 and m_type2 -- which are also never used. Probably remnants of a different strategy.

The next sloppy bit appears at lines 439-445; the function ComputeEdgeSeparation() is called to return an axis, and the type of the axis is checked. This is odd, because the type of the returned axis is always b2EPAxis::e_edgeA (see the function definition at line 620).

I also noticed that the constant "b2_maxManifoldPoints" is used when the number "2" would be more appropriate (e.g. line 561) -- as one always passes two points to the clipping functions, and they return up to two points. But I digress.

The Actual Problem

After muddling through the code for more time than I'd like to admit, I finally began to get a grasp on the problem. In essence, the logic of the m_front determination (lines 273-410) is flawed.

The picture above illustrates what the code is doing -- it's assigning the outside direction (and valid separating axis directions) of an edge based on the polygon's centroid. (I.e. centroids in the blue region will collide against the edge using the blue normal, and in the red region will use the red normal.)

I drew a picture like the above when reading the code, and I'm relatively sure it's what the person writing the code was thinking about. Unfortunately, it's flawed.

Essentially, when the adjacent edges in the chain turn sharply, the "front" region can encompass the back of the edge. This can become especially problematic when using an edge loop as the outside of a level, as in this test case:

This behaves very, very badly owing to the little jogs in the bottom left and right, which convince the collision algorithm that the polygon is colliding (deeply) with the bottom edge.

The Fix

I'd like to be able to say that I have an elegant fix for this problem, but I don't. Partly this is because I still don't have a handle on the problem the collision normal limiting scheme was attempting to solve. That said, just ignoring the adjacent edges -- that is, commenting out lines 273-410 and leaving the no-adjacent-verts code (lines 411-425) to sort things out -- seems to work just fine:

And, thankfully, this only invalidates a few of the level solutions, so I won't need to replay too many paths.