Solve this puzzle – @memo and dynamic programming

Here’s the situation.  You have a puzzle with 15 round coloured plates arranged in an equilateral triangle, and 14 coloured pebbles on top of them.  One plate does not have a pebble – it is called the hole.  Your goal is to rearrange the pebbles so that they are on the matching coloured plates, in the minimum number of moves possible.  For each move, you can only move one pebble in a straight line to the hole, possibly leaping over other pebbles on the way.

The question is – can you design an algorithm to calculate, for any starting board, the minimum number of moves to solve it?

In fact this describes the game Panguru, recently produced by Second Nature Games and available as a board game and online.  In Panguru, there are two pebbles and plates of each colour, and one additional legal move down the centreline of the triangle.  If my quick description is too wordy, the online game will give you a much better feel for it; there are rules available too.

A dynamic programming solution, with memoization

Here’s the approach I came up with, which I implemented in python. This was informed by the excellent book Python Algorithms, Mastering Basic Algorithms in the Python Language, by Magnus Lie Hetland, which I highly recommend.

Think of all the possible moves used to solve the puzzle as a tree. Number the positions 0 to 14.  The root node of the tree is the hole position, and child nodes give the position of the pebble that is being moved. So with the hole starting at the top of the triangle (position 0), one path through the tree might be 0-3-5.  (If you think about it, the last move always tells you where the hole finishes up.)

It is easy to measure how close we are to the solved board: we just count how many pebbles have the same colour as their plates.  When we hit 14, we are done!

In fact we can turn it around.  Let’s assume we have a solution (14 matching pebbles) after m moves. How did we get here?  Clearly, we must have had 13 matching pebbles the move before. (Because you only move one pebble at a time, each move can only increase or decrease the number of matching pebbles by one, or leave the number unchanged.)

And the move before that, we must have had either 12 or 13 matching pebbles. And so on.

This sounds like induction and lends itself to a recursive solution, like this. First define the tree structure via the `Node` class. The core of this is the `__init__` method which keeps track of the node’s parent. I’ve also added `original_pos` to help us later, and two extra methods to display nodes nicely on the command line (`__repr__`) and to make it easier to access the node’s ancestry (`__getitem__`).

```class Node():
def __init__(self, parent, move, num_matching):
self.parent = parent
self.move = move
self.num_matching = num_matching

def original_pos(self, pos):
"""
Return the original position of the pebble now at position pos.
"""
if not self.parent:
return pos
if pos==self.move:
prev_pos = self.parent.move
elif pos==self.parent.move:
prev_pos = self.move
else:
prev_pos = pos
return self.parent.original_pos(prev_pos)

def __getitem__(self, key):
"""
If m is a node which you think of as the last move in a sequence,
m[-3] is the third last move as a Node.
m[-3].move is the third last move as an integer (which position was moved)
"""
if key>=0:
raise IndexError, "You must index moves from the end, e.g. m[-1] for the last move."
if key==-1:
return self
else:
try:
return self.parent[key+1]
except TypeError:
raise IndexError, "Out of range."

def __repr__(self):
return "%s%d" % ((self.parent and ("%s-" % str(self.parent)) or ""),
self.move)
```

Then the puzzle-solving approach could be implemented like this:

```class Puzzle():
def __init__(self, plates, pebbles, allowed_moves):
"""
Set up a puzzle instance for solving.
Args:
plates is a string of 15 chars representing colours
e.g. "WCBRBOGYGPCORPY"
pebbles is the same, with "-" for the hole
e.g. "-PCBRYOGYGBCORP"
allowed_moves is a list s.t.
allowed_moves[i] = list of positions that a pebble at pos i can move to
= list of positions that can move to this position, if it is the hole
e.g. [[1, 2, 3, 4, 5, 6, 9, 10, 12, 14],
[0, 2, 3, 4, 6, 8, 10, 13],
[0, 1, 4, 5, 7, 9, 11, 14],
[0, 1, 4, 5, 6, 7, 10, 12],
[0, 1, 2, 3, 5, 7, 8, 11, 12, 13],
[0, 2, 3, 4, 8, 9, 12, 14],
[0, 1, 3, 7, 8, 9, 10, 11],
[2, 3, 4, 6, 8, 9, 11, 12],
[1, 4, 5, 6, 7, 9, 12, 13],
[0, 2, 5, 6, 7, 8, 13, 14],
[0, 1, 3, 6, 11, 12, 13, 14],
[2, 4, 6, 7, 10, 12, 13, 14],
[0, 3, 4, 5, 7, 8, 10, 11, 13, 14],
[1, 4, 8, 9, 10, 11, 12, 14],
[0, 2, 5, 9, 10, 11, 12, 13]]
"""
self.plates = plates
self.pebbles = pebbles
self.allowed_moves = allowed_moves
self.num_pebbles = len(filter(lambda x: x not in ["-"], self.pebbles))
self.num_matching = sum(plates[i] == pebbles[i] for i in range(len(pebbles)))
hole_pos = self.pebbles.find('-')
self.root = Node(None, hole_pos, self.num_matching)

def matching_nodes(self, turn, num_matching):
"""
Return all the series of moves (as BoardNodes with parents)
that have 'num_matching' matching spots after 'turn' turns.
"""
if turn==0:
if num_matching==self.num_matching:
return [self.root]
else:
return []
result = []
for change in (-1,0,1):
for prev_node in self.matching_nodes(turn-1, num_matching+change):
for move in self.allowed_moves[prev_node.move]:
pebble_colour = self.pebbles[prev_node.original_pos(move)]
# was the moved pebble on a matching plate already?
old_pos_match = (self.plates[move]==pebble_colour)
# does the prev board's hole plate match the moved pebble?
new_pos_match = (self.plates[prev_node.move]==pebble_colour)
# did the move change how many positions were matching,
# by exactly the number we're looking at?
if (old_pos_match-new_pos_match)==change:
result += [Node(prev_node, move, num_matching)]
return result

```

