Blocks, and a Responsive User Interface

By Kevin Packard                        twitter@kevinpackard

Just in time for Apple’s WWDC, I connected the Three Straight game engine to the proto-UI. The result is a very playable game, now available for preview on your iPad, iPhone, or iPod Touch.

I already had the brain: a working game engine running on my Mac, using the Mini-Max algorithm.  And I had a body: the board and marble prototype UI. All I had to do was connect them together.

 

All This, and Brains Too !

Here’s the code that connects brain to body:

 1.  - (void) dragDidEnd:(MarbleView*)marble {
 2.     Position position = [self boardPositionFor:marble.center]; 
 3.     BOOL legalMove = [_engine opponentTurn:marble to:position]; 
 4.     [self updateMarblePositions:FAST]; 
 5.     if( legalMove == YES && _engine.isGameOver == NO) { 
 6.        [_engine computerTurn]; 
 7.        if( _engine.isGameOver ) 
 8.           [self updateMarblePositions:FAST]; 
 9.        else
10.           [self updateMarblePositions:SLOW]; 
11.     } 
12.  }
13.  
14.  - (void) updateMarblePositions:(NSTimeInterval)duration {
15.     [UIView beginAnimations:@"UpdateMarbles" context:nil];
16.     [UIView setAnimationDuration:duration];
17.
18.     for( int i = 0; i < 4; ++i ) {
19.        _playerMarble[i].center = [self boardLocationFor: 
20.                         [_engine positionForPlayerMarble:i]];
21.        _computerMarble[i].center = [self boardLocationFor:
22.                         [_engine positionForComputerMarble:i]];
23.     }
24.  
25.     [UIView commitAnimations];
26.  }

 

The human player makes a move by dragging a marble to a new board position.  The method -dragDidEnd is called when the player lets go of his marble.  On line 2, a board position is calculated from the marble’s new location.  On line 3 the player’s move is passed to the game engine.  If the move is legal, the engine updates its internal model of marble positions, and returns YES.  If the move is illegal, the engine returns NO.

Line 4 serves two purposes.  If the move is illegal, the player’s marble is returned to its old position.  You can demonstrate this by dragging a marble to the other side of the board, and letting go.  If the move is legal, the player’s marble is near the new position, but not exactly on it: his marble needs to be moved to the exact location, so that it appears to settle into place.

The method -updateMarblePositions (Lines 14-26) starts a Core Animation sequence.  The duration of the animation sequence is passed in: FAST for 1/4 second, or SLOW for 1 full second.  This method is non-blocking.  That is, the animation sequence starts, but –updateMarblePositions returns immediately.  The animation continues for the supplied duration, and will complete some time in the future.

If the player’s move is legal and the game is not over, then Line 6 asks the engine to make a move for the computer.  The operation is synchronous, and can take several seconds while the game engine “thinks”.  It will not return until it’s finished.  When it does return, the internal model of marble positions is updated with the computer’s move.

Lines 7-10 animate the computer’s marble to its new position.  Note that it moves the marble slowly (SLOW), unless it wins, in which case it pounces rapidly (FAST).  I’m told that this little bit of personality adds to the addictiveness of the game … (!)

 

The Frankenstein Moment

I tried it.  It didn’t work.  At least not as intended.

When I made a move, my marble didn’t settle into place.  Instead, it stuck where I let go: near the board position, but not directly on it.  Once the computer was done thinking, my marble snapped into place, while the computer’s marble smoothly animated to its new position.

But wait – when I made an illegal move, my marble nicely flew back to its original position.  Hmmm…

Looking at the code, it’s pretty clear that Line 6 is the culprit.  Asking the engine to calculate the computer’s move causes the main thread to block while the engine “thinks”.  And apparently, blocking the main thread immediately after setting up a Core Animation sequence prevents the sequence from starting.  Who knew?

 

Back to the Drawing Board

I thought about adding a timer to delay the engine.  Or putting the engine on a separate thread.  Or using lower-level Core Animation methods.  Instead, I decided to experiment with Blocks.

 

Blocks. What are they?

A Block is a C-language extension that describes an anonymous chunk of work: an anonymous function, plus the data referenced by that function.  Blocks are used for callbacks, iteration, and concurrency.  They’re often declared inline, which improves readability.  There is a wealth of information online about blocks on Wikipedia, and on Apple’s Developer site, so I won’t cover the details.

 

Blocks for Concurrency

In this case, I’m using Dispatch Blocks to manage concurrent work.  That is, we want to schedule the game engine to execute in a Block asnychronously, so the main thread is free to animate marbles.

For concurrency, a Dispatch Block must be scheduled on a queue.  The iOS operating system maintains two important queues for an app:

– the main queue: blocks execute serially, on the main thread. Any block that manipulate the user interface must execute on the main thread.

– the global queue: blocks execute in parallel, using any available resources. Blocks on the global queue may not touch the user interface.

Here’s a new -dragDidEnd method, using blocks:

 1.  - (void) dragDidEnd:(MarbleView*)marble {
 2.     Position position = [self boardPositionFor:marble.center]; 
 3.     BOOL legalMove = [_engine opponentTurn:marble to:position] 
 4.     [self updateMarblePositions:FAST]; 
 5.     if( legalMove == YES && _engine.isGameOver == NO) { 
 6.        dispatch_async( dispatch_get_global_queue(0,0), ^{
 7.           [_engine computerTurn]; 
 8.           dispatch_async( dispatch_get_main_queue(), ^{
 9.              if( _engine.isGameOver ) 
10.                 [self updateMarblePositions:FAST]; 
11.              else
12.                 [self updateMarblePositions:SLOW]; 
13.           });    
14.       }); 
15.     }
16.  }

What’s changed? Line 6 does three things. First, the ^{ marks the beginning of a block that ends on Line 14. Second, dispatch_get_global_queue(…) returns the system’s global background queue.  Third, dispatch_async(…) schedules the block for asynchronous execution on that queue. All together, Line 6 reads “asynchronously execute this block on the system’s background thread.

Line 7, the expensive game engine “thinking” now takes place asynchronously in the background, along with the rest of the block. This means -dragDidEnd now completes without blocking, and the animation created on Line 4 is free to run.

After the engine has finished thinking, the new marble positions need to be updated. However, this block is not executing on the main thread. It’s not safe to touch the user interface. So Line 8 schedules a second block to execute on the main thread, by calling dispatch_get_main_queue() to get the main thread queue. This second block defines the animation that updates the board with the computer’s move.

The results are perfect: the game engine begins thinking at the same time the UI is animating the last marble move.  Try it yourself, by making moves as fast as possible.  If you’re quick, you can make your move while the computer’s marble is still animating, and start the game engine thinking before his last move is even in place.

The main takeaway is:

– blocks are declared inline, which improves readability

– blocks are lighter-weight than threads and work queues, and far less error-prone.

 

Now for Something You’ll Really Like

I hope. The game engine currently recurses serially in a depth-first search for the best possible move. I’ve squeezed about all I can out of the algorithm for detecting wins and losses. In order to gain further speed, I need to leverage all available cores. To leverage cores, I need to convert the engine to blocks. It’s a work in progress, involving the creation of private dispatch queues, and block synchronization. It will be interesting to see what happens when hundreds of thousands of blocks are scheduled to run concurrently.

If it works, it has the interesting effect of changing the search pattern from depth-first to breadth-first. The advantage is that when the computer is pinned down, and can only move one or two marbles, the search can run deeper in the same amount of time as a shallower search with four marbles to move.  Breadth-first searching also allows for better search tree pruning, which is another place to improve the engine speed.