iGIPF — An iOS Game in 2 Weeks

Alexey GrunichevApr 18, 2012

Confession

While weekend work is in progress right now, we have to confess something. Even though we did not have any iOS code written before the project began, we did have small prototypes implemented in python. This prototype gave us confidence that the project could be implemented in 2 weeks.

Even though we lost a couple of days of work on prototypes in scripting language, it was really useful to see the work in action. Indeed, it raised important performance issues and led to our decision to implement part of the game in pure C. But everything is good in its season.

The prototype

The Python prototype was first a console script of 300 lines; basically just game logic (with some restrictions such as remove selection if many rows are subject to simultaneous removal). Later we added some GUI elements (otherwise it was very frustrating and uncomfortable to play from command line) for which we used the kivy framework for those who are curious. It was our plan to try to run it under the Android OS and check performance on mobile hardware.
Just look at this picture:

This is already a good candidate for the AppStore, isn’t it? Just kidding!

Performance Issue

The good news – The game worked and we can play, though it was not so convenient.

The bad news – By looking 3 levels deep, the game needed about 1 minute for analysis. Through simple profiling we realized that most of the time was consumed by copying (cloning) boards for the next move and performing all operations with hexagon rows. We should mention that analysis to a depth of 2 levels is enough for newbie, but for an expert analysis needs to go at least 4 levels deep.

Optimizations

Okay, as we see, performance is a serious issue if we deal with AI calculations on the object-level without special optimizations. Thus, the current goal is to create a layer of the highest possible performance to use 100% of the calculation capabilities of the iPhone/iPad.

Main points:

  • Pure C, only structs
  • Structures have strict grouping
    • Those that are frequently copied (BoardState)
    • Those that are rarely copied (BoardInfo)
  • No heap allocations in repeated operations (only stack)
  • Pre-allocated buffers in heap for all needed storage (arrays, temp vars, etc.)
  • Copy any data using ‘memcpy’ only
  • Optimized board operations

We believe that we could seriously beat our high-level Python implementation, because most performance in the Python prototype is lost on allocations and constructing objects (instead of memcpy to preallocated space). We expect something like a 10x improvement; but we’ll see.