Archive for the 'Gaming' Category

To Tell the Worlds Stories

Closed

“To Tell the World’s Stories” is our mission statement at Prophetic Sky. It sounds exciting, doesn’t it? Everyone loves stories – we watch them on television and in movies, we read them in books and in comics, we imagine them at night in bed.

But what is a story, exactly? Merriam-Webster Online has an answer, if a dry one:

a: an account of incidents or events
b: a statement regarding the facts pertinent to a situation in question
c: anecdote; especially : an amusing one

It isn’t exactly thrilling when described that way.

Stories are really about emotions. We make connections with characters when we get excited, feel sympathy, or draw inspiration.† It’s these emotional highs and lows that cause us to walk away saying – “That was an incredible story!”.

We all prefer particular emotions over others, of course. Personally, I look to find inspiration in tragedy – Moulin Rouge was simultaneously the most painful tragic love story I’ve every seen, and also the most uplifting and hopeful.

We find these points of contact in movies and books, as well as poetry and song. Oddly, though, they seem conspicuously absent from mainstream video games. So why is it, then, that video games deliberately shy away from emotional content? Clearly this isn’t true of all video games – Silent Hill 2 has possibly the deepest and hardest hitting story I’ve come across in any media – but most popular games don’t even reach out for it. Even the most trite movie tries to touch its viewers in this way, while almost all mainstream games run on hollow adrenaline.

Perhaps game studios are afraid of starting a relationship? We all have that fear when trying to make an emotional connection – we go out on a ledge, try to share something meaningful, but risk being rejected. It’s much easier to just be friends, and not try to forge a unique bond with someone. Likewise, game studios are happier just being ‘fun’ games, than stepping out on that ledge and trying to make a connection. After all, in their situation, being friends is just as profitable.

Having that emotional connection, though, means you have an opportunity.† It is an opportunity to change the course of that person’s life; with it, you can grant them insight, forge new memories, or inspire them to greatness.

We created Prophetic Sky because, at our hearts, we’re aware of our basic human desire to make connections: to make a difference in the world around us. We choose to risk rejection because a meaningful relationship with a player can actually impact their lives. At the end of the day, we want to look at what we’ve made of our lives and done with our work, and see that the world has changed for it.

A year ago we released Townrs Defender, a hero defense game, to the public. It earned a very passionate user base – but what amazed us most was how many people loved the very simple story we used to introduce the game! So, we decided to take on a bold endeavor – merge an extensive story with the popular gameplay of Tower Defense! This may not seem like the most natural of compatriots, but then – we’ve always forged our own path. As we thought about what kind of story would fit around this concept, pieces started falling into place, one after the other. At the end, we knew we had a story that had to be told. We called it ‘Spires‘.

The protagonists of Spires are known as Makers, sorcerers who can conjure physical objects out of thin air. You will step in to the role of three students, under the tutorledge of the wise, but old, Iaro. Iaro is from a forgotten age when Makers were prolific – but then the Dark Maker Draelus struck, seeking to kill them all. Draelus’s plan was noble, if misguided – mankind had become complacent and lazy under the leadership of such powerful sorcerers, wanting for – and seeking – nothing. By eliminating the Makers, Draelus sought to free the world. Eventually, after many Makers were killed, the remaining three defeated Draelus, and imprisoned him in the Hollow Realm – a barren realm of nothingness. Iaro, seeking his own solution to the problem, founded a great university where Makers would be taught how to aid – but not rule – their fellow citizens.

For many years, the world has been at peace. But all that is about to change. A giant army, led by a mysterious woman, is about to surprise our young heroes. They will have to learn how to summon more powerful spires, and use great strategy to defeat them. Only then, perhaps, can they try to discover the oncoming darkness’s true intentions…

iOS Development Optimizations Part 5 – Referencing Entities

Closed

For the next couple articles I’m going to get a little bit more technical, and start delving down into the murky depths of our game engine.

