Update On Box2D Performance vs. libGDX

A while back I posted a quick performance comparison between my Monkey port of Box2D and libGDX's JNI version. At the time the libGDX version was about twice as fast.

Since then I've done a bit of optimisation work and I thought it would be worth posting to note that I've just uploaded 1.0.12 of the port and to update the figures.

The Monkey performance on the same domino stack benchmark from the previous post is now ~88ms on average. Assuming that libGDX's Box2D implementation remains the same at ~75ms that means the performance gap has narrowed from 100% to under 20%. The variability of performance with the Monkey version is still higher, with spikes to >160ms where libGDX keeps it under 100ms but it's a much closer race now. Note that this is just a headline figure on a very collision/contact intensive example that is intentionally chosen for being slow on Android, performance in general is likely indistinguishable for the most part.

The performance improvements are significant enough to enable Monkey devs to target lower powered devices and/or create more physics intensive games. So, if you shelved something because the framerate wasn't quite there then it might be worth grabbing the newer module version and taking another look.

Games and the Mundane

Yesterday I had a Twitter back and forth with Rob Fearon, that started from this tweet where he implied that "the mundane" is less represented in games than it was in the past.

 Feel free to have a read of the conversation but the summary is that I suggested that there are a fair number of games that deal in mundane things and we then swapped Spectrum game references in an effort to hash out what boundaries are being drawn around "mundane". It's probably a deathly dull conversation to most but for Twitter it's not bad. Anyway, Rob used the conversation to gather fuel for a subsequent blog post, which you can find here.

To be honest the initial tweet is the sort of thing that I can't leave alone. Firstly, pretty much any claim that games don't do something or include something is usually hard to defend. There are so many games out there that the claim is generally coming from a place of ignorance about what exists or is excluding categories of games for some unspoken reason. Secondly, it smelled a bit of the kind of snobbery that you often hear from people who eschew genre fiction because only writing about normality is literature (unless its "magical realism"). I doubted that Rob meant the second thing but the button was pressed anyway.

Having read the post I'm further convinced that any disagreement was primarily around what Rob meant by mundane in the first place. I took it to mean games that put the player in unexceptional roles/jobs/circumstances, which the casual game market has many examples of. Rob appears to to dismiss games like Diner Dash because they offer aspirational fantasies of achieving great success in these roles. However, leaving that aside, Rob's post really seems to be talking about several different themes that involve mundanity but aren't just about representing the mundane.

So, because I'm a bit like that, I've broken down the mundane elements that Rob fondly remembers from the 80s and blathered at length about each one below.

Street-level Politics

Rob uses the word politics on its own but I think he's specifically referring to the space where policy meets the man in the street and not politics from the perspective of the powerful. Presumably it's obvious that high-level geopolitics remains a fascination in games of war, conquest and competition for resources and games like SimCity let people scratch their top-down urban planning and social-engineering itches in ways that exceed what the 80s could offer.

Taking the "politics in the small" reading I can see why it might seem true that there was more of it in games back then. A game like Hampstead, where you play an unemployed person attempting to climb the social ladder, seems overtly political in a way that's rare now. Indeed if the benchmark is that sort of spotlighted social commentary then I'd probably agree, but for fairly specific environmental reasons.

The enticing intro to Hampstead

I think a big part of it isn't about games but about a general shift in the political climate. Current domestic politics are low-contrast compared to the UK in the early 80s. Back then the class divides were more sharply felt, the left/right political divide was far wider and mass unemployment was a shocking new development rather than just part of the scenery. (Also both Rob and I were considerably younger and stuff just feels more vivid in your youth anyway). As such it was a more attractive and tractable target than we have now. The political references in games of the time mirrored the knockabout anti-establishment wave of alternative comedy and the likes of Spitting Image. This stuff was in mainstream games because it was in mainstream culture and games could at least emulate the broad-stroke cartoonish veneer of that output.

Spitting Image from 1984. Completely impenetrable if you weren't there.

In the round though I'm not sure I agree that current games feature a relative lack of that sort of politics. For a start, politics is implicit in any game that purports to represent social environments and that's something that games continue to try to do with increasing fidelity. When GTA includes homeless NPCs that beg for money, that's politics right there. Of course, the idea that it's a deep commentary on the homeless problem is silly, but I would argue that GTA with its satirical talk radio stations and narratives on crime, race relations, corruption etc. can lay claim to carrying more political weight than Monty Mole or Hampstead even if its scope means that the politics isn't front and centre.

The Everyman Character.

With politics out of the way so is much of my disagreement with what Rob says in his post. When he talks about the loss of the mundane player character I think he's broadly right. Rob's examples of Trashman and Technician Ted and the ones I mentioned in the Twitter conversation: Tapper, Paperboy, Pedro, Wally Week, are just the tip of the iceberg. The early 80s game scene featured a mad explosion of character IP and a huge number of those were working class/average blokes (Yes, pretty much all blokes I'm afraid. Let's deal with one axis of representation at a time.).

