Tag Archives: game

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.

Panguru Online

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.

  

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…