If you’ve done any development for OS X or iOS, you know that apple’s preferred language is Objective-C. †Their top-level frameworks and APIs all use Objective-C to interface and, while many parts are†achievable†from simple C, it’s not what I would call “a fun time”.

Fortunately, Objective-C itself has become a lot nicer about interacting with other languages over the years. †At this point, you can actually intermix C++ and Objective-C in an inspirationally named language called Objective-C++. †We use C++ internally for the majority of our projects, so for our game engine we use a very thin Objective-C wrapper for the out-of-game UI (the menu system, basically) and then jump right into C++.

We use C++ internally in the engine for a few reasons:

  • Familiarity – most of our other projects are written in C++, and it’s the language we’re most familiar with as a team.
  • Type-safety – this is somewhat of a personal preference, but C++ allows me to detect far more errors at compile time than Objective-C does.
  • Portability – an engine written in C++ using OpenGL can actually run on most OSes, including Windows, OS X, and Linux. †Sadly, from my investigation it looks like it’s still not quite workable for Android. †And Windows Phone (which I actually love, btw, but that’s another post) disallows ‘native’ code entirely.

There are a number of popular techniques for referencing entities in a game engine. †There are two big issues to tackle in any solution – object lifetime, and serialization. †Object lifetime is a†particularly†tricky issue – if you try to access an object that has already been destroyed, you’ll at best cause a crash, and at worst corrupt your data. †Serialization is the process of ‘saving the game’, such that any reference to an entity (for example, what enemy a spell is targeting) can be restored when loading from disk.

The first solution we considered was having a master list of entities at the engine level, and handing out IDs unique to each entity. †If you wanted to store a reference, you’d actually store the ID instead, and whenever you needed to access the entity you’d †ask the engine to find it for you. †Usually the engine will store this list as a dictionary of some kind – a hash table, or binary tree. †If the entity you’re asking for has already been destroyed — perhaps the enemy was killed before the spell finished executing, for example — then the engine will return a†sentinel†value (NULL in our case) which you’ll need to remember to check for.

The downside is that any access entails a lookup cost, and that you need to remember to check for dead entities. †The big advantage is that this method is very easily serialized – just write the ID number out to disk along side the entity.

The second solution, and the one we ended up implementing, was smart pointers that reference count objects. †One huge point in favor of this solution is that a library we were already using, boost, provides all of the infrastructure in the form of shared_ptr and weak_ptr.

Reference counting, in a nutshell, wraps an object with a container that counts how many references exist to the object. †Every time a reference is made, the count goes up. †When the reference goes away, the count goes down. †If the count reaches zero — no one at all references the object — we can destroy the object safely. †A special kind of smart pointer called a weak pointer maintains a reference without changing the count. †Weak pointers allow us to say ‘hey, I want to use this object as long as it is alive, but go ahead and destroy it if no one else wants it’. †An example is an entity’s ‘target’ – you want to know who your target is, but allow it to die if someone else kills it.

There’s a different kind of overhead to this method. †Rather than a lookup at access time, there’s a reference count increase whenever a new reference is made to that entity, and decreased when that reference goes away. †Initially, it seemed that this performance cost was far too significant to ever consider this method; fortunately, we discovered a few ways to reduce the cost until it was†negligible.

  • The iPhone threading performance means single-threaded access is better, so we removed all atomic actions and thread-safety from boost. †This cut down on 99% of the cost.
  • We pass constant references around, rather than copying the reference every time.
  • For very tight loops where we know the lifetime behavior, we can cheat and get the raw pointer out of the smart pointer and use that. †This is dangerous, and counter to the entire point of the solution, but we ended up using it in the inner rendering loop.

Strong pointers guarantee that the reference exists and is still alive, but weak pointers may point to dead entities. †However, in order to use a weak pointer you must convert it to a strong pointer – which is a huge reminder that hey, you should probably check to make sure the entity is actually alive before using it!

