ancient wisdom

I'm hard at work on the system for decorating your models with drawings and decals at the moment. It's a particularly satisfying exercise - you paint zebra stripes on your origami horse, then print it out as a square of splintered zebra bits. When you fold the printout, it magically reassembles itself into a zebra.

I'll make a video, but it's not yet ready for primetime. Instead, here's a picture of a pajarita:

The pajarita is a classic Origami model. When you build it out of paper, you make a few creases in a sheet of paper, and it sort of magically pops into existence. I wasn't sure it would be possible to build using the operations available in Blue Comb, but after a bit of fiddling around I found a short sequence of squashes which did the job.

In this update, I'll look at the lighting system in Blue Comb.

A 3D scene is made up of a bunch of triangles with pictures on them. If you don't apply any lighting, you get something like this:

There's a silhouette there, but you can't make out any of the details. The simplest approach to lighting a 3D scene is to imagine a light source, and then darken each part of the model according to how much it faces away from that light. This can be done very quickly, and it looks like this:

Straight away we've improved on the previous image in terms of communicating the shape of the object we're looking at. On the other hand, it looks horrible - like a photograph taken using on-camera flash. It's rather flat, interior parts of the model are much lighter than they should be, and it's just floating in front of the work surface.

What's missing is a shadow:

Awesome! It now looks like an actual thing. It's very dramatic. In fact, if we were to criticise, it would be that it's perhaps too dramatic. The parts that are in shadow are pitch black. If we want people to be able to see and play with shadowed bits, we need to put a bit of extra light in there:

Well, OK. Now it's lost its deep shadows, but it's also lost its pop.

Until recently, that was how games generally did their lighting. There were a small number of light sources, an ambient light (the bit extra we added to make it less contrasty), and some system for casting shadows. The ambient light is there because we've only been considering local lighting effects - the interaction between a particular light and a particular point on an object. In reality, a light doesn't just stop the moment it hits an object - some of the light bounces off, and goes on to light another object. Eventually some light will bounce its way into every nook and cranny, but the intensity and colour of light at any location is dependent on the entire scene.

Calculating this global illumination is currently an interesting area in realtime graphics. It's still computationally intensive enough that there isn't a single approach that will work in all situations on all systems, but it is now possible to pick a set of compromises, or a subset of the problem, and come up with a workable solution.

The first step towards global illumination was a technique called ambient occlusion. This is still essentially a local illumination scheme, but now the ambient light is affected by the amount of self-shadowing at each point on the model. Calculating the self shadowing is still an expensive operation, but for a fixed model it only needs to be done once when the model is created, and the results stored in a texture for use in the game. It allows for very soft and subtle lighting, and it was this look I had in mind when I started Blue Comb.

If we remove the shadow and the ambient light, and switch to ambient occlusion, the scene looks like this:

Now, the fact that I'm simulating Origami means that I'm dealing with a different set of issues from most games. One point of difference is that the model is constantly changing shape, and its shape is entirely (and unpredictably) dependent on the player's actions. This means that I can't use any pre-processing techniques to speed things up at runtime. On the other hand, it's fundamentally a low polygon model, and there's nothing in the scene except for the model and the (flat) work surface. So techniques that would be impractically slow in a modern game turn out to be solvable by brute force.

What I do is take a simplified version of the model (flatten the faces, ignore the curves around the folds, and reduce any curls to a few sharp bends). Then I go through each face and render the whole scene in black from its point of view, multiple times, each time skewing its view direction to cover the whole visible hemisphere. All of these light views get accumulated together, and by the end of the process I have a standard ambient occlusion map. This works great, and on the PC I can accumulate a few hundred passes each frame in realtime, which makes a lovely soft image.

But in doing this, I realised I was only a short step away from quite a nice global illumination system. Instead of rendering the scene in black to record how occluded a point on the model is, I could render the scene fully textured and lit, and record how much light is bouncing to that point on the model:

There are some complications to doing this. I still need the ambient occlusion term, because the simplified mesh I use for the lighting doesn't capture all the surface detail I want. So occlusion gets accumulated into the alpha channel of the light map, while the bounce light is accumulated into the colour channels.

