A selection of open source libs

September 26, 2010 3 comments

Hi everyone,

After my post last week mentioning Speex, Wavpack and Vorbis I had a request for more open source options that may be of interest (thanks @karnakgames) as I hinted at there being quite a lot of them.

This post is going to be a list of interesting libraries that are ones we have used or would consider using, I’ve missed off larger libs such as OGRE / Irrilicht as those include many features covered by our own multi-platform technology. That being said we do occasionally use alternative solutions for things we do support in our tech either as an experiment testing out other interfaces or if feature implementations for a particular project would be too much of a time/cost investment.

I’m sure I’ve forgotten plenty of quality libraries and snippets so please post up in the comment and I’ll integrate those (plus any new ones I think of over the next few weeks!)

Audio/Video

  • Speex/Vorbis/Wavpack
  • Theora http://www.theora.org/
    • Another great package from the xiph.org group, this time a video codec that has become more and more popular the last few years. The encoders have steadily improved since we last used it and I believe it’s reasonably competitive with more popular codecs now (in terms of quality / bitrate) and has been mentioned in the news quite a bit this last year with the support for it in some browsers using the HTML5 video tag. It still has quite a way to go against h264 but it is a feasible solution depending on your video playback requirements.
  • Libsox (LGPL)  http://sox.sourceforge.net
    • A great set of audio manipulation routines as implemented by the command line tool ‘sox’

AI / Pathfinding

  • OpenSteer http://opensteer.sourceforge.net/
    • In the past when we’ve implemented boid systems we wrote our own based off Craig Reynolds work, OpenSteer is a library featuring implementations of the earlier steering behaviours and may be useful as an introduction


Physics

  • Open Dynamics Engine (ODE) http://ode.org/ode.html
    • This was a very popular open source physics engine (and still is though not maintained as much it seems), we’ve worked quite a bit with ODE in the past.
  • Bullet http://code.google.com/p/bullet/
    • The new leader of open source physics engines with as many features as commercially available solutions and an active community. We’ve not had chance to use it in a project yet but look forward to doing so.
  • Box2d http://www.box2d.org/
    • My favourite of the 2d physics engines, very simple to integrate into your code and it seems to be pretty solid.

UI related

  • FreeType2 http://www.freetype.org/index2.html
    • The very popular font engine, we’ve not used it in a project but have integrated it into some of our tools for the future. For completely dynamic font usage you could integrate this directly into your game for on the fly font generation.
  • Gameswf  http://tulrich.com/geekstuff/gameswf.html
    • Thatcher Ulrichs public domain library which I believe is still being maintained and has spawned many of the commercial Flash players / Flash based UI tools. This is something we played around with on internal projects many years ago and I’d love to look at again.
  • CEGUI http://www.cegui.org.uk/wiki/index.php/Main_Page
    • A GUI system which seems to be very popular, I’ve not looked at it in the past as I believe it was previously LGPL which is a bit of a scarier license when working on certain gaming platforms.
  • libRocket http://librocket.com/
    • Another interesting UI middleware package (based on HTML/CSS standards) I spotted the other day and will be investigating as an alternative to our existing UI solutions.
  • wxWidgets http://www.wxwidgets.org/
    • We tend to use wx for tool UI development whenever possible though WPF is certainly very tempting for Windows tool UI development now.

Scripting

  • Lua http://www.lua.org
    • One of the most popular scripting languages used for in-game scripting, we’ve used it on a few projects and are still massive fans. Early development was a lot tougher than it is now (having to write our own debugger!) but the community has really grown.
  • V8 http://code.google.com/p/v8/
    • Googles open source JavaScript engine, I’ve heard of a few people integrating this into their games. I’m not a massive JavaScript fan to be honest but I can see the appeal.
  • Python http://www.python.org/
    • A very popular language for tool development however many people also integrate into their games for scripting.

Networking

  • Libcurl http://curl.haxx.se/
    • The library beneath command line tool ‘curl’ which supports about everything you can imagine in terms of standard internet protocols – HTTP/FTP in particular and is very useful for interaction with web browsers across your cross-platform games.