The interesting recursion here is going on in the `matching_nodes` method.  It just implements the idea that the solutions that have, say, 10 matching positions at turn 10, must have had either 9,10 or 11 matching positions at turn 9. It then works back to turn 0, at which point we know how many matching positions there were.

On top of this, we need a further method which finds the right question to ask. It could start by saying – give me all the solutions after 0 moves. If there are none, find all the solutions after 1 move. And keep trying until you find some solutions, e.g.:

```    def optimal_moves(self, stop_at=20):
"""
Return a tuple (fewest possible number of moves, [optimal moves for this board]).
"""
num = 0
result = []
while not result and num<=stop_at:
result = self.matching_nodes(num, self.num_pebbles)
num += 1
return (num, result)

```

The code above will work, but it will be slow and inefficient, because `matching_nodes` will often recurse through territory it has already covered. And that’s where Hetland’s memo decorator comes to the rescue. (This is only a few lines of code which you can find by searching at Google books.) This will cache the results of the decorated method, so that it does not need to be recalculated.  To use it, simply apply `@memo` to the `def matching_nodes` line, like so:

```@memo
def matching_nodes(self, turn, num_matching):```

And that’s it!

You can see this code in action when you ask for a hint in the online game. Each time you press the hint button, the javascript sends off an ajax query which triggers the server to run the above code on the player’s board, and return which moves would come next if the player plays optimally.

In fact, to get around annoying ever-expanding memory problems on the server, I’m running this asynchronously using Celery and Redis (as covered in an earlier blog post), and restarting the celery worker after every request.  But that’s another story…

I hope that has been of interest, and please let me know if you have any comments or improvements.

Better than jQuery.ajax() – Django with Angular

I have built a website for my games company Second Nature Games using Django.  Django brings lots of benefits like a nice admin panel where my partner can upload new game boards and add new content to the site.

However, to write games on the web you can’t rely too much on a server-side framework like Django. You are going to have to write some javascript as well.  I was keen for the challenge, having used some jQuery before.

In my first attempt, the boards were rendered by Django on the server, and then the javascript on the client-side would manipulate the document object model (DOM) as the game was played. As I described in an earlier post, I used jQuery’s \$.ajax() command to alert the server when the game was finished, and then the javascript would update scores and stats as required.

But this is not easily scalable:  as I added a leaderboard and more stats, more and more things needed to be updated, and I got into a tangle.

The solution is to use a javascript MVC framework like Backbone, Angular or Ember (or Meteor even more so).  I chose to use Angular. There is a great website, To Do MVC, which shows the same To Do application written in many different frameworks, so you can make an informed choice if you’re facing the same decision.

Using one of these frameworks changes how you view the server: the server just sends data and the client renders it. This is known as “data on the wire”.  The effect is to turn the server into an API. (Unfortunately for Django fans, I suspect Django is really overkill for this. But having developed the rest of the site with Django, I stuck with it.)  Meanwhile, whenever the data updates, the javascript framework will update the DOM for you.

Here is a sample template for the Panguru leaderboard, using Angular:

```<div class="info">
<ul>
<span class="name">{{ entry.name }}</span>
<span class="score">{{ entry.score }}</span>
</li>
</ul>
</div>
</div>
```

You can see it’s pretty straightforward and elegant. The code to load it from the API is:

```\$scope.updateLeaderboard = function() {
var that = this;
})
});
}
```

As you may have noticed, Angular and Django both use the double-parentheses notation. You don’t want to have them both try to interpret the same file.

One approach is to use Django’s `{% verbatim %}` tag. I think it’s nicer to separate the Django-rendered templates from the Angular-rendered templates completely, into two separate directories. Django templates stay in their app’s `templates` directory. I put Angular’s html files into the app’s `static/partials` directory. If the server needs to provide data to the javascript, I let Django render it in its template, and pick it up in the static html file. One example is to pass the csrf token. Another example arises because I’m using the staticfiles app, so Django renames all the static files. Unfortunately this includes the locations of all the partial html files and images you need. E.g. in my Django `templates/game_page.html`:

