Calculator/spreadsheet tool for Acme

I got Plan9 from User Space and started messing with it in the hopes of getting a nice toolbench going with Acme. Since I wrote Ober, I've been interested in this idea. Now, I'll probably rewrite it in Go. I'm wondering if I can just use named pipes to mimic what Acme does with its 9p interface.

Anyway, I wrote a simplified version of the Calc tool I wrote for Ober and I put it, here. The calc tool searches an Acme window for variables and their values and some code at the bottom. Then, it executes the code, sending the variables and values to its stdin. The code is expected to output new values for some of the variables. Calc parses the output and replaces the new values into the window. I'm also including two wrappers that make it easy to write calc scripts in rc or Go, so you can say something like this:

Bob's age=30, he is yearsleft=0 years away from retirement (calc).

#!/usr/bin/env calcgo

yearsleft = 55 - age

If you middle-click "calc" in the text, it will update the window to show yearsleft=25.

The Philosopher's Stone

I've been searching for the "Philosopher's Stone" of role playing for years -- a role playing system that combines traditional role playing with the collaborative story telling of Universalis. I think the Blood Red Sands system might allow this. By replacing the coins of Universalis with dice, BRS introduces relative differences between traits, an element of risk into contesting for narrative control, and a competitive framework for play. I think this difference can allow it to support traditional role playing better than Universalis.

That's how the document for the new game I'm working on starts. I found Ralph Mazza's Blood Red Sands about 5 weeks ago, when I checked out the Ramshead Publishing site, to see if there was anything new going on. Wow, was there ever! Blood Red Sands is a highly stylized, competitive role playing/story telling game about heroes and their ordeals as they strive to confront the evil, despotic Witch King in a blasted land called Abalahn. My summary of Blood Red Sands is here and the play test rules are here. There are some discussions about BRS on Story-Games.com.

Universalis is really a different type of game (which is why it was named "most innovative indie game" of 2002). It's not really a role playing game; it's a story telling game. Theory From the Closet interviews Mike Holmes (coauthor) and he talks quite a bit about Universalis here. A later podcast interviews Ralph Mazza about Blood Red Sands, Universalis, and other things here.

I started playing Universalis in December, 2005. In December, 2007, I combined Universalis with FATE and PDQ in a campaign we ran for over a year. We started every session with a few Universalis scenes (usually 20-40 minutes of play), then we played a mashup of PDQ and FATE, incorporating the new information from the Universalis scenes, and we ended a lot of the sessions with Universalis, too. It worked really well. During the Universalis sessions, there were a few ground-rules (enforced by Universalis gimmicks), but other than that, the players had free-reign with the story. They could define NPC motivations, stage events that took place "meanwhile", etc. I was tag-team GMing with a friend and we had to deal with all of the curves the players threw at us -- the players introduced some things into the story we really hadn't thought of.

Universalis is also how we did all of our cut-scenes. What made it radically different from the way MOST GMs do their cut-scenes is that the players could take over in mid-scene and change things. You can look at a bunch of the Universalis logs here.

I loved the Universalis integration so much, that I've been searching for "clean" system ever since; one that allows story telling and role playing all the time. I tried F#, which is a great game (you should check it out). It comes close, but it doesn't quite do what I want. Then I saw Blood Red Sands.

In Blood Red Sands, one player plays their "hero" character, going through ordeals on the way to confronting the Witch King, while the other each play a "faction" which may be aligned with the Witch King, opposed, or neutral. BRS is played on two levels at the same time: the story level, where the characters' loyalties are defined by the ordeal and the game level, where the players are all competing, even though their characters may be allies in the story. This can lead to some interesting story twists and it can support behavior like Pippin's in The Lord of the Rings (check this post, for example). BRS is a great game and I consider the underlying system to be the next generation of Universalis. Also, I think it can lend itself well to traditional role playing, in which every player gets to role play their character during a session.