Previously I only needed a single bit for each light accumulated, so an 8 bit texture was all that was needed for 255 light directions. Recording bounced light, I need more precision. On the PC I use a higher precision texture format; on the iPad I apply some dithering to try to preserve the colour detail.

For speed I'm accumulating every light direction directly into the light map (rather than repeatedly rendering the light for a particular direction, accumulating it into the texture, rendering another direction, accumulating that, etc). The tricky part is that I have to ensure each pixel is only rendered to once per light direction (otherwise it will contribute too much to the accumulated light map). I use the z buffer to ensure a single write per direction, but I can't use it to resolve which is the correct face to write, and instead have to z sort the scene for each face.

On slower systems (including iPad), the number of directions I can accumulate in a single frame is down in the tens, which produces multiple shadows rather than a smooth gradation from light to shade. I allow this during folding operations, but as soon as the movement slows down I start accumulating the results from previous frames to bring the quality back up.

This image shows the effect of accumulating just the occlusion term over increasing numbers of light directions. From top left to bottom right, it's accumulating 1, 4, 16 then about 8000.

This image shows the bounce light for the same number of light directions. The scenes with fewer directions are less acceptable than when it's purely occlusion - the coloured dots appear as solid projections on the surface when they should be just casting a subtle hue.

Note how much lighter the inside of the model is when all the light is allowed to bounce around in there.

Finally, the light bounced onto any part of the model actually comes from the preceding frame. If the scene changes abruptly, then this component of the lighting will be wrong. I rely on the fact that manipulating the Origami model is somewhat damped for the sake of a nicer user experience, and the indirect light from a few frames ago is never far offset from the correct position.

It would be possible to split up the process of accumulating light directions so that it updated the light map a few times per frame, but in practice the lag isn't noticeable. This image shows how long it takes to propagate the light through the model. The majority of the effect is there by the second bounce.

The big win from this approach is that it makes the paper nice and translucent without the various hacks I was previously forced to use. Because it's accumulating light from every direction, surfaces which aren't actually touching cast a very soft, blurred light on each other. However, when they are touching, you see quite a clear image. This video of some aimless folding with a particularly translucent paper stock shows the effect. As the curl flattens out, the paper underneath becomes visible. (Try it with real paper!)

Apart from looking cool, I use this feature in the game part of the game for aligning patterns.

I thought it was about time I started blogging about project Blue Comb, also known as The Origami Game.

Blue Comb has been in development for a rather long time now, and for most of that time I haven't been entirely sure just what it is. It grew out of an idea I was working on for a story-based game. I was thinking about the sort of feel and style I wanted for it, and what was achievable for a tiny team on a tiny budget. Origami seemed like the perfect theme, with low-polygon models (easy for the machine to handle; easy for me to create) and the opportunity for a beautiful papery visual style. I started coming up with a design where you'd explore a world made up of collages, and along the way you'd discover new Origami models that you could transform into - a fish would allow you to swim, a bird would let you fly and so on.

So I sat down and started coding. Clearly the first thing I needed was some sort of editor to create the models… and that's where I got trapped. It turns out that creating an editor for Origami is really tricky and really interesting. Eventually it became apparent that this game was going to be mostly about the editor, and the exploring portion was off at a bit of weird angle to it.

For a while I decided that I would do away with any game aspect - it would be purely an app for learning, creating and sharing Origami designs. Eventually I settled on the minimum viable game for it - a puzzle where you unlock Origami designs by matching patterns as you fold, but with a sandbox mode that contains All The Work.

In this Blog post, I'd like to talk a bit about some of the folds that exist in Origami, and how to achieve them in a simulation.

The first type of fold is the valley or mountain fold. This is where you simply bend the paper along a line. If you bend it towards you, the crease is like a valley. If you bend it away, it's a tiny mountain. Simulating this is easy - if you drag any point on the paper, we just need to create a crease line half way between where the drag started and where it is now. A valley fold puts the action where you can see it, so we do that by default; to create a mountain fold, you'll need to turn the paper over and create a valley from the other side.

This video shows some aimless valley fold creation, and also shows how it tries snapping the fold to likely points and edges.