Smart pointers don’t help with serialization at all, sadly. †Our fix was to add IDs to objects as they are written to disk, and convert all references to these IDs. †Then we can load objects along with their IDs later, and restore the smart pointers then.

iOS Development Optimizations Part 4 – Pathfinding

Closed

Tower Defense and Hero Defense are actually quite different in terms of pathfinding. For Hero Defense, we had to statically create a nav-mesh at design time, and all of our entities – player and foe alike – navigated it using A* at both the high level and the local level. Since we had so many separate entities moving to so many different targets, the mesh needed to be able to reach the entire map, and the entities would have to calculate their exact path on the fly.

For Tower Defense though, the possible paths are constantly – and drastically changed. Players create mazes using their buildings, cutting off certain openings and creating intricate side lanes. The nav mesh was useless, and A* was pretty much in its worst case scenario. The one advantage we did have was that every moving entity on the screen was heading towards the same destination – the resource the player is trying to protect!

Very helpful, thanks...

The best solution we found is also the simplest. We flood-fill out from the resource building to every square on the map it can reach. The maps are reasonably sized – roughly 20×40 squares – so flood filling the entire thing takes a fraction of a frame. If we had to do this for every enemy, or for many resource buildings, it would add up and cause a significant penalty. However, one flood fill will find the optimal path for any entity on the screen, no matter where it is! We also only need to update this when a tower is built. Ok, that’s a bit of a lie, because there’s one painful situation exposed here.

All paths lead to the roman looking building

Players can create mazes as long as they want in our game – but at all times, the enemies must be able to reach their target. We simply don’t let them place towers where they would permanently block all paths. This means that whenever a player drags a tower out, we need to recalculate the paths for every square they drag the tower over, so we can give feedback when the path is blocked.

Now that's just not fair...

Still, since each flood fill takes less than a frame, and checking for a blocking build is easy (does each entity have a path to the goal or not?), this painful situation is… tolerable. I had intended to implement a predictive solver for the background thread, which would monitor the user’s drag motion and attempt to pre-solve for squares it might end up in. Fortunately, play testing revealed this wasn’t necessary, as the delay was unnoticeable. Concrete data to the rescue again!

iOS Development Optimizations Part 2 – Map Design

Closed

The key to having great content is having great tools.

Well, that, talent, and dedication.

We do have a great map editor that we use for our level design, though. †Not only does a custom-built tool make designing our levels much easier, it allowed me another opportunity to apply some optimizations.

A Scene in our Editor

For Townrs Defender, we developed the designer on the principle of re-use – if we could repeat the same texture multiple times across the map, we’d get a ton of savings in texture memory. †So, the background was composed of tiles that could be laid out like dominos. †Likewise, trees were many many instances of the same few tree sprites.

We had fallen into a trap, a trap everyone falls into at some point: Premature Optimization. †Strictly speaking, I suppose, this wasn’t premature–just mis-targeted. †You see, this time around I took some measurements and tested some theories. †It turned out that the scene overdraw–rendering a tree, then another one in front of it in the same place, for example–was the biggest performance killer for us.

Scene image on left, overdraw visualization on right

Because all of our sprites are alpha-blended, we necessarily have to render them back-to-front in sorted order. †This is a worst case scenario then, because for any sample pixel, we may:

  • Render the background tile (the ground)
  • Render a background widget (a flower, for example)
  • Render a tree
  • Render another tree that is in front of the first
  • Render a character
  • Render any spell effects (flames, arrows, etc)

This was terrible! †We needed to review our thought process.

  • The idea of tileable terrain grew out of our original design for terrain that could go on forever. †You could walk from one map to the next, for example. †That wasn’t even remotely true anymore.
  • Instancing the trees was supposed to save on texture memory. †Well, it did – very minutely. †Using a variety of widgets ate into those savings, and even worse, it cramped our design decisions: using a new widget would eat up valuable texture space, so we’d almost always choose to re-use an already placed widget than use a new one. †This made some of Townrs Defender look repetitive and homogenous.

