Saturday, October 25, 2014

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.


Sunday, June 8, 2014

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.

Wednesday, April 16, 2014

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.

Sunday, March 2, 2014

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 real machine learning for which I may have to construct a neural network and play according to the neural schema.

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.

Thursday, February 20, 2014

How to start programming?


A bit about myself:

      I did my schooling in Madurai, India. I love mathematics. In my early school days, I started solving sudoku. I also liked playing Tetris, Bomber man, Super Mario and what not. I like to compete. What’s the fun in playing Fruit Ninja without having friends to brag about our high scores?


Why I started programming?

      I felt goosebumps when a computer bot with artificial intelligence played wiser in a video game. I saw a program which could solve any Sudoku puzzle within a fraction of a second. I saw a program which could chat to me like a human. I saw a robot which could solve any rubik’s cube.  I realized that I could solve such problems by mathematics and little programming. And that’s how I started.


How can you start programming?


      Step 1: Learn a programming language. There are lots of books to learn programming. If you can’t afford a book you can use some Library. If you hate books, you can learn online through w3schools.com. The syntax and the procedures will trouble you initially. But it’s worth it.


      Step 2: Start solving some real time problems. There are many websites where you can start solving real time problems. You can start with SPOJ, ProjectEuler and MyCodeSchool.


      Step 3: After solving few basic problems you should start learning Data Structures and Algorithms which could help you solve challenging and interesting real time problems. As MyCodeSchool provides nice video tutorials, I recommend you to learn and practice there.


      Step 4: Get like-minded friends and participate in programming camps and competitions. Compete in Topcoder where all the programmers in the world take part regularly. Participate in IOI if you are in school and participate in ICPC if you are in college. Win a GOLD for our country.
Data Structures and Algorithms are very important. In addition if you want to learn Game Programming, learn openGL and keep in touch with Vector Algebra and Trigonometry. If you want to create programs which can think like humans you should learn Artificial Intelligence and Machine Learning.


In case if you love mathematics and computers, it’s neither late nor early to learn programming. Start now!.
                                                            - Prakash D(Game Developer @ Smackall Games)