Sunday, March 30, 2014

Latest - March 31

I've just finished the initial framework of the AI engine. I just need to add some more implementation and I hope to get the AI to move an AI agent around in a few days.

Tuesday, March 11, 2014

New Journal Post on Game AI Engine

I've just added a post on my journal page about the AI engine that I've been developing. I give a lot of details. You can read it here.

Building My AI Engine

Fun Indie Games in Development (playlist)

Fun Indie Games in Development (playlist)

I'm all for support other independent developers. That's why I've decided to put this little playlist together of some good indie games that I feel people should see.

Wednesday, March 5, 2014

Code Bits: Linear Equation From Two Points

These days, I've been building a simple 2D physics engine to test with. While I was programming the collision detection, I needed to find the equation of the line between two points. I show a little bit of the Algebra here and write some code. I want the linear equation to be in standard form because I find it to be more useful than slope-intercept form.

Here is the standard form of a 2D linear equation:

\[\begin{aligned} Ax + By + C = 0 \end{aligned} \]
How do we calculate A, B, and C?

Method One: Calculating from Slope-Intercept
One way to calculate A, B, and C is to start with the slope-intercept form of the line and use some Algebra until its in the standard form. The following is the slope intercept form:
\[\begin{aligned} y = mx + b \end{aligned} \] In this form, m is the slope of the line and b is the y-intercept. This is m and b are fairly easy to figure out. For points (x_0, y_0) and (x_1, y_1) \[\begin{aligned} m = \frac{y_1 - y_0}{x_1 - x_0} \end{aligned} \] \[\begin{aligned} b = y_0 - x_0(\frac{y_1 - y_0}{x_1 - x_0}) \end{aligned} \] After filling in the variables and manipulating it so it is in the form whereby the equation equals zero, we get this: \[\begin{aligned} (y_1 - y_0)x + (x_0 - x_1)y + ((x_1 - x_0)y_0 - (y_1 - y_0)x_0) = 0 \end{aligned} \] so ... \[\begin{aligned} A = (y_1 - y_0) \\ B = (x_0 - x_1) \\ C = (x_1 - x_0)y_0 - (y_1 - y_0)x_0 \\ \end{aligned} \] 
Method Two:
The second method takes some special properties of the linear equation into account. Notice the picture below:

The direction of the normal vector is the direction of the vector from (x0, y0) to (x1, y1) rotated 90 degrees. A and B in the linear equation can be thought of as a vector whose direction is the same as the normal vector. So we can calculate A and B just by calculating the normal vector. If we normalize this vector (make the magnitude 1.0), it will also be more useful when doing collision detection calculations. C is the dot product of the the normal vector and any point on the line.

Here's the code for method two:

typedef float vec2[2];

void Normalize2(const vec2 in, vec2 out)
    float inv_length = 1.0f / sqrtf((in[0] * in[0]) + (in[1] * in[1]));
    out[0] = in[0] * inv_length;
    out[1] = in[1] * inv_length;

float DotProduct2(const vec2 a, const vec2 b)
    return (a[0] * b[0]) + (a[1] * b[1]);

void LineFromTwoPoints(const vec2 p1, const vec2 p2, float &A, float &B, float &C)
    // first calulate and normalize a vector from p1 to p2
    vec2 dir;
    dir[0] = p2[0] - p1[0];
    dir[1] = p2[1] - p1[1];
    Normalize2(dir, dir);

    // calculate the normal vector of the segment this will be our A and B
    vec2 normal;
    A = normal[0] = -dir[1];
    B = normal[1] = dir[0];

    C = -DotProduct2(normal, p1);
The two methods give the same formula. In method two I make sure the magnitude of the vector (A B) is 1. This can be done using method one as well by dividing A, B, and C by the square root of ((A * A) + (B * B))