So, my entry in the mix, The Philosopher's Stone. It uses the system from Blood Red Sands, so please by Blood Red Sands when it comes out, but it packages it in a different framework that (hopefully) supports traditional role playing. In The Philosopher's Stone, as in Blood Red Sands, no player is the designated Narrator (i.e. GM) for the whole session -- players trade off acting as the Narrator and they can even "steal" the position of Narrator (just like in Blood Red Sands).

The players cooperate to make the story within a mission/act framework where they define the mission and acts as well as objectives for the group of player characters. A player can counter an objective and steal the victory points for himself. Of course, the other players will try to stop him.

The BRS system underneath TPS contains two key mechanisms to limit the power of the current Narrator: challenges and contests. Any player can challenge the "fiction" that a Narrator composes -- the rationalization that supports a mechanic. This can't directly prevent a Narrator from using a mechanic, but it can force him to reframe the rationalization and may lead him to try a different tack. A contest allows a player to attempt to take over the position as Narrator, preempting what the Narrator was doing. I think these two mechanisms combine well to keep the player who is the Narrator from being "too harsh" on the other players.

One thing that is very different from other role playing games is that in TPS, players control "story components" in addition to their characters, which are NPCs, monsters, beasts, traps, hazards, etc. In fact, there are no NPC or other direct "actors" in the story that are not controlled by one of the players. This means that even in a scene without any player characters, the players are still involved, because at least some of the players will have story components present at the scene. When orcs squabble over who gets to eat a hobbit, it's different players controlling the orcs and one of those players might also have the hobbit in question as their player character (or it could be Neanderthals arguing over a Cro-Magnon captive or aliens planning to torture an earth man).

I don't think that controlling story components in addition to their characters will make it difficult for people to play. I think there will be scenes with only story components present, scenes with only characters present and scenes with both. In scenes with both that involve conflict, players will be attacking other players' characters and story components, so I think there's a clear objective.

So, that's the idea. We'll see if it works.

Xus Rsync/Bittorrent/Git approach

Approach

I started working on my file sharing approach. Sharing will not involve deltas or packs, just chunks, by Git id. The idea is to share Git commits, with all of their associated tree and blob objects. They'll be shared using a manifest for each commit that exhaustively lists all of the chunks in that commit. A manifest will be a binary XML document (using fastinfoset, same as Xus uses for its protocol), since that's a pretty efficient binary serialization format (using BERencoding for numbers in a lot of places and whatnot) and then using another XML doc to list chunks for the manifest:

• A commit manifest contains the serialized commit data, the commit id, and a list of tree object ids/crcs and blob ids with blob chunk ids/crcs
• A commit manifest chunk list contains a list of chunks for the commit manifest file, since a commit manifest file could get large

I'll probably use an extra branch to store the chunks that a peer currently has for that branch. When it gets new chunks, it can store them in its chunk-branch for that Git branch (probably named [branch]-chunks). Git will properly reuse shared chunks because that's what Git does.

A word about chunks. Git stores its data compressed, but to get good chunks, we have to uncompress the data first and then break it into chunks. This is so that we can effectively scavenge the Git repository for chunks so that we can avoid downloading the ones we already have, ala rsync.

How rsync works

The brilliant idea of rsync is that you can cheaply compute a "rolling crc" as you "slide a window" down a file, byte-by-byte. An example of this type of crc is the standard shift-xor hash function a lot of people use for strings. For each byte in the string, shift the crc up one bit and xor the byte in. Assuming you are using a 32-bit hash, the hash is only "good" for 32 bytes of a string.

Here's an implementation of the Rsync chunk finder with a very simplistic rolling crc function:

import java.io.FileInputStream
import scala.collection.mutable.ArrayBuffer
import java.security.MessageDigest

object Rsync {
 def use(test: Boolean)(block: => Any) {
  if (test) {
   block
  } else {
   println("Usage: Findit [-hash string] | [-find file crc sha-1]")
   System.exit(1)
  }
 }
 
