Writing an iPhone Game Engine (Part 2- Maya Tools)

Tools are very important in game production, especially when you are working with someone who cannot write code. In my project, I worked with 2 artists, so I need to write some tools to export their models to my engine. There are different choices to export the models, you can parse.obj file format(for static model only), reading .fbx file using FBX SDK, reading COLLADA files... But I choose to extract it directly from the modeling package that the artists use - Writing Maya plugin to extract the model data.

To write Maya plugin for exporting models, we should know how data are stored in Maya first. Basically, Maya stores most of its data (e.g. meshes, transformation...) in a Directed Acyclic Graphic(DAG). In my case, I just need to locate those DAG nodes that store the mesh data. We can traverse the DAG using the iterator MItDag like this:

1. MStatus status;
2. MItDag dagIter( MItDag::kDepthFirst, MFn::kInvalid, &status );
4. MDagPathArray meshPath; // store the DAG nodes that contains mesh
5. for ( ; !dagIter.isDone(); dagIter.next())
6. {
7.   MDagPath dagPath;
8.   status = dagIter.getPath( dagPath );
10.   if ( status )
11.   {
12.     MFnDagNode dagNode( dagPath, &status );
13. 
    
14.     // Filter out the DAG nodes that do not contain mesh
15.     if ( dagNode.isIntermediateObject()) continue;
16.     if ( !dagPath.hasFn( MFn::kMesh )) continue;
17.     if ( dagPath.hasFn( MFn::kTransform )) continue;
19.     meshPath.append(dagPath);
20.   }
21. }

then, we can get the mesh data in the DAG nodes using the MFnMesh like this:

1. for(int i=0; i< meshPath.length(); ++i)
2. {   
3.   MDagPath dagPath= meshPath[i];
4.         
5.   MFnMesh  fnMesh( dagPath );
6.   MPointArray meshPoints; // store the position of vertices
7.   fnMesh.getPoints( meshPoints, MSpace::kWorld );
8. 
   
9.   // get more mesh data such as normals, UV...
10. }

For the details of getting the mesh data, you may refer to MAYA API How-To and Maya Exporter Factfile. After getting the mesh data you can export them by creating a sub-class of the MPxFileTranslator and overwrite the writer() function. You can find some useful sample code provided by Maya inside the Maya directory (/Applications/Autodesk/maya2010/devkit/plugin-ins/ on Mac platform) such as the maTranslator.cpp and objExport.cpp.

Another reason I choose to write plugin instead of parsing .fbx/COLLADA is because of extracting the animation data. In my project, I just need to export some simple animations which linear interpolates between key frames, and I would like to get the key frames defined by artists in Maya. I have tried using the FBX SDK but when exporting animation data, it bakes all the animation frames as key frames... Using COLLADA get even worse because I cannot find a good exporter for Maya on the Mac platform... So writing Maya plugin can get rid of all these problems and get the data I want. I can also write a script for artists to set the animation clip data:

After exporting the mesh data, I think it would be nice to edit the collision geometry inside Maya, so I have written another plugin to define the collision shapes of the models:

This plugin works similar to the Dynamica Plugin (In fact, I learnt a lot from it.), except mine can just define simple shapes with only spheres, boxes and capsule shapes. And my plugin cannot do physics simulation inside Maya, it is just for defining the collision shapes. Those collision shapes (sphere/box/capsule) are just sub-class of MPxLocatorNode by overriding the draw() methods with some openGL calls to render the corresponding shapes.

In conclusions, extracting mesh data directly from Maya is not that hard. We can get all the data such as vertex normals, UV sets and key frame data from Maya and do not need to worry about the data loss during export through another formats, especially animation data. Also Maya provides a convenient API to get those data and it is easy to learn. After familiar with the Maya API, I can also write another plugin to define the collision shapes. Next time when you need to export mesh data, you may consider to extract them directly from the modeling package rather than parsing a file format.

Reference:
[1] MAYA API How-To: http://ewertb.soundlinker.com/api/api.018.php
[2] Maya Exporter Factfile: http://nccastaff.bournemouth.ac.uk/jmacey/RobTheBloke/www/research/index.htm
[3] Rob The Bloke: http://nccastaff.bournemouth.ac.uk/jmacey/RobTheBloke/www/
[4] http://www.vfxoverflow.com/questions/add-remove-framelayouts-in-a-window-using-mel
[5] http://bulletphysics.org/mediawiki-1.5.8/index.php/Maya_Dynamica_Plugin

Writing an iPhone Game Engine (Part 1- Memory management)

On the iPhone platform, memory is a very precious resources. If they are not handled properly, the application will receive one or two memory warning, and then your application will be killed by the OS. So I decided to write my own memory allocator to preallocate a large chunk of memory so that my game will not be killed by the OS when running, it will either start or not start. This is my first time to write a memory allocator, and it is not as sophisticated as "Ready, Set, Allocate!", but it just works fine enough for me.

