So this last weekend I was bored. I could have played any number of video games (including my recently acquired copy of Wario Land 2 ), but instead found myself reading instruction manuals for instructions (CPU instructions that is).

On a number of occasions I’ve found myself looking into ways to better optimize Chipmunk specifically for iOS devices. A few years ago I spent a bunch of time looking into the VFP (the vector math extensions) for the original iPhone and iPod friends. VFP was the SIMD (Single Instruction Multiple Data) instruction set supported by the ARM 6 hardware. The idea is that instead of adding up numbers one at a time, you put them into a vector and add (multiply, divide, etc) them up 2 or more at a time and be 2 or more times faster! Nice idea, not so great implementation. VFP’s big letdown was that it didn’t really make anything 2 or more times faster. It just sort of uses less instructions and is a little bit faster. The really big problem is that in order to get “a little bit faster” you have to write a lot of assembly code, and you have have to do it just right or it will end up being slower than the compiler generated code anyway. Generally people stuck to using VFP for implementing things that were straightforward and well ordered like matrix math or particle effects. Trying to use VFP to optimize Chipmunk seemed like a colossal waste of time.

Now enter the 3GS with it’s shiny new ARM 7 CPU. It has a fancy new vector unit called NEON. Unlike VFP, with NEON you can process a vector of two floats in the same amount of time as applying the same operation to a single float. Also, because NEON uses ordinary instructions without needing to set extra state in the CPU, the compiler provides “intrinsics”. Basically, these are functions that map more or less directly onto the instructions the CPU provides. That way you can let the compiler allocate registers for your variables and move your data into and out of memory, and pack and unpack vectors while you just write the math. There is still one problem though. You can’t just switch back and forth between vectors and scalars whenever it’s convenient. Simply replacing Chipmunks vector operators (cpvadd, cpvsub, etc) with NEON intrinsics (vadd_f32, vsub_f32, etc) works, but the performance is awful (I tried it…). The problem is, despite being a vector instruction set, it doesn’t cover a lot of vector algebra (dot or cross products, etc.) because it’s designed to be simple to implement in silicon. This basically leaves you to do some of the compiler’s work and figure out how to rewrite the code onto the limited vector instruction set.

I’ve actually made several attempts to speed Chipmunk up using NEON now. It’s sort of demoralizing to spend hours rewriting a chunk of code to be more complicated only to have it run slower. Ugh! The first time I simply tried replacing the individual vector functions (cpvadd, cpvmult, cpvdot, etc) and seeing what happened. It was a lot slower. The problem was that all the rest of the code didn’t use NEON vectors, and some operations (such as cpvdot or cpvcross) couldn’t be written to use NEON efficiently. So it ended up spending more time packing and unpacking vectors than it ever saved by processing two numbers at a time. Months later I tried rewriting only cpArbiterApplyImpulse() to be vectorized. In most Chipmunk programs, half or more of the CPU time of everything used by Chipmunk is spent in cpArbiterApplyImpulse() so it’s a good candidate for optimizations and has already been the target of a half dozen passes. After hours of tracking down new bugs that I had made, it just ran slightly slower again. Ugh… The problem was that I hadn’t gone all in. I only tried to vectorize the parts that were easy and still avoided things like dot products and all the fancier operations that I really needed to be able to use. So I was still doing a bunch of unnecessary packing/unpacking. The general trick to get around that is to do something like process two pixels at a time instead of trying to process one pixel twice as fast. Unfortunately, while it’s easy with pixels, I couldn’t really do that when processing contacts because it was just too complicated to set up in a sequential solver.

This time I decided I was going to do the whole function (or just give up). Several of the key vector operations that I needed didn’t map onto the instruction set and processing two contacts at once was too complicated. I needed to do something else and realized that I had a third option, why not just rearrange a bunch of math so that I can perform two unrelated dot products or cross products (or whatever) at the same time? When it’s not possible to pair two operations up, just continue processing as a vector anyway and throw away the unused component at the end instead of unpacking several vectors along the way. So I spent an evening turning the 30 lines of fairly readable code into 90 fairly unreadable ones. The best case scenario is that you can double the speed of a piece of code if it maps perfectly onto the vector instructions. Realistically I was expecting maybe a 10 or 15% speedup due to some inevitable packing/unpacking costs and a few places where I had to waste some of the calculations. Instead I got a 40% speedup. Not bad at all! Running the benchmark demos I have, I found that it was a 19% average speedup *overall*! The demos that had a lot of stacked objects were as much as 30-35% faster. The best part is that unlike multithreading, there is 0 overhead and it works on 95% of the iOS devices out there. You can leave it on all the time for any sort of simulation and it will always make things faster.