Misc

  • Open Asset Import Library http://assimp.sourceforge.net/index.html
    • I came across this looking for some for a mesh import routine on a prototype project I was working on and flagged it as something to look into integrating with our tools. It seems to support a decent list of file format imports and mesh cleaning.
  • John Ratcliff’s Code Suppository  http://codesuppository.blogspot.com/
    • A range of useful snippets (and larger) varying from convex decomposition to mesh cleaning and micro memory allocators.
  • Boost  (http://www.boost.org/)
    • Not a library we use to be honest but very popular and for good reason especially in terms of useful code for tool development.

That’s all!

The above list is far from complete and I could have added quite a few more in each section, I’m sure I’ll kick myself over some of the ones I’ve missed.

Next week I’m actually away so I’ll be putting together the post in a few days and scheduling it, any requests are welcome for upcoming posts. We’re getting nearer to talking about our upcoming project releases which is very exciting for us.

Things we’ve been enjoying this week

  • Minecraft
    • I’m not going to link it as I’m not evil. I finally gave it a try and got sucked in!

Sound/Speech compression

September 18, 2010 1 comment

Hi all,

This week I’m going to talk a bit about some very useful open source libraries we’ve used in developing some of our past client projects. These have mainly been used on DS which is a little more restricted in terms of space than other platforms.

Sounds interesting!

Sound has been the main component of the projects I’m covering today, probably 60%-80% of the final size of the games was audio.

One of the titles consisted of 5 languages of speech audio data to playback during gameplay. We also have to deal with very little available RAM on the DS which means we can’t precache much information if any, and so data needs to be decompressed on the fly.

Looking at the English speech only for one of the titles we had 187,199,378bytes (178.5mb) of source data stored at a sampe rate of 44100hz with 16bit mono samples this was roughly 35 minutes of speech.

Storing speech at 44100hz is a little excessive to start with, the Nyquist-Shannon sampling theorem tells us that perfect reconstruction of a signal (a sound signal in this case) is possible as long as the sampling frequency used to represent it is possible when the sampling frequency is greater than twice the maximum frequency of the signal being sampled.

This means we can safely resample down based off the highest frequency in the sound, this can be automated in a tool so that we find the maximum frequency in the audio and then resample to twice that.

Speech tends to be 0-4000hz frequencies which is why most speech data is sampled at 8khz. Note this obviously doesn’t represent all possible sounds a person can make and is purely meant for speech which is why listening to music (or singing) down the phone doesn’t exactly sound great!

Our speech data is kind of stylised and we actually used a sampling rate of 11025hz. If we were just storing the data as raw PCM this would mean our data is 1/4 of the size (46,215,824bytes, 44.1mb for our data set) already but that’s not good enough for our needs.

ADPCM

This is an alternative compression method for audio data and is supported in hardware on many platforms (meaning lower in RAM storage overhead and no playback slowdown), the actual algorithm varies but most platforms use IMA ADPCM. Depending on the implementation the compression ratio varies but generally it’s 4:1 (another 1/4 of the data size!) note this is a fixed ratio compression and the same amount of data would be used to store a piece of silence in your audio data as it would to store the most ‘interesting’ data.

Most audio people I’ve worked with don’t really like ADPCM for general use, I’ve not really looked into how it fares in terms of comparing to the source sample but even I can hear some of the issues on certain sounds!

For our speech data 4:1 ADPCM would result in 11,553,956 bytes (11mb) of data at 11025hz.

Speex of the devil

There are some truly great open source / free software packages available and one of them is Speex from the same xiph.org who bring us Vorbis (mentioned briefly below) and Theora.

As you can probably guess from the name Speex is intended for speech compression and therefore won’t perform as well with none-speech data.

For our project we implemented a decoder thread that would when notified stream the compressed data from disc and decode either directly into a double buffered audio stream (i.e. direct to the sound hardware or the sound API) or into a decompressed buffer if the speech was going to be used a few times in that particular part of the game (to save decompressing the same sound over and over).

To give an idea on compression ratio using quality 5, complexity 1 on our 11025hz mono speech data we compressed all the data into only 4,401,832bytes (4.2mb). As you can see this is a massive saving on the original data! The quality is still very good. During development we produced a tool that we sent to testers to help them evaluate the various quality settings so we could find a good trade off on size/quality.

Wavpack

Briefly I want to mention WAVPACK this is a compression format we used for a really great but unfortunately unreleased project a few years ago.

This again was a DS title but this was featuring instrument samples and needed to be really high quality in terms of the quality achieved. WavPack produced some really impressive results for us and again worked very quick even on the DS CPU for both compression and decompression.

Vorbis

A final brief mention for another quality compression format from xiph.org this time Vorbis which is a very decent competitor for mp3 and doesn’t come with any associated licensing overhead or concerns. Again we use this for decompressing on the fly on PC and newer console hardware plus have used on iPhone on Aurifi


Thanks

Hopefully some of you are looking at reducing your games footprint and these libraries may be of use, even in terms of install size you could use the above methods to compress the files and then decompress on first load.

Things we’ve been enjoying this week

  • http://cbloomrants.blogspot.com/
    • Charles Bloom is posting at the moment about data compression challenges, it’s an area that fascinates me but I’ve never had chance to do much work in other than tinkering on the periphery. If you’ve not read his blog before it’s well worth looking into including some great posts on threading last year and many more before that – I’ve no idea how he gets so much time to write some really quality posts.

User Clip Plane sailing

September 11, 2010 No comments yet

Hi all!

A little bit of a shorter post this week from me and also a little bit more technical in content.

GL ES 2.0

One of our upcoming projects is going to be (currently at least!) 100% GL ES 2.0 based, I ported our engine over quite a while back but only recently started looking at anything more advanced than vertex colour diffuse * diffuse texture shaders being applied.

It’s been enjoyable working on graphics code again and like we’ve seen working with iPhone and new mobile platforms previously there are a lot of déjà vu moments from early PC/console days (or not so long ago if you’re also working on DS / Wii as we are!).

Clipped!

We’re using a reflection pass in the title and so need to clip along a certain plane (to prevent geometry below the reflection plane from appearing in a ghost like fashion when we render using the reflection texture).

User clip planes aren’t supported GL ES 2.0 so we had to work out which option was nicest to resolve this.

This was something we’d gotten round on an Xbox 1 title by calculating the distance from the current vertex position to the clip plane and then passing that value into the pixel (fragment) shader to be texkill’d (i.e. the pixel wouldn’t be rendered) if the interpolated distance value was less than 0.

Another method I’ve heard of (which would work on hardware without pixel shaders also) was using alpha testing in a similar way by passing the distance from the clip place as a 1D texture coordinate which then looks up into a simple clamped alpha texture, the alpha test in the fixed function hardware would then cull the pixel.

One other method which sprung to mind writing this article but haven’t thought about much (or tried) would be to render the plane into the z-buffer (i.e. with colour / alpha writes disabled) and let the zbuffer clip the rest of the geometry for us. (Apologies if this has a major flaw I’ve not considered yet!)

Oblique

One method I recalled from a Game Programming Gem book but had never used before was Oblique Near-plane clipping which was written by Eric Lengyel and he covers in the following slides from GDC (PPT PDF).

The projection matrix in the rendering pipeline projects your vertices from their camera/view space positions into clip space which are then divided through by w to give normalised device coordinates. Once projected valid geometry will exist between a near and far plane which is defined by the projection, the final primitives rendered are clipped to these planes (and the other side planes of clip space) by the graphics hardware (generally).

The technique takes advantage of this clipping by adjusting the near plane to be the same as a clip plane we specify. This effectively gives us free clipping against our own clip plane – as it’s part of the matrix multiplication already being done!

As described in the GDC slides the far plane has to be adjusted by the algorithm to contain the original view frustum fully and in doing so the z-buffer precision will likely be reduced due to increased distance between the new ‘near’ and far planes.

You can find a GL implementation of a function to transform a GL perspective projection matrix to clip a specified plane here

http://www.terathon.com/code/oblique.html

The code assumes the projection matrix being  modified is a perspective projection, Aras Pranckevičius wrote a post removing Erics optimisation based on that assumption and providing a generic version of the algorithm that will work for orthographic projections just as well.

If you’re working with DirectX it’s worth noting you’ll need to adjust the algorithm to project the z values from 0 – 1 rather than -1 to 1 as with OpenGL, you’ll need to change the the 2.0 divide in Erics to code to a 1.0 and remove the +1 near the bottom of his code to get rid of this mapping.

A couple of other notes from Eric (taken from a thread on the technique)

  • Ensure your clipping plane normal points away from the camera position C. That is, the camera is on the negative side of the plane P. If the dot product (Px,Py,Pz,Pw) * (Cx,Cy,Cz,1) isn’t negative, then negate all four components of your clipping plane.
  • The clip plane should be specified in camera space so you’ll need to transform from whatever space the clip plane is specified in.

Additionally NVIDIA have also a related sample on their site.

Thanks!

Hopefully this technique was new and could be useful to a few people and might encourage further exploration into 3D maths for others, I really recommend the following books

Things we’ve been enjoying this week

Aurifi – a postmortem

September 4, 2010 4 comments

Hello!

Thanks for all the great feedback on last weeks post about QuizQuizQuiz it was really appreciated.

Today I’m going to talk a little about a project called Aurifi, an audio-only game for iPhone/iPod which was launched at the end of May.

We performed all the programming work and were also involved in the design process with the great bunch of people at Punk Pie Ltd.

What is Aurifi? (Or-If-Eye)

The game is made up of a set of challenges which the player must successfully complete  to advance and ‘grow’ the music. Each challenge only requires you to listen and to touch, tap, tilt and shake as indicated by the beat. The game features no meaningful visuals and can be played with your eyes closed (in fact it’s almost recommended!)

The music in the game is mixed real-time from a large amount of professionally created tune segments, because of the way these segments are selected and mixed together the music you hear will never be the same. After completing each piece of music the player will be asked to ‘steer’ towards the style of music they would like for the next set of challenges.

Be sure to check out the teaser trailer that Punk Pie had produced before release and even better buy the game


Scripting / Fast iteration

The design process was really interesting as not being able to use visual cues is a handicap when you’ve become used to certain techniques to communicate with the player – especially with any slightly complex mechanic!

Due to the amount of tweaking and testing we’d need to do during the development before the first design document appeared I started putting together a prototyping app based on the initial list of possible challenges. I did this using our own multi-platform middleware (‘Lemon engine’) at the backend, FMOD for the audio capabilities (at this stage we expected to use a lot of DSP effects) and Lua.

Previously we’ve written our own C++ to Lua glue code there are however quite a few options for this nowadays, I picked luabridge (despite – I believe – it no longer being maintained) simply because I preferred the syntax after scanning through a couple one evening. It was pretty complete in terms of our needs.

The prototyping app was designed for quickly testing out the ideas we had for the challenges, we worked on PC initially quickly tweaking the challenges in self contained Lua files with calls for playing samples, applying DSP effects to active channels, adjusting pitch, frequency, volume, looping mode, ‘3d’ position and velocity. Executing one of the challenge lua scripts overwrote the previous definition for that challenge so reloads could be done incredibly quickly.

My next step was to move all our prototyping across to the device, this never quite happened as we got too involved on the design and challenge side of things for me to implement the simple network update system I had in mind for the Lua files. The idea was that a HTTP server on the Mac/PC I was editing the challenge Lua files on would get requests from the iPhone to check for updates to any files and would push down the update.

This would have worked perfectly I feel but we stuck with PC due to time. We paid for this as we later encountered issues on device that we’d have found sooner (Early SDK versions of FMOD iPhone reacted a little differently to FMOD PC).

While(1) { script_some_more(); }

We ended up with a lot of script in the game by the end (I’ll include a few codebase stats later), initially the plan was just to script the challenges and have the rest of the game be implemented in C++ (mainly as it wouldn’t be tweaked much).

I found though that I was working so quickly in Lua for implementing challenges that the song selection and playback code (plus the data definitions for the pieces of music) just ended up getting implemented before I could think about what language I was working in!

The only code that I planned to script and ended up in C++ was the menu code, which was added fairly late in the project and I was coming back to the project having been on a non-Lua project for a little bit so perhaps wasn’t in the groove as much!

Terms & Conditions?!!

During development and as we came up to release there was trouble rumbling on the net over section 3.3.1 of Apple’s developer agreement stating

Applications may only use Documented APIs in the manner prescribed by Apple and must not use or call any private APIs. Applications must be originally written in Objective-C, C, C++, or JavaScript as executed by the iPhone OS WebKit engine, and only code written in C, C++, and Objective-C may compile and directly link against the Documented APIs (e.g., Applications that link to Documented APIs through an intermediary translation or compatibility layer or tool are prohibited).

As a company we felt this was mainly aimed at Flash however we were bracing ourselves to re-code the Lua scripts into C++ should we be rejected by Apple. We knew of plenty of other apps using Lua on the store so felt pretty happy, we also precompiled our scripts into bytecode which made the scripting a little less obvious!

Sound plan?

So how did things work out?

Well the client was (they tell me!) very happy with the way things went during development which is always a nice result.

The scripting system worked great for quick adjustments to the challenges as we tweaked near the end of development (this was stuff like tolerances for acceptance, applying different filtering to the inputs and in some cases a complete adjustment of how the scoring system worked).

Choosing to use Lua wasn’t an accident as we’ve got a fair bit of experience with it (we started using it around 8 years ago on a Xbox 1 title followed by heavy use on a MMO system, plus various smaller projects and some personal WoW mod writing!). It is possible to make quite a few syntax errors with Lua especially if you’re coming back to use it after a while, there are quite a lot of code modifications and tricks you can use to help with this and it’s still seems to be as popular as ever as a scripting language.

The main issues encountered with the project were down to the FMOD wrapper I wrote and not completely understanding FMODs channel management when initially writing it (and due to time not fixing it quite as well as we should have). This was further complicated as our requirements in terms of sound channel grouping changed later on as we rewrote parts of the song playback and randomisation system.

When moving over from PC to device we found had a lot of sync issues due to the update rate on device being slower than it was on PC (we were working with a dynamic timestep so the iPhone when running slower due to the amount of mixing / DSP work being done in FMOD ran at a slower rate). These were fixed by implementing callbacks for touches so that input code could run immediately and also by reducing the size of FMODs mix buffer (which was a fixed size in an earlier version of the FMOD iPhone libs) to reduce the latency between a call in the script and the sound being heard.

Another issue was memory usage, we had some crashes on older devices (jailbroken in particular) which we couldn’t replicate but do plan to re-investigate soon, I think this was purely down to available RAM on certain devices and our startup RAM usage being quite high with all the tutorial assets pre-cached. The best solution for this will be to stream more of the assets on lower RAM devices and pay attention to Apples low memory warnings at the expense of reponsiveness!

The main reason for our high memory usage was that lower end devices couldn’t decode the number of compressed samples we needed at once as well as FMOD mixing and applying DSP effects so we streamed and decoded to PCM data on load and then passed uncompressed buffers in (plus FMOD doesn’t support on the fly OGG decoding – we did implement our own but again it was just a little too slow and wasn’t worth the time optimising).

To control all this we had a fairly awkward pre-cache system which allowed us to tell the background stream system what we knew we’d need soon (for example during song transitions or in tutorials) and we could force these to be freed when we no longer needed them.

Stat attack!

A few stats on the data / source code involved with this game

The game data contained

  • 24minutes 48seconds of music audio (compressed with OGG Vorbis to 20.3mb)
  • 12minute 16seconds of game samples and tutorial speech (compressed with OGG Vorbis to 11.6mb)
  • 722,762 bytes of PNG images! Kind of obvious it’s an audio game looking at how little this is of the total build size!

The game source code was made up of

  • Lua – 11021 lines of code (28% comments)
  • C++ / ObjectiveC – 7679 lines of code (21% comments)
    • This is of actual game code we wrote not including PNG loader, fmod headers, lua, ogg or vorbis. This also doesn’t include the GL rendering code.

Note I’m considering writing an alternative loc (lines of code) tool which will calculate the number of cans of Pepsi (or Dr Pepper, Sprite, Fanta or tea based on the individual developer) involved in development of each SVN commit! A very important statistic I feel!

Unique set of gamers

The game had a great initial following despite it being a really hard concept to communicate to people, I believe it’s still selling well today.

Specifically one market of really strong supporters of the game are blind gamers, through the tilt controllable menu and having no requirement to see the screen we of course hoped it would really appeal. I think this is really great and I’d love to think about how our future games could be modified to cater for this passionate group of gamers.

Thanks!

Hopefully this was a useful review of Aurifi, we’ve been really lucky to be involved in some very interesting projects over the years and this was certainly up there in terms of the challenges faced especially in design terms.

Things we’ve been enjoying this week