2013-06-21

Super Foul Egg for iPad Released

Finally, after months of procrastination:

This one got straight into the App Store.

Obvious changes from the OSX version are:

  • Two player mode removed (still got a bug in the garbage transmission code);
  • Controls designed for the iPad touch screen;
  • Controls displayed via icons on the menu screens;
  • Pause and exit buttons whist in-game.

Less obvious changes are:

  • Multithreaded AI;
  • All code refactored.

I’ll open up the source code soon.

Give the game a try and let me know what you think!

EDIT:

Source code can be found here:

Apologies for its current scrappiness; adding networking support has meant changes all over the place. I remember reading an article years ago by a developer who suggested that networking should be built into a game from the start rather than added later as it’s a huge pain. I definitely agree with him.

2013-01-02

SFE Network Updates

In the last SFE update post I described an approach to choosing eggs by a voting system rather than “a pseudorandom progression for the sequence of eggs”; however, as every developer should know, random number generators are almost all pseudorandom. If each client starts with the same seed and only uses the random number generator for generating new egg colours, all peers in the game should agree as to the order of eggs.

The real problem is that the rand() function might be called for egg generation and for other things, meaning the generators will be out of step. I’ve stripped out egg voting and replaced it with the MTRandom library, which wraps the Mersenne Twister random number generation algorithm in a class. All peers vote for the random seed at the start of each game (and each round) and the vote from the peer with the highest ID is chosen. The egg factory sets up an internal MTRandom instance and the egg sequences are synchronised automatically with no further network traffic.

The next problem to solve was the issue of minor timing differences between peers throwing out synchronisation. Suppose an egg lands on one player’s screen. The next egg appears at the top of the grid, and the other player throws across some garbage eggs. Those garbage eggs will have to wait until the current eggs land before they can be added to the grid. Meanwhile, on the networked view of that player on another iPad, the other player throws across some garbage before the egg lands. Network lag meant that the “drop egg” message was delayed by a fraction of a second. The egg lands, the garbage appears, and the two representations of that player’s grid disagree entirely about the current state of the game.

My fix for this was to hold up the appearance of the next egg until all of the networked representations of a grid are ready. Once the current egg pair lands the grid sends a “waiting” message and enters a wait state, in which they can receive garbage eggs, until all peers announce that they are waiting. At that point they all add new eggs and switch back to the active state.

The final problem is rather more tricky: sometimes egg movement messages can be processed out of sequence. All of the egg movement messages are sent by the player’s grid instance. Moving, rotating or dropping an egg results in a message being sent to all peers in the network. Once received, all of the messages are dispatched to the “network controller” instance (where they are queued in order) except for the “egg drop” message, which is sent directly to the appropriate grid. This means that an “egg drop” message could be sent after a “rotate” message, but would end up being processed before the “rotate” message. To fix this I’ll either have to send the “egg drop” message to the controller and treat it as a “down” button press, or I’ll have to scrap the entire concept of a networked controller and create a duplicate grid class that excises most of the game logic and relies on network messages instead. I’m hoping that the controller option works.

The to-do list isn’t growing any shorter. I still need to:

  • Create a peer chooser (though it’s possible that I might be able to use an Apple-provided class to do that for me);
  • Provide a way to quit the current game when paused;
  • Replace the “press a key” bitmap with a “tap to continue” bitmap;
  • Figure out why taps on the “press a key” screen are intermittently detected;
  • Quit the game automatically when a networked peer disconnects.

Once all of that’s done I’ll sign up for the iOS App Store and get a release out. Next steps will be to merge the changes into the OSX version of the game (to allow for Mac/iPad networked games) and increase the number of players that can participate in a game from 2 to 8.

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.

2012-11-20

Super Foul Egg iPad Progress

Hardware test successful! SFE runs on both the standard and retina iPads. Now that I’ve switched it to using standard UIGestureRecognizers instead of trying to roll my own in the Cocos2D touches callbacks, the control system works flawlessly.

