Applications of Vector algebra

This post does not cover all the applications of Vectors. This only covers very few real world applications.

Before we proceed lets recall..

What are vectors?

Vector is a quantity having a direction and a magnitude.

Example : A car moving east with a velocity V. Here velocity is a vector quantity because it has both magnitude (how fast the car is moving) and direction (east).

Some of the terms/properties we may have learnt from school : magnitude, Vector addition, subtraction, dot product, cross product etc.,

What is an Origin? : Origin is an assumption point from which every other position is referred.

For example if I am the origin and I'm looking at a cat that is 2 meters away from me, then if I assume my position at (0,0) and draw a line towards the cat, the length of the line will be 2 meters.

Warm up example : (vector addition)

Two forces are acting on a stationary object F1 and F2. Suppose if F1 and F2 are equal, then the resultant direction of the object will be the vector addition of these two forces. How much the object will move can be found using parallelogram law of forces.

Example application 1 : (vector subtraction, magnitude of vector, unit vectors)
Given the Tamil Nadu map with origin at Chennai (we know the exact location of any city from the origin in the given map), find the exact location of Erode with respect to Madurai. (all co-ordinates in kilometers)

By vector property,
Chennai to Erode vector = Chennai to Madurai vector + Madurai to Erode Vector

Madurai to Erode vector = Chennai to Erode Vector - Chennai to Madurai vector

= (-350 i - 220 j) - ( - 214 i - 360 j)

= -136 i + 140 j

This means that Erode is located 136 kms west and 140 kms north to Madurai.

If we have to compute the distance from Madurai to Erode, we just have to find the magnitude of the vector

distance = sqrt(-136^2 + 140^2) = 195.2 kms

To find the unit vector we have to divide the vector by the distance

Madurai to Erode unit vector = (-136 i + 140 j)/195.2 = - 0.69 i + 0.72 j. If we calculate the magnitude of the unit vector it will be exactly 1.

Now suppose if we have to find the position of that tea stall that is exactly 50 kms in the direction from madurai to erode, we have to multiply 50 with this unit vector

Tea stall position with respect to Madurai = 50 * (-0.69 i + 0.72 j)

= -34.5 i + 36j

i.e. Tea stall is exactly 34.5 Kms west and 36 kms north from Madurai.

In the example we've used 2 dimensional positions.

Suppose we had to compute the distance or position the same way for satellites, planets and galaxies in 3D, we can use the same method.

Example application 2 :

What you can understand : When to use dot product and when to use cross product

Lets assume you design a humanoid robot with a gun. Now suppose you want to program the robot to shoot a balloon you need to know what angle the robot should turn in order to shoot the balloon.

Suppose lets say your robot is stationary at position (0,0) (origin) facing east.

i.e. facing directional vector = i

Now lets say the balloon is at position (6,9).

target unit vector = (6i + 9j) / sqrt(6*6+9*9)

= 0.55i + 0.83j

The robot has to turn an angle in the anti clock wise direction until the gun is pointed at position 6,9.

To find this angle you can use dot product..

initial vector . target vector = initial vector * target vector cos Theta

Theta = cos^-1 (initial vector . target vector)

= cos^-1 (0.55 i + 0.83j  . i + 0j)

= cos^-1 0.55

= 56.63 degrees

Cross product is usually used when we need a 3rd perpendicular vector (in a 3D space)

Always remember this 2 line rule :

1) Dot product is used to find the angle between two vectors
2) Cross product is used in case of 3D when we need to find how much a vector is tilted from each axis.
Cross product is also applied when we find angular momentum, Torque etc.,

Example application 3 :

Vector physics
From the above problem you have found the angle your robot has to rotate to shoot the balloon. Now assume the bullet is traveling from the gun towards the balloon and you need to find the position of the bullet after 0.5 seconds after you shoot.

Bullet position = Gun position + velocity vector of the bullet * T

The same principle is used if you need to find the position of a rocket when a rocket is launched in space. Note that friction, gravity and other external factors should also be considered. In vacuum, we can safely assume that there are no external factors.