Knowing now that this often hurt, rather than helped, we looked at it from another perspective. †What if, no matter how many widgets or background tiles we used, the texture space remained constant? †What if we could reduce the overdraw down to four or even three passes? How could we possibly achieve that?

In the end, it was simple. †Each level is rendered out as its own texture. †True, that means each level has its own dedicated texture, but only one is loaded at a time. † Disk space is cheap compared to resident memory. †Now, we couldn’t actually render out everything into one texture–characters have to be able to walk behind trees, after all. †So after saving out the ‘background’ of the map, we now go through and render out horizontal stripes of widgets, and save them one big texture atlas. †There is some fidelity lost here–all widgets act as if they were in the center of the stripe, so some gradations of depth are lost. †But, for the purposes of a small screen on an iPhone, it worked fine.

Background Texture for Level 1

A Foreground Widget Atlas

Our render pass was now more likely:

  • Render the background texture
  • Render the foreground pseudo-widget
  • Render a character

An added benefit was that there were now far far less texture changes, because 90% of our objects on the screen (somewhere in the hundreds) were now 15 objects. †Our frame rate actually more than doubled. †It also helped for memory budgeting–rather than an unknown number of textures, each level had a set cost that we could account for. And, much to the relief of our map designers, they were now free to use as many and as varied widgets in any level as their heart could desire.

And players benefit in-game too: where Townrs Defender could only put 15 enemies on screen at a time, Spires can render closer to 50!

Gauntlet mode pits you against a massive wave of enemies.

Since I originally wrote this article, Spires has actually been published on iTunes – so if you want to check out the engine performance yourself, go pick it up!

iOS Development Optimizations Part 1 – Sprite Engine

Closed

In the time between Townrs Defender and Spires, I had the opportunity to rework the sprite engine to optimize performance in many ways. †You may remember that Townrs Defender had a number of, in particular, memory issues – on older devices it would frequently have to disable music to guarantee it would run. †So, memory usage was something I wanted to focus on for our version 2 of the engine.

One very common optimization, used in both 3d and 2d engines, is called atlasing. †Every texture change the render makes has overhead, so atlasing takes a series of textures and combines them into one big texture, on the assumption that if there are less textures, you’ll need to change them less frequently.

Sprite Sheet for an American Hero

Sprite Sheet for an American Hero

This is a great optimization, and very easy to parse – take the frame number you want, and treat it like an index into the image as a 2D array. †Creating it is as simple as downloading ImageMagick and running the ‘montage’ command from the commandline.

But †all that white space is a bummer, huh? †File compression will collapse a lot of it, but we have to expand the whole file and keep it in memory eventually. †We can try to crop the spite more tightly, but we’d always be limited by the largest sprite – an outstretched limb could wreck everything! †You can see it in this image alone – the sprites at the top where our mystery hero is running upward are much thinner then the ones at the bottom, where he runs sideways.

Well, I’m a programmer, so my fix is to write a new tool!

All we have to do is crop each individual sprite as tightly as we can, but when we do so, we have to remember how much we cropped from each side.

Our Hero Cropped Tightly

This allows us to push in from each side of the image without worrying about the center point of the image – by recording the edge offsets, we can re-align the sprite in-game with its original center point.

If we don’t record this information, the final sprite will bob around crazily!

Top-Left Aligned Sprite

Correctly Centered Sprite

Once we’ve cropped each sprite as tightly as we can, it’s time to pack them all together. †2D packing is a topic that has been extensively researched and implemented. †From my quick research and prototyping is seems that – at least for our rather simple ‘aligned rectangles packed within a square’ situation – a simple greedy algorithm gets us about 90% optimization. †Advanced algorithms can certainly boost that higher, but tend to take exponentially longer to run.

The result is quite nice. †Rather than using up a portion of a 1024×1024 sheet though, it makes more sense to split it into two 512×512 sheets:

