Tuesday, March 20, 2012

Apple's turn-based game API (and what it needs)

As I have alluded in some blog post or other, I've been working on an iOS port of the board game Fealty, designed by R. Eric Reuss. For the project, I chose to use the "turn-based game" API which is built into iOS 5.

(This is part of the GameCenter toolkit, aka GameKit; but not the whole thing. The original GameKit, in iOS 4.1, supported achievements, leaderboards, and peer-to-peer games, but it didn't have a system for turn-taking games. That came along in iOS 5. Just to be clear about the background.)

Building a game using Apple's API was kind of an adventure, which I may document on this blog someday. But the thing is, Jmac and I spent 2005 and 2006 building a platform for these sorts of games, with servers and APIs and everything. It was called Volity; it was very clever. (We weren't nearly so clever about PR, which is why nobody used it, which is why we took it down a few years later, which is why I'm not linking to it.)

We are not Apple, but we are gamers, and our Volity system is more general than Apple's toolkit. It can be used for more kinds of games. This blog post is my attempt to rattle off the differences. Not for bragging rights (Volity is down today, GameCenter is up, end of story) but to point at features that GameKit will (I hope) adopt in future releases.

Here's the one-line summary:

Volity supports Rock-Paper-Scissors. GameKit doesn't.

Okay, it's implied by the name: Apple's API is for turn-based games. RPS doesn't involve taking turns! But we thought it was one of the fundamental game models of the world. (The others were Tic-Tac-Toe and Hearts.) If you can implement those, you should be able to implement all strategic games. Our system covered it. Apple's doesn't.

What's missing? Basically, Apple's turn-based API presumes that it's always the turn of exactly one player at a time. The game starts up with one player in the hot-seat, so to speak. That player gets to decide What Happens Next. The game absorbs that move, updates its state, and puts a new player in the hot-seat. Continue until game over. A player not in the hot-seat cannot affect the game at all (except by dropping out of the game entirely, which is always possible).

It's clear enough why Apple chose their model. It's simple, and it bypasses all synchronization questions: only one player has the write bit at a time. It requires Apple to run a game server, but the server doesn't have to run game-specific logic; it just coordinates the hot-seat. All of the game logic (deciding what happens and who plays next) runs on the device of the hot-seat player.

But RPS doesn't fit this model. Instead, both player decide on moves independently. The game doesn't care who moves first. When both moves have been submitted, the game absorbs them and decides the outcome.

To cope with this, Volity just didn't have a turn model at all. Players submit moves, which are valid or not. (We offered sample code for strict turn-based games, because it's a common case; but it wasn't wired into the platform at all.)

Of course you can do RPS in a turn-based way. You just keep the moves concealed. First it's Alice's turn to pick a move, then it's Bob's turn, then the game reveals the moves and decides the outcome.

But this doesn't generalize very well. Many board and card games have this sort of parallel-move structure. Consider Werewolf: a bunch of players sit around and vote. When votes reach a majority, the day is over. Or Charades/Pictionary variations: someone posts some kind of picture, and the first player to submit a guess gets a point (or not). It comes up in Fealty, for that matter -- all players choose a card to play and reveal it simultaneously. It's common; the underlying architecture should support it.

You may say, well, Werewolf is a real-time game -- it should be using the real-time GameKit API, not the turn-based one. My point is, Apple draws this sharp line between synchronous games (all players logged in at the same time, all players can move in parallel) and asynchronous (players can log in and out freely, but exactly one player has the hot-seat at a time). Real gaming doesn't have this distinction. Games have parallel phases, and one-at-a-time phases, and some games have both. Really, it's just players submitting moves. Any strategy game can be played "real time" or "by email". Werewolf or RPS by email is slow, but so is any other game-by-email.

(In case it's not clear, when I say "logged in", I mean "the app is running and authenticated with GameCenter". A player logs out either by exiting the app or sleeping the device.)

It's true that you need one device to be in charge of game state. You don't want the central server running game logic. That would involve Apple running third-party apps on their server, which is just asking for abuse. (Volity's solution was for the game designer to run his own server, but it could be a really simple server -- just a Perl or Python process hanging out on the Internet and processing game moves. It didn't have to coordinate player communication or anything like that. This was very clever, but I understand if Apple doesn't want to go there.)

This isn't a huge problem, though. You just pick one player to be the game logic hot-seat, and relay all moves to that player. It's a common enough model in real-time games. (Easier here, because latency can be seconds rather than milliseconds.) Occasionally a player logs out and you have to switch hot-seats, but that's fine. And you have to think about race conditions in the moves. If Alice keeps changing her mind about her RPS move, and sending updates to Bob's device, one of them might arrive after Bob has made a decision (and ended the game). None of these are difficult situations to deal with; you stick on some sequence numbers and allow a move invocation to return a "sorry, the game has moved on" error.

In Volity, we found that it all worked, as long as you remembered to keep the game UI clean. You select a move, push the "that's my move" button, and the game doesn't do anything special with the UI. Just keep everything in place. It doesn't even have to react to the "sorry" error response. When the game-logic sends a new move state, that's when the UI updates. (Again, a latency of a few seconds is fine.)

With a little bit of care, this can all be made a superset of the current GameKit functionality. That is: if the game sticks to a one-move-at-a-time model, the player hotseat is always the same as the logic hotseat, and it works the way it does today. If the game decides to permit more players to submit moves, you have the generalized model.

Timers and clocks and off-moves, oh my!

This architecture has other advantages. For example, you can build a chess clock: run out a timer on somebody else's turn. (Either to force them to forfeit, or just to skip their turn.) That's currently tricky: if the other player logs out during their turn, nothing can force their turn to end. If you allow the game-logic hot-seat to jump to whoever's currently logged in, the problem goes away.

(If nobody's logged in, then nothing can happen, but that's fine -- if nobody's logged in, nobody cares! The next time a player fires up the app, the game logic runs and all the necessary timeouts will be handled.)

This is a real-life issue. In the original iOS version of Ascension, if your opponent abandoned a game, your only choices were to keep the incomplete game on your list forever, or hit "Forfeit". Neither feels right. Recently, the designers added a game-clock on every game. Now, whoever abandons a game gets credited for forfeiting. This is a clear improvement, but you can't do it with GameKit as it stands today. (Ascension uses its own server and protocol, although it ties into GameCenter for authentication.)

Here's another advantage: since any player can submit a move at any time, you can implement chat! A chat message is a just a game move that doesn't update the game state (except for the chat display on each player's screen.) Not every game would want this, but it's important for Werewolf and other such party games.

You also want a feature like this for trading games, and games with trading components. (Settlers of Catan, M.U.L.E...)

As long as we're discussing Ascension...

Yes, Ascension is pretty much the gold standard for iOS turn-based games right now. As far as I'm concerned. (Ignore the awful menus for now.) So here are some features that GameKit should suck into its turn-based API:
  • Display a list of open invitations. (As opposed to silently matching people up and starting the game.)

I fire up the online game list. I see open games featuring "Steve621", "RoboMaster", and "OpenAsshole". Guess which one I'll decide not to game with. Even in a game system with no chat, I like having this social context.

Also, in a game with variations, I like being able to browse and see what variations people are offering to play. GameKit has a notion of game variations -- it only matches up games with identical playerGroup values -- but you have to pick one and post an invite. You can't browse, and you can't post a general invite (covering several game variations.)
  • Display whether your opponents are logged on or not.

Is that slowpoke contemplating a move, or disconnected from the network? Or contemplating a move in a different match? Ascension shows this as a three-value status indicator. It's good to know.
  • Allow spectators in public matches.

Ha! Gotcha! Ascension doesn't have this -- but Volity did. You could browse a list of in-progress matches (if they weren't marked private), and jump in on any of them. You got all the (public) game status updates. It was generally easy to program, because the UI code is already built to receive game status and display it; you just have to disable the move controls.

(I should probably make a reference here to Isotropic and its vast repository of online Dominion match records. Not exactly the same deal, but close.)

Okay, enough blathering. I'll probably think of two more feature as soon as I post this; that's always the way.

Comments imported from Gameshelf

Doodpants (Mar 20, 2012 at 11:26 PM):

All programming languages that are "Turing complete" are equivalent, in that anything that is computable in one of them is computable in all of them. Any calculation that can be performed can be implemented by a Turing complete programming language.

Similarly, any game engine that can implement Rock-Paper-Scissors, Tic-Tac-Toe, and Hearts, can implement any strategic game. Such a game engine is said to be "Volity complete".


Baf (Mar 21, 2012 at 2:29 AM):

One other major example of RPS-style parallel gameplay you don't mention: Diplomacy. I can see people pooh-poohing RPS and Werewolf, but Diplomacy is significant enough, both culturally and commercially, that it's hard to see the API's failure to support its central mechanic as anything other than a real failure.

Christopher Cotton (Mar 22, 2012 at 9:46 PM):

Excellent article. We were looking at using the GameCenter turn based API for our game, but I don't think we can. The biggest reason is that we really want to have a "turns take 24 hours" And if someone doesn't submit a turn in that time, they get the default orders for their turn. This way, the game can continue even with someone who is taking forever, or even those who "time out" and stop playing. 1 person not playing won't ruin an 8 player game.

Jota (Mar 23, 2012 at 6:29 PM):

Even Monopoly would suffer if you couldn't offer deals to other players outside of your turn.

No comments:

Post a Comment