Tuesday, 13 November 2012

How to outperform std::vector in 1 easy step

Everyone who's familiar with C++ knows that you should avoid resizing a std::vector inside a loop wherever possible. The reasoning's pretty obvious: the memory allocated for the vector doubles in size each time it fills up and that doubling is a costly operation. Have you ever wondered why it's so costly though?

It's tempting to assume that because implementations of the STL have been around for so long that they must be pretty efficient. It turns out that's a bad assumption because the problem, in this case, is the standard itself: specifically, the allocator interface.

The allocator interface provides two methods that obtain and release memory:

allocates uninitialized storage
(public member function)
deallocates storage
(public member function)

(taken from this page).

What's missing is a way of growing an existing memory allocation in place. In C this is provided by the realloc function, but there's no equivalent in the std::allocator interface. To see why this is costly, here's pseudocode for doubling the capacity of a vector using just allocate() and deallocate():

  1. Allocate a new block of uninitialised memory, twice as large as the old block.
  2. Copy the old values to the new memory block.
  3. Destroy the values in the old memory block.
  4. Deallocate the old memory block.

For comparison, here's pseudocode for the same thing if we have a reallocate() function with the same semantics as C's realloc():

  1. Grow the existing memory block.

...and that's it. We don't need to do any copying, so there are no copy constructor invocations and no destructor invocations either.

One of the gotchas with realloc() is that it will move the underlying memory block if it can't be grown in place. This means any pointers into the vector, including pointers between elements in the same vector, will become invalid. In practice this makes no difference: vectors already have this limitation anyway.

I wrote some test code to see how much of a difference this made. I made a template class called realloc_vector with the same semantics as a std::vector, but which calls realloc under the hood. The test code called push_back 10 million times in a row, first on a std::vector<size_t>, then on a realloc_vector<size_t>. I repeated with vectors of std::string as well, to check the performance when there are constructors and which need to be called. Compiled with g++ -O3 on 64-bit Linux, the results were:

push 10,000,000 size_ts:
std::vector<size_t>: 121.866 ms
realloc_vector<size_t>: 52.483 ms

push 10,000,000 copies of "Hello world" as a std::string:
std::vector<std::string>: 501.651 ms
realloc_vector<std::string>: 154.316 ms

The realloc_vector was approximately 2.5 times faster in both cases. This is an extremely artificial test; in practice, if you know the size in advance you would reserve space in the vector up front to minimize the number of reallocations. When I modified the test to do this, the times for both vector classes were identical.

So there you have it. That's how you can outperform std::vector in one easy step: change it to use realloc(), to grow it's memory allocation in place where possible.

Tuesday, 18 September 2012

Ludum Dare 24 Results

The voting has finally finished and the Ludum Dare 24 results are finally out. My game, frankly, did a lot better than I expected:

  • Humour #36
  • Fun #239
  • Mood #296
  • Overall #417
  • Graphics #600
  • Innovation #603
  • Audio #615
  • Theme #672

There were 1006 entries in the 48 hour competition. I'd been hoping to finish in the top half of the rankings this time after a poor showing last time and that's what I managed: 417th overall.

The big surprise was the humour score: wow! I was worried that the humour might be a bit too straight-faced for people, or that I'd be the only one who found it funny. Being wrong has rarely been a happier experience!

I was also really pleased with the Fun score. To me that's the most important category after Overall. It means I made something that people enjoyed playing and that's a really rewarding feeling.

It was nice to get a decent score for the mood category too, but I've never really understood what it means exactly. The other scores were more or less what I expected, except for audio: I didn't have any, so ranking above 391 others was a bit of a surprise!

I think if these results tell me anything, it's not to give up. It's still possible to make a decent game, even when you're starting over with less than 24 hours remaining in the competition. Also: the Ludum Dare community is awesome!

Wednesday, 5 September 2012

Invaders: Evolution Post-mortem

Invaders: Evolution is the game I wrote for the 24th Ludum Dare competition. It's the 3rd time I've made a game for LD (as well as one for a MiniLD event) & although I think my games get a bit better each time, I still have so much to learn. This is a post-mortem not just for the game, but for my competition experience as well.

The game is basically Space Invaders, but with a twist: it tells the back-story of the aliens through cut-scenes as you play. It also has two possible endings, one of which is rather unconventional by video game standards. You can try it out, or find out more, here:

What went right

I made a game! There was a low point where I thought I'd have to quit the competition (see the "what went wrong" section), but in the end I came through and got a game finished - and while it's not going to win the competition, it's definitely something I feel proud of.

In particular, Invaders is the first game I've done which tries to tell a story & I think it was successful. Most of the people who've commented on it seem to have got the humour and enjoyed the twist that the story adds.

On the technical side, the code I added to show the dialogue during the cut-scenes actually turned out to be useful for way more than I originally thought. I ended up also using it for spawning aliens, checking victory/loss conditions & transitioning between cut-scenes and play. Just a small amount of code, but so handy! I'll definitely be keeping this around for future comps - in fact, it's general enough that I should be able to reuse it pretty much unchanged.

What went wrong