Packed Sprite Sheet 1

Packed Sprite Sheet 2

1024 x 1024 sheet = 1048576 pixels

512x512x2 = 524288†pixels

That’s a 50% savings off the bat – and as you can see, we even have some leftover space to stuff more sprites into!

Tools of the Trade

Closed
Hero Character in Blender

Hero Character in Blender

Once weíd figured out our implementation details, we needed to pick the tools to get us there. We quickly determined that Blender was well suited to our needs.† Blender is an open source modeling program, whose abilities span modeling to video editing to being an entire game engine.† It has most of the features of 3dsmax or Maya, all of the useful ones, and many more to boot.† Of course, the fact that itís free helps a great deal.† But honestly, out of all of the open source alternatives Iíve tried over the years (Gimp, Open-office, Thunderbird) Blender is the model of ìgetting it rightî (Alongside, perhaps, Firefox).

Particle Effect in Blender

Particle Effect in Blender

Our modeling and rigging is done in Blender, and textures are created in Photoshop.† From there, we render out a series of individual frames in the standard 8 directions to a PNG format.† We then use ImageMagick, a command-line tool that comprises a lot of the functionality of Gimp or Photoshop.† ImageMagick gives us the ability to run batch manipulations on the images, and compose them together in interesting ways.

From the resulting PNG format, we compress to PVR, using appleís texturetool program.† PVR is an interesting format; in a nutshell, itís a highly regular compressed image format that can use either 4 bits or 2 bits to represent pixels.† The huge advantage to this format is that the iPhone supports it natively, and can render directly from the compressed format.† We found that PNGs didnít work because a) decompressing the PNG format takes up a ton of CPU time and b) when uncompressed, a 1024×1024 image will be stored at its native size of 4MB.† When you only have 20MB or so to work with, thatís pretty limiting.† For comparison, a 4bpp PVR of the same image is only 512kb ñ yes, thatís 1/8th the size.† However, for small images the compression artifacts become very noticeable, so for those we actually double the resolution of the initial images.† For those keeping track, the compressed double-resolution image is still only ? the size of the original resolution uncompressed image.

BlenderNation also has a quick writeup on us.

Investigation and iPhone Limitations

Closed

Weíve had a lot of requests for insight into our toolset and development process here at Prophetic Sky, so I thought Iíd write a few entries to summarize some of what we do here. Weíre typically a Windows/Linux workshop, and so we had to make a few adjustments to work on an OSX platform for iPhone development. Fortunately, OSX overlaps a great deal with Linux, and we tend to use a lot of great open source tools.

There arenít a lot of real statistics for the performance of the iPhone out there, but you can get a rough feel for it by just looking at the existing games out there. Our tests let us to conclude that 3000 triangles/second was a good maximum (weíve read 6000, but couldnít reproduce that to be comfortable with it). Even assuming our physics, game logic, AI and special effects didnít eat into that time at all, if we wanted to fit 20 characters on the screen at once, each character had to be 150 triangles or less. Thatís not terrible; many games run with those limitations. But once you realize you still have to fit terrain, trees, towers, walls and spell effects in there, it starts to become very cramped.

Nova Spell

Better detail, but less flexibility

So we turned to sprite assets. There are many advantages to sprites ñ namely that 3000 triangles equates to 1500 sprites on the screen at a time. Also, we can render the characters in much higher detail initially, from source models in the thousands of triangles. The feedback that weíve gotten on the game leads us to believe that this was the right choice; universally we hear that the game looks beautiful.

There were drawbacks, as well. While we arenít limited by the rendering power of the iPhone, we are limited by the available memory, and sprites take up a lot of space. In addition, it means our art is limited to running at a fixed frame rate, and in fixed directions ñ the characters can only run in one of the 8 standard directions, for example. Also, we cannot change the perspective ñ moving the camera will just show that the sprites are flat.