Friday, March 22, 2013

Virtual D-Pad Killed by Geometry

I hate virtual D-pads in mobile games. The D-pad was great on my Nintendo Entertainment System, but trying to play Mega Man II on my iPhone with the standard touch-screen replacement for tactile control made me regret spending $2.99 on the game. With nothing to stop my thumb from sliding right off the control zone, Mega Man plunged needlessly to his death so many times. So many times. Oh, the humanity! Well, in this case, the android...ity? Androidity? Is that a word? Feel free to substitute another word in your head when you read this. A word that you would use to express anguish over the massacre of heroic humanoid robots.

So let's just say I hate virtual D-pads. In the Android version of my FFZ game, I was not about to use one. There are a few alternatives that people have come up with, but here I'm going to talk about my current favorite and how I implemented it. It just took a little geometry.

What I wanted was a system where I could swipe my finger anywhere on the screen, and then my frog would move in a similar way. I swipe down and to the right, the frog moves down and to the right by the same distance. I don't have to start my swipe on the frog, so I don't have to block anything on the screen that I don't want to. I basically just want to create a vector with my finger that is then applied to the frog.

Doing this seemed fairly simple. I would just need a class that could represent the line segment created by the finger swipe, and then create a parallel line segment for the frog to move along.

Formula for a Line


Remember back to high school geometry class. The standard equation for a line is
y = mx + b
where m is the slope and b is the y-intercept (where the line will cross the y-axis). Slope is really important in this case, since that's basically what I want to duplicate in a second line for the frog's movement. Remember, lines with the same slope are parallel.

How, then, does one calculate slope? If you have a line, take any two points on it. Let's represent these two points as (x1, y1) and (x2, y2). Subtract y2 from y1 and divide that by the value of x1 minus x2.
m = (y1 - y2) / (x1 - x2)
The two points I'll use are the positions of the start of the touch event and the end of the touch event. So here's what my FrogPath class looks like so far.

public class FrogPath {

  private float x1;
  private float x2;
  private float y1;
  private float y2;
  private float slope;
  private boolean vertical;
 
  public void setStart(float x, float y) {
    this.x1 = x;
    this.y1 = y;
  }
 
  public void setEnd(float x, float y) {
  
    this.x2 = x;
    this.y2 = y;
    this.calculateSlope();
  
  }
 
  private void calculateSlope() {
    if (x1 - x2 == 0) { // don't divide by 0! no!
      slope = 0;
      vertical = true;
    } else {
      slope = (y1 - y2) / (x1 - x2);
      vertical = false;
    }
  }

}

Note the special handling for lines that go straight up and down. If there was no change in the x values for the two points, you'll divide by zero if you're not careful to check for that. Instead, a vertical line is said to have no slope. The formula for a line with no slope looks a little different, it's just x = n. The y value can be anything, but x will always be the same and there's no y-intercept. It's a little different than a horizontal line, which has a slope of 0. You can use the standard formula for those types of lines, but the value for m is 0 which essentially eliminates x from the equation. You're left with just y = n where n is always equal to b, because the line will cross the y-axis at the same value as every other point on the line! Consider the horizontal line y = 2, for example. Anyway, the point is that we have to perform special handling for vertical lines but not horizontal ones.

Thanks to Garrett Bartley for the Virtual Graph Paper I used here! 

So in my Android app, when I get an ACTION_DOWN MotionEvent I create a new FrogPath object and set the start coordinates. I hold on to that object until I get an ACTION_UP event, at which time I set the end coordinates. The FrogPath object calculates the slope of the line. That was the easy part!

Can We Get There from Here?


Now I have a slope and I have the current coordinates of my frog. I calculate the distance I want the frog to move, based on his speed and how much time passes between animation frames. What now? To calculate his new position, I have to figure out new coordinates that are on a line with the calculated slope that passes through the current coordinates. These new coordinates have to be the calculated distance from the current coordinates. Sound easy? Let's look at the picture...


Here we can say that c represents the distance we want to move the frog along the line. We know where the frog is now. Your first thought might be to call on your old friend Pythagoras and do that whole a2 + b2 thing. Sorry, but Pythagoras can't help you here. There's just not enough information. We need to find both a and b, and we can't do that with just c. This is where it get's tricky. You need to look at the problem in a different way. What if instead of seeing a triangle, you see a circle?