 def pad(n: BigInt, width: Int) = {
  val s = n.toString(16)

  if (s.length >= width) {
   s
  } else {
   ("%0"+(width - s.length)+"d").format(0)+s
  }
 }
 
 def next(hash: Long, number: Int) = {
  var p = 0
  var n = number

  for (i <- 1 to 8) {
   p ^= n
   n >>= 1
  }
  (hash << 1) | (p & 1)
 }

 def sha(msg: String) = {
  val digest = MessageDigest.getInstance("SHA1")
  val i = BigInt(digest.digest(msg.getBytes))

  digest.reset
  i
 }
 
 def find(file: String, crcIn: Long, shaIn: BigInt, len: Int): Int = {
  val input = new FileInputStream(file)
  var crc = 0L
  val buf = ArrayBuffer[Char]()
  var offset = -1
  var mask = (1 << len) - 1

  while (true) {
   val c = input.read()

   if (c == -1) {
    input.close
    return -1
   } else {
    offset += 1
    crc = next(crc, c)
    buf.append(c.asInstanceOf[Char])
    if (buf.length > len) buf.remove(0)
    if ((crc & mask) == crcIn && sha(buf.mkString) == shaIn) {
     input.close
     return offset
    }
   }
  }
  return -1
 }
 
 def main(args: Array[String]) {
  use(args.length > 0) {
   args(0) match {
   case "-hash" => use(args.length == 2)(println("args: -find file "+pad(BigInt(args(1).foldLeft(0L)(next(_, _))), 16)+" "+pad(sha(args(1)), 40)+" "+args(1).length))
   case "-find" => use(args.length == 5)(println("offset: "+find(args(1), BigInt(args(2), 16).longValue, BigInt(args(3), 16), args(4).toInt)))
   }
  }
 }
}

This is more or less what Xus will use. As you can see, you can efficiently update the crc a byte at a time, so it's quick to locate a chunk. When you have several chunks, just use a set of CRCs. As you scan the file, check each crc to see if it's in the set.

So after Xus gets a manifest it has to download all of the chunks it doesn't have. Here's how it will work:

1. Check the Git repository for the file id. If it's in there, no need to download
2. Check the Git repository for a previous version of that file (we can eventually include extra information in the manifest if the creator's Git detected a rename). If there is a previous version, scavenge the previous version for chunks using the rsync algorithm
3. If there are any outstanding chunks we need to download, request them from the DHT

Requesting from the DHT

When a peer needs to download a chunk, we use the topic as a DHT, backed by the master peer's storage:

1. Use a DHT message to send a chunk request to the peer with ID nearest the chunk's ID
2. If the peer does not have the chunk, it requests it from a topic master using a mini topic master DHT to distribute the load
3. Once the peer has the chunk, it connects to the requesting peer and transfers the chunk to it

Connecting to a Peer

Some peers may not be able to accept connections. This interferes with chunk sending requests. Xus has two ways to deal with this problem:

1. The preferred way is the connection service: if one peer can receive connections but the other cannot, the peer which can receive connections can delegate a message to the other peer to connect back to it
2. If neither peer can receive connections, they can delegate all of their messages through the topic master

So, there you have a fairly detailed idea of how I'm implementing the Xus file sharing service.

Story telling in role playing games

I play a lot of indie RPGs, like Spirit of the Century and Swashbucklers of the Seven Skies, but for the past couple months, we've been retrying D&D 4e (and I'll be using "DM" below a lot of times in the generic sense). I tried it for 5 months in 2008, running a Keep on the Shadowfell adventure. I have to say that I think that was a mistake for Wizards. It's a dungeon. A lot of the monsters aren't intelligent (rats, oozes, skeletons, zombies). Etc. It ran like a 5 month long miniatures game. Maybe it was me, I don't know.

