Monday, January 26, 2015

Cocos2D State Machine Wish List

I'm a big fan of Cocos2D for iOS and Android game development.  You only have to read the last 2-3 years of this blog to see that.  Cocos2D is tightly integrated with SpriteBuilder which is an excellent visual tool for creating levels, mapping out game objects, setting up animations and many parts of a game.  As of writing this it just keeps getting better with the advent of V4 road-map and SpriteBuilder's partnership with Apportable we see some great new features.

Right now you can easily integrate, animate and setup your assets in scenes, and then switch back to code in Swift or Objective-C to manipulate your game objects with a nice separation of responsibilities between the SpriteBuilder data files and the Cocos2D code.  

There is only one thing missing, a decent State Machine implementation.

Promotional image of Hutong Games "PlayMaker" State Machine for Unity
PlayMaker by Hutong Games -

UPDATE: I have started hacking around to get a sense of how much work there is and what sort of stuff there is in SpriteBuilder's code base to help.  On Github:

Screenshot of the SpriteBuilder state machine fork
There's already some support for this from SpriteBuilder and Cocos2D folks which is awesome.  The executive summary is:

  • we can have a better state machine that suits Cocos2D games
  • we can have it visually designable in SpriteBuilder

My goal is to get something very humble that might not represent the best UI idiom up and working in the next 2-3 weeks, and this will go back to the community for some early feedback.

The gold standard for State Machine implementations at present in game development is surely Hutong Games PlayMaker for the Unity 3D game development system.  Of course PlayMaker is not available for Cocos2D, and even if it was PlayMaker's tight integration with Unity's component system would mean that Cocos2D would have to be re-architected to work with it.  There's no way that a "port" of PlayMaker to Cocos2D makes sense, as far as I can tell.  Nonetheless if you ask what is the premier experience for game developers using state machines in their work, I'd have to point out PlayMaker.

Unreal Engine - editing State Machines
Unreal Engine's State Machine editing -

Unreal Engine's editing tools also include a State Machine editor, but its very tightly bound to the skeletal animation system.  I have never built a game using Unreal but I suspect that despite the apparent power and sophistication of Unreal's editing tools you'd be hard pressed to use the State Machine to do the kind of complete visual game development that Hutong promises with PlayMaker. I know that realistically if you create a game with Unity and PlayMaker you are going to have to write some code, but if you can for example do great swathes of your game logic in PlayMaker that is very powerful as the less technically savvy members of your team can then get in and work on play without having to know C# or how to script & code Unity.

What Can We Learn?

So we don't have PlayMaker in Cocos2D, but we have an opportunity to learn from the state machine implementations of others, and make something great for 2D game development in our favourite toolkit.

Given a port of these tools is not the right thing, what can we take from PlayMaker?  Of the many things that PlayMaker gets right with respect to its visual editor would have to also be gotten right for a decent State Machine implementation for Cocos2D:
  • tight integration with the visual level editor
  • preview states and actions in the visual level editor
  • states, events and transitions can be stored inside objects/components
  • on publish, state machine data is integrated with the game object files
  • tight integration with object animations to easily do common things
  • can be used for many parts of gameplay, not just animations
Obviously in the case of Cocos2D the editor is the SpriteBuilder tool, which already handles animations and visual editing of many object properties.  We could in theory make a separate State Editor but it would have to be able to be docked in Sprite Builder in order to achieve these things.

What is there Already for Cocos2D?

At present Cocos2D has many of the things needed to profit from a great State Machine implementation, but there are no pro-grade State Machine tools around as far as I know.

There are a few open source implementations around for State Machines in code.  I used Blake Watter's Transition Kit in my game Space Bot Alpha.  Its a nice project, well set up with CocoaPods, unit-testing and so on, so as a piece of Software Engineering its nicely done.  But for game development for me it really failed on the count of making my job easier.  I wound up doing more work for it that it did for me.

A big part of why that was the case is that there is no tooling integration.  I cannot create a State Machine visually with Transition Kit, or any of the other current offerings - it all has to be done in code.  First off this has the problem that its very difficult to do this with a nice separation of concerns and a clean interface.  You wind up embedding the State Machine setup into the objects initialisers and then calling the transitions from various places scattered throughout the code.  Secondly its time consuming and confusing to layout the State Machine in code - with the best syntax and API in the world any useful state machine quickly becomes cumbersome and difficult to maintain.

A second problem is that there is no tight integration between the Cocos2D objects and the State Machines.  You would have to write a whole binding system, but that is work over and above writing the game I needed to write.

