I was supposed to write a post mortem on Watexy-Java before this one but since the gadget has already been accepted over at the Google Wave Samples Gallery, it’s probably better that I write this one first.
How I came to write Pick-up Sticks
I’ve been thinking about making a game for Google Wave for some time now. Unfortunately, most of the other games in the samples gallery are turn-based and don’t really show how to handle the race conditions when multiple users try to modify the state at the same time. (Well, there is the Sudoku gadget, but it’s freaking huge! I mean, the state has to be stored in JSON for crying out loud!)
After a lot of thinking about what game would suit Google Wave’s environment, I suddenly remembered playing a PC version of Pick-up Sticks when I was a kid. It wasn’t turn-based or dexterity-based as its real life counterpart, but it allowed simultaneous play from multiple players while being completely asynchronous in nature, that is, unlike other real-time multiplayer games on the PC or consoles, it doesn’t need a server to keep the state consistent.
After some personal brainstorming, I sat down and started coding the gadget last Saturday.
My main reference source codes were the Magnetic Poetry gadget for the rectangles and state storage and the Connect 4 gadget for the player information. I’ve got the API Reference bookmarked, but I didn’t know about the Dev Guide until I was looking for info about dynamic height. (Note to Google: Link the dev guide below the gadget reference link at the sidebar of the Wave Dev Guide.)
My IDE for this project is Eclipse 3.5 (because I’m more comfortable with it) with Mercurial as my revision control.
Lessons Learned
Google Wave is a lot more asynchronous than you would imagine.
Quoting the gadget guide:
Not only is a Wave gadget’s state shared among all Wave participants, but in the typical case, any participant can change the gadget’s state at any time. If two users change values for different keys at the same time, the wave resolves it. However, if the value for the same key is changed, only one change goes through.
Translation: Don’t assume that everyone’s state is synchronized. One participant may have state X1 when he sends his updates to the wave while another participant may have state X2 while she sends her updates.
At first I thought that the setStateCallback() callback was partially synchronized i.e. it will run only once for all clients like some kind of server. Turns out I was wrong: that callback runs locally on each client every time a state update is received from the server. This means that the callback could operate on different inconsistent versions of the state, ruining any chances of using it as a synchronized function.
The solution to race conditions: avoid them.
Google Wave’s asynchronous mode screwed up my first implementation of scoring in Pick-up Sticks. Originally I stored the score inside state[participantId] and let the state callback handle the synchronization. Which, as I mentioned in the previous point, doesn’t work.
Here’s what happens:
- Participant A clicks a free stick.
- Gadget checks the state, sees it as a legal move, then sends
delta[A] = state[A] + 1. - At the same time, Participant B clicks the same free stick.
- Gadget checks the state, also sees it as a legal move (A’s state has not yet been received), then sends
delta[B] = state[B] + 1. - You now have two players credited on the same stick.
AFAIK, there’s really no way to synchronize the state to prevent such things from happening. My current approach simply made sure that the state was never inconsistent, even though the behavior might seem wrong. This makes use of a different state, state[picked_stickId], which stores the ID of the participant who picked the stick.
- Participant A clicks a free stick.
- Gadget checks the state, sees it as a legal move, then sends
delta[picked_x] = A. - At the same time, Participant B clicks the same free stick.
- Gadget checks the state, also sees it as a legal move, then sends
delta[picked_x] = B. - Both clients determine each participants score by checking the current state of
state[picked_xxx].
The case above looks like a case of Last In, First Out. It isn’t intuitive (it should be FIFO), but at least it produces decent consistent results regardless of the state.
For programmers, the terms “avoid race conditions” and “consistent results regardless of state” should point to one concept: Functional Programming.
In FP, you are not supposed to write transactions that rely on a proper sequence of events nor are you supposed to write code that produces a lot of side effects. Avoiding those two allow you to neatly deal with the synchronization problems in Google Wave Gadgets.
Here’s another example:
- Participant A clicks a free stick.
- Gadget checks the state, sees it as a legal move, then sends
delta[picked_x] = A. - At the same time, Participant B clicks the New Game button.
- Gadget clears and re-initializes the state and sends it as a
delta. - The delta is processed. New Game shows up with Participant A having one point already.
Solution: Make each game a different state altogether by appending a _gameId to all states.
The scenario is now:
- Participant A clicks a free stick.
- Gadget checks the state, sees it as a legal move, then sends
delta[picked_x_gameId] = A. - At the same time, Participant B clicks the New Game button.
- Gadget clears and re-initializes the state (generates a new gameId) and sends it as a
delta. - The delta is processed. Participant A’s move is ignored because it’s for a different game.
Never let the state change callback send a delta.
In other words, the function you send to wave.setStateCallback() should only display the current state of the gadget. Aside from preventing the obvious problem (infinite loops), this also prevents the gadget from making the state inconsistent.
A clear example would be adding gadget initialization code within the callback, as seen in Magnetic Poetry where the word locations are randomized if they aren’t already. The problem with this approach is that when the gadget is placed inside a wave with many participants, all of those participants will see that they meet the condition and each will send a delta initializing the gadget state.
This is the main reason why I removed the auto-initialize feature of Pick-up Sticks. Clicking “reset” (as it was called then) produced somewhat weird results. Blame the sucky broadband service here in the Philippines.
Random UI stuff
Sticks are thicker in Firefox than in Google Chrome. I’m not a web designer so I’m not really good at all this CSS crap.
Dynamic Height is your friend.
You can’t use terms with “@” symbols in them in jQuery selectors. So if you’re planning to set an element ID to the participant ID, you’ll have to rely on document.getElementById() to select them.
The Show Rules button was a last minute addition as I couldn’t find find space to add the rules. Then I thought about dialog boxes and jQuery UI.
States Used in the Game
Here’s the list of states used by the game:
- game_id – stores the ID of the current game. Reason explained above.
- time_[game ID] – stores the time when the game was started. Uses
wave.getTime(). - last_move_[game ID] – stores the time when the latest move was made. Used to determine how long it took to win the game. Also uses
wave.getTime(). - stick_[stick ID]_[game ID] – stores the state of individual sticks. Stick ID is from 0 to NUMBER_OF_STICKS. Format is “class|x|y|color” (style copied from Magnetic Poetry):
- class – both the orientation and the CSS class of the rectangle. Either “vertical” or “horizontal”.
- x – x-coordinate of the rectangle.
- y – y-coordinate of the rectangle.
- color – color of the rectangle. In the form “rgb(xxx, yyy, zzz)”.
- picked_[stick ID]_[game ID] – As mentioned above, stores the ID of the participant who picked the stick.
- mistakes_[participant Id]_[game ID] – Stores the number of mistakes a participant has made.
Not too complicated, just enough for the game to infer the entire state of the game. (Going the FP route also forces you to choose deriving the other states like score over storing them in state.)
Possible Future Features
Option to set the number of sticks, their sizes, and the size of the “board”, as well as the penalty for clicking a wrong stick are obvious future upgrades. They’re also pretty easy to implement. I think.
I’d also like to remove non-active participants from the list of participants. This would add another class of states, but at least it would make the playing field shorter in waves with a lot of participants.
UI Upgrade – The UI’s already clean, but I think there’s still a lot of room for improvement.
—
And that’s it for this post. Tomorrow’s post will be about my first Google Wave Robot, Watexy-Java.
