2012-12-07

Voting For Eggs

The iOS version of Super Foul Egg is still underway. Since the last post I’ve fixed all of the coding problems I identified and added the pause function, but there’s no visible button for that yet. There’s still no exit game function and I haven’t yet replaced the “press any key” bitmaps, either.

Instead, I’ve been working on adding back in a feature I removed: two-player mode. Where’s the fun in SFE if you can’t play against a real person? I took out the feature because it’s far to complicated to try and track and differentiate between two users interacting with the same touchscreen. To add it back in I’ve been playing with Gamekit.

Gamekit is a very simple networking framework that allows iOS devices to communicate over Bluetooth or wifi. It announces the availability of a peer via Bonjour, automatically assembles a network of peers with no user intervention, and then allows multicast messaging between them. Having written a network library for games I know how tricky it is, and I’m impressed at how easy Gamekit is to use.

Although Gamekit takes care of the messaging system admirably, there’s still the problem of co-ordinating the behaviour of multiple instances of the same game across a network. The control system was easy:

  • Every time the player moves an egg, transmit the move over the network;
  • Receive the message on the peer;
  • Send the move as notification to the notification centre;
  • Receive the notification in the grid representing the remote player;
  • Perform the move.

I disabled the drop timer for the second player’s grid and rely on a “drop egg” network message, which keeps the two devices in sync. Fortunately Gamekit has a messaging mode that is guaranteed to transmit and receive messages in the correct order.

The difficult part has been choosing the next pair of eggs. Eggs are chosen randomly. How can two devices be made to choose the same random pair of eggs?

I came up with a few solutions for this. Disregarding the option of using a pseudorandom progression for the sequence of eggs (which would have removed the need for any network communication but would also have made the game extremely predictable), the first was to allow network peers to choose their own eggs. Every time they choose an egg, they send a message to the network: “I chose red”. All peers add a red egg to their next-egg lists. They only need to choose an egg when they reach the end of the next-egg list.

This would work in most situations, but it falls apart if two or more peers try to choose an egg at the same time. Peer 1 would choose red; peer 2 would choose blue. Peer 1 and peer 2 now disagree on what the next egg will be. Other peers will have either red or blue as their next egg depending on which message reached them first.

Despite the race condition this is a temptingly simple approach, but the most likely time for a disagreement to occur is when the game first starts up and all peers choose their first set of eggs. Everyone disagrees; the game is a shambles.

The second approach was to designate one of the peers as a server and the others as its clients. Any time a client requires an egg it sends a message to the server: “I need a new egg”. The server responds to all of its clients: “The next egg is red”. All peers add a red egg to their lists. If the server needs a new egg it just broadcasts the next-egg message without being prompted.

One handy feature of Gamekit is the way it automatically chooses a randomised ID for all peers in the network. The server can be chosen by ordering all peer IDs numerically and selecting either the first or last in the list. As long as all peers use the same algorithm, no network traffic is required to select a server.

However, I was dissuaded from using this approach because it requires two sets of code for all network-related functionality. One set has to perform server actions, whilst the other has to perform client actions. It would be better if all network participants were peers and ran the same code.

Thinking about the problem some more led me to the phrase “reaching consensus in a distributed system”, which resonated with my distributed systems class at university: This is a solved problem. I need to implement a voting system.

The algorithm works like this:

  • Peer 1 needs a new egg.
  • Peer 1 sends out a message to all peers: “I vote for a red egg for vote 1”.
  • Peer 2 receives the message.
  • Peer 2 responds to all peers with the message: “I vote for a blue egg for vote 1”.
  • Peer 3 receives the message.
  • Peer 3 responds to all peers with the message: “I vote for a red egg for vote 1”.

As each peer votes, all participants in the network store each peer’s vote along with the peer ID and the vote number. Once the number of votes collected for that vote number is equal to the number of peers, all peers have voted. All peers use the same algorithm for selecting the “winning” vote. The network arrives at consensus.

It’s important to note that each peer will only vote on a given vote number once. Otherwise, each peer would respond to each incoming message, resulting in an never-ending, exponential cascade of voting.

To choose the winning vote, I initially planned to sum the votes for each egg colour and select the colour with the most votes. In the case of a tie, I’d choose the vote from the peer with the highest ID. I then realised that I could greatly simplify the algorithm by using the American approach to an election: ignore the popular vote and just use the single vote from the peer with the highest ID. At last I have a system that works.

Next steps are to ensure that the next-egg list is never empty. If the list is empty gameplay has to halt to allow voting to take place, which can take a few seconds. Other than that, I’m going to simplify the garbage egg placement algorithm. It currently fills up the columns with the fewest eggs in first, which is predictable across all peers, but given two columns with the same number of eggs it will randomly choose one of the options. I could implement a messaging system for garbage egg placement, but it is far easier to change the algorithm to be deterministic when running a network game.