Think about Chipmunk as it is bound in Cocos2D right now.  Just turning on Physics and having Cocos2D node objects under a Physics node in SpriteBuilder enables it for physics.  Then once I have checked the enable physics box, the Chipmunk system can change the x and y position of my Cocos2D nodes in response to the physics simulation all without me having to write any code.  Nice!

That's how it should be for a State Machine.  I should be able to hook up a State Machine to my object and have transitions drive changes in the objects properties.  Even if that had to be done in code, having some sort of binding system would save a lot of work.  As it is the code to alter properties in response to state changes gets messy and its easy to circumvent the state machine by mistake and get unexpected results.

Another interesting project is hsm-statechart which is written in C, and is scriptable in Lua.  In theory this should be easy enough to integrate into a Cocos2D project.  However despite some attractive extra features (discussed below) relating to Hierarchical State Machines, and C performance, I tried Transition Kit first as it had an Objective-C API already.

Also worth understanding is the Apache SCXML project which provides an XML format for describing HSM's like those you can build with hsm-statechart.

Memory and Performance

Another problem I see with some State Machine implementations - and Transition Kit is not too bad here but it could be better - is object proliferation.  Its should be possible to create states and destroy them without doing a lot of allocation and destroying of objects off the heap.  Let's imagine we have a zombie game with 40 zombies, and a hero firing hundreds of bullets - we don't want to have an NSObject for every state in every machine for each of those.  But that's how some FSM's are set up.

Instead you need some sort of manager class that can create a unique state machine "pointer" record without duplicating the state objects for each entity using that machine.  Its like a set of CPU registers for a process or thread referencing a copy of a binary program file without making a copy of it for each process or thread.

Also for performance the management of updates on the machine would have to be done well - tightly integrated with the game objects own update mechanism where timers were needed; or designed so that it does not unnecessarily get updated.  String dispatch would be ideal, as long as it does not impact on performance, and it should be used where it can reduce coupling of the objects in the program - we don't want to create circular pointer chains that could result in ARC retain cycles.

Blending and Animation Integration

Check this video on setting up an animated door in Unity using PlayMaker.  Of particular interest is the blending of the open to the closed state & animation which comes for free.  Here you have an animation for the "closed" door, which specifies certain XYZ positions for the door model, and similarly XYZ positions for the "open" animation.  Creating a transition between open and closed gives you a smooth blending from one set of XYZ to the other, similarly as setting keyframes for a Cocos2D animation would.

In a game getting the State Machine to work well with the animation and actions system is vital.  If a whole lot of extra code has to be written to get this to happen the you wind up doing more work for the State Machine than it does for you.  Blending is part of the story - here you are getting basic animations for free just for using the State Machine.  But where you want to have an animation play as an object transitions from one state to the next you need extra care.

Sub-States: A Hierarchical State Machine

How do you handle the fact that during an animation from open to closed, you are not really in either of those states but in fact you're in some in-between animation state??

One option is to have a 4-state model for your door: open, closing, closed and opening and then you can have the animation complete handler for the closing animation cause the transition from closing to closed.  The problem with this is when you have some other game logic that depends on checking the state of the door.  Lets say you have some poison gas in the room - it can escape into the adjoining room if the state of the door is one of open, closing, and opening - but if an NPC character wants to walk through the door they can only do so in the open state.

A more complex State Machine implementation is to use State Charts to solve the problem.  These add hierarchies of states, and also variables & guards to the system.  Variables are like game objects values, except they only exist within the framework of the State Machine.  Heierarchies mean that you can take the animation states which are visual effects that depict and implement an object; and place them inside a semantic (or meaning related) concept of a state.  So you could have two high-level states of Closed and Open; with Open having as sub-states Opening, Closing and and Completely-Open animation states.  This way you can have the Open high-level state trigger the release of the gas, and the NPC only get access when the low-level state Completely-Open is triggered.

Effectively what you are doing is grouping your states.  You need to specify which of the sub-states is entered when the superstate is entered, and there are some other details, but basically they're an extension of the simpler FSM concept.

So here's the remainder of the items, which would apply to a State Machine implementation regardless of the game level editor question.  Here's part 2 on my wish list:
  • the FSM must have simple bindings to objects (like Chipmunk)
  • transitions can be configured to drive changes in objects properties
  • blending of property changes should come for free (see video)
  • load states, transitions and events by reading some kind of data file
  • can also create states, transitions and events in code if needed (rarely)
  • state machines can be serialised for use in save/load-game and other cases
  • small memory footprint/CPU usage
  • ability to specify variables and guards as for HSMs (nice to have)
When?  Why?