We can figure out the next position of the frog using the formula for a circle and determining where a circle centered at the frog's current coordinates and with radius r will intersect with the line. You may not be as familiar with the formula for a circle as you were with the formula for a line, but here it is. If the coordinates for the center of the circle are represented as (c, d) and a point on the circle is represented as (x, y) and r is the radius, the standard form circle equation is
(x - c)2 + (y - d)2 = r2
It might look crazy, but if you think about it, we have enough information to solve the problem if we combine the equation of our line with the equation of our circle. We know c and d, because those are the current coordinates of the frog. We know r because that is the distance we want the frog to move. And we know y (in terms of x anyway) because the line formula is y = mx + b. We know m because that is the slope. We can find b because we have a point on the line (the frog's current coordinates) and the slope. That's everything. Just plug it all in and solve for x! If you factored it all out, you'd come up with an equation like this for x:
x = c ± r / √(1 + m2)
Now you might notice that plus/minus thing in there, and rightly so - if you look at the picture above it clearly shows that the circle intersects the line in two places. How do you know which x value you want? Simple. You go back to your original two points that you used to calculate the slope in the first place. If the x value for the end point is greater than the x value for the start point, do a plus in the equation above. If not, do a minus. This basically means that if the user moved their finger from left to right you want to pick the intersection point on the right to keep the frog moving in the right direction. Pun intended.

We're almost done now. We can solve for x. But we still need a y value for the frog's new coordinates. Back to the line formula! Take our newly acquired value for x and plug it into our line equation y = mx + b along with the known values for m and b. You'll easily get y and now you've got a coordinate pair!

Just one more minor note before we get to the code. Remember that whole vertical line thing? Yeah, we need to handle that. But, good news! If we have a vertical line we don't need to mess with any circles or triangles or dodecahedrons or anything. Just add or subtract the distance moved from the current y coordinate (again, depending on if the original swipe was up or down) and return that paired with the current x coordinate.

Here's the two new methods that should be added to the FrogPath class shown above:

private float yIntercept(float x, float y, float m) {
  return (y - (m * x));
}
 
public float[] getNextPoint(float c, float d, float dist) {
  
  if (vertical) {
 
    float yp = d;
    if (this.y2 < this.y1) {
      yp -= dist;
    } else {
      yp += dist;
    }
    return new float[] {c, yp};
   
  } else {

    float b = yIntercept(c, d, this.slope);

    float xp = 0f;
    if (this.x2 < this.x1) {
      xp = (float) (c - (dist / (Math.sqrt(1+Math.pow(this.slope, 2)))));
    } else {
      xp = (float) (c + (dist / (Math.sqrt(1+Math.pow(this.slope, 2)))));
    }
    float yp = (this.slope * xp) + b;
    return new float[] {xp, yp};

  }
  
}

Just note that I return the new coordinates as an array of floats where the x coordinate is at position 0 and the y coordinate is at position 1. You could easily substitute some kind of object that represents a point if you prefer.

The only thing left to do is to figure out when to stop moving. That task is relatively simple, you just have to keep track of the total distance moved and stop when it equals the distance moved in the original screen swipe.

So that's it. That's how I used geometry that I probably should have learned in high school to defeat the dreaded virtual D-pad in a mobile game. And speaking of defeating something, who do you think would win in a fight between Pythagoras and Archimedes? Leave your comments below. My money's on Archy. Yeah, that's right. I called him Archy. Archimedes had a nickname. That's what his friends called him.

Sunday, March 17, 2013

It would appear that I've made an error

Back in 2011 I implemented the Separating Axis Theorem in JavaScript to help detect polygon collisions in HTML5 games. Now that I've started implementing similar games in Java to play on my OUYA, it has come to my attention that my algorithm had a slight mistake in it.

The problem had to do with calculating the Minimum Translation Vector, which tells you how to move one of the polygons to get them out of collision. If you were just using the algorithm to detect collision with a true/false you wouldn't notice any problem.

Here's what I did wrong...

After projecting both shapes' vertices onto the normal axis, you will have two line segments and you are supposed to determine how big the overlap (if any) is between the them. You can read a great explanation of the whole algorithm on the Code Zealot blog.

So let's say you end up with two line segments, A and B. Both sit on the X axis, so you can ignore any Y value. A runs from 1.5 to 4.4 while B runs from -2.8 to 2. What would you say the overlap is? The correct answer would be 0.5, but my implementation of the algorithm was coming up with 7.2.

Here was my calculation of the overlap:
o = (maxA > minB ? maxA - minB : maxB - minA);
See anything wrong there? In the case I outlined above, maxA was 4.4, obviously greater than minB which was -2.8. So I calculated the overlap as 4.4 + 2.8. Wrong! What was I thinking? Try it yourself with other line segments...you'll see that it sometimes gives you a correct value but often does not. If only I had created a good unit test for this code years ago. Fortunately, I did create such a test for my Java version using JUnit, and found my mistake. Here is the correct calculation of overlap:
o = (maxA > maxB ? maxB - minA : maxA - minB);
I've updated my JavaScript version, so people who find it on my previous blog entry won't be led astray. Sorry about that. I'll post my Java version soon, along with what is (hopefully) a good explanation of how it works.