```<html lang="en" ng-app="panguru">
<title>Panguru Online</title>
...
{% addtoblock "css" %}{# if you are using sekizai #}</pre>
<style type="text/css">
</style>
<script type="text/javascript">
csrf_token = '{{ csrf_token }}';
container_url = '{% static "partials/container.html" %}';
...
</script>

<body>
<div panguru-container></div>
</body>
</html>
```

This part I’m not especially proud of, and would love to hear if you have a better solution.

You can then either use a Django API framework like TastyPie to serve the `api/leaderboard/` URL, or you can write one yourself. I did this starting from a JSON response mixin like the one in the Django docs, or this one by Oz Katz, developed for use with Backbone. Then, in Django `views.py`, I put:

```class LeaderboardApi(JSONViewMixin, View):
"Return the JSON representation of the leaderboard"
def get(self, request, *args, **kwargs):
return self.json_response(Score.as_list(limit=20))
```

That just requires a method on your model which returns the object in an appropriate format, e.g.

```class Score(models.Model):
user = models.ForeignKey(User)
score = models.PositiveIntegerField(default=0)
class Meta:
ordering = ['-score']
@classmethod
def as_list(cls):
return [score.as_dict() for score in cls.objects.all()]
def as_dict(self):
return {'name': self.user.username, 'score': self.score }
```

There’s just one more thing, which is an inconsistency in how Django and Angular apply trailing slashes to URLs. Unfortunately if you use Angular’s `\$resource` approach to interacting with the API, it will strip off any final slash, and then Django will redirect the URL to one with a slash, losing any POST parameters along the way. There’s a fair bit of discussion about this online. My approach has been to just turn off Django’s default behavior in `settings.py`:

`APPEND_SLASH = False`

Get ready to thoroughly test your app when you make this change, especially if you are also using Django-CMS, as I am. I uncovered a few places where I had been a bit sloppy in hardwiring URLs, and was inconsistent in my use of slashes in them.

The full result is the logic puzzle game Panguru, which you can play online or buy as a physical boardgame.  Please check it out and let me know what you think!

The Rubik’s Cube

And now for something completely different.  In my spare time I’ve been learning how to solve the Rubik’s Cube, almost entirely by following the beginner’s solution on Ryan Heise’s website. He gives a way to do it with only four different sequences you need to memorise, and the site has cool animations of the moves.  He also shows how to do it without memorisation and has a good page on the maths of the cube.

Here are my notes on his approach. They are not a sophisticated analysis, just an effort to record it so I can come back in a few years’ time and save some time relearning it.

I’ll use Singmaster notation for moves, where a clockwise turn of the frontwise face is labelled `F`, an anticlockwise turn `F'`, and the other faces are back `B`, left `L`, right `R`, up `U` and down `D`. (We won’t need `D`.)

Also, to take the “mirror image” of a sequence, just substitute:
`R` ↔ `L'`
`L` ↔ `R'`
`F` ↔ `F'`
`U` ↔ `U'`.

The first layer

You build up the completed cube by layers. The first layer is fun to work out without any memorised moves, but you can refer to earlier link for details. One useful strategy I learnt there is to focus first on the edge piece and then on the corner pieces.

The second layer

The second layer is where I have always got stuck in the past, as any moves you make cannot affect the first layer any more, making it much harder. I did work out my own way of moving an edge piece from the top layer down into the second layer; unfortunately it does affect one other piece in the second layer, so it can only ever be part of the solution.  For the record, to move the piece from the top-right edge to the front-right edge, in the same orientation, the sequence is:

`U2R2U2RU2R2`

But the better sequence in this situation (because it does not affect any other pieces in layer 2) is:

`(U'F'UF)(URU'R')`

Moves like `U'F'UF` are called commutators in group theory.  If `U` and `F` had no edges in common, then the sequence would have no effect. But because they do share an edge, this sequence winds up affecting three edges: the upper-left, the upper-front, and the front-right edges.

Then `URU'R'` affects the upper-back, upper-right and front-right edges.

For this move, we don’t really care what happens to the upper face, so it is only the impact on the front-right edge that matters, since it contains one corner of the first layer, and the edge piece we want to replace.  If you think through where that corner piece of the first layer goes, it gets caught by the moves: `(.F'UF)(U.U'R') = F'UFR'` . That’s interesting – we know this piece ends up where it started, but that is not obvious from this analysis. The mysteries of the cube!

If you can’t get any pieces on the right side in the correct orientation, you will need to do it on the left side using the mirror image of the above sequence.

The third layer

That brings us to the third layer, which will take four separate steps.

The cross