This is all very exciting and whatnot, but when will it see the light of day, right? Expect it to be available as part of Chipmunk Pro very soon when I release 6.0.3 (along with properly integrated AutoGeometry). You might also be glad to hear that I’ve made the Git repository for Chipmunk Pro to be readable by our customers. That way when I work on improvements like this or need to fix a bug, you can always pull and use the latest without having to wait for the next release. If you have bought Chipmunk Pro and want a free performance boost _right now_, all you have to do is pull from the repository, build it, and replace ChipmunkSpace with ChipmunkHastySpace (or cpHastySpace if you are using the C API).

To check out Chipmunk Pro from git run this, substituting in your own Chipmunk Pro login name and password.
git clone --recursive http://myLogin@chipmunk-physics.net/release/chipmunkPro/ChipmunkPro.git

From there you can just run the iphonestatic.command script (double click or run on the command line with ruby iphonestatic.command) and copy out the ChipmunkPro-iPhone directory into your project.

While Andy was working on Leader of Mans, Scott joined forces with Max Williams to create Your Story.

Just another day at the office? Not so! Your career takes a sudden plummet as you get promoted to a position deep underground.

Your Story is a 2D platformer with a retro style.

Max finished and posted the Your Story postmortem as well. Here’s a playthrough video. Watch out for spoilers, although if you can’t play the game on a Mac, at least you’ll get to see it!

Leader of Mans Postmortem

A big thanks to everyone who voted for Leader of Mans in uDevGames. I was awarded 2nd place in the ‘overall’ category!

Leader of Mans was my uDevGames 2011 entry. I wanted to create something that felt a bit unique- LOM is a construction based rts-like game that is a bit difficult to place squarely in a single genre. Gameplay focuses around developing resources and constructing settlements, but Leader of Mans also directs you to explore your varied surroundings and overcome challenges.

Leader of Mans was sort of an experiment for me; When I started, I didn’t have a really specific picture of how the game would play. The goals of a score based arcade style game have some pretty direct goals, and I wanted to try something a little different. I think a driving force was to make unique challenges on each island, and to make advancing to each island feel like a new experience, while retaining what you’ve lovingly constructed on previous islands. I have a lot more ideas and plot I could add, but I think what I’ve got is pretty satisfying as a complete experience.

Original Design

One reason I struggled initially with gameplay, is because I wanted to make the game multiplayer. I used my knowledge from my previous uDevGames entry, Reclaimed to write a fully networked game, featuring fancy stuff like client side prediction and latency reduction code. That was working pretty well, until I realized interacting with other players within the context of the gameplay didn’t really make a lot of sense. I was hoping for a cooperative environment, but exploring and unlocking content wasn’t really suited to multiple players sharing a world.

So I figured I’d save some time and I dropped multiplayer support, and instead focused on plot and progression elements.

What Went Right

Tool Choice

I used tools I was familiar with, and I leveraged my codebase from my previous contest game, using the networking code, the UI library I wrote, and enhancing the rendering engine. I used some neat new techniques to dynamically generate terrain and plugged in code for a non-tile based engine. I was able to work much faster in my own code, even though I am familiar with tools like Unity, which Scott and I use in our day job. It’s nice to use the contest as an opportunity to get away from ‘work’ games.

No menus or crazy UI

While I slowly figured out how the game was supposed to work, I constantly examined how the user interface would work for the game. As I considered how constructing a building worked, I was very conscious of implementing it in a way that was fun on it’s own, and unobtrusive. Reclaimed approached this problem with large sets of menus. Constructing an item in Reclaimed meant scrolling through a list of 80 possible items. Adding filtering makes it easier, but further complicates the UI. I wanted all interactions in Leader of Mans to happen without opening a menu or an in-game window.

I think keeping a simple UI kept the game approachable and fun. Working out the gameplay like this surprisingly difficult, but it feel it was a big success. When you see a simple detail implemented in game, it seems obvious and trivial, but it often took a lot of thought and iteration to get that point.

Friends!

Since I didn’t really have a clear picture of the game when I started, it was easy to get myself stuck in a rut. At that point, I turned to my friends in iDevGames and asked for some ideas. A huge thanks to Scott, Seth, Alex, Keith, Neil, and everyone else in the channel for sending me ideas! And thanks to those who send feedback to the Leader of Mans forum thread. The unique use of the word ‘mans’ came out of a IRC discussion, and Seth produced the excellent bear artwork. My wife, Beth, was very supportive. On night before submission she stayed up late and drew the dead trees used on the last island. Thanks hun!

Getting feedback and ideas really energized me. Those were the nights I stayed up late, plowing through features without realizing how quickly the time was passing!

What Went Wrong

Oops, I forgot to blog!

