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.