First, you want to form a cross on the top.  At this point, you are only aiming to get the upper colours correct, not the side colours. If you can make a little J on the top layer (i.e. the back and left edge pieces have the right colour on top), then use:

`R'(U'F'UF)R`

This flips the orientation of the front and right edges and rotates the left, front and back edge pieces anti-clockwise.  (It also plays havoc with the corners.)

You can see that it can only affect the top layer from my earlier reasoning: `U'F'UF` only affects the upper-left, upper-front, and front-right edges.  By enclosing it in `R'-R`, that front-right edge gets transformed into the upper-right edge – so the sequence affects only the upper-left, upper-front and upper-right edges (it leaves the single upper-back edge piece alone).

If you have a straight line instead of a J to start, put the straight line across from left to right and you can use this sequence to turn it into a J.

The whole face

I find this the trickiest step to remember, not because the sequence is hard, but because you need to orient the cube properly before you use it.

If you have just one corner with the right colour on top, then put it in the front-left position. Do you now have the top colour on the front face on the right, and on the right face at the back? If so, you can now do the sequence:

`(RUR')(U)(RU2R')`

This flips the three corners other than the front-left, and rotates all the corners 180 degrees around the upper face.  I know saying it “flips” the corners is not precise – there are three sides to the corners, so there are two ways they can flip.  That’s partly why I find it hard to remember how to use this move.

(The move also rotates the edge pieces, without flipping, like so: the front is unchanged while the others are rotated anti-clockwise around the upper face.  Ryan uses this fact to re-use this move for another purpose later.)

If you have just one corner with the right colour on top, but the sequence didn’t work, you will need to put that corner in the front-right and use the mirror image sequence.

If you have zero or two correct top colours on the corners, then you need to know what orientation to hold the cube before using it. This is harder to remember.  See Ryan Heise’s website for the correct orientations. I tend to just keep trying the move over and over, sometimes mirror-imaging it, until something works…

Position the corners

Now that the top face is all the right colour, it is just a matter of rotating the corners and edges around the top face.  Start with the corners.  This sequence will leave the edges untouched and the front-left corner untouched, and rotate the other three corners clockwise around the top face:

`R'(FR')(B2)(RF')R'(B2)R2`

This is pretty tricky, and the only way I can get my head around it is to think through how it affects each piece.

It’s also interesting that with this info, you can think of two ways to rotate the corners anti-clockwise: you could perform the mirror image of this move (starting with the correct corner in the front-right), or you could apply the inverse of this move (i.e. work backwards to undo the move you just did).  These are two very different sequences of moves that have the exact same effect on the cube. More mysteries of the cube!

Position the edges

You can rotate the three edge pieces, other than the back one, clockwise around the top face using the “whole-face” move above, then rotating the entire cube clockwise as viewed from above, and finally performing the mirror-image of the “whole-face” move, i.e.:

`(RUR')(U)(RU2R') [whole cube clockwise] (L'U'L)(U')(L'U2L)`

You have now solved the cube!

Conclusion

Writing this has helped me to understand a little better how these moves work, and certainly to remember them.  I hope it’s helped you too!  I’d love to hear if you’ve seen it explained better somewhere else – I’m just learning this as I go.  Also please let me know if you spot any errors in what I’ve written.

Lua for scripting NPC behaviour

With character movement looking good, now it’s time to give the non-player-characters (NPCs in role-playing game parlance) some behaviour.

I have the idea that monkeys might chase after bananas, foxes after chickens, etc.  And what platform game would be complete without animals mindlessly going back and forth patrolling their platform?

After reading this post at Stoked Software, I like the idea of using Lua to script NPC behaviour, even though I’m sure the simple behaviours above could be much more easily done without it.  I downloaded Lua following the instructions in the second part of that post, and added it to my project by renaming the src folder lua, and dragging it into my XCode project. (Unlike the post, I downloaded Lua 5.2.1, not 5.1.)

Note this is the bare bones DIY approach, not using any existing wrappers like Wax or Corona, which are nicely described at Lua Nova. I’ll try it this way until I get frustrated.

Some initial set up decisions:

• I decided to include the header files directly into the GameModel, since we only want one Lua state.  I was originally thinking of having one per animal.
• Whereas the post adds an instance variable `lua_State *l`, I am adding a `@property (readwrite) lua_State *luaState`.
• Also, to keep the NPC control separate from the rest of my code (in case I decide one day to use something other than Lua), I have added an NPC category to GameElement.

Some hurdles:

• I get lots of “Undefined symbols for architecture i386:” errors, starting with one for `luaL_error`, the first Lua call I was trying to make. I posted a question on stack overflow which quickly sorted this out: it is because Box2D is in C++, but Lua is in C.  So you need to wrap the Lua includes with an `extern "C"` command. (See stack overflow for the precise solution.) In fact you’ll also need to wrap all the upcoming C code in this.
• I get the error “Use of undeclared identifier ‘`self`‘” when the static C function which communicates with Lua tries to access the GameElement `self`. This is OK, the C code doesn’t have any concept of self; it means you have to pass the relevant object from Lua to C. Fortunately, the Stoked Software blog explains how to do this in Part 3, for enemy ships.
• ARC – I have used `__bridge` everywhere so there is no transfer of ownership, would appreciate any thoughts on whether that’s correct.
• Lua 5.2 does not use `luaL_register`, but instead `luaL_setfuncs`.  There’s a good discussion on the Lua users wiki, but in the end I could not make this work, so had to go back to Lua 5.1. Any advice on how to apply this to Lua 5.2 would be gratefully received.
• The Stoked Software blog gives great examples of how to send position data from Objective C to the Lua script, and how to get the Lua script to trigger methods in Objective C so long as the only parameter is a single object.  However, I want to set a target point using Lua.  I have stumbled upon one way to do this, hinted at by the Lua users wiki, using `luaL_checknumber`, e.g.
```static int setTarget(lua_State *luaState) {
//
// Parameters: The GameElement whose target you want to set
//             The x-coordinate of the target
//             The y-coordinate of the target
//
// Returns: nothing
//
GameElement *element = (__bridge GameElement *)lua_touserdata(luaState, 1);
float x = luaL_checknumber(luaState, 2);
float y = luaL_checknumber(luaState, 3);
NSLog(@"target (%6.2f, %6.2f) %@ %p",x,y, element.appearName, element);
[element touchLocation:Point3DMake(x,y,0.)];
return 0;
}```

and then from the Lua script, it’s just:

```function process(gameElement)
game.setTarget(gameElement, 1.1, 0.5)
end```

I have no idea if this is a good way to do it, but it works.

With those hurdles surmounted, I can now use Lua to script my NPC behaviour.  I just need to think what that should be…

One last note – I see that the license for Lua requests that users give Lua credit (see the download page).

Controlling character movement with Box2D

So – the next challenge is a nice way to move the player’s character with Box2D. I would like the user to touch a spot in the game, and have the character try to move to that location (noting that the place on the screen may be different if the world scrolls).  The character should move at constant speed while on the ground, and follow normal physics while falling. I also like the little bounce the character gets with Box2D on landing on the ground after a fall.

For now, I am just representing the character as a ball, but ignoring its rotation for drawing.  I realise now this representation actually matters, since a ball rolls along the ground differently to how a box slides. If I need more realism, I expect to replace the ball representation with a small ball for the legs and a custom shape for the body, with a (wheel?) joint holding the two together, like a car.

Here are some alternatives:

1. Apply an impulse to the character every update (1/60th of a second)
I was using code like this in GameElement:

```-(void) applyImpulseToVelocity:(Point3D)targetVelocity {
b2Vec2 vel = self.body->GetLinearVelocity();
float dvx = targetVelocity.x - vel.x;
float dvy = targetVelocity.y - vel.y;
float mass = self.body->GetMass();
self.body->ApplyLinearImpulse( b2Vec2(mass * dvx,mass * dvy),
self.body->GetWorldCenter() );
}```

The target velocity is basically proportional to the distance between the character’s current location and the touch location (modified so that the character can’t fly).
The problem is, this doesn’t look realistic at all: when the character is falling, gravity has very little effect on it – it just drifts down slowly.

2. Use a mouse joint
This is inspired by Ray Wenderlich’s breakout tutorial. According to the Box2D manual, a mouse joint attempts to drive a point on the body to the target. It required a bit of a rewrite of GameElement and GameModel, because the mouse joint needs to know the world and the ground body, which I was hoping to isolate from the GameElement.
Quite an interesting effect: the character speeds to the touched location and then spins around it at a small radius as if on a rope.  Gravity does act on it at this point, if not while it speeds along. Not the game play I was after.
Also, the manual advises “Many users have tried to adapt the mouse joint for game play. Users often want to achieve precise positioning and instantaneous response. The mouse joint doesn’t work very well in that context. You may wish to consider using kinematic bodies instead.” Hmmm… kinematic bodies, the manual says, do not respond to forces, and do not collide with static or other kinematic bodies. You normally move them by setting their velocity.  I don’t think I’ll pursue this option: I definitely want forces to apply in some situations, and want them to collide with static bodies.

3. Apply an impulse to the character every update (1/60th of a second), but only when in contact with the ground or a platform
This approach most closely matches the description of what I want. It felt like a hack but in fact, humans can only propel themselves when on the ground, so it is (somewhat) realistic. With the contact listener already working, this was not too hard to implement. The main work was changing the ground to a GameElement (it was previously just a part of the GameModel), and setting user data for the ground, platforms and ladders as well as animals. The contact listener needs the user data to send a begin/end contact message to the object.
This is virtually the same as option 1 above, but is only applied if a flag is set on the character’s GameElement saying that it is in contact with the ground, a platform or a ladder.  In fact all these are subclasses of the Platform class, so the test is very simple.
Great news – this works pretty well!