The first few folds are straightforward enough, but we soon hit what turns out to be quite a tricky problem with simulated Origami. You can put a crease across wherever you like and you'll have a valid fold, but there are situations where moving a crease a small amount will result in a large change in the folded result. The following video shows how I handle the situation where dragging a crease will suddenly involve a previously unfolded part of the paper. The active fold uncurls a little way while the newly involved fold curls up to join it. With a mouse this is easy enough, but on the iPad it means that your finger starts getting ahead of the drag point. I experimented with various way of resolving the offset. The best solution I found was simply zeroing the physics when the catchup curl is complete, so that it slowly accelerates to rejoin your finger (allowing you time to adjust where you're pointing).

During the catchup curl, you have the opportunity to decide whether you really mean to involve the new flap of paper - it takes a certain distance to commit to it (which is proportional to the size of the flap), so there's time to stop and go back if your intention is to snap to the edge of the flap.

Mountain and valley folds are all very well, but most of the interesting models involve some slightly more complex moves. (There is an Origami discipline called Pureland which aims to use only those folds, and it's fun to see how much expression you can achieve within such constraints). I was going to be disappointed if I couldn't create the classic crane model within my simulator. In fact, my goal was to be able to create it using intuitive prods at the onscreen model, with no buttons or obscure gestures.

Spoiler:

This sort of model requires a few techniques. First, there is the squash fold, which looks like this:

To perform a squash fold, you first need to have a model that has creases defining two flaps which hinge over, and a flap carried between them. Where you'd start a valley fold by picking a vertex or a silhouette edge to start dragging, for a squash fold you put your finger in the middle of a crease and smudge it sideways. The simulation searches for a valid pivot point and collects all the affected faces, and drags them around. If there are multiple valid squash folds, you smudge back past the starting point and in again, and it will cycle to the next possibility.

Then there's the petal fold:

If you look carefully, you'll see that the petal fold is just two squash folds stuck together in the middle. The tricky part is that we can't choose a starting point for the drag which says unambiguously that this is a petal fold rather than a valley fold. What happens is the simulation assumes that if a petal fold is possible from your start point then it's probably what you want. Again, multiple valid petal folds can exist at one location, so the same trick of dragging back and coming in again cycles through them, and this is where you can cycle on to the valley fold if wanted.

Cycling through possible folds is shown in this video:

And a related technique, dragging back to gather multiple flaps into a fold, is shown here:

The last major fold required for the crane (and most of the traditional models) is the inside reverse fold. This often used for heads, beaks, legs and so on, and involves opening up a flap enough to flip it inside out, like this:

It's achieved by pushing on the edge of the fold. The simulation just assumes that picking an edge that is reversible should invoke an inside reverse. If you actually want to perform a valley fold, you pick the pointy end instead.

There is another reverse fold, the outside reverse, which is very similar but ends with the flap folding around outside of itself rather than flipping inside. I currently handle this with some restrictions that I'm hoping to overcome. Models such as the traditional swan can be folded, but require an additional step to set up.

That's probably enough for this update, but I'll finish with a couple more video clips. This one is me folding (most of) the bird base:

And this one shows how you can scrub through a folding sequence if you're learning how to fold a model for reals. (The simulation automatically combines multiple symmetrical folds into a single step where that would improve clarity.)

I just spotted that Word lets me edit blog posts, and I thought it might be more convenient than the web interface.

Here's a picture of a pretty bug in Blue Comb:

Did it work?

(Update: Eventually, yes.)

Palm held a competition to promote their PDK. Ancient Frog was eligible, but (possibly because it had passed its peak before the competition started) didn't fare as well as I'd hoped.

On the other hand, there was a category for free apps, and for a while the number of entrants was smaller than the number of prizes on offer. This looked like a good opportunity to bang out some free apps - it meant I might win something, I could experiment with what genres of app generate the most interest, and I could have a bit of fun doing some rapid prototyping. All models of Pre and Pixi have OpenGL ES2.0 hardware, so I could go to town with shaders.

I gave myself no more than two days per app. The speed of development and the limited scale of what I expected to achieve meant that it was a proper hackfest. All the code went into one ugly C file. Magic numbers, hard-coded data, copy-and-paste coding - everything that shaves a few minutes off writing a bit of code at the expense of making it unmaintainable, bug-prone and difficult to build upon. I felt simultaneously dirty and liberated.

The first thing I made was Earth Now. It shows a 3D view of the Earth (rendered using NASA satellite imagery, including normal mapping from the height data and specular mapping for water / ice), and downloads the latest global cloud cover imagery to display on top. I thought it would be a quick app to ease myself in to things, but it ended up taking two days - most of which was locating a decent source of cloud imagery, and writing my own http code to get at it through its content network.

The next one was a sandpit app called Liquid Planet. It combined a bunch of tricks that I found useful in museum interactives - GPU-based interactive water and earth, with a bathymetric model of the Earth that you can flood and drain. It's quite fun drowning continents, or seeing just how much land there was during the last ice age (New Zealand was huge!). This one took less than a day, but was unfortunately a bit too demanding of the phone's GPU. (I'm used to doing this sort of thing on high-end PC gaming cards, and while it's impressive how much you can do in a shader on a Pre, it can't really handle the number of textures I wanted).

Then, a music app called Tonal Pool. I've traditionally been very bad at handling sound in my games, generally seeing it as the area responsible for the majority of the game's data footprint, the majority of the annoying configy crashy bugs, and the least important part of the experience. (Throughout my time in the games industry, I'd hear people repeatedly argue that it's the most important part of the experience, but really - try playing a game with the speakers turned off. Oh, you already do! Now try playing with the screen turned off.)

Anyway, it's time I made my peace with that particular sense, so I decided to make an app that was all about the sound - a Tenori-On-style sequencer. Of course, I still didn't trust it to survive on sound alone, so it's framed in a nice little GPU-based interactive water pool, with ripples going off as each peg sounds. I was pleased with the result - one day of work, and I had several nice emails about it.

Banner came next. It was a bit of an experiment - I wanted to see if I could create a software version of those light sticks that you wave to spell out messages using persistence of vision. The screen can only handle 60fps, which is definitely at the low end of what you need to pull off the trick, and there's an accelerometer to help sort out synchronisation.

You draw your design on the screen with a rudimentary paint application, then start waving the phone. It automatically senses this, and starts flashing a line of dots to recreate your image in the air. It works, but only in a really dark room, and it takes some practice to get good results. After a day on it, I decided that it was never going to be good enough to meet the Free App Downloader's expectations, and rather than get slaughtered in the comments, I decided not to publish it. (Search the iPhone app store for similar apps if you want to read how people respond to basic physical limitations...)

Finally, my favourite: Ancient Pond. (Yes - I liked it so much I gave it the Ancient seal of quality). It's your basic fish pond app, using (ahem) that GPU water effect again, this time with a nice flocking algorithm running under it to make fish dart and swim about. It took a couple of days, and then another day or so updating it to add different themes and do some tweaking of the experience. I managed to keep the framerate up to an acceptable level (particularly on the Pixi, which, surprisingly, handles it better than the Pre) by strictly limiting the effects. So there's a theme which has shadows and refraction on the water, and a theme which instead has specular highlights and caustics.

Ancient Pond took off really well - there's clearly an interest in this sort of app, and I really enjoyed myself writing it. It's very tempting to turn it into a real app, cross-platform, with downloadable creatures and ornaments and so on. I'm still mulling over whether to put Blue Comb on hold and do this first.

In the meantime, it would be nice to add a few more features, but it's right up against the hack-it-now-and-never-look-back approach I used to create it. To do anything more to it at all would really mean tearing it down and starting again properly.

So, how did I fare in the competition?

Well, the results don't seem to be up yet, but I've had an email which confirms that my placement in the leaderboard was accurate. Ancient Frog snagged one of the $1000 HP store credit prizes, as did Ancient Pond and Tonal Pool. Both of them hovered tantalisingly in the $10,000 actual money prize category, but were finally beaten out. Earth Now and the free version of Ancient Frog were also in the running until the last few days of the competition. Liquid Planet fizzled, and I ended up pulling it from the store.

I had a lot of fun, and I have a nice little purse which I have to spend on fun things, so that's great. And since the HP store sells Canon lenses, and I live for Canon lenses, I'm a happy man.

And here I am again, shooting my mouth off to Intel:

http://appdeveloper.intel.com/en-us/article/iphone-appup-porting-ancient-frog

Ancient Frog currently runs on all of the devices in this picture, and a few more that happened not to be there when I was playing with my camera.

The iPad port is out and failing to set the world alight. It did pretty well in its first week, getting featured by Apple. But featured on the iPad in launch week turns out to fall a long way short of featuring on the iPhone, and when the week was up, it didn't have any momentum.

The Palm Prē version is out too. I really enjoyed doing that one - I discovered at GDC that Palm was opening up native development, got a Prē straight away, and had something running in a couple of days. It's essentially the Windows build in its iPhone-sized debugging configuration, with the OpenGL ES code and textures from the iPhone version. Wonderfully painless, and with the crisper screen, and the river-polished-stone feel of the Prē, it's beautiful. My favourite version so far. It takes a while for the sales figures to come through from Palm, so I don't really know how it's doing yet - but it doesn't need to do anything spectacular to justify the effort.

The Android port is still rumbling along. I have something that runs well on the Nexus One, although it lacks sound, there are some situations where it fails to recreate textures correctly, and the levels all need redoing (again). (This time they need to be higher res and aspect-ratio agnostic versions of the original iPhone levels - the iPad versions only make sense on a physically larger screen). The textures also can't be compressed, because there's no standard GPU on Android devices, and there's a silly restriction on how much data you can fit in internal storage. So lots of bitty work to get it to run reliably on a decent cross section of the various devices out there, and still no way to charge money for it from New Zealand. I keep picking away at it because at some point it'll probably be worth the pain to nail all of the remaining problems.

The desktop version, OS-X and Windows. I keep flip-flopping on this. I'm just not sure what sort of market there is for a game like Ancient Frog on the desktop. The App Store has lowered everyone's price expectations, and I don't think I'd be able to sell nearly enough copies at $5-ish to be worth the support hassles of getting it running on decade-old malware-ridden boxes.

The netbook version. This is basically the desktop version, but with Intel handling some of the config testing woes, and the possibility of prizes in their competition, I'm tipped in favour of it.

With all of this stuff, Ancient Frog continues to take up a couple of days a week of my time. The rest of the time I'm working on two new game prototypes, hoping to get one of them to a critical point where I can announce it and go all in on it.

You may have missed it - the news slipped out pretty quietly - but Apple has announced a new product line.

The iPad is essentially a scaled up iPod touch, so naturally I'm interested in what it means for Ancient Frog.

According to the announcement (and my experiments in the simulator), iPhone apps work on the iPad straight out of the box, with no changes needed. However, since the screen is higher resolution (1024x768 instead of 320x480), and a different aspect ratio (4x3 instead of 2x3), such apps won't look their best. Below are a couple of mockups of what you'd see if you had an iPad right now and ran Ancient Frog on it. (All of the pictures are shrunk down to fit on your screen - click on them to see them full res.)

The first mode just runs the iPhone app at its original resolution, giving you a little window in the middle of the screen:

It also gives you the option to run it "2x" - doubling the size of each pixel (in each direction), so the app uses more of the iPad's screen (640x960 of it). This makes it bigger, but either blurry or blocky depending on whether or not the device is going to filter the image when it scales up. I suspect they'll go for blocky, which is what I've simulated here.

Now, neither of these options is particularly elegant or attractive. With a bit of fiddling around though, I can make the current iPhone application recognise the iPad and behave more like a native application on that platform. What I've done here is run it at 768x1024, but allowing it to letterbox slightly to retain the original aspect ratio (luckily the ragged border gives me a neat way to bring the edges in a bit, as well as a bit of room to lose some pixels top and bottom). This already looks way better than the previous shot - lots of elements are still blurry, but things that appear at varying scales in the game are already at a higher resolution. This means the text, the daisy and the particle effects are all crisp, which makes the whole thing seem higher resolution.

So that's good - I can put a bit of work into the current app, and release a free update that makes it play nicely on the iPad. But it's still blurry - what would be involved in making it look great on the new hardware?

That's where it gets a bit tricky. The work involved suddenly goes up by an order of magnitude. Every level has to be reworked, and I have to handle the original aspect ratio, as well as two new ones for the iPad (for portrait and landscape). The download size also goes up - currently I fit just under the 10MB limit that allows people to download over their phone. With the background textures doubled up, I'm over 20MB and start to lose impulse buys (as well as bloating out the app for everyone, regardless of whether they have an iPad).

So my plan is to leave it at that - an incremental upgrade to make the experience worthwhile on the iPad - and offer a separate, HD, version for iPad only. This will use the reworked levels I've been beavering away at for the last few months, and make use of its groovy auto-aspect-ratio handling (the desktop version can be stretched to all sorts of whacky resolutions without breaking the effect).

And here's the result:

It's work in progress (the lighting has yet to be graded correctly, and the particles are missing), but you get the idea. The full screen is used, the frog is back down to a more appropriate size for human fingers to prod at, and there's some nice little environmental stuff going on for you to play with.

It would be nice if there were a way to offer a cheap upgrade path for people who already have the iPhone version, and I'm looking at whether there's a clever way to do that.

I can't wait to get my hands on the physical hardware. I think there's going to be some very interesting times for gaming in the next few years.

My thrashing around trying to pin down the details of project Blue Comb continues. I have decided on an art style, which is helping to frame the rest of it. Ancient Frog started with a very simple and clear premise, but this new project is just a collection of obsessions which I haven't yet managed to glue together. I suspect something will need to get cut before I'm able to finish it.

I just received an email from Jef Armstrong, whose game Mondrian was recently released. Jef emailed me last year, shortly after Ancient Frog was released, saying words to the effect that he liked my puzzle game, he was writing his own puzzle game, so let's talk about puzzle games. Flicking back through the emails, there's some blogworthy stuff about how I created the levels in Ancient Frog:

Creating the puzzles was one of the big challenges with Ancient Frog. I've been thinking about writing a blog article about it, because it's something I personally find fascinating. A large proportion of all the code written for Frog (possibly the majority - I should check) went into the tools for creating the puzzles. However, I'm a bit wary about talking too much about it in public because I suspect that some people would be disappointed to learn that it's not all lovingly hand crafted by some sort of puzzle making master craftsman.

Seems a bit silly now. Let's hear the details!

The most important part of the toolset is the solver. This has two levels - a quick pass to determine whether a particular layout has any solution at all, and a slow pass to exhaustively determine the optimum solution. (In this context, 'quick' means anything up to 15 seconds, and 'slow' can be up to 6 hours). There's nothing clever about the way it works. It uses brute force and a fast computer to walk down the tree of possible moves. There's some interesting optimisation, and stuff like exploiting symmetry, early-out, loop detection and so on, but essentially it uses the approach that computer scientists say is impossible. But that's because it's their job to come up with general solutions which work for the worst cases in the biggest data sets. I'm able to limit the problem space to something which is achievable by brute force, and just skip puzzles which are taking too long to check.

So the process for generating a puzzle goes like this:

* I choose a start point and an end point, and a set of pegs from which it can choose its route (this lets me put a particular move into a puzzle, but often I'll just leave it to choose from all pegs)

* I press the magic button

* It goes through a loop where it removes a random peg and tests whether a solution exists. If there is no solution, it replaces the peg and flags it as required. This process is repeated until no peg can be removed without creating an impossible puzzle.

* It checks the result against all the previously generated puzzles to ensure it's not a duplicate (taking into account simple translation, rotation and mirroring)

* If I like the look of the result, I press magic button #2 and generate the optimum solution for it

* I quickly step through the solution to see if I like the look of it. I tend to reject puzzles that require too much walking backwards, or that push the frog's head off the side of the screen or have the legs passing over the fly.

I like to generate a whole bunch in one sitting, then try to put them in order based on how difficult I think they look, and how difficult the solver reckoned they were (that's a bit of code that needs some work by the way - some of my rankings are quite a bit off). Then I leave them for a day or so while I get on with other stuff, so I can play them through without knowing how they're solved. In my playthrough, I log how long it takes me to solve, how many dead ends I go down, how many undos etc, all of which information also goes into the difficulty ranking. Each time I play through, I'll generally shuffle levels around a bit to improve the progression, but I also like having runs of very similar layouts with increasingly difficult solutions.

The tools also include stuff for applying backgrounds, frog species, fine-tuning of board position, rotation & translation of the whole puzzle and so on.

Interesting stuff!

Happy new year.