Few more :
1) Vectors are used in every game you play. So if you want to create games, you've to be strong in vector algebra.

2) 3D glasses / VR glasses project 2 different 2D images. It appears 3D because of a hack called Depth Vector! Our naked eyes is capable to see things on 3D because it knows how far is every pixel/color of an object is. This is exactly what is projected in the two images (distance from left eye in the left eye image, distance from right eye in the right eye image)

• 
  
  
  We'll see where it's used in the real world.

Getting started with 3D games and applications

Step 1: Modelling:

     The first step is to create the 3D models(meshes) required for your game or application. 3D characters are made up of triangles. There are many modelling tools. But note that Blender is the most popular free open source tool.

Step 2: Texture mapping:

     The second step is to paint the 3D model with attractive colours and thereby create the UV-map for the created 3D models.

Step 3: Rigging:

     In case your game/application includes animating human/animal meshes you require rigging. In this process, you assign some weight for each joint in the bone with every vertex in every triangle in the mesh which are affected by respective bone. This helps smooth animation to the skin.

Step 4: Animation:

     Animation data is stored in the form of position and rotation for each joint in each frame. These frame loops can also be created using softwares like Unity3D, Blender, Maya etc.,

Step 5: Applying Shaders:

     This is the most complex step in the process. In this process, we perform the calculations required for camera movements and shadows. This is where all your knowledge in Matrix Algebra and Vector Algebra will be applied.

Steps involved in Game Development

1. Modelling
2. Creating texture map
3. Rigging
4. Animation
5. Applying Shaders
6. Game play (Depends on your game)
7. UI and music (Menu, Scoreboard, Background sounds etc.,)


For learning some important concepts on meshes, triangles and all the math involved behind 3D games, you can watch the videos in this youtube channel.

To start with OpenGL in C++, I'd suggest you can directly start running the examples in Irrlicht and thereby start developing 3D games quickly. You can download the freely available 3D characters from the web.

Everyone is to blame

Enough of programming related posts. I felt like writing this post for a long time and here am I.

Without having much knowledge about the society and the environment, I entered the college. I saw students who blame their teachers, blame their college mark system, blame about the traffic in their city, blame about the reservation system, blame about the counseling system, blame about not getting sponsorship for an event, blame about the placement system, blame about their wrong friends, blame the leadership,  even blame about the entire nation. Of course I was one among them.

After getting out of college, I saw a bigger set of people. People blaming about the salary they get, blaming about petrol price, blaming caste system, blaming about the software industry, blaming about the politicians, blaming about IPL scam, blaming about the smokers in public places, blaming about the rapists, blaming about the terrorists, blaming about the corruption, blaming about the wrong police men, blaming about the rich persons, blaming about their previous generation people, blaming about their next generation people and this list never stops.

Everyone of us are bad people. Each and everyone of us who blame about all these things and doing nothing other than speaking about them are all bad people. You know that all these things are wrong but still accept that you can survive with all these things. Because you are a lazy coward to fight against them. If you can live with what you have, then you better stop blaming. You don't have any rights to blame on anything when you do nothing to fix it.

How does the approach to solve Josephus problem work?

Josephus problem:

There are people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.

The task is to choose the place in the initial circle so that you are the last one remaining and so survive.

The approach:

Lets say we have to find the solution for n=5 and k=3 (We kill every 3rd person)

Step 1: Kill the kth person (in our case, kill the 3rd person). "2" will be removed and the counting out begins at "3"

Step 2: Instead of finding the solution for the above diagram, we can simply find the solution of the following diagram. Note that 3 is mapped to 0 and 4 is mapped to 1 and so on..