Nonetheless I expect this is not the end of the story…

Cocos2D, Box2D and MVC

As I indicated in my last post, I am going to write my kids’ game in Cocos2D. After implementing the simple bear animation tutorial from Ray Wenderlich, I had a few questions:

1. How do you use automatic reference counting (ARC) with Cocos2D? The approach I’ve taken is to follow this blog by Steffen Itterheim.
2. How do you write code with Cocos2D (and maybe with Box2D) in an MVC (model-view-controller)-compliant way?  The approach I’ve taken is to follow this blog and its sequel by Bartek Wilczyński.
3. How do you add Box2D to the project once you’ve already started it (and continue to use ARC)?  The approach I’ve taken is to make it a static library by following this blog by Red Glasses. This is a pretty involved procedure but does the job. I imagine you can do point (1) above using this approach too – it would be nice to be consistent – but I have not tried this.

I’ve done all this and got it all running, and I thought others may find it helpful, so I have put the result on github at https://github.com/RacingTadpole/Cocos2D-Box2D-MVC-example. You are welcome to download it as a starting point for your own projects, or just to poke holes in it (but please tell me what they are!). The frame rate seems to be only 20-30 frames per second on the simulator, but on a real device it is close to 60, and I have read elsewhere that this stat should be ignored on the simulator anyway. Edit – the project on GitHub was compiled using a slightly older version of XCode, and the latest XCode complains when I try to run it on a device (ld: file is universal (2 slices) but does not contain a(n) armv7s slice: …./libbox2d-lib.a for architecture armv7s ). For now I am solving this by setting “Build Active Architecture Only” to “Yes” in the target’s build settings (see this stackoverflow question), but in the long run it looks like I’ll need to redo step 3 above using the latest XCode.

The game as it stands (called Zambazi) simply involves a host of monkeys and bears falling from the sky onto a grassy foreground, and bouncing like rubber balls. When you touch anywhere, all the animals are hit with random forces.  It’s not much, but my kids find it surprisingly engrossing! They decided you win if you can make all the bears run off the screen before the monkeys… Maybe I’m not so far from the App Store after all?

All images are from Ray & Vicki Wenderlich’s sites – thank you both for making these freely available!

Here’s the basic structure/flow:

GameController

When PLAY is pressed, a GameController is initialized.  The gameController has a GameView and a GameModel, each of which is initialized. The gameController also schedules the updates.

GameView

The gameView has a delegate (actually the gameController) which currently does nothing, because it doesn’t need to know which sprite you’ve touched. This delegate may be useful if you do need to know – see Bartok’s blog for his vision here. In fact I’m planning instead to remove this delegate and simply register the controller with Cocos2D as a touch delegate, as described here.

The view creates the necessary layers:

GameLayer

The gameLayer is in charge of all the sprites. It knows nothing about the view or the controller, but does have a reference to the model. It also registers itself as an observer of notifications from the model. The notifications are:

• Model initialization – this is so that the gameLayer can get a reference to the model in the first place.
• Revise game elements – this is so that it can set up the sprites that correspond to the model.

The gameLayer starts by loading in all the sprites for the game, and setting up their actions (`CCAction`).  I am sure there is a much better way to do this – but this does the job for now.

It also keeps track of which actions are running. This seems an unfortunate complication, but as far as I know, you need to do this so that you can stop the action later. If you can get away with stopping all actions on a sprite – and maybe you can – then you could remove this stuff and use `stopAllActions` instead.

The gameLayer does not know about Box2D – I see that as a model-level thing.  The gameElements provide their own velocity, where, rotation etc methods.  I have defined a `Point3D` structure to pass around points – this was when I was thinking the model may have a 3D world even if the view is only 2D.  However, with Box2D, the third dimension is irrelevant – so it would be simpler to just use `CGPoint` for example.  I am leaving Point3D nonetheless so that if you want to use this code with a 3D model (without Box2D), it shouldn’t be too hard to adapt it.

The other trick is that gameLayer has an `NSDictionary` (called sprites), with the gameElements as keys and the sprites as the objects. The complication is that `NSDictionary` copies its keys before it uses them, so that the key winds up being a different object to what you requested.  The solution (implemented in my code) is to override `copyWithZone:` to return self, without copying, as described in this stack overflow post.  I am assured this is good practice if the object is immutable. All this may be too tricky by half, but it seemed sensible at the time, and works fine.

GameModel

The game model is the Box2D world, and an array of the game elements. When `createGameObjects` is called (by the Controller – this could equally well be part of the initialization), it sets up some default game elements. It has an `update:` method which uses Box2D to update the physics; optionally each element may have its own additional update behaviour (I have adopted Bartok’s “Updatable” protocol).

GameElement