Once I’d succeeding in getting the controls working, I was very concerned about how usable and intuitive they’d be. My first few games saw me lose miserably to the easiest AI setting, but after a dozen games I progressed to the point where I can occasionally beat the “hard” setting. I’m nowhere near as good with the touchscreen as I am with the cursors (where I can sometimes beat the “insane” AI), but it proves that the touchscreen can work as an input device for this kind of game without resorting to an onscreen joypad.

Needless to say, I’m planning to buy an iCade 8-bitty joypad and get it working with that.

2012-11-17

Super Foul Egg - iPad

Soon:

Here’s what’s left to do:

  • Pause/exit game;
  • Replace any bitmaps that mention keys with bitmaps that mention touches;
  • Test it on real hardware.

I don’t currently have an iPad to test on. I had a quick try on the office iPad and discovered that the initial control system I’d written was unresponsive and unusable, so I’ve just finished a re-write of that.

I had two options for the control system. The obvious solution was to use an on-screen joypad. However, I detest iOS games that use an on-screen joypad to such a degree that I don’t even bother trying them. A more interesting solution was to try and work with the touchscreen instead of working against it and use gestures.

This is what I’ve implemented:

  • Tap with one finger to rotate the current shape clockwise;
  • Tap with two fingers to rotate the current shape anticlockwise;
  • Swipe downwards with two fingers to auto-drop the current shape (I had to concede that the hated auto-drop makes sense in the context of an iPad);
  • Touch and drag with one finger to move the current shape left and right (it follows the movements of the finger).

These gestures can be performed anywhere on the screen, which means the player’s fingers won’t get in the way of the action.

Unfortunately, I had to remove the two-player mode in order to accommodate this control system. I’m hoping that I’ll get around to using GameKit to allow multiplayer on several devices. Perhaps I’ll get an 8-player mode implemented.

Getting SFE working on a new platform has allowed me to look over the code again. Back in August 2011 I said this about the codebase:

My code probably looks hideous to experienced Objective-C coders as I’ve trampled conventions all over the place.

Just over a year later, I’m pleased to say that I agree with myself. The SFE code is pretty nasty in places. Here are a few mistakes I’ve spotted in the last few minutes:

  • Using #define instead of constants.

C guys use #define. C++ guys use consts. I went with #define because objc is clearly C-with-classes, but consts are better style.

  • Using blocks instead of protocols and delegates.

Blocks are cool! They’re also finicky when doing manual memory management and are an exceptionally good way to end up with cyclic references. For the most part I used blocks to separate out the game engine from the I/O code, which made the code vaguely MVC-like. Great idea (and wonderful for getting the game working on the iPad) but using delegates and protocols would have simplified things immensely and been more conventional.

  • Not cleaning up references after releasing objects.

Try doing something to the live block references in a Grid object when it doesn’t have live blocks. Ooops: crash.

  • Not following standard Objective-C naming conventions.

Pretty much everything should have been prefixed with “SZ” but wasn’t.

  • Following standard Objective-C naming conventions.

The enum names follow Apple’s official enum naming style (aside from the missing two character prefix), but then Apple have two styles and the official style sucks. It’s impossible to use autocompletion to determine the contents of an enum if the values are named “NSUTF16BigEndianStringEncoding” instead of “NSStringEncodingUTF16BigEndian”.

  • Using “SomeType* variable” instead of “SomeType *variable”.

Nitpicking, I know. I think the former makes the most sense semantically - the full type definition is “a pointer to SomeType”, so the asterisk is grouped with the type name - and is what I use in C/C++. However, I’ve been following Apple guidelines and now use the latter in objc. Apple don’t always follow this themselves, though. The fact that their templates don’t consistently place the opening brackets for a code block in the same place irritates me, too.

  • Protocol names.

“ControllerProtocol”: It’s like backwards Hungarian notation.

  • Fear of singletons.

It’s widely acknowledged that singletons are a Bad Pattern. They can’t be tested! They can’t be mocked! Every time you use a singleton a child dies! Look through most of my code and I’m pretty sure you’ll find that I try to avoid singletons wherever possible. Part of this was a response to the irrational level of hate levelled at the pattern, and part of it was due to the number of issues that singletons cause when working on web applications in .NET (hint: static variables have an application-level scope, not a client-level scope).

