Lifting the orb

07 May 2014

As mentioned in the previous post, next on the todo list was the game logic and supporting functions required to have the player ship lift the orb using its tractor beam. I was able to spend a few hours almost every day of the previous week and made some nice progress, things are starting to come together nicely now.

A few things had to be sorted out before the orb-lifting game logic could be implemented as part of the K14Ship step method. Most notably, I needed the K14Planet peek method I already talked about way back when I designed the first iteration of the data model for the game. The peek method should basically implement a planet query, returning all entities visible from a certain viewpoint and direction. It is used to check whether the orb is in range of the tractor beam when it is activated.

In addition to the K14Planet peek method, a few state tracking variables had to be added to K14Ship, indicating whether the tractor beam is active, whether the orb is in attached (but not lifted) state, and whether it is being lifted. I won’t go into much detail about these since they are pretty much self-explanatory, instead I’ll dedicate this post to just the peek method and the actual orb lifting game logic.

The planet peek method

The problem to be solved by the peek method can be formulated as ‘find all entities (partially) inside the viewing cone defined by an origin (location), depth (distance) and breadth (field-of-view angle). The following diagram illustrates the basic idea:

The green squares represent entities that are considered ‘visible’, the red square is an entity outside the field-of-view. The viewing cone can be extended to a full 360 degree angle for an omnidirectional field of view. Translating the relevant parameters for the peek operation, I ended up with the following K14Planet selector:

-(NSArray ) peekFromPosition: (CGPoint) position 
                        angle: (float) angle 
                          fov: (float) fov
                  maxDistance: (float) distance;

Instead of thinking the problem through first, I immediately started out hammering in a function that would iterate all entities, and for each entity determine visibility by calculating a vector from the viewing cone origin to the entity center, then testing the angle between this vector and all corner points of the entity bounding box. If one or more corner points were within half of the view direction at less than the viewing distance from the viewing cone origin, the entity was considered ‘visible’. This seemed like a solid approach, but actually it wasn’t. Suppose for example that there’s a really wide entity somewhere very close to the origin of a very narrow, but very deep viewing cone, ie: a small field-of-view angle but a large viewing distance. The viewing cone could cross the entity, but all of the corner points of the entity bounding box could be far outside of it. This wasn’t going to work and I needed to come up with something different.

A quick search on Google revealed a solution so obvious I should have figured it out myself before wasting the better part of 2 hours on a defective solution. Especially considering my coworker Ton already mentioned it to me, having implemented a solution to a similar problem at work. The visibility test is basically a 2D convex polygon intersection (overlap) test between the entity countour (its translated, rotated bounding box), and a polygon representing the viewing cone. The polygon intersection test can be implemented by a very simple and elegant algorithm based on the separating axis theorem. The premise of this theorem is that two convex polygons do not intersect if you can draw a line that separates them, and that you can find such a line by projecting the vertices of both polygons on an orthogonal line (the separating axis) to get the projection intervals (‘shadow’) of both objects. If the intervals do not overlap, any line between them that is orthogonal to the separating axis, will separate the two shapes. The Wikipedia page does a great job explaining the theorem, so I’ll just refer to that for a more in-depth treatment.

The intersection algorithm itself is actually very easy to implement, it took me only 30 minutes. I still had to add a contour property to the K14Entity method to get the transformed bounding box for an entity, and inside the K14Planet peek method I needed to setup a polygon representing the viewing cone. I chose to sample the arc at the end of the viewing cone every 1/4⋅π radians (45 degrees), which should me more than sufficient for visibility testing. The whole peek function now just came down to iterating all planet entities, getting their contour polygon, and returning all entities with a contour overlapping the viewing cone polygon.

For anyone interested, here’s the full source code for my 2D convex polygon-polygon intersection function that uses the separating axis theorem, maybe I’ll save someone some time having to implement this themselves. Feel free to use this snippet if you have a use for it:

BOOL polygonsIntersect(NSArray *polygon0, NSArray *polygon1)
{
  // If either one of the polygons has less than 3 points (degenerate),
  // the rest of this function makes no sense. Just return 'no intersection'.
  if ((polygon0.count < 3) || (polygon1.count < 3))
  {
    return NO;
  }
  
  // Iterate edges of the first polygon, and test whether all points of the second
  // polygon are on the same side of it. If they do, we found a separating axis,
  // and the two polygons do not intersect.
  for (int i = 0; i < polygon0.count; i++)
  {
    CGPoint v0 = [polygon0[i] CGPointValue];
    CGPoint v1 = [polygon0[(i+1) % polygon0.count] CGPointValue];
   
    // Create vector perpendicular to edge vector v1-v0
    GLKVector2 pv = GLKVector2Normalize(GLKVector2Make(v1.y - v0.y, -(v1.x - v0.x)));
   
    // Project polygon0 and polygon1 points onto p, tracking their projection interval
    float t0_min = INFINITY;
    float t0_max = -INFINITY;
    float t1_min = INFINITY;
    float t1_max = -INFINITY;
    
    for (NSValue *p in polygon0)
    {
      float t = GLKVector2DotProduct(pv, GLKVector2Make(p.CGPointValue.x, p.CGPointValue.y));
      
      t0_min = MIN(t0_min, t);
      t0_max = MAX(t0_max, t);
    }
    
    for (NSValue *p in polygon1)
    {
      float t = GLKVector2DotProduct(pv, GLKVector2Make(p.CGPointValue.x, p.CGPointValue.y));
      
      t1_min = MIN(t1_min, t);
      t1_max = MAX(t1_max, t);
    }

    // If the projection intervals for both polygons do not overlap, the current polygon0
    // edge is a separating axis, and the polygons do not overlap. We bias the interval
    // check towards determining no overlap in case the projection intervals are touching.
    if (((t0_min + COMPARE_EPSILON) > t1_max) || ((t0_max - COMPARE_EPSILON) < t1_min))
    {
      return NO;
    }
  }
  
  // Tested all polygon1 points against all polygon0 edges, but found no separating
  // axis. This means the polygons intersect.
  return YES;
}

