Linear algebra for artificial intelligence's student

A brief about how to start a game world simulator to test machine learning methods

Posted by dsapandora on May 29, 2016
Why do we care about linear algebra?

This phrase can be hear repeatedly from freshmen students, when they are just staring their first steps in programmming and differential calculus, they didn't pay to much attention to this subject, and learn just what is needed to complete the course. Then a few years later when they reach the artificial intelligence course (INF 513), they get a big headache and regreat when Its said that they need to make their own test enviroment for machine learning technics usually using virtual worlds. So I decided if I'm going to help them, I will write about that, and I might as well start at the beginning!.

Why do we care about linear algebra?

Linear algebra is the study of vectors. If your virtual world involves the position of an on-screen button, the direction of a camera, or the velocity of a race car, you will have to use vectors. The better you understand linear algebra, the more control you will have over the behavior of these vectors.

What is a vector?

In virtual worlds, vectors are used to store positions, directions, and velocities

The position vector indicates that the man is standing two meters east of the origin, and one meter north. The velocity vector shows that in one minute, the plane moves three kilometers up, and two to the left. The direction vector tells us that the pistol is pointing to the right.

As you can see, a vector by itself is just a set of numbers -- it is only given meaning by its context. For example, the vector (1,0) could be the direction for the gun as shown, but it could also be the position of a building one mile to the east of your current position, or the velocity of a snail moving right at a speed of 1 mph.

For this reason, it's important to keep track of your units. Let's say we have a vector V (3,5,2). This doesn't mean much by itself. Three what? Five what? In Overgrowth, positions are always given in meters, and velocities in meters per second. The first number is east, the second is up, and the third is north. Negative numbers represent the opposite directions: west, down, and south. The position represented by (3,5,2) is 3 meters east, 5 meters up, and 2 meters north, as shown here:

Now that we've gone over the basics of vectors, we need to know how to use them.

Vector addition

To add vectors together, you just add each component together separately. For example:

(0,1,4) + (3,-2,5) = (0+3, 1-2, 4+5) = (3,-1,9)

Why do we want to add vectors together? One of the most common applications in virtual worlds for vector addition is physics integration. Any physically-based object will likely have vectors for position, velocity, and acceleration. For every frame (usually 1/60th of a second), we have to integrate these vectors -- that is, add the velocity to the position, and the acceleration to the velocity.

Let's consider the example of Mario jumping. He starts at position (0,0). As he starts the jump, his velocity is (1,3) -- he is moving upwards quickly, but also to the right. His acceleration throughout is (0,-1), because gravity is pulling him downwards. Here is what his jump looks like over the course of seven more frames. The black text specifies his velocity for each frame.

We can walk through the first couple frames by hand to see how this works.

For the first frame, we add his velocity (1,3) to his position (0,0) to get his new position (1,3). Then, we add his acceleration (0,-1) to his velocity (1,3) to get his new velocity (1,2).

We do it again for the second frame. We add his velocity (1,2) to his position (1,3) to get (2,5). Then, we add his acceleration (0,-1) to his velocity (1,2) to get (1,1).

Usually in virtual worlds the player controls a character's acceleration with the keyboard or gamepad, and the virtual world calculates the new velocity and position using physics integration (via vector addition). Fun fact: this is the same kind of integration problem that you solve using integral calculus - we are just using an approximate brute-force approach. I found it much easier to pay attention to calculus classes by thinking about physical applications like this.

Vector subtraction

Subtraction works in the same way as addition -- subtracting one component at a time. Vector subtraction is useful for getting a vector that points from one position to another. For example, let's say the player is standing at (1,2) with a laser rifle, and an enemy robot is at (4,3). To get the vector that the laser must travel to hit the robot, you can subtract the player's position from the robot's position. This gives us:

(4,3)-(1,2) = (4-1, 3-2) = (3,1).