Thursday, October 25, 2012

How Granny Got the Look

In my last post I mentioned briefly how all graphical objects in Granny Smith are made out of 2D polygons which are transformed into 3D at load time. It was never initially designed for the sometimes complex environments in the game, but we decided to stick to this method instead of involving a separate 3D modelling software. I think, at times real 3D objects could have come in handy, but overall the current workflow is preferable since it's much more efficient. There is no need to track separate files or assets - every level is totally self-contained. Because the 2D data is so small, we don't even use instancing, so there is no risk of trashing another level when altering objects.

This is how a factor level looks in the editor.

The most fundamental transform is a simple extrude, but we can also apply a chamfer or fillet in the process. This is used extensively, especially for round hills and other natural shapes in the game. This beveling is done by gradually shrinking the polygon while extruding it, in one or more iterations.

Shrinking or expanding a polygon is not as easy as it sounds. For "well-behaved" polygons there is no problem, but sometimes vertices disappear in tight corners, or new ones must be added. I tried several different ways of implementing this myself, but it's really hard to find a robust method that never fails, or even one that failes gracefully. After a few failed attempts, I found the awesome Clipper library, which can do all kinds of polygon operations, including expanding and shrinking. It's reasonably fast, very robust and super-easy to use, I highly recommend. Even when using the Clipper library it was not trivial to get the beveling to work correctly. The Clipper library does not track or correlate vertices, so after a shrink operation you have no idea how the new vertices correlate to the old ones, hence it is really hard to stitch the two polygons together with triangles. It took me a few tries to implement a robust stitching algorithm, but I finally came up with one that deals with all well-behaved polygons, and most (but not all) tricky corner cases.

Shadows also deserves a mention. I started experimenting with different methods for smooth soft shadows very early on. The traditional way of using precomputed low resolution shadow maps didn't quite fit our needs, because all geometry is generated on the fly, and levels can be quite large. Since most geometry in Granny Smith is front-facing, extruded, flat, 2D polygons I came up with a scheme where the shadows are semi-transparent triangles based on projecting the 2D polygons onto each other. Thanks to Clipper, I already had a great toolbox for this. Each polygon is expanded and clipped against overlapping polygons in the background. The resulting "shadow" polygon then uses vertex coloring to smooth out the penumbra and a special shadow shader to achieve quadratic fall-off. All these shadow triangles are put in separate vertex buffers and rendered simultaneously. The engine supports dynamic soft shadows as well, but it's rather expensive, because all the expensive geometry clipping needs to happen every frame, so it's only being used in a very few places in the game. Because shadows are computed from the 2D polygons, there will only be shadows in the XY plane. To somewhat overcome this I also added self-shadowing along the extruded surface using the same vertex coloring scheme, so creases get a darker tint.
The anatomy of Granny Smith

The characters are basically a composite of 2D sprites, but slightly rotated to compensate for the camera angle, so it's somewhere in between an oriented sprite and a billboard. There was never a discussion about using "real" 3D characters for this game. My personal opinion is that 2D character are highly underrated for this type of game. 2D characters obviously yield better performance, but I'd also argue they also look better in many cases, especially on low resolution devices. Polygon aliasing completely disappear, because all edges are drawn into the alpha channel of the texture and rendered with mipmapping, so the characters always look crisp and sharp.

Characters is not the only area where we combine 2D graphics with 3D objects. Grass and foliage are two examples. The grass is added procedurally, while the decals for trees and bushes are placed manually along the rim of the object to hide sharp polygon edges and add extra detal. The grass is rendered with a special vertex shader to sway in the wind.

After completing a level, you get a replay in vignette and sepia color and with occasional bluring plus added dust and scratches to give the impression of an old movie. The vintage effect is just a shader effect in a post pass, but the replay itself features alternative camera angles and slow-motion effects which took some time to get right. The camera angles are determined by what's going on in the game. For example, it often switches to slow-motion close up right before fracturing an object. The replay data is basically just recorded input for the player, plus position correction data in case of divergence, similar to a networked multiplayer game, but I also record "special events" that are used to trigger camera angles. The replay data is analyzed and all the camera angles are decided before the replay starts. Choosing camera angles on the fly wouldn't work since you want to switch camera before the action happens. Getting everything in the game to support slow-motion playback without diverging too much was a real challenge, and you can still see artefacts here and there. The replay system is also driving the apple thief playback (in very subtle slow-motion) during regular gameplay.

