Launching Pad blog
How Zoo Lasso works, part one: looping
For a while now, I’ve been meaning to write a series of posts about how Zoo Lasso is put together internally, in the hope that it can help other budding iPhone developers. Some nice people on the cocos2d forums have been asking about the mechanics behind the loop drawing and animal grouping, so that seems a good place to start.
Note that the game use the rather fantastic cocos2d for iPhone, so the code relies heavily on that framework.
Some caveats:
- Before this project we had never done anything with the iPhone SDK, Objective-C or cocos2d. There are a lot of things I’d approach differently knowing what I know now.
- I’m very much still learning programming craft. There is plenty of bleeding between what should probably be separate model, view and controller code. (But writing about your messy code helps you write less messy code next time, right?
- My mathematical skills are weak, so don’t expect the World’s Most Efficient Algorithms.
With those in mind, read on!
DrawingLayer reads the touches
In Zoo Lasso, the player must encircle groups of like animals with their finger. Matters are complicated by the possibility of using figure-eights or clover-leaves around multiple species, but in any case we first need to read the positions of the player’s finger.
In this case, multi-touch events are a big no-no — we just want a nice linear array of touch positions from the moment the player puts their finger down until it comes off again. Cocos has a suitable delegate known as a TargetedTouchDelegate, so the first step in building a class is:
@interface DrawingLayer : Layer <TargetedTouchDelegate> {
Polygon *polygon;
}
(A Polygon object simply holds an array of points and a few extra bits and pieces.)
How does a TargetedTouchDelegate work? Basically it needs to implement three methods:
- (BOOL)ccTouchBegan:(UITouch *)touch withEvent:(UIEvent *)event;
- (void)ccTouchMoved:(UITouch *)touch withEvent:(UIEvent *)event;
- (void)ccTouchEnded:(UITouch *)touch withEvent:(UIEvent *)event;
In ccTouchBegan, you’ll want to return YES to ‘claim’ the touch, ensuring that ccTouchMoved and ccTouchEnded receive their follow-up touch events.
Here is our implementation of those methods plus a helper method, leaving out the particle-related view code.
- (BOOL)ccTouchBegan:(UITouch *)touch withEvent:(UIEvent *)event {
polygon = [[Polygon alloc] init];
[self appendPointFromTouch:touch];
return YES;
}
- (void)ccTouchMoved:(UITouch *)touch withEvent:(UIEvent *)event {
[self appendPointFromTouch:touch];
[[(GamePlayfieldLayer *)parent loopsLayer] extractLoopFromPolygon:polygon];
}
- (void)ccTouchEnded:(UITouch *)touch withEvent:(UIEvent *)event {
// A more forgiving loop detector is used at the moment the finger comes off
// To compensate for Nic-style looping technique
[[(GamePlayfieldLayer *)parent loopsLayer] extractLoopFromPolygon:polygon loopClosingDistance:120];
[polygon release];
polygon = nil;
[(GamePlayfieldLayer *)parent removeAnimalsInLoops];
}
- (void)appendPointFromTouch:(UITouch *)touch {
ZLPoint *newPoint = [ZLPoint newPointWithCGPoint:[[Director sharedDirector]
convertToGL:[touch locationInView:[touch view]]]];
[polygon appendPoint:newPoint];
[newPoint release];
}
Ouch, this is clumsy code — it’s amongst the first that we wrote, and clearly hasn’t been revisited often — but it gets the job done. As you can see, when you first touch and when you move your finger, an x-y point is space-converted and added to polygon.
When you move your finger, another layer (LoopsLayer) is instructed to try to derive or ‘extract’ a closed loop from the current polygon. This also happens when the touch ends, but as you can see from the comment I’ve left in, our tester Nic found that loops sometimes wouldn’t register, so we increase a tolerance value. We’ll look at this mysterious value and the rest of the extraction process below. (Note that we attempt to extract loops while the touch is still in progress — there are good reasons for this which I’ll also cover.)
Finally, when the touch is finished, we reset the polygon and can at last check whether animals are inside the loops. But first we have to find the loops themselves…
LoopsLayer extracts loops out of the touches
So, we need to find the loops as the player’s touch is in progress. The first consideration is that there are two different ways us humans go about drawing loops. We might cross back over our own line, or we might just want to end quite close to where we started (see my super-classy illustration). The game needs to understand both ways, especially the ‘cross-over’ method as it’s important for Zoo Lasso’s gameplay hook, the multiple-loop combos.
I won’t publish the complete code here, because it’s an embarrassing mash of to-ing and fro-ing between different classes. But here are the basic principles:
Loops are detected as the player draws, and their points are removed from the drawn polygon’s array of points. (You can actually see this happening in-game — the brighter ‘sparkle’ of particles means that a loop has been identified.) This means we only need to worry about the points that are not so far marked as a loop. In the diagram, we would now only need to worry about the bottom bits to the left and right of the loop’s intersection point.
Loops need to be larger than a certain width and height, because we don’t want a microscopic ‘loop’ to register. [Polygon appendPoint:] updates minPoint and maxPoint as new points are added:
- (void)checkPointForMaxAndMin:(ZLPoint *)point {
if (maxPoint == nil) {
maxPoint = [point copy];
minPoint = [point copy];
return;
}
minPoint.x = minimum(point.x, minPoint.x);
minPoint.y = minimum(point.y, minPoint.y);
maxPoint.x = maximum(point.x, maxPoint.x);
maxPoint.y = maximum(point.y, maxPoint.y);
}
(minPoint and maxPoint can be used to derive the width and height. Think of them as the bottom-left and top-right corners of a bounding rectangle.)
If the current touch was very close to the starting touch, the player probably wants to close the loop, assuming that the entire loop is large enough (width and height-wise). This is doubly true if they’re also taking their finger off at this point. As you saw above, the ‘loopClosingDistance’ is increased to 120 in that case (from a default of 40).
To check whether they’re close enough to the start point, you just need to measure the distance between the start point and the end point. Foolishly, I built this custom line-segment-length method:
+ (float)lengthWithCGPointStart:(CGPoint)start end:(CGPoint)end {
return sqrtf(pow(end.x - start.x, 2) + pow(end.y - start.y, 2));
}
But see that code? Erase it from your memory for ever. In a future update, I’ll be replacing all calls to it with calls to this perfectly good (C-style and presumably much faster) built-in function from CGPointExtension.m:
CGFloat
ccpDistance(const CGPoint v1, const CGPoint v2)
{
return ccpLength(ccpSub(v1, v2));
}
Lesson: get to know the built-in libraries, because they probably work pretty well. (And of course the code would be faster if it didn’t need to call sqrt() at any stage, but we’ll leave that optimisation for another day.)
If the polygon crosses over itself, you’ve got yourself a loop.
Okay, so what the player has drawn can be thought of as a series of connected points, or as a series of line segments. We’ve thought of the polygon as points up until now, but at this stage we need to think about it as line segments.
Each new point that is captured ‘creates’ a line segment with the previous last point. Something like:
[LineSegment segmentWithStartPoint:[polygon lastObject] endPoint:latestTouchPoint]
(My actual code is uglier than that.) So it’s a question of looping through all the previous line segments and checking whether any of them intersect with the just-created one. (Remembering that we only need to worry about line segments that aren’t already part of a loop.)
So how do we actually calculate whether our new line segment intersects another line segment? This is the tricky part, and it’s where my limited maths and geometry sent me on a quest to gain more understanding and to (hopefully) find some public domain code which I could adapt. Low and behold: this great article by Darel Rex Finley. Have a read!
Since we’re interested in line segments rather than complete lines (those theoretical entities which stretch into infinity), we can go ahead and adapt his last code example (which is a C function, so put it outside your @implementation block):
// public domain function by Darel Rex Finley, 2006
// Changed by Tim Knauf to use only single-precision floats
// Determines the intersection point of the line segment defined by points A and B
// with the line segment defined by points C and D.
//
// Returns YES if the intersection point was found, and stores that point in X,Y.
// Returns NO if there is no determinable intersection point, in which case X,Y will
// be unmodified.
bool lineSegmentIntersection(
float Ax, float Ay,
float Bx, float By,
float Cx, float Cy,
float Dx, float Dy,
float *X, float *Y) {
float distAB, theCos, theSin, newX, ABpos ;
// Fail if either line segment is zero-length.
if (Ax==Bx && Ay==By || Cx==Dx && Cy==Dy) return NO;
// Fail if the segments share an end-point.
if (Ax==Cx && Ay==Cy || Bx==Cx && By==Cy
|| Ax==Dx && Ay==Dy || Bx==Dx && By==Dy) {
return NO; }
// (1) Translate the system so that point A is on the origin.
Bx-=Ax; By-=Ay;
Cx-=Ax; Cy-=Ay;
Dx-=Ax; Dy-=Ay;
// Discover the length of segment A-B.
distAB=sqrt(Bx*Bx+By*By);
// (2) Rotate the system so that point B is on the positive X axis.
theCos=Bx/distAB;
theSin=By/distAB;
newX=Cx*theCos+Cy*theSin;
Cy =Cy*theCos-Cx*theSin; Cx=newX;
newX=Dx*theCos+Dy*theSin;
Dy =Dy*theCos-Dx*theSin; Dx=newX;
// Fail if segment C-D doesn't cross line A-B.
if (Cy<0. && Dy<0. || Cy>=0. && Dy>=0.) return NO;
// (3) Discover the position of the intersection point along line A-B.
ABpos=Dx+(Cx-Dx)*Dy/(Dy-Cy);
// Fail if segment C-D crosses line A-B outside of segment A-B.
if (ABpos<0. || ABpos>distAB) return NO;
// (4) Apply the discovered position to line A-B in the original coordinate system.
*X=Ax+ABpos*theCos;
*Y=Ay+ABpos*theSin;
// Success.
return YES; }
Astute readers will notice that the only things I have changed from Darel’s original code are the number types: double becomes float. As I understand it, the less-precise-but-certainly-fine-for-our-purposes floats have a speed advantage over more-precise doubles, at least on the newer iPhone 3GS. (Do test these things for yourself, though!)
We now have an array of loops
As loops are identified, we add them to an array of loops. So when the player finally takes their finger off, we are ready to check each loop for animals. But that will have to be an explanation for next time. Thanks for reading and see you then!
