Social Networks in Games: Playing with Your Facebook Friends

This is another article in Game Programming Gems 8, talking about accessing web services of social networks from our own games. For example, log people in using their Facebook account.

RESTful Web Service

Representational State Transfer (REST) is the predominant architecture for offering programmatic access to data stored on the web. A RESTful service is composed of a collection of resources, which are identified by a web address, such as http://example.com/resource. It is based on stateless operations, which means any state information is held in the client, so a service can scale to a large number of clients–ideal for web services.

In practice, a RESTful service works with HTTP requests. We send HTTP GET to retrieve data, and the response are usually in JavaScript Object Notation (JSON) format, which looks like this:

{“trends”:{“2009-08-23 04:00:47”:[
  {“query”:”\”Best love song?\”“,”name”:”Best love song?”},
  {“query”:”#fact”,”name”:”#fact”},
  {“query”:”#shoutout”,”name”:”#shoutout”},
  {“query”:”#HappyBDayHowieD”,”name”:”#HappyBDayHowieD”},
  {“query”:”\”District 9\”“,”name”:”District 9”},
  {“query”:”\”Inglourious Basterds\”“,”name”:”Inglourious Basterds”},
  {“query”:”\”Hurricane Bill\”“,”name”:”Hurricane Bill”},
  {“query”:”#peacebetweenjbfans”,”name”:”#peacebetweenjbfans”},
  {“query”:”#Nascar”,”name”:”#Nascar”},
  {“query”:”Raiders”,”name”:”Raiders”}
]},”as_of”:1251000047}

Authenticating a User

Normally we have to confirm a user’s identity before we gain access to data. The most basic authentication mechanism requires users to enter a user name and password, which our application sends to the web service. It requires users to trust our application not to collect passwords and abuse them for other purposes. This fear might stop users from trying out new applications.

Applications on the web have answered this need by offering authentication mechanisms based on forwarding. When logging into an application, users will be forwarded to the login page of the account provider and enter user name and password there. The application will never see user’s credentials, but will only receive a confirmation of whether the login was successful.

Facebook Login

Let’s try the Facebook Login on a web page. There are 4 steps:

  1. Set Redirect URLs.
  2. Check the login statues.
  3. Log people in.
  4. Log people out.

The first step can be done in Facebook App Settings. It ensures Facebook login page only responses to calls from valid URLs.

When loading our webpage, the first thing to do is check if a user is already logged into our application with Facebook Login. We can start that process with a call to FB.getLoginStatus, this function will trigger a call to Facebook to get the login status and call our callback function with the results.

However definitely we should load and initialize Facebook JavaScript SDK. Here is the codes:

<script>
  // This Init function should be inserted
  // directly after the opening  tag
  window.fbAsyncInit = function() {
    FB.init({
      appId            : 'your-app-id',
      cookie           : true,  // enable cookies to allow the server to access
                                // the session
      autoLogAppEvents : true,
      xfbml            : true,  // parse social plugins on this page
      version          : 'v2.12'
    });
  };

  // Load the SDK asynchronously
  (function(d, s, id){
     var js, fjs = d.getElementsByTagName(s)[0];
     if (d.getElementById(id)) {return;}
     js = d.createElement(s); js.id = id;
     js.src = "https://connect.facebook.net/en_US/sdk.js";
     fjs.parentNode.insertBefore(js, fjs);
   }(document, 'script', 'facebook-jssdk'));
</script>

Now that we’ve initialized the JavaScript SDK, we call FB.getLoginStatus(). This function gets the state of the person visiting this page and can return one of three following states:

  • Logged into our app (‘connected’)
  • Logged into Facebook, but not our app yet (‘not_authorized’)
  • Not logged into Facebook, so we cannot tell if they are logged into our app or not (‘unknown’)

These three cases are handled in the callback funtion.

<script>
  // This Init function should be inserted
  // directly after the opening &amp;amp;lt;body&amp;amp;gt; tag
  window.fbAsyncInit = function() {
    FB.init({
      appId            : 'your-app-id',
      cookie           : true,  // enable cookies to allow the server to access
                                // the session
      autoLogAppEvents : true,
      xfbml            : true,  // parse social plugins on this page
      version          : 'v2.12'
    });

    FB.getLoginStatus(function(response) {
      statusChangeCallback(response);
    });

  };

  function statusChangeCallback(response) {
    console.log('statusChangeCallback');
    console.log(response.status);  // three states
  }

  // Load the SDK asynchronously
  (function(d, s, id){
     var js, fjs = d.getElementsByTagName(s)[0];
     if (d.getElementById(id)) {return;}
     js = d.createElement(s); js.id = id;
     js.src = "https://connect.facebook.net/en_US/sdk.js";
     fjs.parentNode.insertBefore(js, fjs);
   }(document, 'script', 'facebook-jssdk'));
</script>

Once our app knows the login status of the person using it, it can do one of the following:

  • If the person is logged into Facebook and our app, redirect them to our app’s logged in experience.
  • I the person isn’t logged into our app or isn’t logged into Facebook, prompt them with the Login dialog with FB.login() or show them the Login Button.

Facebook provides an easy way to generate a Login Button by one click:

WX20180214-004201

After user logged in, we can access authorized data using FB.api(). I have made a demo on http://chenglongyi.com/test/fbapi/, and the full code is below:

<!DOCTYPE html>
<html>
<head>
  <title>Facebook login</title>
</head>
<body>

<script>
  window.fbAsyncInit = function() {
    FB.init({
      appId      : 'your-app-id',
      cookie     : true,  // enable cookies to allow the server to access 
                          // the session
      xfbml      : true,  // parse social plugins on this page
      version    : 'v2.12' // use graph api version 2.8
    });

    // Now that we've initialized the JavaScript SDK, we call 
    // FB.getLoginStatus().  This function gets the state of the
    // person visiting this page and can return one of three states to
    // the callback you provide.  They can be:
    //
    // 1. Logged into your app ('connected')
    // 2. Logged into Facebook, but not your app ('not_authorized')
    // 3. Not logged into Facebook and can't tell if they are logged into
    //    your app or not.
    //
    // These three cases are handled in the callback function.

    FB.getLoginStatus(function(response) {
      statusChangeCallback(response);
    });
  };

  function checkLoginState() {
    FB.getLoginStatus(function(response) {
      statusChangeCallback(response);
    });
  }

  function statusChangeCallback(response) {
    console.log('statusChangeCallback');
    console.log(response);

    if (response.status === "connected") {
      welcome();
    } else {
      document.getElementById('welcome').innerHTML = "";
    }
  }

  function welcome() {
    FB.api(
      '/me',
      'GET',
      {"fields":"id,name"},
      function(response) {
        console.log(response);
        document.getElementById('welcome').innerHTML = "Welcome " + response.name + "!";
      }
    );
  }

  // Load the SDK asynchronously
  (function(d, s, id) {
    var js, fjs = d.getElementsByTagName(s)[0];
    if (d.getElementById(id)) return;
    js = d.createElement(s); js.id = id;
    js.src = "https://connect.facebook.net/en_US/sdk.js";
    fjs.parentNode.insertBefore(js, fjs);
  }(document, 'script', 'facebook-jssdk'));

</script>
<div class="fb-login-button" data-max-rows="1" data-size="large" data-button-type="continue_with" data-show-faces="false" data-auto-logout-link="true" data-use-continue-as="true" onlogin="checkLoginState"></div>

</body>
</html>
Advertisements

Behavioral Questions

Following Dave’s advice, I am reading the book CRACKING THE CODING  INTERVIEW. It is a great book, not only listed all the knowledge I should know to pass the coding tests, but also mentioned how to prepare for general non-tech questions I may neglect, such as behavioral questions. Here are some tips.

Projects

Questions often come from the projects listed on resume. So to ensure I can talk more details about them, those projects should be selected following these criteria:

  • The project had challenging components (beyond just “learning a lot”).
  • I played a central role (ideally on the challenging components).
  • I can talk at technical depth.

Here are more components would be helpful for going through each project. This grid can be filled with some keywords, and put it in front of me during an interview as a reminder.

Common Questions Project 1 Project 2 Project 3
Challenges
Mistakes/Failures
Enjoyed
Leadership
Conflicts
What You’d do Differently

Response

When answering behavioral questions, it should be specific, but with limited details, and offers an opportunity for the interviewer to drill in further. For example, putting “I can go into more details if you’d like” after a clear and short answer.

The expanded answer should be structured. Start with a “nugget” succinctly describes what it will be about, then approach it via three steps of Situation, Action and Result. The Action should be more detailed as it is the most important step, so break it into multiple parts to encourage sufficient depth. Also, rephrase it in a better way to demonstrate personal attributes like Initiative, Leadership, Empathy, Compassion, Humility, Teamwork and Helpfulness.

Here is also a grid would be helpful for organizing stories:

Nugget Situation Actions Result Attributes
Story 1 1…2…3…
Story 2 1…2…3…

Weaknesses

To avoid making myself looks arrogant, give a real weakness. I think my biggest weakness now is time management and execution.

Fast-IsA

This is a GEM from Game Programming Gems 8, by Joshua Grass, provides a better method for processing class hierarchy data that can increase the efficiency of IsA check from O(N) to O(1). Here is my summary after reading.

Given a typical class hierarchy like below:

WeChat Image_20180130164516

A normal way to perform IsA check, determine whether Class A is a subclass of Class B would be:

bool IsA(Class *pA, Class *pB)
{
    while (*pA != NULL)
    {
        if (pA == pB)
        {
            return true;
        }
        pA = pA -> GetParentClass();
    }
    return false;
}

The worst case of this algorithm would perform a traversal from leaf to root, which can be very expensive.

So let’s simplify the problem. Imagine we are lucky and the class is in a perfectly balanced binary hierarchy, which means each node branched exactly twice, just like below:

WeChat Image_20180130174959

In this situation the class hierarchy can be put into a contiguous array.

WeChat Screenshot_20180130175525

We noticed that on each level we add 2^(N-1) new nodes to the array, where N is the new level. According to the index in the array(the second row in above table), we can easily find the relationship between each node and its parent:

int parentIndex(int nodeIndex)
{
    return nodeIndex >> 1;
}

So according to this algorithm, on a perfectly balanced tree, we can improve IsA() from O(N) to O(logN):

bool IsA_Balanced2Tree(Class *pA, Class *pB)
{
    int nodeAIndex = pA -> GetClassIndex();
    int nodeBIndex = pB -> GetClassIndex();

    while (nodeAIndex != 0)
    {
        if (nodeAIndex == nodeBIndex)
        {
            return true;
        }
        nodeAIndex = nodeAIndex >> 1;
    }
    return false;
}

Actually once the index for a parent of A is less than the index for B, there is no way that they can be equal. So we can reduce worst-case scenario.

bool IsA_Balanced2Tree_V2(Class *pA, Class *pB)
{
    int nodeAIndex = pA -> GetClassIndex();
    int nodeBIndex = pB -> GetClassIndex();

    while (nodeAIndex >= nodeBIndex)
    {
        if (nodeAIndex == nodeBIndex)
        {
            return true;
        }
        nodeAIndex = nodeAIndex >> 1;
    }
    return false;
}

According to the relationship between a node and its parent, here is the algorithm to find the index of a child, depends on its position in the sub-tree:

int childIndex(int nodeIndex, bool bRight)
{
    if (bRight)
    {
        return (nodeIndex << 1) + 1;
    }
    else
    {
        return (nodeIndex << 1);
    }
}

The binary representation looks like this:

WeChat Image_20180130190605

We can observe that: if Class A is a child of Class B, then the leftmost N bits of B will match A, where N is the highest bit set in A.

Using this rule we can remove the while loop in IsA():

bool IsA_Balanced2Tree_V3(Class *pA, Class *pB)
{
    int nodeAIndex = pA -> GetClassIndex();
    int nodeBIndex = pB -> GetClassIndex();

    if (nodeAIndex > (BSR(nodeAIndex) - BSR(nodeBIndex));

    return nodeAIndex == nodeBIndex;
}

The BSR() here is a wrapper for an inline assembly function that uses the BSR assembly instruction BitScanReverse, which returns the index of the leftmost set bit. If would be easy to pre-calculate the most significant bit index even if the platform does not support BSR().

However, all of the previous work has been built upon the notion that our class hierarchy is a perfectly balanced tree. Fortunately, our IsA() function does not care about the depth between nodes, only ancestry matters. So we can convert the unbalanced tree into balanced tree by adding phantom class, as long as we keep them in fact ancestors.

WechatIMG144

The following algorithm is the simplest implementation for building the class tree.

void BuildTree(Class *pA)
{
    int nCurrentClassIndex = pA -> GetClassIndex();
    int nNumChildClasses = pA -> GetNumberOfChildClasses();
    int nNumLeverls = BSR(nNumChildClasses() + 1;
    int nChildIndexStart = nCurrentClassIndex << nNumLevels;

    for (int i = 0; i  GetChildClass(i);
        pChild -> SetClassIndex(nChildIndexStart + i);
        BuildTree(pChild);
    }
}

Independent Study for Spring 2018

I am taking the Independent Study for Spring 2018, my last semester in ETC, focusing on strengthening my programming skills, and keeping practice on solving technical interview questions, to make myself well-prepared for finding a job.

More specifically,  here are three main goals:

  • Get familiar with C++.
  • Consolidate technical interview knowledge, especially on data structures and algorithms.
  • Polish resume and portfolio, become more confidence for interviews.

And ultimately, find an ideal job.

My study will under the supervision of Dave, one of my favorite faculty in ETC. Dave is experienced in game development, and he is super smart, also very nice to talk with. He has referred me some books to study. I am really appreciated for his help.

I will write down some posts in this blog as summaries during my study. Hope everything goes well.

Good luck to myself, keep calm and carry on.