On the other hand, singletons are used extensively in Apple’s objc frameworks, and I now use them everywhere too. TDD crowd be damned. The “BlockFactory” could easily be a singleton, accessed via [SZBlockFactory sharedFactory], instead of being injected into every class that needs it like I’m writing some kind of enterprisey abomination.

  • “SZPoint”.

I’m hoping that this was a holdovee from the C++ version, because I can’t think of a valid reason why I’d create a class with identical functionality to CGPoint.

  • Reference counting.

I haven’t seen any examples yet, but this sentence from the August blogpost sounds extremely dumb:

For the most part, I’ve used what Objective-C calls “weak references” - I’ve got pointers to objects without retaining them, the same as I would in C++.

I might try to tidy some of this mess up. On the other hand, it ain’t broken…

2012-09-22

Super Foul Egg 1.4 Rejected

Another rejection! This time the reviewer changed the left and right directions to the same key via the prefs menu and rejected the game because the left and right directions are mapped to the same key.

Really, Apple? Really?

EDIT: Apple reviewer makes idiot developer eat own words when the developer finds obvious bug. Resubmitting it now. Will it get rejected because two directions can be assigned to the same key? Or will it get rejected because it doesn’t remove the borked prefs file saved by the last version?

2012-09-19

Super Foul Egg Resubmitted

Half an hour or so of hacking gave me this solution:

Whenever an unrecognised key is pressed, the above popup appears listing the current controls. Pressing a known key causes the popup to disappear.

The reviewer had a legitimate complaint - the controls aren’t obvious. Hopefully the ability to change keys via the Preferences menu option mitigates that, and the new popup should encourage players to have their fingers on the correct keys when the game starts up.

I’ve submitted SFE 1.4 to Apple. What’s infuriating is that the update will no doubt languish in their approval queue for the next month.

2012-09-19

Super Foul Egg 1.3 Rejected

After a month of waiting for the Apple guys to get their act together, SFE 1.3 finally got rejected today. It seems that I was unfortunate enough to land the only person to have never played the Game Boy version of Tetris as a reviewer. He couldn’t figure out how to use the menu system and got stuck on the game type selection screen.

I’m trying to think of how to make it not just idiot-proof, but Apple-reviewer proof. If I change the menu so that any key press other than the movement keys jumps straight to the next screen I can’t imagine that even the most ham-fisted oik could fail to figure it out.

2012-09-01

Super Foul Egg Updates

Getting updates into the App Store is a far simpler process than getting the first version ready, mainly because I’ve already gone through the tedious process of getting the various certificates installed. Updates still seem to take the same amount of time to get reviewed as new apps, though: SFE 1.3 has been in their queue for 9 days so far. I’m hoping that competition from Windows 8 and its app store will force Apple to streamline their approval process. If Microsoft could guarantee that they would approve apps and have them ready for sale within two days I’d bet that developers would abandon Apple in droves.

I currently have two SFE updates queued up. 1.3 replaces TTF with BMFont labels on the menu screen, making it usable on the retina MacBook Pro. It also has sound effects when choosing a menu item. 1.4 (not yet with Apple, but you can grab the sourcecode and compile it yourself if you want a sneak preview) includes the following changes:

  • Replaced the “Controls” window with a preferences panel allowing keys to be redefined;
  • All game settings - keys, game type, speed, height, etc - are saved;
  • AI is multithreaded for a small speed boost.

The multithreading is a neat (if obscure) change. The AI works by simulating all possible moves when it is given a new shape to play with, which means it must run 24 simulations (4 rotations multiplied by 6 positions) of a complete move (move shape right 3 times, rotate twice, drop 12 times, remove chains, drop eggs, remove chains, etc). Each simulation produces a single value that represents the score for that move. This is obviously a lengthy calculation but is something that could very easily be done in parallel, so I’ve used dispatch_apply() from Grand Central Dispatch to run the entire 24-iteration loop in one go.