Cloning Zelda, part 5D: Scaling the Math Wall

Previous posts in this series: Part 1 | Part 2 | Part 3A | Part 3B | Part 4A | Part 4B | Part 4C | Part 5A | Part 5B | Part 5C

I blogged last week about the strides I've made with refactoring the various monster classes into the new sprite engine, and related how I got stuck, for the second time, trying to make the boomerang work right (I'd had it mostly implemented a while ago when I first decided to do the sprite engine refactoring, in large part because it didn't animate well in the old engine). Well, a few afternoons later, I knuckled down while on my lunch break and got it working. (fair warning for the math-averse: the rest of this post is going to be pretty trigonometry-heavy)

First, I owe a huge debt to a couple of sites that helped refresh my memory of vector geometry. I recalled the old "rise over run" rule for defining the slope of a vector or line, and I knew that the Pythagorean Theorem (a2 + b2 = c2) could be used to figure out the length of a vector c, given its X and Y components a and b. The rest took some memory-jogging: lbackstrom's tutorial at TopCoder.com was a good refresher, and the Slopes and Lines overview at WhySlopes.com filled in the rest (good thing, too, because my daughter is going to need me to help her with her geometry homework before I know it...)

Anyway, the basic math of the boomerang problem works like this: when thrown, a boomerang has an initial vector that determines its movement in the X and Y directions. When it reaches its apogee or hits the edge of the screen, it then reverses course, homing in on its thrower. In order to do this, the boomerang version of the Projectile class had to override the base class's updatePosition() function, which gets called from the game main loop:

main: function game_main() {
...
  // move all active projectiles
  for (var j in this.items) {
      if ("updatePosition" in this.items[j]) { this.items[j].updatePosition(); }
  }
...
}

(Note that we first have to check to see if each item in the game's item list actually has the updatePosition() function, because non-projectile items, like dropped hearts and rupees, won't.) The boomerang projectile's updatePosition() function looks like this:

updatePosition: function boomProj_updatePosition() {
    // move me to the next point on my current trajectory
    this.pos.x += this.vel.x;
    this.pos.y += this.vel.y;

    // check to see if I've gone off the edge of the screen
    var offscreen = true;
    if (this.vel.x < 0) {
        // moving left; check left edge
        offscreen &= (this.pos.x <= game.constants.screenBound.left);
    } else if (this.vel.x > 0) {
        // moving right; check right edge
        offscreen &= (this.pos.x >= game.constants.screenBound.right);
    }
    if (this.vel.y < 0) {
        // moving up; check top edge
        offscreen &= (this.pos.y <= game.constants.screenBound.top);
    } else if (this.vel.y > 0) {
        // moving down; check bottom edge
        offscreen &= (this.pos.y >= game.constants.screenBound.bottom);
    }

    // calculate distance from my owner (set in the constructor via dojo.mixin() args)
    var dx = this.owner.pos.x - this.pos.x;
    var dy = this.owner.pos.y - this.pos.y;
    var distance = Math.sqrt(dx*dx + dy*dy); // thanks, Pythagorus!
    if (this._returning) {
        // if we're already returning, check to see if we're close enough to our owner to be caught
        if (distance <= 8) {
            this.owner.catchItem();
            this.terminate();
        }
    } else if (offscreen || distance >= this.apogee) {
        this._returning = true;
    }

    // calculate return velocity, if we're on the return path
    if (this._returning) {
        // change my vector to match the direction from me to my owner; valid values are -1, 0, or 1
        this.vector = {x: (dx) ? dx/Math.abs(dx) : 0, y: (dy) ? dy/Math.abs(dy) : 0};

        if (dx && dy) {
            // vector is on a diagonal; I need to calculate both x and y components of velocity
            var slope = dy / dx;
            this.vel.x = Math.sqrt((this.speed*this.speed) / (slope*slope + 1)) * this.vector.x;
            this.vel.y = this.vel.x * slope;
        } else if (dx) {
            // dx only: horizontal vector
            this.vel = {x: this.speed * this.vector.x, y: 0};
        } else {
            // dy only: vertical vector
            this.vel = {x: 0, y: this.speed * this.vector.y};
        }
    }
}

A boomerang's return velocity is easy when it's strictly horizontal or vertical: the full measure of speed is devoted to either X or Y, respectively. The complicated part is when the boomerang is on a diagonal offset from its owner; in that case, the speed needs to be divided into X and Y components, in a ratio that matches that of the X and Y portions of the difference between the boomerang's current position, and that of the player (typically referred to as Δx and Δy, but which I called dx and dy in the code):

Subtracting the player's position from the boomerang's gives us the values for length of sides Δx and Δy: in this case, 30 and 43, respectively (note: the image is enlarged for clarity). The slope of the boomerang's velocity vector can be found by dividing Δx into Δy (Rise over run, remember?). That gives us:

slope = Δy / Δx = 30 / 43 ≈ 0.698

Now comes the tricky part: we know the total velocity of the boomerang, Vel_total, as it needs to be equal to the predetermined speed for boomerangs: 3 pixels per frame. But, we don't know either the X or Y components of the velocity, which is what we need in order to do the right thing in updatePosition(). Dredging up an old trick I learned in high school algebra, I remembered that if you have two unknown variables, you can solve them both if you can find two interrelated equations. Fortunately, we have them: the Pythagorean theorem, and the slope ratio. We'll figure out the x-component of the velocity Vel_x first, because that will make the calculation of the y-component Vel_y easy. Solving the Pythagorean Theorem for Vel_x, we get:

Veltotal2 = Velx2 + Vely2
         = Velx2 + (Velx * slope)2 -- (substituting in the slope formula: Vely = Velx * slope)
         = Velx2 + (Velx2 * slope2)
         = Velx2 * (1 + slope2)
Velx2 = Veltotal2 / (1 + slope2)
Velx = √ Veltotal2 / (1 + slope2)
    = √ 32 / (1 + 0.6982)
    = √ 9 / (1 + 0.487)
    = √ 6.052 
    = 2.460

Then, solving for Vel_y:

Vely = Velx * slope
    = 2.460 * 0.698
    = 1.717

So in this instance, the X and Y components of the boomerang's velocity should be set to 2.46 and 1.71708. Now that we've worked it out, these calculations can be done every time the game calls updatePosition(), and in all but the most extreme cases (i.e. 20 Goriyas in a dungeon room, all throwing boomerangs at the same time) this won't cause any measurable slowdown.

You can see the results for yourself, by loading up the latest iteration of the game, here. The arrow keys control the player's movement, and the Z and X keys throw the boomerang and sword, but the map and inventory screens aren't converted to the new codebase yet, so that's the next order of business. I've also added some preliminary code that should take care of preloading all necessary resources, but it's still a bit buggy, so if nothing happens when you first hit the page, hit refresh and try again. Of course you can also go to the Bestiary if you prefer, and see for yourself how the Goriyas can handle their boomerangs. Collision detection still isn't turned on yet, but I fully expect to have that for the next update.