Nevertheless, we're giving 4e another go (this time, I even get to be a player!) D&D 4e has some great ideas and it has great resources for DMs. Since 2005, I've used techniques described in the "Group Storytelling" in the DMG2. You can find a lot of helpful hints for DMs out there on the net and I haven't read nearly all of them, but maybe I use some novel techniques. Some of these techniques were new to the veteran DMs and RPG designers I've spoken with. I created/independently discovered/borrowed/stole several techniques specifically to prevent wasting the work I do as a DM/story writer.

A friend of mine ran an adventure for us a while back and after we failed a search check in one room, I noticed him file away a sheet on which he had written a LOT of text. I asked him later if we were supposed to see that only if we succeeded in that roll, thus wasting all of that work. He said "yes." I thought it was a shame that he did all of that work and we never got to see it.

Usually, I have a campaign story arc, with subarcs for sections of the story. For each subarc (i.e. adventure), I do something kind of like what the DMG2 describes in the "Branching" section. Rather than make a tree with possibly dead scenes, I write a LINEAR story line which is really just a list of scenes, usually using an outline format in a google spreadsheet (this is great for collaborative DMing, by the way). This list represents the order in which I THINK the players are going to experience the scenes. I almost never have any "dead" scenes in my stories -- I work too hard coming up with ideas and fleshing them out to allow them to be skipped :).

Players almost never make the decisions I'm expecting them to make, so the actual order of scenes usually ends up different from the way I wrote it, with from-the-hip scenes inserted in the list as well, along with alterations to the original scenes (I usually change the spreadsheet as I run the adventure). To prevent the players from skipping over scenes and information that I've worked so hard to produce, I use a few techniques that they didn't mention in the branching section.

First, a few observations to keep in mind:

1. The players don't have a lot of information until the DM reveals it; they don't know what's behind every door or around every corner
2. The DM can ask a player to make a roll without telling them why; "make a perception roll"

If the players skip over a scene, there are a few techniques I use to "reclaim" the scene so I can present it to them later on:

1. if it is an appointment that they missed, make it a "chance meeting" later
2. if it was with a particular person who is out of the story now, reassign it to another person or use a messenger to convey the information
3. make a new scene on-the-fly that accomplishes the same goals

Sometimes the story requires a prerequisite before an event can happen, like searching, detecting an ambush, etc. Prerequisites can be a way to put a certain character in the spotlight, like requiring a certain ritual, a certain skill, a bloodline, a race, etc. Lock-and-key scenarios that require successful rolling can be a bit dicey (sorry :D). You don't want the players to blow a roll and fail to see the cool document with the burnt edges that you antiqued by heating up paper soaked with lemon juice! The "Avoiding Dead Branches" section in the DMG2 presents two alternatives for "fake" branches; i.e. situations that look like a branch, but where there is no actual chance of failure. The alternatives are setting the DC of the check to 1 and "dropping the pretense" by just telling the players they succeeded (i.e. no roll). Here are some techniques I use to make sure that the players get the information or have the experience that I put so much work into, but still "keep the pretense"...

Ball and cups

Ever see that magic trick, where the magician shuffles around 3 cups and you can't tell which cup has the ball under it? The first two cups you look at never have the ball; it's always in the third cup. That's because the magician has the ball in his hand.

When the players are searching for something which could be anywhere, sometimes I assign it to "the third place they check". So after they look in two empty rooms, the third room will have what they're looking for, regardless of what the map looks like.

Suppose the players are looking for clues. Prepare several clues for them to find and have them gain the clues on successful search rolls in a specific order, regardless of where they are when they actually do the searching. So they can search 5 rooms in a house, find two clues and then search the alley to find the third clue. If they succeed in each of the first 3 rooms in the house, they get the clues then. If they blow all of the rolls in the house and the alley, they can discover the clues in some other location entirely.

Well, aren't you clever!