The orb-lifting game logic

With the peek method in place, having added a tractor beam input action, and K14Ship flags to track whether the tractor beam is active and whether the orb is attached or already lifted, the actual orb-lifting game logic was pretty straightforward to implement. Whenever the tractor beam is activated while the orb is within range, the orb is attached until the tractor beam is deactivated. When during that time, the distance between the orb and the player ship increases beyond the tractor beam range, the orb is lifted by creating a Box2D distance joint that between the ship and the orb. After lifting the orb, it cannot be de-attached anymore.

All of the orb-lifting game logic is implemented inside the K14Ship step method called at regular intervals. The idea is to eventually make this kind of logic fully scriptable, which means it should only depend on high-level public interfaces. At this point in time, this isn’t possible yet as I didn’t add abstractions and interfaces for creating joints between entities, instead I’m calling Box2D directly from inside the step method. The following code snippet is taken verbatim from the K14Ship step method:

-(void) step: (NSTimeInterval) dt

  // ...

  // Handle tractor beam game logic
  self.tractorBeamActive = [self.planet.game.inputs isInputActive:K14_INPUT_TRACTOR_BEAM];
  
  if (self.tractorBeamActive)
  {
    if (!self.orbAttached && !self.orbLifted)
    {
      // Tractor beam active, and orb not attached or being lifted. Peek around 
      // to see whether the orb is within the tractor beam range. If so, attach it.
      NSArray *entities = [self.planet peekFromPosition:self.position 
                                                  angle:self.angle 
                                                    fov:2.0f*M_PI
                                            maxDistance:self.tractorBeamRange];
      
      for (K14Entity *entity in entities)
      {
        if ([entity.entityClass isEqualToString:K14Orb.entityClass])
        {
          self.orbAttached = YES;
          self.orb = (K14Orb *) entity;
          break;
        }
      }
    }
    
    if (self.orbAttached && !self.orbLifted)
    {
      // Tractor beam active while orb attached but not lifted yet. Test whether 
      // the distance from ship to orb exceeds the tractor beam range. If it does, 
      // we lift the orb.
      CGPoint pp = self.position;
      CGPoint op = self.orb.position;
      
      float d = GLKVector2Length(GLKVector2Make(op.x - pp.x, op.y - pp.y));
      
      if (d >= TRACTOR_BEAM_RANGE)
      {
        // Orb lifted! Create a joint between the ship and orb entity
        b2DistanceJointDef jd;
        
        jd.bodyA = self.body;
        jd.bodyB = self.orb.body;
        jd.length = self.tractorBeamRange;
        jd.localAnchorA = b2Vec2(0.0f, 0.0f);
        jd.localAnchorB = b2Vec2(0.0f, 0.0f);
        
        self.orbJoint = (b2DistanceJoint *) self.planet.world->CreateJoint(&jd);
 
        self.orbLifted = YES;
      }
    }
  }
  else
  {
    // Tractor beam inactive
    if (self.orbAttached && !self.orbLifted)
    {
      // In case the orb was attached but not yet being lifted, it isn't anymore now...
      self.orbAttached = NO;
      self.orb = nil;
    }
  }

  // ...

Orb lifting in action

Here’s a video showing orb lifting in action. I simply tweaked the action replay I’ve been using so far, adding simulated inputs to activate/deactivate the tractor beam at the right moment. I also added some color-coding to the renderer for debugging purposes, using a debug color that entities can set on themselves. The K14Ship entity sets this color to red when thrust is active, blue when the tractor beam is active, or purple when both are active. Otherwise it’s set to yellow. To top it off, I also draw a line between the orb while it is attached. Don’t mind the missing edges at the far left and right of the planet surface by the way, they got lost as a side effect of the refactored wraparound code, I didn’t care enough to modify the debug renderer to render them again. None of this is supposed to be pretty yet! ;-)

Next steps

With world-queries implemented through the K14Planet peek method, and inputs and state tracking for the tractor beam, it should be trivial to implement the fuel pickup logic. After that, it’s probably a good time to add the game logic to kill entities or the player when collisions, and to implement game termination conditions. I’ll likely want to add a round of cleanup and refactoring around that time.

Development scoreboard