The first idea I came up with after hearing the theme was a game about the predator/prey relationship between wolves and bison, inspired by this clip from the BBC's Frozen Planet documentary. My head was filled with grand ideas about realistic 3D snow-filled environments, tense chases and even tenser standoffs, smooth lifelike animation... You get the idea. The game I somehow thought I was going to make over the next 48 hours by myself, would probably have been about 6 months work for a small team.

Unfortunately it took me all of the first day and most of the following night to accept this. By the time I finally did, I thought I might have to quit the competition. This was a real emotional low point. When I started to think positively again, and came up with the idea for Invaders: Evolution, I only had about 12 hours left to do it in so it turned into a real rush job.

That meant things had to be cut, just so I could get finished on time. Music was the first thing to go, followed closely by sound effects - any attempt at audio at all, in fact. Shame, because I think some cool retro-sounding space invader noises would have really helped with the atmosphere of the game.

The other thing missing was any real relationship to the theme. Apart from having the word "evolution" in the title. Maybe it's an evolution of the old Space Invaders formula? Pretty tenuous...


The main thing I learnt from this is that I need to spend more time thinking through a game idea to see whether it's actually doable in 48 hours. A bit of time thinking up front can save a whole lot more time later if it prevents you from going up a dead end.

Up 'til now I've avoided doing any kind of time management for my Ludum Dare weekends apart from a vague idea of using day 1 for code, day 2 for assets & polish. I always thought it would make it more like work, less like fun. But with hindsight, the fun actually comes from making something good - and time management helps you to do that. So for the next LD I think I'll try coming up with some estimates and a rough schedule before I start work on an idea. If the schedule won't fit into the 48 hours, well I'll just have to find another idea.

To me, Invaders was a qualified success. I think it could have been a lot better if I'd been able to spend all of the available time on it, instead of just a fraction at the end. I've already greatly improved my basecode as a result of this competition, so my mission for the next LD will be to use my time more effectively. In particular, to make sure I don't have to throw all my work away after the first day.

Thanks for reading!

Monday, 27 August 2012

Ludum Dare 24: Evolution

The 24th Ludum Dare competition has just finished.  I got a game in for it, but only barely. In what seems to be becoming a pattern for me, I spent the first day working on an idea I ended up having to abandon. The game I ended up submitting was done in a mad 12 hour rush at the end.

Here it is: Invaders: Evolution

It's a fresh take (I hope) on the Space Invaders story. What, you didn't realise there was a story to that? Well if there wasn't, there is now...

There were a few things about it I was really happy with and a few things that could have gone better. Expect a post-mortem soon.

Friday, 27 April 2012

Solar Sailor Post-mortem

Solar Sailor, for those of you who aren't yet aware, is a fairly simple racing game that I made for the Ludum Dare 48 hour challenge.

Here's the competition entry page:
Or you can get straight into it here:
Making a playable game in just 48 hours is a pretty intense experience. This is my attempt to make sense of it all, with the benefit of a few days worth of hindsight.

What went right

I used Javascript and WebGL to write the game. Although I was fairly new to Javascript*, it turned out to be a great language for writing a game:
  • Built-in support for object literals (a.k.a JSON) made it very easy to get content into the game.
  • Being able to just hit reload in the browser to test out changes made for a very tight edit-run loop.
  • You effectively get image and font loading for free, thanks to the web browser. Sound too, theoretically, though I didn't get far enough to need that.
My content pipeline for the game came together really nicely towards the end. I was drawing the race track using Nuke's roto paint node and exporting it to JSON with a custom python script. Unfortunately it was about 2 hours before the final deadline by the time I got this in place. It would have only been a matter of minutes to add more tracks - but I didn't have time to make a menu system for choosing them.

Finally, using Dropbox as my web host was a really good choice. It meant that deploying the game was as simple as doing a recursive directory copy and almost instant. The time I didn't waste with upload forms I was able to spend working on the game.

What went wrong

I struggled to come up with an idea to fit the theme. I did some unsuccessful brainstorming after the theme was announced & didn't come up with anything too inspiring. I had a game in mind before the start of the competition, but I couldn't find a way to make it fit the theme & it just proved to be a distraction. I ended up starting to write code without a clear idea of the game I was making: big mistake. It wasn't until Saturday afternoon (about 18 hours into the compo) that I realised I wasn't getting anywhere. I took a walk away from the computer for a couple of hours to rethink & that was when I came up with the idea for Solar Sailor.

Once I'd got the idea for Solar Sailor, I decided I wanted a Geometry Wars kind of look for it: glowing polygonal outlines, simple shapes, etc. I wasted an awful lot of time trying to write a glow effect which ultimately didn't work, in an attempt to get that look. Worse still, I was doing this before I'd even got the most basic gameplay elements in place. As a result, the level design was left 'til the last minute & I didn't have time for any half-decent artwork.

After submitting the game, I got some people to try it out & they all had the same comment: WTF is going on?! If I'd done this playtesting earlier - if I hadn't been so preoccupied with writing glow effects - I would have realised that the game needed a tutorial. Badly.

Lessons learnt

Stick with Javascript & WebGL kiddo, you're onto a winner there. Ditto for Dropbox as a web host.