Suppose you want to have the characters spot an ambush in a jungle way before it happens so they can ambush the ambushers. The D&D game mechanics represent keen senses as a high perception skill value. Call for a perception roll from the group and if they blow it, give them a "soft ball" random encounter. Wash-rinse-repeat until they get a successful roll. When they do succeed, run the "real" encounter where they get to surprise the ambushers as they are preparing the ambush. Instead of just declaring that the characters have surprised the ambushers, they surprise them "because" they succeeded on a perception roll.

Reality is how you perceive it

OK, this one is from Donjon. Sometimes, the players search for traps and none of the chests/doors/cabinets in the whole building actually have traps. If they ask to check for traps, sometimes you'll want to put a trap there anyway. If they blow the roll, it can explode, if they make it, they can disarm it. When the characters use their skills, the player is actually requesting some spot light time for their character. Give it to them.

Use rsync with Xus file sharing?

I'm wondering if it would be a good thing to use a variant of the rsync algorithm with Xus file transfer. This would help save a lot of bandwidth for large files that only have small changes. One example is Sauerbraten maps, which can be 2M or more (after compression). When you move a tree, only a small part of the map file is changed, but without rsync behavior, pushing an update requires transferring the whole file.

At this point, Plexus breaks files into chunks that are 50K (if I remember correctly) and keys them by SHA-1 hashes. If we include rsync's rolling CRC with the chunk ID, that would be enough (I think) for a peer to determine whether it could reuse a chunk from its current file and avoid downloading a chunk. I'll have to check on rsync to see its default chunk size. We chose 50K based on tuning with Pastry and Xus' behavior will probably be very different.

Xus file sharing

It's been a long time since my last post; various RL intrusions encroached on Xus. Now I'm starting the file sharing piece. I'm basing it on what I did in Plexus, but starting right away with Git integration instead of putting it off, since that seems to be a better way to actually have Git integration :).

Xus has kind of a weird profile for a p2p system. It's made to handle a mass of small clusters, rather than a giant, monolithic cloud. It's really based on the needs of Plexus, but I suspect other systems out there can benefit from it. In a monolithic p2p storage system like bittorrent or FreePastry's PAST, the cloud can (theoretically) be so large that the data can "live in the cloud". In a game like Plexus (or Sauerbraten), however, the clusters are small and may often drop to 0 users (like when the players for a particular world are asleep), so there needs to be a way to restore cluster state (so a world with no players is still up-to-date when a player joins, even if they weren't around recently).

The most straightforward way I could think of to accomplish this is just to use a Git repository for the Xus file cache and mirror it to a remote Git repository for backup/restore. When a topic space master boots a topic space, it can pull from a remote git repository to restore the state. To avoid a single point of failure, the owners can push to more than one designated repository. The DHT portion of the repository is only useful for peers that are connected, since the DHT expands and contracts, causing chunks to be copied around over time.

Storage:

1. each resource is tracked with a tag: an outer directory containing chunk-list file and a subdirectory with standard names
2. creator sends packed delta to topic owner
3. owner pushes delta to remote Git repository
4. owner returns signatures for the chunks, etc. to creator
5. creator stores chunks, etc. in the DHT.
6. creator gets an event when storage process is complete

Retrieval:

1. request tag from owner, which responds with ID of chunk-list file
2. retrieve chunk-list from DHT (which delegates to owner if chunk not in cache)
3. retrieve chunks from DHT (possibly delegating to owner to fill cache)
4. requester gets an event when the retrieval process is complete

Several owners is a good thing in this model, since they back the DHT cache.

So, that's the idea. I decided I'm going to include the source to jgit and its dependencies (jsch and jzlib) with this. Requiring on a properly installed command-line Git is just too much work to make developers do (or force their users to do). Requiring developers to download, test, and package a compatible version of JGit wouldn't be nice either. So I have some bloat now. I really don't see the file sharing part as being quite so optional, anyway. From my experience, nontrivial p2p apps tend toward bit torrent the same way most apps tend toward email clients (that's someone's law; maybe I'll get a comment with a citation for it).