We’ve got a blog at Howling Moon Software… and if you read it, you would think we only did one interesting thing every 3 months! Unfortunately, when we’re doing something exciting, sharing it on our blog isn’t a high priority. When we do think about making a post, we’re usually working on a client project that’s covered under NDA.

What Went Okay

No Clear Initial Idea

I’m actually pretty happy with how things worked out despite not having a clear idea of what I wanted. It took extra time, but I’m happy with how iterating the gameplay turned out. I figured this could be a recipe for disaster, but it worked out alright.

My first few weeks of programming all ensured a working multiplayer experience. I dropped this when I realized I had no idea how the game would play in a multiple player environment. Although it did add up to some lost time, I made the decision early enough to still be able to pull together a finished game.

Development time

Scott and I actually set aside some time for working on our uDevGames contest entries. Since many of my evenings are scheduled with my wife and our new house, it’s difficult to find time (and energy!) for programming in the evening after a full day of game programming. So I got a week or so of work done early in the contest, but then additional important work showed up from clients. I managed to eek out most of the last week to really throw the game together. It could have been worse, but it’s always hard to schedule time exactly.

Conclusions

I learned a lot since my entry in uDevGames 2008. I had a better idea of what would work well in the contest, and I’m very happy to be awarded the second place overall award. I think Leader of Mans pulled together nicely- I did manage to get some of the important polish in, like nice sounds, music, and some graphical effects. I spent a lot of time improving the interface and controls, although there’s still a few more things I would have liked to get to. Leader of Mans was very very close to several other awards, so next time I’ll need to give it a little extra oomph to get it up into third place in each category!

• Developer: Andy Korth
• Title: Leader of Mans
• Team Size: 1
• Hardware: Mac Pro, Macbook
• Critical Software: Eclipse IDE, Photoshop, Amadeus Pro, Pedegree particle dohicky, Heiro font thingy
• SDKS & APIs: Slick library, OpenGL, homegrown code

“All of creation is at your fingertips. Your mans look to you for guidance. Lead them to greatness.”

Leader of Mans was my entry for the uDevGames contest. uDevGames is the big Mac game development contest. It’s a multi-month contest with very few restrictions, just make a game and share it!

Leader of Mans was sort of an experiment for me; the game ended up being an interesting exploration based RTS god-game. I had a lot of fun putting it together and figuring out where I wanted to take it. I think a driving force was to make unique challeneges on each island. and to make advancing to each island feel like a new experience, while retaining what you’ve lovingly constructed on previous islands. I have a lot more ideas and plot I could add, but I think what I’ve got is pretty satisfying as a complete experience.

Leader of Mans got a fantastic review that walks you through the game and has some great screenshots.

Download and Play: Leader of Mans

Scott has posted a new screencast of the latest automatic geometry generation. Here we demonstrate how creating a level in your game can be as simple as painting the mask in Photoshop. This new automatic geometry generation code is included in Chipmunk Pro.

Scott also demonstrates other ways to use the autogeneration code. It can dynamically generate terrain using something like a noise function- or any other sampling function you supply for the generator.

Live updating is also demonstrated; changes to terrain while a game is running can be processed well under one ms, and makes bitmap backed levels trivial to create. (Think of games like the Worms series or the Scorched Earth genre.)

On Tuesday Scott gave a talk to the Twin Cities iPhone Development group about Chipmunk.

The talk went great, although the projector wasn’t very clear. If you were at the talk and wanted to see the video, check it out on youtube:

Chipmunk Physics on Youtube

And we’ve also got a copy of Scott’s Chipmunk presentation.

We’ve already had a few people who were at the meeting follow up with questions and interest in Chipmunk. If you haven’t done so yet, download the latest chipmunk and check out the demos!

On the heels of our new web page, we’ve released Chipmunk 6.0! Our press release follows:

Howling Moon Software is excited to share Chipmunk 6.0, the latest major version release of their popular physics engine. Chipmunk is a high performance, MIT licensed 2D physics library with all the fixings. Written in C99, bindings and ports exist to over a dozen languages. Including an official binding to Objective-C that makes it fit right in on the iPhone. Chipmunk has recently been seen in many top iOS hits, including Cars 2, Feed Me Oil, I Dig It, Alice in New York, and Zombie Smash! It’s been used on many platforms including Mac/Win/Linux, iPhone, Android, Symbian, DS, PSP, and even the Wii.

We’ve also released Chipmunk Pro, a library with extra features that can dramatically speed development. Chipmunk Pro features an Objective-C binding with additional iPhone specific features to ease things like input handling. Push the envelope with new beta features like multicore support and automatic generation of terrain and geometry based on images.

New features in Chipmunk 6 include many API improvements to aid the clarity and ease of using the engine. Chipmunk 6 now supports multiple spatial indexes and includes a bounding box tree which doesn’t need tuning. Support for variable timesteps and release-mode error handling has also improved.  Chipmunk 6 comes right behind Chipmunk 5.4.3, which featured numerous bug fixes.