In my little engine, a pool allocator is written for memory allocation, with different pre-defined pool size ranging from 8, 16, 32, 64bytes to 1048546bytes. As my target platform is iPhone, the maximum pool size is 1048546bytes which is used only for a few high resolution textures, most of the memory is spent on the the smaller pool size. During the program starts, a large chunk of memory is created and it is divided into different smaller chunks for different pool size as follows:

Notice that the large byte chuck is located in the smaller memory address for proper byte alignment. And within each chunk, it is divided into equally sized block for each particular size allocation:

The memory blocks within each chunk are maintained as a linked list so that when the pool memory allocator need to allocate/deallocate memory, it just need to return a free memory block from the list/add it back to the linked list. The memory within each memory blocks is used to store the 'next pointer' for the next free memory block in the linked list so that we do not need to allocate extra memory to keep track of the linked list (this approach is learnt from Game Engine Architecture):

For each allocation, the allocator need to decided which pool chunk need to be used depends on the size of the allocation. Then within that chunk, a free memory block is returned which is just the head of the linked list within that chunk. For each deallocation, as we divide the memory into different chunk, we know the boundary address of each pool chunk, so by checking the deallocated pointer address, we can determine which pool chunk it belongs to, then we can just add the memory back to that chunk's free memory block linked list. One drawback of this approach is it does not verify whether the deallocated pointer is actually allocated by the user nor it is double freed. To 'partly overcome' this problem, I added limited check to verify the input to each deallocation. First, I would check whether the input is byte aligned, for example if the deallocated pointer is within the 1048546 bytes chunk, then the pointer address must be 1048546 byte aligned. Second, as we partition the memory chunk, we know how many memory blocks is within each memory chunk, we can maintain a current free blocks number which will increase and decrease for each allocation and deallocation. When the program exits and this free block number does not match with the total number of blocks, then memory may either be leaked or double freed. But this only solve the problem partially.

To actually solve the problem and also check for memory leaks. I need to log every allocation and deallocation. Originally, for each allocation, I just store the returned pointer address and location of each allocation(which source file and line number) using the macro __FILE__, __LINE__. But this does not do well enough to track down all memory leak as some files are templated such as btAlignedAllocator.h in the bullet physics library(yes, I use bullet physics in my engine). Using the macro __FILE__, __LINE__ will only log down the allocation in these header file which does not help much for tracking memory leak. Therefore, I also log the callstack of each allocation using the system call backtrace() and backtrace_symbols()(which is available in Unix-like platform). Then I can track down all memory leak easily. However, logging every allocation is a very slow process and it is only enabled in debug build/ enabled when necessary.

In conclusion, my memory allocator still have different things to improve such as verifying the user deallocation; adding some meta-data within each memory block such as the allocation size; And for the thread safety, currently I only use a mutex to protected the memory, I may switch to a lock-free version in the future. Despite these short comings, this allocator works well enough for me as it avoid receiving memory warning from the iOS, avoiding memory fragmentation and help me track down memory leaks.

Reference:
[1] http://g.oswego.edu/dl/html/malloc.html
[2] Ready, Set, Allocate!: http://altdevblogaday.com/2011/04/11/ready-set-allocate-part-1/
[3] Game Engine Architecture: http://www.gameenginebook.com/
[4] http://gcc.gnu.org/onlinedocs/cpp/Standard-Predefined-Macros.html
[5] http://developer.apple.com/library/mac/#documentation/Darwin/Reference/ManPages/man3/backtrace_symbols.3.html

Writing an iPhone Game Engine (Part 0- Introduction)

This time I would like to talk about my hobby project which is writing an iPhone Game Engine. This project started from August last year and works with 2 artists. Although the game is still not finished, I want to share what I have learnt so far. Let's show some screen shots first:

Fighting against Ships

Exploring the game world

In the game, the player will control a ship to explore the world, discovering new cities and fighting with other ships. The player can also change the ships when the game progress.
I will have several blog posts to talk about the techniques I used in my little engine. The up coming topics will includes:
    - Memory management
    - Tools (Maya plugin and level editor)
    - Scripting (Lua)
    - Streaming system

    - Audio (OpenAL for effect sounds and Apple audio queue for BGM)
    - Performance tuning
After finishing the above topics I will talk about what I have done right and what have done wrong in this project.
In my next post, I will start to talk about the Memory management in my game engine. To end up this introductory post, I would like to show you more screen shots of the game and tools I have developed so far:

Profiling the game

Editor to compose a game entity

Level editor

Mac version of the game for artists to preview the game