The gameElements are the models of the platforms, the enemies, etc.  They basically have a Box2D body and a name.  The name is used by the gameLayer to work out what sprite to show. The gameElement uses Box2D to provide where, velocity and rotation methods, so the `body` variable itself is kept private (i.e. in a class extension).

I am subclassing GameElement (e.g. Animal) to provide different behaviour for different models.

Technical note – so that subclasses can still access the `body` variable, I have declared `body` in a class extension header file called `GameElements_Private.h`.  Then `GameElements.m` and `Animal.m` both import `GameElements_Private.h` instead of `GameElements.h`, so that they can refer to `body`.

Further ideas

As I start to turn this into a functioning game, I have found two further issues, one conceptual, one practical:

• It’s nice to cleanly separate the model from the view – but the image you are using is a particular size, and I’m finding the model sometimes needs to know this size (so you don’t have to scale the image). I’m solving this with another delegate pattern.  I’ve introduced a `NaturalSizeProtocol`, which the GameLayer and the GameView follow.  The GameModel then has a `naturalSizeDelegate`.  When a gameElement needs to know its natural size (i.e. the size the view wants to make it), it asks its `naturalSizeDelegate`.  This returns the size in model co-ordinates (as a `Point3D`).  This feels like a contortion of MVC, so I’d love to hear if anyone has a better solution to this.  It has left me wondering if MVC is more trouble than it’s worth after all for image-intensive games.
• Getting a background image to repeat in Cocos2D is hard.  I have only managed it so far by loading the background image multiple times, which doesn’t seem right.

That’s it for now.  Please let me know if you find this useful, or have any suggestions.

Edit – I have just come across Steffen Itterheim’s excellent post on exactly this subject, which inspired him to write KoboldTouch. Together with problems I am having getting Lua to compile in my Cocos2D/Box2D project, I am starting to wish I had used Kobold2D…

A kids’ game

I have an idea for a kids’ game (though there’s quite a bit of competition out there on the App Store!).  The question I’m debating is whether I should implement it as a 2D game or a 3D game. It would only have a fixed camera position, but I’d like some depth to the world, so that characters going up the screen go into the distance, and can then go behind other characters or objects. From Wikipedia’s 2.5D entry, this could be considered “scaling along the z-axis”. I actually haven’t found any games with that sort of view, perhaps because a 2D model looks dodgy (see below), and by the time you have a 3D model, there are so many cooler things you can do with one. Here are the options I’m considering:

2-dimensional graphics

This basically comes down to Cocos2D. I put some code together using Cocos2D for iOS, based on Ray Wenderlich’s tutorial for an animated bear, and made the bear smaller if it goes up the screen and bigger if it comes to the front.  This looks pretty good and is quite simple to do, as long as the bear is not going mostly up or down the screen.  In that case you’d need more animation sequences so the bear faces towards or away from you.  But what if you go on a diagonal away from you or towards you?  I think you’d need those sequences too.  That’s quite a few sequences, and of course whereas any walking angle would be allowed, graphically it would have to snap to one of the 8 available animations. So the problems with this approach are:

1. I couldn’t use freely available art (like Vicki Wenderlich has available)
2. It won’t look awesome – and I’m not sure it will even look good enough.

Also, no 2D physics engines (like those that come with Cocos2D) would work, since the gameplay is not actually 2D. In my case I don’t plan to have any complex physics, so I can make my own.  Potentially though I could use a 3D physics library like Bullet.

3-dimensional graphics

I think this basically comes down to Unity3D (and perhaps Unreal, but I can’t use this on a Mac so it is less appealing), although there are a few other related options out there too. Unity3D is amazing, there are lots of 3D graphical assets available on their asset store, and compiles cross-platform to boot. I have succeeded in building my own terrain in its editor, putting in an eerie sky and swaying grass, and can compile a game to my iPad which lets me look around it (in a first person view).  I followed a youTube demo for this from TechZone. I have also read about ways to layer native iOS elements on top of this – Millipede gives a good explanation of this here, and their Navy Sink’Em game is the best example I’ve found of the camera angle I want, though I didn’t intend that level of realism. Adding a iOS front-end to a Unity project is also covered by this Blurst post. The problems with a Unity3D approach are:

1. Troubleshooting how to do things in Unity is probably harder than I’m used to with Cocoa.
2. Will take some learning how to communicate between Unity and iOS.
3. I can imagine the project flow getting quite complex as I want the player to be able to add assets to the scene, and associate scripts with them. I probably want an iOS interface to do this, which would need to display Unity assets.
4. Costs a bit.
5. I don’t like being forced to use a new development environment, and being locked into Unity’s world.

The other 3D options include:

Cocos3D. There is very little online about this – no tutorials. It also comes with the caveat that it “is not yet compatible with cocos2d 2.x. Please use cocos2d 1.x.”

SIO2. I have just come across this here. It looks promising, as it does not force you into a particular SDK.  I have not investigated this in detail.

Conclusion

