1. icon for News
  2. icon for TCHOW

News

Showing posts with label coding. Show all posts
Showing posts with label coding. Show all posts

Tuesday, August 11, 2020

Interactive vs Generational Collaboration

My research group has been writing a lot of papers recently. Like any reasonable set of CS folks, we use LaTeX as our typesetting tool of choice. Of course, like any modern set of collaborators, we also all want to be editing the paper at the same time, changing words as others are writing, and completing each-others sentences.

To accomplish this, we have generally turned to Overleaf, which -- like LaTeX itself -- isn't a great solution to the problem, but it is the best solution we have. One of the interesting things about Overleaf is that it supports two completely different models of collaboration, which -- for the purposes of this post and without reference to any external sources -- I'll term "interactive" and "generational".

Interactive Collaboration

Interactive collaboration models a shared workspace. All changes are made simultaneously and with fine-grained (real-time) synchronization. Interactive collaboration seems to work best when edit operations are "local" -- generally modeled by granting participants a notion of a cursor or selection around which their edits are centered.

Interactive collaboration doesn't work very well with dependent or global edits (e.g., trying to make an overarching change to the order of sections). And -- as often happens on Overleaf -- it really doesn't work well when the synchronization system begins to bog down.

Generational Collaboration

Generational collaboration models... well, I'm not exactly sure what it models. Perhaps a series of independent artifacts, individually crafted, but with reference to other previously created artifacts? Regardless, changes are made individually, and merged non-real-time into a final artifact.

Generational collaboration works well for changes that don't overlap and (thus) can be merged automatically. It is, thus, a natural fit for global but distinct changes (e.g., changing all references to a figure; doing a global re-ordering of paragraphs in a the "Results" section while another collaborator works on the "Introduction" section).

Further, generational collaboration can operate in a decentralized and disconnected way, which are distinct advantages, especially on a paper deadline when nobody has time to wait on a slow server. (Or, e.g., on an airplane.)

Combining the Models

So, how do we combine the models to get the benefits of both?

Overleaf's approach is to support the generational collaboration model via git push/pull support, but to require that no interactive edits happen between a git pull and the subsequent git push. This, effectively, makes generational collaboration lower priority than interactive, making it incredibly awkward to leverage this model while others are using the interactive model.

My preference here would, instead, be to start with a decentralized generational model and build in some notion of interactivity. I tend to like disconnected/disjoint tools, so perhaps the way to do this is to have the notion of a multiplayer editor protocol that can work (optionally, in parallel) with a git repository.

Here's a sketch of how that might work:

When a multiplayer (text?) editor opens a file, it would check in the same folder (and parent folders) for a .multiplayer subdirectory and contained config file. (Similar to how git looks for a .git subdirectory.)

The .multiplayer config file would contain either the address of a responsible server and a project token to identify the project to that server, or a list of peers to contact directly. Any multiplayer-capable editor would -- after prompting the user -- get the list of peers to coordinate editing with (possibly via connecting to a server, possibly via direct peer entries). The server could also handle STUN to make peer-peer communications easier.

Regardless, said multiplayer-capable editor would now be connected to a peer cloud and could use peer-to-peer multicast techniques to keep the document synchronized, publish cursor state, and so on.

So that takes care of the interactive collaboration. How about the generational part? We could make it so the .multiplayer directory contains a reference to the most recent point in shared edit history at which an editor had synchronized to the peer cloud. If -- when your multiplayer editor connects -- your current file matches the recent version in the .multiplayer directory, then all changes between that version and the current peer cloud version could be automatically applied.

If, on the other hand, your current file differs from the reference version in the .multiplayer directory, then there's a generational change to merge. This is the classic "three-way merge" problem that (e.g.) git solves reasonably well. In the interactive setting, it might even make sense to allow you to request others stop for a second and help with the merge.

Of course, if your text editor of choice doesn't support multiplayer, you could still edit single-player and use a command-line utility to deal with the three-way merges. (Perhaps with a "hang on, let's do the merge together everyone" option to avoid the same problem that overleaf has.)

So, Who's Building It?

Perhaps the most surprising thing for me in my (scant) research around this topic is that nobody has built an interoperable interactive collaboration system that actually supports, e.g., cross-editor cursor sharing; at least not one that is still in action today (I seem to recall that google docs at some point had an API with cursors).

Perhaps the notion of a cursor is so editor-specific that it takes special sauce to do it. Perhaps the idea that you need to run a server makes people want to lock in users to finance said server. And perhaps I just haven't looked hard enough.

In the latter case, let me know! I'd love to try out something different with my group when we next have a big crop of papers ready to go.

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.

Friday, July 19, 2013

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.