(To find the solution of the above diagram we use the same approach from step1. I'd like to ignore that part.)
The solution for n=4 and k=3 is 0.

Now look at the first diagram. We know that 0 is mapped to 3 in step2 which is the required solution.


Thanks to xorfire for teaching me this awesome problem.

Comments are welcome.

My AI tron bot

Tron is just similar to the snake game you play on mobile. There is a slight variation that at every step, the snake keeps growing on it's size. You hit anywhere, you die.

The movie Tron Legacy is entirely based on this game.

My tron AI was ranked 31/672 bots in Codingame. I actually didn't use any machine learning techniques. Instead I learnt myself by watching the replays of a lot of games to decide my strategy.

The challenge in this game is that our code should work for any number of opponents into the arena and it should run in 100 milli seconds. And within 100ms, our bot should decide the next move (left/right/up/down).

This is the core logic of my tron AI.

struct Direction{
    int dir;
};

//Just a comparator which could compare two directions and returns true if directionA is better than directionB

inline bool operator < (Direction A, Direction B){
    if(A.dir==B.dir)
        return false;
   
    if(isSafe[A.dir]!=isSafe[B.dir])
    {
        if(isSafe[A.dir])
            return true;
        return false;
    }

    if(selfish[A.dir]!=selfish[B.dir])
    {
        if(selfish[A.dir])
            return true;
        return false;
    }       
    if(defend[A.dir]!=defend[B.dir])
    {
        if(defend[A.dir])
            return true;
        return false;
    }
   
    if(attack[A.dir]!=attack[B.dir])
    {
        if(attack[A.dir])
            return true;
        return false;
    }

    if(!(target[A.dir]==target[B.dir]))
        return target[A.dir]<target[B.dir];    
           
    if(futureful[A.dir]!=futureful[B.dir])
    {
        if(futureful[A.dir])
            return true;
        return false;
    }
   
    if(best[A.dir]!=best[B.dir])
    {
        if(best[A.dir])
            return true;
        return false;
    }

    if(closer[A.dir]!=closer[B.dir])
    {
        if(closer[A.dir])
            return true;
        return false;
    }
   
    if(safeTouch[A.dir]!=safeTouch[B.dir])
    {
        if(safeTouch[A.dir])
            return true;
        return false;
    }
   
    if(touches[A.dir]!=touches[B.dir])
    {
        if(touches[A.dir])
            return true;
        return false;
    }
   
    return A.dir<B.dir;
}

Step1: Choose a safe move. An unsafe move is a move which lets your bot die.
Step2: Be selfish. Choose the direction containing maximum free spaces. This might sound crazy. But if you don't take this path, you are probably going to lose anyhow. It's better to take a selfish move which might help you if your opponent makes mistakes.
Step3:

Proof: If player X can reach a point (x,y) faster than any other player, then regardless of the shortest path X choose, no one can stop X in reaching (x,y).

By finding the nearest player for all the points in the map, we could know the points a player can reach faster than anyone else.

A defensive direction is a direction which will make the number of nearest points to be maximum (points we can reach faster than all enemies should be maximum). Choose such a direction.

Step4: Choose an attacking direction if possible.
Let S be the set of points we can reach faster than all the enemies.
For each point in S, draw a line from S[i] to current position and check whether the enemies have less survival time than us. Choose a point for which ∑(survivalTime[me]-survivalTime[enemy[i]]) is maximum and move towards that direction.

Step5: In case we have many possible positions to attack with equal score, choose the target which is closer and move towards it.

Step6: We should think at least one step ahead in order to utilize maximum space on the board. We need not waste spaces on the board. (Edit:  This can help to utilize more spaces than that of this step.)

Step7: Block all the points enemies can reach faster than us. Now choose the direction with maximum survival time.

Step8: Get closer towards the farthest enemy faster!. Going towards the farthest enemy can give us some space to breathe in.

Step9: Once we know that an enemy is about to die, we should try to occupy that space. It's better not to touch the enemy who is about to die. This should be done only when aliveEnemies>1.

Step10: It's always safer to move on the edges of walls to occupy more spaces.


You probably could have got bored if I had shared my entire 1035 lines of code.
Hope you liked it :) Share your suggestions/improvements.