Tuesday, October 23, 2012

The Physics of an Old Lady

It's been almost two months since we released our second title - Granny Smith (available on App Store and Google Play). It's a platform racer starring an old lady chasing an apple thief through different environments. Our ambition was to make a smaller game than Sprinkle, but it turned out to be a lot more ambitious. I think mostly due to graphics. It started off as a 2D platformer with 3D-ish graphics - a few layers of parallaxed polygons, but the editor got gradually more advanced, and even though all graphics are still drawn as 2D polygons or splines, they can be extruded, beveled, rotated, textured, etc in heaps of different ways. In fact, all level data is still stored as 2D polygons and then transformed into 3D object at load time, making the level data extremely small. Even a complex level in the city environment is typically less than 30 kb in compressed form (not including textures).

I will talk about the physics in this blog post and save the graphics details for later. Just as with Sprinkle, we use Box2D for gameplay physics, with the addition of a special "motion joint", described in my previous blog post. In Sprinkle, each level was small enough keep all dynamic objects awake at all times, but in Granny Smith, the levels are much bigger, so objects are sleeping until touched and then completely disabled at a certain distance behind the player. Some of the more complex objects use fixed joints to glue objects together. It's a rather expensive method instead of just merging several objects into a single body, but 2D physics was never a bottleneck in this game, so I just went with the simplest solution.

Using a physics-based character for a fast-paced racing platformer was in retrospect quite a bold move, and we ended up implementing certain "speed normalization", "jumping aid" and "grabbing aid" sensors, manually placed in the level editor to help the player time jumps and release handles at exactly the right moment (pushing it more and more in the direction of an arcade game). This was by far the most tricky part of the whole project - to give the impression of a physics-based game while still making it playable and enjoyable. Without all the sensors, levels were practically unbeatable unless you followed the intended path very precisely.

The most interesting physics in Granny Smith is the fracture feature. We realized early on that we wanted a "wow"-feature in the game, similar to the water in Sprinkle, and our choice fell on fracture and breakable objects, mostly because it has not been used much in mobile games and it fits the setting nicely. I have always argued that when fracturing objects in games, it is very important that the fracture pattern is determined by the point of impact. Exactly how it breaks is less important. I also think it's very important that the broken pieces sum up to the original object. It sound obvious, but many games just replace the broken object with some random pieces when it breaks, which creates a very noticable pop. Lastly, I think the motion of the broken pieces must respond physically to the impact. To sum it up, it is very hard to cheat with breakage - at least from a geometric perspective. The exact breakage pattern is not that important, but it's highly relevant that it a) breaks at the point of impact, b) that the pieces sum up to the original object, and c) that they follow a realistic trajectory after the impact.

In Granny Smith, we only break flat objects, so the breakage actually happens in 2D. This simplifies things a lot. Breakable objects are special objects in the editor, and from a level design perspective they are always a straight line, which is then extruded and can be broken along the extruded surface - a quad. The quad is broken in real time, based on the point of impact. The breakage algorithm itself is rather dumb, basically just slicing polygons with random lines recursively (while preserving texture coordinates) until there is a certain number of pieces. Pieces that fall within a certain radius from the impact are made dynamic and the rest are marked static. Impulses from the impact are then applied to the pieces to ensure that they fly off in a natural trajectory. It took some tweaking to get it all right, but it turned out quite nicely in the end.

The broken off pieces are simulated using my own 3D rigid body solver and collision detection (see previous blog posts) in the simplest way possible. There is no contact manifold, no pair tracking, no friction tracking, just a single contact point per piece and no collision between pieces. There is a very lightweight sleeping algorithm to disable objects that fall below a velocity threshold. Once they fall asleep they never wake up, and objects that fall outside the screen are immediately removed. Because Granny Smith is a fast-paced game you typically only see a breakable object for a second or two, so the relative inacurracy in the brekable physics is very hard to notice. I think this is a quite good example of "effect physics" in 3D that don't need a full-fledged, generic rigid body simulator.

All pieces from a breakable oject are rendered in a single draw call using a dynamic vertex buffer. This is far more efficient than drawing each piece separately, even though dynamic buffers have a some overhead. On multi-core devices (most phones and tablets nowadays!) the 3D physics calculations take place on a separate thread.