New in Chipmunk 6.0:

* API: Chipmunk now has hard runtime assertions that aren’t disabled in release mode for many error conditions. Most people have been using release builds of Chipmunk during development and were missing out on very important error checking.
* API: Access to the private API has been disabled by default now and much of the private API has changed. I’ve added official APIs for all the uses of the private API I knew of.
* API: Added accessor functions for every property on every type. As Chipmunk’s complexity has grown, it’s become more difficult to ignore accessors. You are encouraged to use them, but are not required to.
* API: Added cpSpaceEachBody() and cpSpaceEachShape() to iterate bodies/shapes in a space.
* API: Added cpSpaceReindexShapesForBody() to reindex all the shapes attached to a particular body.
* API: Added a ‘data’ pointer to spaces now too.
* API: cpSpace.staticBody is a pointer to the static body instead of a static reference.
* API: The globals cp_bias_coef, cp_collision_slop, cp_contact_persistence have been moved to properties of a space. (collisionBias, collisionSlop, collisionPersistence respectively)
* API: Added cpBodyActivateStatic() to wake up bodies touching a static body with an optional shape filter parameter.
* API: Added cpBodyEachShape() and cpBodyEachConstraint() iterators to iterate the active shapes/constraints attached to a body.
* API: Added cpBodyEeachArbiter() to iterate the collision pairs a body is involved in. This makes it easy to perform grounding checks or find how much collision force is being applied to an object.
* API: The error correction applied by the collision bias and joint bias is now timestep independent and the units have completely changed.
* FIX: Units of damping for springs are correct regardless of the number of iterations. Previously they were only correct if you had 1 or 2 iterations.
* MISC: Numerous changes to help make Chipmunk work better with variable timesteps. Use of constant timesteps is still highly recommended, but it is now easier to change the time scale without introducing artifacts.
* MISC: Performance! Chipmunk 6 should be way faster than Chipmunk 5 for almost any game.
* MISC: Chipmunk supports multiple spatial indexes and uses a bounding box tree similar to the one found in the Bullet physics library by default. This should provide much better performance for scenes with objects of differening size and works without any tuning for any scale.

Chipmunk Physics is especially popular on iOS devices, and we look forward to seeing even more great games using Chipmunk Physics. Chipmunk is open source, licensed under the MIT License. Basic Chipmunk is free to use, and Chipmunk Pro is available for $200. Howling Moon Software also takes donations to support Chipmunk development and offers contract development services.

The Chipmunk Physics engine now finally has it’s own web page!

http://chipmunk-physics.net/

It’s been a long time coming, but now all chipmunk-related information is on the same web page. Previously we had documentation, downloads, and the forums scattered across different pages. But Chipmunk has been steadily growing, and the time came for it to have a proper page.

We’ve had a lot of high profile games use Chipmunk recently, including the last few #1 iOS games:

Feed Me Oil uses Chipmunk for the non-fluid physics simulation bits. It was the number one game just a week or so ago. Now Cars 2 has hit number one on the store- it also uses chipmunk for it’s side scroller racing action.

Times are good for developers using Chipmunk!

Well, it’s taken longer than we expected, but Upshot is now in the Mac App Store!

Share the link with your friends! I’ve just started a sale- reducing the price to $8.99.

http://bit.ly/jFIZ2P

Upshot is basically a program we created for ourselves. Scott and I need to share screenshots of our work easily and quickly. The ability to send a screenshot of what you’re working on to someone else instantly can really improve your workflow. We realized others would appreciate this sort of sharing, so we converted our quick-and-dirty scripts to a fully fledged application.

It took a few tries before Upshot was accepted into the store. We had to make a few changes regarding how Upshot’s “Launch Application on Startup” functionality worked. We also had to replace some frameworks that made private API calls. Sometimes it’s tough to play by Apple’s rules, but we’re hoping to see at least enough sales to make up for the couple days spent updating the app for the Mac App Store.

Sixty dollars- Cash! Thanks to Valve for the picture that perfectly captures our situation.

If you’ve been wondering where we’ve been for the last few months, we were working on a big Unity contract. Now we are moving on to our big backlog of new projects that we’ve had waiting for us.

First, we’re taking the opportunity to do some work on Chipmunk. Chipmunk 6 will be coming out soon- and it’s got a bunch of great new features and improvements. We’re also looking at some possibilities around interactive books. And finally, we’ve updated our contracting page.

We’ve got a lot more planned in the next upcoming months, so expect more frequent blog posts. Sorry for the dry spells while we’re on big contracts- they tend to be covered by pretty strict NDAs.