Don't start working until you've come up with a game idea that you actually like. Even if it feels unproductive, spending extra time thinking about the theme and what to do with it is a lot more productive than throwing away a days work and finding yourself back at the same point.

Polish doesn't make a game - gameplay does. Good gameplay can excuse bad graphics but the reverse isn't true. Especially glow effects. The main lesson is to always work on gameplay before trying to add graphical polish. Make it fun, then make it look good. It's never completely cut and dried, but that's a pretty good rule of thumb.

Monday, 23 April 2012

Solar Sailor is done!

I've submitted a "completed" version of Solar Sailor to the Ludum Dare website.

Play the finished game

It's been an intense 48 hours but really satisfying now that I'm at the end of it. There's loads more I would have done if I had time, but there some things I was pretty happy with too. I'll post a more complete post-mortem here in a couple of days... once I've had some sleep.

Sunday, 22 April 2012

It's a real game!

Solar Sailor is now a real game! It's actually possible to win or lose. This is quite a breakthrough. :-) Once again,

you can try it out here.

Also, I've made the play area bigger - it felt a bit too small at 1024x512, so I've enlarged it to 1024x1024.

Now to work on the map...

Solar Sailor: semi-playable

More progress! Solar Sailor is now kinda- sorta- playable. You can't win or lose yet, but it does have all this goodness:
  • There are gates that you have to pass through.
  • There's a direction line showing you which gate you have to pass through next.
  • The NPC racers now have some basic AI and will actually try to fly through the gates instead of just drifting serenely and hoping for the best.

You can try it out yourself here!

If you can't be bothered to try it out, this is what it's looking like now:

If you do try it, I'd really appreciate any feedback - especially bug reports!

Progress Update

Solar Sailor is starting to take shape... very very slowly. This is what it looks like now:

Doesn't look much different from the first screenshot I posted, does it? Fortunately now there are some proper game mechanics going under the hood: the blue balls are racers, the brown balls are obstacles and I'm simulating the effects of gravity on all the racers. You can control one of the blue balls with the WSAD keys.

I can't honestly call it a game yet because there are no win or loss conditions, or anything remotely resembling a challenge. But it's getting there.

Saturday, 21 April 2012

Rethinking my Ludum Dare idea

After spending most of today working on a game concept that didn't even excite me, I've realised I need to change direction.

The new idea is: Solar Sailor!

You're captaining a (tiny) planet on an epic race around the galaxy. It's going to be, more or less, a top-down 2D racing game - but with a couple of twists.

I'm a lot more excited about this one. Hopefully I'll still be able to use most of the code I've written this morning too.

Ludum Dare 23: Tiny World

I'm taking part in Ludum Dare this weekend. The theme is Tiny World. Here's what I've managed so far:

This represents about two hours worth of work so far. Most of that time I've spent brainstorming because I was a bit stumped by the theme, but I've got a few ideas now and I'm forging ahead. Wish me luck.

Friday, 20 April 2012

WebGL doesn't have query objects.

WebGL doesn't support query objects yet. There's not even an extension for them. It's a bit of an oversight, but stems from the fact that they aren't in OpenGL ES 2.0 (which WebGL is based on) either.

Queries are useful for a number of things. Timer queries can be used to extract detailed profiling information about your rendering. Occlusion queries can be used for culling objects before they're drawn (especially useful if you have an expensive fragment shader). And so on.

This is a nuisance for me because I was using an occlusion query to perform fast pixel-accurate collision detection for my c++ game Schroedinger's Cat. Now that I'm attempting to port the game to WebGL, I need to find an alternative approach.

I've written a follow-up to this post: OpenGL ES and occlusion queries.

Quick and easy collision detection

This is a neat little trick I found a few months ago, which I thought was worth documenting.

If you're making a 2D sprite based game and want a quick and easy way to do collision detection between the player sprite and the enemy sprites, you can use an OpenGL occlusion query.

First of all, start an occlusion query, draw the player's sprite into an empty buffer, then end the query. The result will give you the total number of pixels in the sprite. Then, on every frame:

  1. Draw all the enemy sprites at the same depth.
  2. Start the occlusion query.
  3. Draw the player sprite behind the enemy sprites.
  4. End the query and get the result.
If the number of pixels drawn from the player is less than the total, they've collided with an enemy.

The beauty of this is that it's pixel-accurate and essentially zero cost. The downside is that occlusion query support isn't available in OpenGL ES or WebGL yet, so it won't work there.

Modulus for previous array index

In JavaScript, C and C++, x % y will return a negative number if x is negative. This isn't what you want if you're trying to wrap around an array index (for example). Fortunately there's a nice solution. Instead of writing something like this:

  int prev(int x, int N) {
    int prevX = (x - 1) % N;
    if (prevX < 0)
      prevX = N - 1;
    return prevX;
you can simply write:
  int prev(int x, int N) {
    return (x + N - 1) % N;

and let the magic of modular arithmetic do its work. This works for unsigned integers too.

Hello world

#include <iostream>

int main(int argc, char** argv) {
  std::cerr << "Hello world!" << std::endl;
  return 0;