I think I’m biting off more than I can chew right now if I try to make a grand 3D game. So I will adopt the 2D framework for now and try to get a good game logic happening.  Perhaps even give up and modify the game flow so that it is a true 2D game (with parallax of course… I always loved Moon Patrol).  Then, if that doesn’t look good enough to release, come back to Unity.

Indie life

Ray Wenderlich‘s monthly newsletter has been my friend this week, especially his links on Indie Game Development and in particular this post from Mode 7, which has a lot of advice and further links on topics from coding to finding people to help do art and animation, to business realities and marketing. The life of the Indie game developer is evidently not easy. Even a good-looking, critically acclaimed game that is featured on the App Store can still be a flop…

Now, was it sensible to spend the evening reading these things instead of developing my game (ummm – ok, I also need to prioritise among the games and non-games I have already started), befriending journalists who work for review sites, or working on my business plan?

Probably not.

Using Gimp

I mentioned before I’d downloaded Gimp, a free paint-style program, to help make graphics for my apps.  I’ve struggled to use it for anything much though, but last night I was able to make a simple tab-bar icon.

To make a tab-bar icon in Gimp:

• Choose File -> New an make a new 60×60 (for retina) image.
• Choose Layer -> New Layer and choose layer fill type “Transparency”.
• Delete the original background layer over in the “Histogram” window: drag the old layer from its position about halfway down the window to the tiny garbage bin in the bottom right corner (on my Mac this is half covered by the window-resizer).
• Now paint into this layer with black where you want the image.  You should only use one colour.  I tried using black and white, and only union of the two shows up in the tab bar.
• File -> Export the picture.

To take an existing image and set a background colour:

• Use the magic wand tool, which selects regions by colour.
• Select the coloured region you want to make transparent.
• Choose Layer -> Transparency -> Add Alpha Channel (if you can).
• Choose Edit -> Clear.

I expect you can use this directly as a tab bar icon now – just the remaining colour information will be ignored.  But I have yet to test this.

Time for sound

Time for sound.  In iOS it looks like sound can be played by AVAudioPlayer, and recorded by AVAudioRecorder.  The broader framework is called AVFoundation.  However, at a very low level there is also the Core Audio framework, which includes the Audio Toolbox and Audio Unit frameworks.

There are some great sample projects available at Apple’s Audio & Visual Starting Point:

• AddMusic shows how to pick songs from the iTunes library.  This also includes setting up an AVAudioSession, which I’m not sure is necessary.
• avTouch shows how to play sounds using AVAudioPlayer.
• SpeakHere shows how to record sounds using AQRecord.  On closer inspection this looks extremely daunting.
• AVAudioRecorder is another approach that looks a lot easier, as documented in this Stack Overflow post, and this Techotopia post.  However, there is a subtlety when you try to play the recorded sound in an AVAudioPlayer – for some reason using
```self.recordingPlayer = [[AVAudioPlayer alloc]
initWithContentsOfURL:self.audioRecorder.url error:&error];```

does not ever call the delegate routines when the URL is that of the recorded sound (in either the simulator or the device). So instead, I used

```NSData* recordedData = [NSData
dataWithContentsOfFile:[self.audioRecorder.url path]];
self.recordingPlayer = [[AVAudioPlayer alloc]
initWithData:recordedData error:&error];```

- which worked fine.  Another gotcha is to make sure the AVAudioPlayer object is not disposed of at the end of the method, but before the playing actually happens. My solution was to make it an instance variable (as in the sample code above).

• Audio UI Sounds (SysSound) shows how to play alert sound-effects, but on closer inspection comes with the warning this should not be used for other sound effects, e.g. in games.
• OpenAL is one solution, with sample code called oalTouch.  This comes with some C code (MyOpenALSupport.c) which looks handy, if a little daunting.  Note that to call this with Automatic Reference Counting (ARC), you need to use `(__bridge CFURLRef)` and then delete the line `CFRelease(fileURL);`. I forgot this last part and it took a while to realise what was going on.  There is also a great basic tutorial by Ben Britten.

The Multimedia Programming Guide – Audio has more context.  And as usual, Ray Wenderlich has a great summary and tutorial.

I found strange behaviour with AVAudioSession.

• You can provide a category to the session, and I chose `AVAudioSessionCategorySoloAmbient`, which is meant to silence sound from other apps.  However it seems to also silence OpenAL and other AVAudioPlayer sounds from the same app. Switching to `AVAudioSessionCategoryAmbient` solved this problem for me.
• I had set my category to `AVAudioSessionCategoryAmbient` while setting up the audio recorder, but changed it to `AVAudioSessionCategoryRecord` just before the  `record` command; I changed it back again after recording stops.  This worked on the simulator, but on the device the call to `record` simply returned NO with no explanation, and nothing was recorded.  I spent most of a day trying to work out why.  The answer: use the category `AVAudioSessionCategoryPlayAndRecord` while setting up the recorder.