Maybe we can thank Mario (not that Mario's character stuck with "just a plumber") for popularising this character theme in games or maybe Mario's success was a result of pre-existing cultural desire that the others were also trying to tap into. Looking at popular culture outside of games I tend to think the latter is true. From Charlie Chaplin through George Formby and Coronation Street to Boys from the Blackstuff (forgive the UK-centric examples, but we are talking about the UK games scene primarily), Joe and Jemima Ordinary had characters to connect with. They were commercially successful ventures too, particularly in post WWII cinema and TV. There's no reason why someone designing a game character wouldn't try to target the same market.

George Formby, singing about real work.

It's not an argument without wrinkles though. Average people are in modern commercial games. The ubiquitous modern realistic military combat games that get so much stick often feature soldiers that are average, working class guys. I'm sure Rob would counter that a soldier in a combat situation is outside of "mundane" but then how is he wrapping that same concept around the surreal craziness of Technician Ted's factory? Another criticism might be that such games tend to exaggerate the influence of the player (you won WWII!) and imbue them with super-powers such as the ability to absorb multiple bullet wounds. I'd accept that but I think several games have made efforts to portray the limited agency of a soldier in an overall conflict and their mortality within the bounds of creating a playable game.

But I said I'd stopped disagreeing with Rob, right? Well, to disentangle this I think we have to put soldiers (and cops, secret service etc.) to one side as characters. They're average people in mundane jobs but the situations they're trained to deal with aren't what we deal with every day (hopefully). I'd still argue that games can treat them in ways that embrace their mundane nature but can't deny that it is more often abandoned in favour of allowing players to raise the character's inherent combat agency to the point of situational mastery.

Just an average guy doing my job.

We also have to separate mundane themes and characters from mundane representations and scenarios. As Rob says, you can put Tapper in space with aliens at the tables but he's still just serving drinks. To coin an example from fiction: Arthur Dent doesn't become extraordinary by being beamed into space -- he remains resolutely ordinary while the universe does extraordinary things to him.

So what we're talking about is not just an ordinariness of character that makes them empathetic but an ordinariness of skills, goals and possible rewards. I still baulk at Rob including the goal/ability of saving a small business in the realm of hyper-agency but I understand the line even if I disagree about where it should be drawn. I also agree that it's a line that modern games mostly don't recognise at all.

Unfortunately it's not difficult to see why that's the case. There are huge trade-offs with this sort of ordinary. There's a big audience that enjoys the power fantasies and escapism available in games. From a marketing perspective it's more attractive to insert little touches of romance or an emotional backstory to excuse or soften an escapist fantasy character than it is to abandon the fantasy. I doubt that Max Payne started with a desire to make a game about losing a child and had the slow-mo gun-fighting added after. We shouldn't confuse which part is decoration and which part is the game.

It seems unlikely to me that we'll see a resurgence of games about mechanics, postmen, plasterers and shelf-stackers struggling to achieve little more than getting to the end of another day. For the most part I don't think it's much of a loss either. A good 70+% of those games in the 80s were just Jet Set Willy remixes, including Technician Ted. I'd certainly like to see more ordinariness in games but I can't pretend that much of the 80s output could be used as an example of how to do it.

Skool Daze - better than Rob's examples.

Just as an aside, my pick for the 1984 example of how great a game can be made out of this viewpoint would be Skool Daze. It puts the player in the shoes of an ordinary character (Eric, a schoolboy),  a very ordinary but punishing environment over which they have little control (a school), gives them a very small goal (steal your report card) and then gives them just enough agency to have fun and play out minor fantasies of bad behaviour.

Un-Mundaning

Final bit, honest.

Rob brings up Frankie Goes To Hollywood. With this one I think he's off on another tangent. Now we're not talking about games including mundane reflections of reality, we're talking about games taking the mundane and making it not mundane.

When other forms do this sort of thing it can run towards escapist fantasy or towards a kind of celebratory metaphor. I imagine that Rob's really on about the celebratory end, taking the weirdness and magic of ordinary human life and expressing it as "real" magic in the game world. To be honest, I don't much care either way, I just like the idea of mixing humdrum reality with fantasy and think games are very well placed to do it. Fantasy, magical realism and dream logic are all workable within games.

So I'd like more of that, definitely. Do I think there was more of it in the 80s? Yep. However, much as with the other facets of mundane, I don't think it was really done with any great artistic intent or merit for the most part. When Matthew Smith put man-sized perambulating toilets and hovering telephones into Manic Miner the scene was kind of set for normal things to behave in very abnormal ways. FGTH was a standout game in its use of the banal mixed with surreal imagery but it stood out because nearly everything else in that vein consisted of toothbrushes bouncing around in yet another arcade adventure platformer.

Pyjamarama - Self-Inception

Besides FGTH I have to put forward Pyjamarama as an example of un-mundaning done well and in a way that could be relevant today. In it you play Wally Week's disembodied dream spirit in his nightmare. You have to explore a house and work out how to get your body to wake up so you can get to your job on time, which you hate.


*I'm not ignoring the fact that plenty of us live unable to achieve such aspirations. I'm just saying that being the owner-operator of a coffee shop isn't a life beyond the realms of everyday reality.

F2P, IAP, Micro-transactions and DLC

The news that EA is planning to put micro-transactions into their games has brought the simmering discussion surrounding IAP back to a boil. For many it represents a new offensive on the "core" gaming territory by a business model that had been mostly confined to mobile and Facebook casual.

I think gamers are right to be very suspicious of how this will play out. If this review of the EA published Real Racing 3 on iOS is anything to go by then they're willing to try putting frequent and high tariffs on gameplay. On the other hand Real Racing 3 is still a free-to-play iOS game. How they'll incorporate micro-transactions into PC or mainstream console titles has yet to be seen.

There is a strong argument that consumers have a choice to buy or not buy whatever is offered  (as voiced by CliffyB while I was writing this post). I can't deny the truth in that but it doesn't mitigate the valid concerns of fans of existing games titles. EA owns many well-loved brands and fans of those brands are now faced with the possibility that future iterations will be warped to conform to a business model that needs to generate ongoing payments. It's not just a matter of the games being less fun, or even more expensive, it's the possibility that the very nature of those franchises will be changed. SimCity, Command and Conquer or Mirror's Edge wrapped round a micro-transaction model may well not be SimCity, C&C or Mirror's Edge as we know them. There won't be a choice to buy or not buy the games we want -- those games will simply not exist any more.

Maybe, Just Maybe, It'll Be Okay

There is, as always, a middle ground. It's the zone in which we can imagine games that incorporate micro-transactions in non-destructive ways. Unfortunately, a position that recognises the danger in applying free-to-play models to the traditional games market but also holds that it's not uniformly evil is too grey to be attractive. Nuanced opinions don't get heard much in a debate that exists between corporate spin-drone press-releases and hyperbolic teenaged gamers in comment sections.

Despite the lack of vocal recognition the reality is that IAP just means "stuff" you can buy from within the game. DLC is just "stuff" you can buy to add to your existing game whether from inside or outside that game. "Micro-transactions" is just code for virtual currency to buy "stuff"*. F2P just means it's free to install and play at least some of it or for some period of time and you'll have to buy "stuff" to play more.

None of these things are inherently evil concepts. My local coffee shop is F2P in that you can walk in and hang around for free. They have IAP coffee and cakes and a micro-transaction currency involving gift vouchers and reward stamps. If I stretch a bit I can even say they have DLC ground coffee that you can order for use at home. I doubt that many people would compare them to Hitler for doing any of that.

The debate needs to move from blanket "this thing good"/"this thing bad" to being about the specific behaviours. People need to express what is not okay and what is okay. Not all DLC is horse armour. Not all F2P is Real Racing 3.

If EA sells me a full-price Tomb Raider and then offers extra hats, clothes, hairstyles for more further payment then that's fine. If they want to sell me ammo or "Lara Energy" needed to play freely then it's not. I'll be honest, I probably won't buy the hats but some people will and I don't mind them being available.

If EA sells me a full-price Need For Speed and then offers extra cars, paint jobs, decals for further payment then that's fine. If they only offer the "best" car as an added extra then it's not. It's really, really not okay to do this if a game contains multiplayer competitive elements.

If EA sells me a full-price Mirror's Edge and then offers extra missions for further payment that's fine. If those missions are actually required to bring a narrative close to the story in the game I paid for then it's not.

If EA creates a franchise specifically for F2P then I reserve the right to hate it, but it's really no skin off my nose. If they take a franchise that I enjoy and subvert its nature to fit F2P then they're not just making something I dislike but they're destroying something I liked. It's not illegal but certainly a dick move.

If EA creates micro-transactions that are proxy subscription fees for ongoing services, that's fine by me. You can justify selling the ability to play if the game has a significant ongoing running cost. Justification goes out of the window if you've manufactured the need for that cost (always-connected DRM, unwanted social/multiplayer features). 

If EA introduces micro-transactions to create an on-ramp between demo/piracy and  full purchase then that could be acceptable. I'm okay with free to install and pay-to-play purchases for single-player games as long as I can get off the treadmill with a single purchase (infinite coins/fuel/whatever) that is in line with traditional game pricing. We also need to be able to release games from IAP treadmills in instances where the payment mechanism ceases to exist.

But Probably Not

I'm afraid that my instinct and experience tells me that we're in for a bad time no matter what arguments are made and heard. I foresee the inclusion of payment models that don't seek to increase revenue by upselling or extending the market but rather by getting people to pay more for less. I foresee micro-transactions shoe-horned into games and game designs broken to include them. I foresee a proliferation of virtual currencies as consumer "company scrip" and we'll have to collect EAbucks, Ubibeans, and Acticredits to play their games.

Ultimately it's just too tempting for publishers to ignore. F2P/IAP aren't just the kind of buzzwords that business types feel they must add to their CV. The massive numbers coming out of the top mobile freemium games are real. If you add to that the possibility that micro-transactions can be used to open a new front in the digital shop-front battle (Can't spend $EA on non-EA titles and no-one else gets a cut) then it becomes inevitable that the big boys are going to try it on.

I also frankly doubt that it's going to go away. Even if gamers vote with their wallets as CliffyB suggests and we see some big franchise releases bomb due to bad micro-transaction implementation once the systems are in place they will be used. We can only hope that market forces result in tolerable usage to most of us.

If there's a silver lining to this looming cloud it's that, by moving to payment models that are unpopular with large numbers of gamers, the big players will make space for others to offer alternatives. "Pay once, play forever" might just become a selling point in itself that indies can exploit.


*Micro-transactions were once touted as a mechanism for monetising web content and literally meant "small value transactions". The idea was that you could charge 0.5c or whatever for reading a blog post. These transactions were enabled via virtual currency (to avoid the overhead of real currency transactions). The meaning in games has taken great liberties with the interpretation of "small value" and now it really just means the use of in-game currency to buy stuff, whether for 10c or $10.

Game Camera Work

My on-off dev schedule has been on again recently and with it I may as well resurrect this neglected blog space.

I did a bit of work on the camera for one of my game projects and thought the progression of the solution lent itself to a post. Then I remembered that I'd been wanting to try my hand at creating one of those dev video things and so I tried that.

The creation of the video was a whole adventure in finding a workable capture solution, a working microphone, working video-editing software and getting my mouth to produce coherent sentences but I'll save you the long story.

Here's the video:

Monkey's Garbage Collection on iOS

Not long ago I finally got around to buying the bits needed for iOS builds: a new iPod Touch, a ridiculously priced block of white plastic that runs OSX and Apple's 99 USD blessing to run my own code on the device I've already paid for. Besides the money there was a certain cost in time and frustration getting everything up-to-date and working but it is done and I can now build my project and run it on my iPod.

Well I guess this is enough to let you in the club.

I never really swallowed Monkey's promise of write-once and run pretty much anywhere so I wasn't expecting completely smooth sailing. Sure enough there have been a few wrinkles to iron out: graphics differences, an odd lack of response to touch events and performance issues - including the garbage collection (or GC for short) wrinkle that this post is about.

Some time ago someone else tested my Box2D port on their iOS device and posted on the Monkey forums that they were seeing poor frame-rates. I've not heard anything since but it stuck in my mind as a concern so I was specifically looking for performance issues when I first tried my game on my iPod. Happily the performance looked fine. I played a level with a reasonable number of entities in it and it seemed to be keeping a steady 30fps. Then I restarted the level a few times and everything got slower. A few more restarts and it was barely responding to input.

I'm Not The Only Problem Here

It was clear that I had a resource leak that was somehow holding onto game data between level restarts. What was unclear was why this was only happening on iOS or at least only causing a slow-down on iOS. An internal game bug that collected actual processing elements, such as holding on to multiple active instances of the physics simulation, shouldn't only occur on iOS so it must be something else. It seemed as good a time as any to take a look at the XCode profiler so I fired it up and re-ran my test of restarting a level several times. Not much digging was required. The game was spending increasing amounts of time in the garbage collection code marking objects.

Here's a quick explanation of that last sentence. Monkey is a garbage collected language. That means that if you create an object you don't need to explicitly free or destroy that object when you're done with it. When the reference goes out of scope or otherwise becomes unreachable by your code Monkey makes the promise that the memory it uses will be recovered.

Now several of Monkey's target languages/platforms provide their own garbage collection implementations: Java (Android), Javascript (HTML5), C# (XNA) and Flash. When building to those targets that's what your game will use. The C++ targets (GLFW and iOS) have no native GC implementation and so one is provided in the Monkey code itself. All well and good.

Garbage collectors come in many different flavours but Monkey's C++ GC is essentially a mark and sweep collector. What this means is that when the collector runs it first traverses the tree of object references in your application and "marks" those that are reachable, then it reclaims the memory or "sweeps" those that weren't marked. What the profiler was telling me was that my game was spending more and more time doing that "marking" process.

As I said, it was clear that I had a resource leak and it didn't take me long to track that down. The leak was resulting from a failure to remove one of my UI elements from a list of mouse event listeners. As the list existed for the lifetime of the game the UI element and everything attached to it remained reachable and so were never collected.

It's Already Spotless. You Can Stop Cleaning Now.

Problem solved? Only sort of. Once I'd fixed the leak I re-ran the test on my ipod and was unhappy to see that the marking process was still the biggest single chunk of time per frame. In fact I built a test that did nothing more than create and hold a bunch of objects and show the time spent in marking -- it seems that there's an approximate cost of approx 1ms per 10,000 live objects per frame on my 4th gen iPod. That's not talking about collecting objects that have been discarded, that's the standing cost of just having those objects. On every frame the Monkey code walks the tree of objects and marks them all and it takes that long to do it. Here's a graph of the average per frame cost:

Click to embiggen.

Why is this a problem? It's a problem because this behaviour is different from all the other GC implementations. Let's say you create a million map cell objects in your game and then don't allocate anything else while your game is running. If you do that on any of the other targets the GC cost will probably be zero. On iOS it would be crippling (on GFLW desktop hardware the marking process is generally so fast that it's not a problem, but it's just a question of scale, not principle).

How many objects are likely to be in a game? It totally depends but it's really not that difficult to get up there. My game is just a physics platformer with quite small levels and it runs up 20-30 thousand live objects in some situations. I could certainly do things to reduce that number, but it's kind of strange that I would have to do so just to bend to the behaviour of the garbage collector.

Trying To Be Helpful But Just Getting In The Way?

There is an argument for aggressive garbage collection and it's that you minimise the pauses seen in other garbage collectors. If you look at Android, for example, it's not unusual to see the garbage collector stop your application for a hundred milliseconds or more while collections take place. In theory, if you collect frequently, the interruptions will be smaller and more consistent and avoid pauses that are noticeable to the user.

The theory breaks down when I look at the iOS numbers, however:

Firstly, the load isn't that smooth. One frame might take a 1ms hit, another will take a 7ms hit. If you're close to the frame limit then that's easily enough variance to give you issues.

Secondly, and more importantly, the behaviour means that you can't escape the GC cost and if you're trying to do so on other platforms then you may well be making things worse on iOS. With the other GC implementations you can minimise their impact by not allocating objects during your game loop. On iOS that doesn't matter because you pay for every object you have live. What that means is that object pooling or caching strategies will benefit you on Android and actively work against you on iOS. This is not a recipe for cross-platform consistency.

What To Do?

Option one is to accept the situation and reduce your numbers of objects. If you can do that then it's not a bad thing to do in general, it just won't gain you much outside of iOS. There comes a point when avoiding using objects becomes an unreasonable expectation in an object-oriented language though.

Option two is to start performing surgery on the Monkey garbage collector. Clearly this is way over the line of abstracted cross-platform development but needs must when the devil drives and all that. An obvious change to make is simply to add a memory allocation trigger to the GC process: "Don't do anything unless x objects or x kilobytes of memory have been allocated". This would make it behave somewhat more like the standard Java collector in that you can expect strategies like object pooling to reduce garbage collector activity rather than increase it.

That memory allocation trigger could be extended all the way to "Don't do anything unless a memory allocation fails" but doing so would guarantee expensive collections and wouldn't work with the way that the GC currently attempts to spread the cost over a number of frames.

What I'll probably do is wait until the game is pretty much complete and then see if I can reduce allocations/tweak a collection trigger so that levels can be played through without a collection. Then I can add a call to force a collection to occur when the game is transitioning to the results screen or somewhere else where the player won't be bothered by a frame-rate hiccup.

If/when I settle on something I'll probably post the code for others to use. That's if the standard collector isn't altered before then. In the meantime my advice is to just be aware that the GC on iOS behaves differently to that on Android/Flash/XNA and the difference could be problematic if your game is large and/or has tight performance requirements.

Tetris In... How Long?

Yes, I know I write very long blog posts. Feel free to skim. There's a playable thingy linked below!

The Preamble

I've been following Andy Moore's blogging, vlogging, podcasting and social networking output for a fair while. Andy is the dev behind Steambirds and has recently started iOS dev with Iceburgers. He's often got interesting things to say about his life as an indie, information about the business aspects, technical tips for AS3 coders and he's also involved in a lot of face-to-face social stuff (I'm neither an AS3 coder or social but it's fun to hear about them from a safe distance). As far as I can tell, he's an all-round decent chap.

But I'm not liable if he kills you and wears your skin as pyjamas.

However, one thing he's mentioned a few times in the past has always left me kind of perplexed: doing game-jams on very short timescales. I'm not part of the game-jam scene. I've started a few 48-hour jams in the past and sort of finished one of them. I normally take a look at the Ludum Dare theme to see if I'm inspired but I haven't yet been inspired enough to spend a weekend in crunch. I can at least see that you can create a complete game in 48 hours though. Andy talks about writing a game in five minutes.

My thoughts? In a word: "bollocks". I didn't think he was lying -- he strikes me as a very honest person. I just had to assume that there was some glossing over of the reality of what comes before that five minutes and that there would be a large gap between my expectations of something I'd call "a game" and what he was talking about creating. Could it be a bit of fun? Maybe. Some sort of lesson about scope or perhaps about using short goal-oriented sprints to get past motivation issues or to test simple ideas? Perhaps.

The Actual Thing

So, anyway, Andy's been on a bit of a video spree recently. He's started a new vlogging series, which you should check out, and he's been doing a bit of live streaming. A few days ago he did a stream with a five minute dev challenge, so I got a chance to see what was up. Well, pretty much what I thought. The starting point was a template project ready to go and the end result was a moving a block with the mouse and a debug print if that block collided with some other blocks. That's no criticism of Andy as it's pretty brave to try such a thing in front of a live audience. To be honest I was relieved not to be proven wrong. Frankly it would have been awful if he'd whipped up a complete platformer or something in the time.

Harsh, but I told you he was honest.

This morning I noticed that Andy had tweeted that he was going to do another live stream; this time to build Tetris in fifteen minutes. To me this was much more interesting that just "a game" in five minutes. Tetris is a game that we're familiar with. It's not very complicated, but it's not utterly trivial either. I've never implemented it before, but it's something that I'd suggest as a project for someone just starting out with games coding and expect them to take a few days or maybe a week or so to pull something together. I'd imagine that an experienced coder could turn a basic, unpolished but technically solid version around in a day. How quickly could you just hack it together though? Surely not fifteen minutes?

I decided to see what I could do with plain out-of-the-box Monkey and then compare with Andy's run at it. Handily, he put a countdown timer on his stream, which meant that I could kick off at t-15 and see how far I got. Before I started, I quickly thought of what makes up a valid "Tetris" to me:

• Grid x by y (I couldn't recall the dimensions)
• All the Tetris shapes in differing colours
• Random piece generation plus next piece indicator
• Pieces can be moved left,right,down and can be rotated
• Shape movement is locked to grid (vertical drop visual increment can be smaller, but left and right are snapped to the grid and blocks can only settle at a snapped position) 
• Line removal
• Fail state when a block settles at the top

There are probably some bits missing that Tetris fans would insist on and maybe some parts could be argued as irrelevant to the core design on the other end but I think it's a reasonable starting point. Here's how the fifteen minutes went:

2 minutes: Creating new Jungle IDE project. Laptop is being slow so it takes a while.
4 minutes: Written the main function, app template and an outline Grid and Piece class.
5 minutes: Jungle starts flaking out. Throws error dialogs when trying to autocomplete type definitions.
7 minutes: I decide that Jungle is borked and restart it.
8 minutes: Jungle restarts and informs me there's an update. I decide to take it in case it resolves the instability I just experienced.
12 minutes: I've got the grid render written but untested
14 minutes: Base definitions for five pieces added. Not sure if the structure is good.
15 minutes: I've added left, right and drop movement and the code for instantiating a random piece from the set. and started looking at the collision. Time's up. I haven't even compiled yet.

So much for that. I watch Andy make his attempt. Andy gets something up on screen, which is more than I do. Essentially, he gets a block that follows the mouse. You can drop the block and they will stack. It's very noticeable that he pays very little attention to most of the stuff I listed above. For example, I wrote multiple shapes from the start and grid-based movement while Andy did neither. His focus was entirely on getting something on screen, not on getting Tetris on screen.

Again, this was pretty much what I expected and I'm relieved that he didn't blow me out of the water. Thumbs up from me for even trying it on a live stream. I left the stream not long after (need to preserve the bandwidth down here in NZ) but before I did there were a few suggestions for extra increments and Andy seemed to admit that he hadn't considered elements like row removal in what he had written. Clearly we had come at the problem from entirely different angles. If anything, we saw completely different problems.

I went off and toasted a bagel, made myself a coffee and thought about it a bit more. I was kind of proven right that you can't really write Tetris in fifteen minutes, but how long would it take to complete my list of functional requirements? I could afford a morning to see how far I got, so that's what I did. I got myself a little timer app and started doing micro-iterations. I stopped the timer if I got interrupted or when I got to a stage where it was worth making a note or taking a screen grab. The approach was to meet the functional requirements but to ignore any desires to pretty the code unless it helped me get where I was going faster. Here are my notes:

20 minutes: After umm-ing and ahh-ing over collision for a minute I just hacked in the first thing that came to mind. It won't handle rotation though.

22 minutes: Attempt first compile expecting to see block dropping down the screen. Of course there are compilation errors.

25 minutes: Errors cleared. I have to fix them one at a time thanks to Monkey's "something's wrong, I give up!" attitude to parsing. It runs, but I've got a nice blank screen for my troubles.

28 minutes: I had forgotten to set the update rate, which on HTML5 results in no updates at all. I'd also neglected to consider that the active piece needs to be added to the grid as it moves or be drawn separately. I implemented code to remove and re-add itself as it moves. I don't like it. Still, there's something on screen. As soon as I saw it I realised that I haven't put in detection for hitting the floor. Also, the size is clearly horribly wrong.

Awesome, isn't it?

34 minutes: I now have blocks dropping, colliding, settling and a new block coming in at the top (although it doesn't appear in the right place).

43 minutes: Added left, right and drop movement. Code starting to get hairy with ugly bounds checks and cut and paste. Although the movement works, there's a bug where I get to keep moving old pieces.

56 minutes: I've now got row removal. The code is a mess though. Also fixed the bug from the last iteration, which was caused by me failing to create copies of the base pieces so I was recycling references.

Look, one of each. That's amazing... oh, it's a bug.

58 minutes: Added a fail state. All it does is check if a spawned piece is already colliding. If it is then it prints "Failed" to the console and re-initialises the grid. Not very satisfying and probably different from Tetris proper but it matches the requirement. Rotation next. This will be quite a big chunk, I think.

1h16m: I've got rotation (one way) apparently working. I'm totally unconvinced by the code though. If I wasn't working against a ticking clock and actually intended to build a Tetris for release I'd definitely stop at this point and rethink. I've done it by changing all shape definitions to be 4x4. These are rotated clockwise and then the shape is moved to the top left of the grid again. It's quite inelegant. Also, I've just realised that it doesn't account for collisions on rotation.

1h21m: Just fixed the rotation so that it won't rotate into a colliding position. I also added the two "L" shaped blocks that I missed from the Tetris set. I just need the next piece indicator now as far as features.

1h31m: I've got the next indicator in. It's not pretty and the code to do it is a chuckle-worthy hack for re-using the existing grid code. However, we're now feature complete. Now to do a bit of testing and look at some pictures of actual Tetris to see about grid dimensions and stuff.

Fat and grey. Like creator, like creation, I guess.

1h50m: Right, a bit of research dug out the standard play area size (10x20) and the block colours. Getting the block colours involved picking them off an image from wikipedia. That required me to find my "everywhere eyedropper" tool that I rarely use and then paste all the colours into the code, correct the formatting and write the bit to reference the palette. Hence nearly twenty minutes. Also, I've found a crash bug when you lose, which I shall now have to fix...

1h55m: Fixed the crash bug, and also moved the spawn to the middle. However, I also noticed a bug where pieces weren't colliding properly on the right side. I fixed that and then realised that it now stops you rotating a piece on the right if it goes off the playfield. I'm sure in the original that it simply shifts the piece over in that scenario.

2h04m: Okay, I've added a check to see if the rotated piece is hanging off the right and, if so, it attempts to move it in. The piece still won't rotate if it's blocked by another Tetris piece on the right but I'm less sure if the original does this. As I'm also unsure of the precise row removal rules I'm going to leave it here as "job done".

The Result

I guess it's done... hey, look the next piece is a long one. Do we need multi-line bonuses?

If you want to play it, you can do so here in html5 and here built to flash. The controls are up arrow to rotate, left and right arrows for the obvious and down is a surprise... not really. If you want the code for some insane reason, it's here.

The Opinionated Bit

So, based on that, and assuming that I can at least be considered in the range of "average" as a programmer, the realistic timescale for banging out a recognisable and playable Tetris clone is about two hours. To be honest, considering I stopped the timer if I went to the loo, made a coffee or took a break and played Portal 2 for half an hour and those all allow a bit of subconscious processing I'd put it higher.

If we throw out "realistic" and talk about "possible", what then? If you discard the issues I had with my tools, then 1h45ms. If you discard my fussiness about the colours, playfield size and such then maybe 1h15m. If you're just hugely better than me and/or have written very similar code before then I'm sure you could do it in under an hour, but I think we're getting into an area where the great majority of people who try to do it are going to fail to come close. The only way I can believe you'd do it in 15 minutes is if you're pretty much just typing it from memory and that's not development as far as I'm concerned.

So, two hours for Tetris. Still quite fast, eh? Here's the thing though. While what I've got is "Tetris" it's so far away from being a releasable game that it's unreal. Firstly, the code sucks. Most of it is right on the brink of being more expensive to continue with than to rewrite. Even working on my own I'd be unable to face leaving it as is and there's no way it'd stay that way if the code was shared.

Beyond the technical debt there are still a whole bunch of missing features: there's no score or length of time played to provide achievement; no score-board to record that achievement; no difficulty curve; no music or sound effects; no menu system/options. It looks bloody awful. The movement is okay-ish but needs work. The row deletion mechanism is questionable as a modern Tetris clone and just uninteresting and unsatisfying aesthetically. I've no doubt there are bugs in there. I'd say there was at least another several days of work and tuning to get it even done enough to throw out as a freebie web game (not that I would, the world has enough Tetris clones).

Would I encourage someone to do a game jam or prototype sprint? Sure. I think it's great for people to just try building a game. I do wonder sometimes if the message gets confused between "Just have a go" and "It's easy" though. If you want to try to make a game in five minutes or fifteen minutes or even Tetris in two hours then go for it. Can you do it? Maybe, although you may have to bend the meaning of "making a game" at the short timescales. Will you do it? Probably not. Is it worth doing? Only if you enjoy it and maybe finding out if you enjoy it, even if you fail, is the real thing to take away if you're interested in games development.

1D vs 2D Arrays, the Performance Reality

Programmers are generally seen, and like to think of themselves, as logical, rational people. Sometimes we get titles like "software engineer" that flatter us with the implication that we deal in known quantities and proven methods (at least to whatever extent that the reputation of the title "engineer" has survived its abuses).

Unfortunately, the truth is that all of us occasionally operate more on faith than fact and there are large numbers of coders who work with a cargo-cult knowledge base rather than a deep understanding of their work. It may seem odd for such an definitively digital field but human nature manages to create myth, rumour and unquestioned traditions of received knowledge even in the cold clarity of a world of ones and zeroes.

Even if you avoid the pitfalls of the incurious mind, there are plenty of errors of over-simplification and failure to differentiate context to be made. What's true in one language, on one platform, or in one framework, may not be true on another. Knowledge can be falsified by time as the underlying technology changes: a new processor, a new OS, a new language revision, an updated library.

These traps are common enough for programming in general but they're thick on the ground in the realm of performance. If you push it again to dealing with performance concerns on a cross-platform, translated programming environment like Monkey there are almost more traps than safe ground.

All of which brings me to the topic of the post, because the "fact" that 1D arrays are hugely faster than 2D arrays is one that I've seen repeated on a number of occasions in the Monkey forums. I asked in the past if there was any evidence for the claim but didn't get any reply. While I understood why it might be true in certain circumstances, it was hard to swallow as an unsupported assertion. So, when it recently raised its head again, I got the urge to see if it stood up to scrutiny.

1D? 2D? What?

I'll just quickly cover what we're talking about here. In the world of 2D games, it's very common to use some sort of equally 2D array of values to represent aspects of the game world. An obvious example would be a tiled map where the world is basically a grid of tile-type values. The straight-forward approach to this is to use an actual 2D array so that accesses are of the form:

Local array2d:Int[][]
'initialise array here
Local val:Int = array2D[row][col]

The proposed faster alternative is to use a 1D array and to do the indexing calculations yourself:

Local array1d:Int[] = New Int[ROWS*COLUMNS]
'initialise array here
Local val:Int = array1D[row*COLUMNS + col]

Why would that be faster?

Firstly, if you're iterating over an array in some manner, you can avoid some of the indexing arithmetic. Hitting every element only requires incrementing a single index and you can traverse a column by simply incrementing by the row length. This is one step removed from the standard C technique of using a pointer to traverse an array rather than a subscript index (which is also questionable depending on circumstance, but that's another story).

Secondly, it avoids the construction of multiple arrays as Monkey uses the array of arrays model for >1D. This might be cheaper to initialise, it also might be cheaper on garbage collection costs if you're throwing these arrays away. When accessing a value, it's possible that there are costs from the row indirection that are avoided by directly calculating an index. There's also a possibility that you'll get more benefit from lower-level things like predictive caching if all the data is in one consecutive lump.

Sounds convincing. Why doubt it?

Because none of that may be true for a given target or implementation. Remember that Monkey isn't a directly compiled language. It gets translated to another language and then that code is compiled for a platform target. Those targets have very different properties and optimisation paths. Making broad simplistic statements about micro-optimisation performance across all those targets seems, well... simplistic. Pushing those statements to the point where they're blanket "1D is always much faster than 2D" is even worse.

I've been doing this coding thing for a fair while now and much of it has been spent in environments where performance is a significant concern. I've worked on low-level C programming, embedded Java apps, desktop .NET applications and in high-level scripting languages. Every one has thrown up instances of people (including me) doing things based on "facts" about performance that turned out to be entirely untrue, partially untrue or just so small in effect that there was no point in doing it.

The Tests

I set up a very simple test that constructed and initialised the values of an array, performed sequential iteration over all the elements of the array and then a large number of random accesses to the array, timing each group separately. The accessed array data was just added to a total value to minimise the costs outside of the array accesses and loop structures required.

The test ran with five variations on a one million element array of Ints: 10x100,000, 100x10,000, 1,000x1,000, 10,000x100 and 100,000x10. What's that about? Well the major difference between a 2D array and a 1D array in most OO languages is that the 2D array is an array of arrays. This means that each row is another array instance, therefore there is potentially a big difference between a "wide" array versus a "tall" array (for the purposes of this post I'll talk about arrays as row x col).

So, lets take a look at some graphs shall we? Who doesn't like graphs?

Construction And Initialisation

Here are the results from the construction and initialisation part. The array instances were constructed and then the elements initialised to known values:

The graph is displaying the percentage difference between the timing for a 1D array and a 2D array. So, if the 2D array took twice as long, that would register as 100%. If it took half as long, then it shows as -50%.

There are some obvious big spikes on the Android and XNA platforms when dealing with the "tall" arrays, which is where I'd expect to see the biggest difference because of the numbers of objects being constructed. The gap rapidly narrows though and it's 20-30% for the square array. The Flash results are a bit weird but that double spike is repeatable - I don't know what's going on there - the other variants are pretty much even though. The GLFW target shows the 2D array as faster in all but the tallest case.

The HTML5 results I'm showing here are from Chrome 18. I didn't spot how decidedly screwy they were until I plotted the graph. Not screwy as in the results are wrong, just screwy as in those results are bizarre. For whatever reason, this particular test runs very slowly on the 1D array. I'll deal with the various browsers separately later. For now just take it as a clear demonstration of how actual performance can vary from expectation.

Iteration

The next test is simply iterating over the whole array and summing all the values. Again, the graph shows the percentage difference in time for the 2D operation versus the 1D.

Those Android figures show a fairly solid advantage to the 1D array. The rest though? Outside of the one spike for the tall array on GLFW it's all pretty close. For the faster targets the variation is small enough that the 1ms timing precision is a factor. I certainly wouldn't say anything other than "they're pretty much the same" for XNA, Flash and HTML5.

Random Access

The last test was to generate a list of random row and column indices and then run through them, summing the values. This sort of accessing tends to frustrate low-level optimisation techniques like predictive caching.

Now that is a pretty dataset if I do say so myself. The pattern across all the targets is clear and I think it can do without detailed commentary.

Are We There Yet?

Okay, so what do we make of the "1D arrays are much faster than 2D" now we've got the data? Well first we can see the nugget of truth in it -- if your array is tall and narrow going with 1D indexing will likely be faster. On the other hand, you could just swap your columns and rows and it's going to be a dead heat or maybe even a win for the 2D representation. For the usual case where the array is square-ish I can't see that the small wins that are there are worth the bother.

Frankly the number of situations where 1D might be worthwhile seems like it's going to be pretty small. Even on Android, where the 1D array is consistently faster across the board, I'd struggle to justify fiddling about with array index calculations. "No way!" I hear the 1D fans shout "There's a 20-50% performance boost!". Well, yes and no. What we're looking at here is a micro-benchmark that is specifically intended to put the costs of array access in the spotlight and it does that by doing very little with the data accessed. If you're doing anything more than adding integers then the picture changes quite rapidly.

That's a chart showing the Android costs for 2D versus 1D when calling a simple addition function versus a function that does just an additional multiply, Sin and a Cos operation. The earlier tests did the addition inline and you can see that just the function call overhead on the addition mutes the advantage significantly. As the function gets more computationally intensive that effect increases and our simple bit of trig reduces everything but the worst case to under 5% difference.

Whatever array access costs are in play will quickly become swamped by any real calculation work done on the data being accessed. Unless your game loop is pretty close to the perfect storm of just summing the elements of an enormous array the actual visible frames per second speed increase from going with a 1D array is likely to be non-existent.

Don't Listen To Me

So, perhaps I've convinced you that 1D is a waste of time. Don't bother. Not worth it. Right?

Wrong.

Practically, what I'm saying is that you should just leave this technique in the toolbox until you've identified a performance hot-spot where you could gain some benefit. Hopefully the data above gives you some insight into what that situation might look like. If you find such a situation then bring it out, add a little messiness to your code and enjoy the benefits of a worthwhile speed boost in exchange.

More generally I'm saying that Monkey isn't BlitzMax, or C or Java or anything else. Micro-optimisations often fail to remain valid between compiler revisions on the same OS and hardware and they're far, far less likely to be valid across all Monkey targets. Further, when people lean on such tricks to gain performance it tends to blind them to larger optimisations at the data structure and algorithm level that can make a much greater difference and which are far more likely to hold value across multiple targets.

That HTML5 Thing

Oh, yes. So those Chrome initialisation results where 2D was many times faster than 1D? Here are the results for all the tests across Chrome, FF and IE:

There you have it. One target and there are circumstances where no matter if you go with 1D or 2D you'll lose by as much on one browser as you'll gain on another. Feel free to try to make a snappy catch-all recommendation from that.