Monday, July 15, 2013

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.

Thursday, July 11, 2013

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.

Tuesday, July 2, 2013

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.

Sunday, May 26, 2013

Why, cl.exe, Why?

When compiling C++ projects (e.g. Rktcr), I use different compilers on different platforms: Microsoft's cl.exe from Visual Studio Express Edition on Windows, Apple's clang++ from XCode on OSX, and g++ from the GCC on Linux. (These also use different versions of the C++ Standard Library, for added variability.)

This is great for catching errors in my code, as I get three different sets of static checks and three sets of design decisions (for those memory bugs that "just happen to work" on one system or another). But it also means I get exposed to a fair amount of compiler (and system library) quirkiness.

Today, I'm going to talk about one of the odder bits of behavior I've seen out of cl.exe (Version 17.00.60315.1 for x86 from Visual Studio 2012 Update 2).

I ran across this a few months back, but have been lax in posting because I didn't have any sort of CSS styling set up for posting code in news.tchow.com ; a situation which I have partially rectified (no syntax highlighting or fancy line numbers; sorry).

The Code

Apologies about the spacing in this code. Blogger apparently converts tabs to single spaces. For reference, using spaces to indent code is wrong.

#include <iostream>

template< int N >
struct TrivialTemplate {
    int val;
    typedef TrivialTemplate< N > type;
};

struct NoTemplate {
    int val;
};

//Consider different types of Coord:
#if COORD==1
typedef NoTemplate Coord; //<-- (1)
#elif COORD==2
typedef TrivialTemplate< 27 > Coord; //<-- (2)
#elif COORD==3
typedef TrivialTemplate< 27 >::type Coord; //<-- (3)
#endif

struct Pt {
    union {
        Coord arr[2];
        struct {
            Coord x;
            Coord y;
        };
    };
};

int main(int, char **) {
    Pt pt;
    pt.x.val = 12;
    std::cout << pt.arr[0].val << std::endl;
    return 0;
}

This C++ code defines type Pt, which makes use of a struct wrapped in a union to allow individual coordinate access as pt.x and pt.y, and easy coordinate indexing with pt.arr[i]. (This method can be extended to allow synonyms like pt.x and pt.r and subvectors like pt.xy or pt.yz. I use it in my Vector.hpp.)

The Problem

Notice that the lines marked (1), (2), and (3) all define Coord to be the same type -- a struct with a single int as a member -- but in slightly different ways.

So, with the line marked (1), things compile fine:

c:\Users\ix\Code\rktcr>cl /nologo /EHsc /W3 /WX /DCOORD=1 weird_template.cpp
weird_template.cpp

c:\Users\ix\Code\rktcr>weird_template.exe
12

c:\Users\ix\Code\rktcr>

If I use line (2), I get some weirdness:

c:\Users\ix\Code\rktcr>cl /nologo /EHsc /W3 /WX /DCOORD=2 weird_template.cpp
weird_template.cpp
weird_template.cpp(20) : error C2621: member 'Pt::arr' of union 'Pt::<unnamed-tag>' has copy constructor
weird_template.cpp(31) : error C2039: 'arr' : is not a member of 'Pt'
        weird_template.cpp(18) : see declaration of 'Pt'
weird_template.cpp(31) : error C2228: left of '.val' must have class/struct/union

So, what happened? Well, cl.exe has (presumably) synthesized a copy constructor for Pt::arr -- which, after some typedef expansion -- is an array of TrivialTemplate< 27 >. Now, having non-trivial constructors and destructors for data in a union is problematic, because the whole point of a union is that its members overlap in memory. However, it's also odd that a copy constructor would be synthesized -- after all, TrivialTemplate< 27 > is functionally identical to NoTemplate, and no constructor was synthesized there.

Indeed, neither g++ or clang++ have any problems compiling this code.

But here's where it gets really weird. If I compile with the line marked (3) active -- that is, if we talk about TrivialTemplate< 27 > using a typedef it contains for itself, one would expect the same error.

Instead, it just works fine:

c:\Users\ix\Code\rktcr>cl /nologo /EHsc /W3 /WX /DCOORD=3 weird_template.cpp
weird_template.cpp

c:\Users\ix\Code\rktcr>weird_template.exe
12

c:\Users\ix\Code\rktcr>

So, where does that leave me? Spending time writing workarounds -- in this case, my planar map code (which uses templated classes wrapping integers to make sure it isn't going to overflow) now has a fair number of uses of the somewhat odd-looking BitsInt< N >::self.

This is certainly a lot nicer than the llvm-gcc bug that incorrectly passed unions to functions (effectively reordering function parameters). That bug led to me abandoning Apple-supplied compilers on OSX until clang was mature enough.