I think having a solid State Machine implementation with editor support would get new comers to game development much more excited, productive and involved in game development.  It could give existing experienced developers relief from some tedious, detail-focused coding tasks and make those things accessible to the level designers.  And it could make complex bug-prone parts of a game project into data-driven cleanly-seperated modules.  I think it would have huge value.

I'd like to see this happen, so I might be interested in pitching in on such a project.  But it would need broad adoption by the core SpriteBuilder/Cocos2D team.  Let's see if we can get them to have a think about it.  :-)

Sunday, January 18, 2015

Game AI in Lua

Recently an email turned up in my inbox asking me to have a look at a new book on Lua titled Learning Game AI Programming with Lua, by David Young (published by Packt).  Here's my thoughts on the book following a read of the first half of the book, and a skim through the second half.

First some of my background for context.  Most of my career in computing (which professionally goes back to 2000) has been in C++ development on Linux devices, but also includes some server-side work, and lately iOS/Mac development in Objective-C.  I spent 4 years from early 2009 working on and then leading the team that built Qt3D, a C++ OpenGL rendering system which was scriptable in QML, and was mainly intended for Linux mobile devices, and embedded systems.  I gave a number of talks on Qt3D at Qt Dev Days in Munich and San Francisco during those years.  

From 2012 I have been working on my own business: doing some client work, and my own game development projects, including Ethex 2080 which was written in Objective-C for iOS devices and which used Lua scripting.  I demo'ed Ethex 2080 at the 2013 Game On symposium, but its currently on hold.  A series of screencasts covering the approach I used to create my Lua bindings for Ethex 2080 is on this blog.

In 2014 I wrote Space Bot Alpha, an Qix-style area claiming game in Objective-C using Cocos2D, and its currently available in the App Store and soon to be available for Android (via Apportable's Objective-C environment for Android).

Lua Scripting in Games

Using Lua for scripting a game is a great idea.  You often need a high performance language that compiles to native machine code (e.g. an x86 or ARM binary) in many parts of a game engine, for example the main rendering functions, the parts that traverse the scene graph.  So you write your engine in C++ or some other C-like language.

But often game development involves cycling around the edit-compile-run loop over and over until game play feels right.  Removing the compile step and loosening up the syntax from a strongly typed language like C++ makes that development so much quicker.  Enter Lua, a language born for this job.

Also some other parts of game functionality are really hard to abstract out and do good software engineering on, and also maybe you want to be able to put small pieces of ad-hoc or hard-coded functionality into an game character.  Lua is ideal for working in this way.  Engineer your engine in C++, and hack your game logic in Lua - its a great approach.

Lua performs well also, even marshalling over from C/C++ into Lua and back is fast.  Its ability to handle pointers to chunks of native memory via the userdata Lua type is very nice.  Once you know you're using Lua in your native-engine game, the problem of how to handle AI rears its head.  This is where David Young's book comes in.

The Downloads and the Book

The book itself is relatively slim at 328 pages, but the must-have downloadable accompaniment is much of the value for your spend on Learning Game AI Programming with Lua.  It includes a copy of the Decode Lua IDE, Young's Sandbox game engine (which is a proxy for "insert your game engine here") and a heap of open source projects for the back end of the Sandbox engine, including Ogre3D the popular 3D rendering framework.

Knowing the versions of the software that work together is for example very useful - this book targets Lua 5.1 and as the project just recently released 5.3 its handy to know you'll need to go back a minor version or two to get everything working.

Is this Book Right for Me?

If you're planning to script your game logic in Lua whilst your main game engine runs in C++ (or a similar language) and you know you're going to have to deal with AI then this is a great book to buy. If you're working with CryEngine, Unreal or some other game engine like that then Young's sandbox is a proxy for that engine and the concepts will come across very well as far as I can tell.

If you develop for iOS, then you'll be on Mac and the Windows Visual Studio solutions in the book will be difficult for you to evaluate, as they were for me.  Similar story for Linux.  I didn't take the time out to fire up my Windows VMWare image and try out Young's sandbox engine, but a look through the code (downloadable from Packt's website as a companion to the book) shows fairly clean (if sparsely documented) C++ that is a good exemplar for Lua bindings in a game engine.  Here's an example:

int Lua_Script_AgentApplyForce(lua_State* luaVM)
    if (lua_gettop(luaVM) == 2)
        Agent* const agent = AgentUtilities::GetAgent(luaVM, -2);
        const Ogre::Vector3* const force =
            LuaScriptUtilities::GetVector3(luaVM, -1);

        AgentUtilities::ApplyForce(agent, *force);
    return 0;


I don't think it would take long to get the sandbox ported to run on Mac and since all the components of Young's sandbox engine are popular Open Source items like Ogg Vorbis, Ogre3D, Bullet physics and so on the whole thing could probably be gotten ported to Mac without a lot of work.  Maybe future editions of the book will ship a Mac version of the sandbox.

But even if you just bought the book to get Young's code as an example of how to do your bindings then that is good value.  In my opinion writing your own bindings across exactly the part of the interface that you need them is the right way to do it.  I'm not sure about bindings done using bindings generators - I think its better to manually write those bindings yourself.  While Young does not cover bindings writing in the book, his code and the chapters in the Lua book should get any competent programmer over this part.  That's true even if you're on a system that does not support Microsoft's Visual Studio.

If you want a more generic book about game AI, where algorithms are expressed in generic language then a good start is O'Reilly's AI for Game Developers which is an excellent book.  I have a paper-back copy that stays on my desk at work and it is accessible and high level enough to inform many projects.  The content of that book is still relevant today after it was first printed in 2004.  Learning Game AI Programming in Lua covers a lot of the topics in that book just by doing an implementation, and adds a few more things like Influence maps for agent AI (something that was totally new to me).

To learn Lua itself the actual Lua book, is pretty good, also functions as a reference, and buying it helps the development of the language.  Young's book is not too demanding on Lua knowledge, but it won't try to teach you Lua either.  Its best to have a reasonable understanding of Lua, especially of its type system, associative tables and stack based C language interface (covered in the final chapters of the book) before you go into scripting your game and AI in Lua.

If you're writing games in Lua, using for example Corona; or hosted game content in World of Warcraft or another Lua scriptable game, then this is not so well suited.  It's really for developers of hard-core games, especially 3D games, and less suitable for indie dev's hacking on a smaller game using something like Corona.  You probably need to read a generic book on Lua and a book on game AI, like the two mentioned just above.

AI and Animation Hand in Hand

One thing I love about this book is the pragmatism about how tightly bound AI and animations are.  Young's management of this is well done, and its something that you don't see in generic books on AI.  For example you need your state-machine to handle AI, but it also has to handle the animation states of your characters and props in the game.

The book develops an animation state-machine in its early chapters and then goes on to base its AI work on top of this, which is a solid approach, and one that clearly shows the author's experience in real shipped games.  I wonder if a Harel state-chart with hierarchical state machines could handle the relationship between character animation states and AI states with a solid theoretical framework to underpin it, but the pragmatic approach is the straightforward one.

Frameworks like Playmaker for Unity do hierarchical state-machines well but I think in code it would become unwieldy without a visual editor to manage the structure.  The approach in the book is clean and seems to work well.

This kind of AI tight integration with animation is a little bit less relevant for 2D games but still important.


Though I have not been able to compile and test the code shipped with the book from my read it looks really good, and an invaluable resource for the hard-core game developer adding AI to a Lua scripted game.  The information in this book is solid and immediately applicable while still being knowledge that is not going to date quickly.  A good addition to any game developers library.


Packt Publishing provided me a free copy of the book for review.  Otherwise I have no affiliation with Packt.

Friday, January 2, 2015

Swift and Cocoa

The primary reasons for Apple's language gurus going to Swift as the core language for building iOS and Mac OS X applications was to make it easier for developers to create good, secure, stable applications.  It wasn't actually a conspiracy to drive us all mad, it was actually a long-game move that was very well executed.  Yes, its not "there" yet in many ways.  But here's why you should use it anyway, and a couple of things to look out for: optionals and type-safety.

Objective-C has a lot of pointers flying around, it is very easy to be loosey-goosey about when those pointers are null.  Especially since its OK to send a message to a null object, and because the clang compiler ensures initialisation in many cases, we often write sloppy code with respect to null pointers.  Apps that crash are not only a bad experience for users of iOS products, but they're also likely to have security holes.  Also apps that are light on type safety can similarly be unstable and have security problems.

Also, there's type safety.  You'd think being C-based that Objective-C was type safe, but the existence of the id type, a generic go-anywhere do-anything type based on the venerable C void * pointer type, means that a lot of the time that type safety is circumvented.  An Objective-C array for example is of type NSArray and can have any Objective-C object stored into it, as its members are all id types.

Swift does a lot for type safety, and while it does not do away with null pointers, what it does do is force you to be explicit about them.  This is done with the Optional type.  An Optional behaves like a union struct in C where you can either have a None value, or a Some<T> value. (Actually its implemented with a Swift enum).  Swifts generics have a syntactic sugar for this where instead of writing

var userAnswer : Optional<String>

you write

var userAnswer : String?

which means a var that may or may not contain a value.  In general in Swift you are encouraged to initialise variables as you declare them, and then you get the benefit of type inference like this:

var userAnswer = "Placeholder"

This is perfectly type safe: the variable userAnswer is strongly typed as String, which is inferred by the compiler from the initialisation, and the variable cannot have a value of another type assigned to it.

Some folks seeing code like this have assumed that Swift is something like Javascript where the variables are dynamically typed: they can contain data of different types at different times. Nope.  Swift is not a scripting language.  Its not even a managed language in the true sense of that term.  Its a compiled language that has a powerful and expressive syntax, and a rich standard library, but its not a scripting language.

OK, so what does all this fancy footwork with Optionals actually buy you?  For my money its like trading one problem for another that is easier to solve.  I like to write invariants in to my comments in code:
"Such and such a condition will always hold here."  
By putting such things into the class definition you remind yourself that you are in control: there is not some spooky stuff going on.

Superstitious coding is a terrible disease.  If you hear someone saying "I don't know how I fixed it but I had to type that to get it to work" or "I know that variable should always have a value, but what if someone sets it to null?" then you know superstition and magical beliefs have taken hold in your team and its time to call the exorcist.  In other words abandon all hope and compile your code with a ouija board because you don't control it any more.

Instead, use invariants.  Yes comments are not code, but you can type them in nonetheless and at least enforce them during debug builds using asserts.  This is coding by contract and if you start out as you mean to continue then your code will make sense as it continues to be modified long into the future.

This is where Optionals come in.  They allow you to make contracts and invariants succinctly and naturally as you write code.  If you use a Swift implicitly unwrapped optional by writing:

var userAnswer : String!

func displayTheAnswer()
    myAlert(title: "Got it!", text: "You said \(userAnswer)")

...then what you are doing is effectively writing the following invariants and asserts:

/* Invariant: I undertake and swear & declare that I will make sure this has a value by the time its used! */
var userAnswer : String!

func displayTheAnswer()
    /* kaboom if I didn't live up to my promise */
    assert(userAnswer != nil, "You failed to stick to the invariant!")
    myAlert(title: "Got it!", text: "You said \(userAnswer)")

And while this can still crash at run-time if the assertion is wrong, its much much easier to read what you are intending, and to locate the cause of the crash at the site of the error, not at some point much later where the result of the null finally propagates to.

In fact when you write UI code in Swift such as the following:

@IBOutlet var surnameLabel : UILabel!

you are using an Optional, and an implicitly unwrapped one at that.  This is what you get if you use Interface Builder to control drag a control into your Swift NSViewController.

Because you know that you controller will spend most of its life-time running with the surnameLabel set to the value obtained from the NIB file, this is a sound invariant promise to make.  Superstitious coding where you run around checking to see if this is null all the time makes no sense.

So I like the idea.  Its a bit weird at first, but its a good language feature, and once the idiomatic use settles down will make for more stable and more secure software.

Where things are a little rough is at the interface between Swift and Apple's now long-in-the-tooth User Interface library, Cocoa.  Cocoa is full of crufty, bizarre, unsafe and down-right confusing APIs that no matter what modern language you used would always behave badly.

Here's an example:

Here I'm trying to implement an NSValueTransformer to use in the Swift project I'm working on that uses Cocoa and bindings.  The class method transformedValueClass (where class means "+" instead of "-" or instance method) returns a Class as a result.  Because Swift's Array type is actually implemented as a Swift Struct it does not conform to the AnyObject protocol; and since AnyClass - the return type from this function - is actually a type alias for AnyObject.Type - you cannot return the type "array of strings" from this function.

Instead to work around you need to return an NSArray - the old Objective-C type - which will get transparently bridged to a Swift array, but which of course is not type safe.

Other issues are the difficulties working with key technologies like Key-Value Coding, which is critical to the Cocoa bindings used by Interface Builder, and the cryptic type messages that can come out of the type system at the interface with Objective-C.

Its here at the interface between Cocoa and Swift that the new language really runs into rough terrain.  Still, its worth persevering with, and the online community is abuzz with new pundits who are happy to drop knowledge bombs on your gnarliest conundrums, providing you've put some time into scratching your head over them yourself.

Also, my prediction is that while at present the Cocoa layer for Swift is mostly just ultra-thin bridging-headers and wrappers, we'll slowly see more pure Swift classes put in front of these things and kludgy Cocoa issues will slowly be solved.

At present it is perfectly do-able to write your new apps in Swift and I think starting out greenfield projects using Objective-C is probably a mistake, all things considered.

What do you think?