Monday, November 23, 2009

High Score List - Finally Solved

Over the past week I have been grappling with a simple problem: determining how to create a high score list for the Fangs Invader game. This seemingly simple problem gave me a complete mental block that took a week to thaw. I am happy to report that on Friday night I was finally able to solve this problem. Here is a simple sketch that displays the functionality that I created followed by an overview of my solution.

The Architecture
From an application architecture perspective, I decided to do most of the heavy lifting in Processing because I am know it better than PHP. Hence the PHP script only has two functions: (1) saving the high scores to a text file; (2) displaying the high scores from the text file. Processing takes care of the following functions: (1) Determining if current player’s score qualifies him to be added to the high score list; (2) capturing the player’s name, if he has a high score; (3) re-sorting the high score list to include the new score and name.

PHP Script
Two weeks ago I struggled with PHP to create a script that was able to read data from a query string and save that data to a text file, and read data from the same text file and display it appropriately. After much trial and error I successfully put together a short script that is able to accomplish this feat.

I found PHP to be a very temperamental language. I am not used to working with un-typed languages – I am not skilled enough to take advantage of the additional flexibility they provide while I seem to get caught up in many unknown and unexpected quirks and behaviors. Nonetheless, I have not been dissuaded from learning this language and hope to build my skills over the next three semesters.

Processing Sketch
Shortly after I finished the PHP script I started working on the Processing sketch. In no time I had the Processing application reading from and writing to the PHP script. I quickly lost steam when I tackled the sorting of the highscore list. This is not to say that this problem is particularly hard, however, in the road to solving it I encountered a major a blank.

At first the problem seemed simple, I created a short algorithm that seemed to work fine. I was actually very satisfied with myself for having solved this problem so quickly and simply. I had even started to integrate the solution into my fangs game.

So my solution did work fine unless there was more than one entry on the list with the same score. When this occurred the algorithm would select the name of one entry and apply that name to all others with the same score. Another issue was that the logic for the Fangs high score list is reversed - the better scores are the lower scores. Therefore, I needed to create an algorithm that is able to locate the lowest score that is above zero.

This is when I hit into a hard brick wall, head-on. The problem was back and I did not know where to even start. My attempts at writing pseudocode were totally unhelpful at first. My mind was so focused on integrating the functionality into the game and doing other things to the game that it just did not want to deal with this problem anymore.

In retrospect, I see how my initial approaches to this problem were overly complex (I won’t even try to explain it here). At first I had a hard refocusing and “seeing the forest from the trees” so that I could tackle the problem from a different perspective. It took me 6 days to figure out a different approach to solve this problem. Part of this process required that I stop working on this problem for a few days so that my mind could disassociate from it.

Here is a pseudocode-like overview of the solution that I developed for sorting the highs core list. All of the functionality outlined below is encapsulated in the changeList() function that is part of a class called PHPconnect. To support my algorithm I declared three array variables, each one holds eleven variables: a position for each from the current high score list and one position for the current player’s score.

The newLocation array is used to store the new location of each element on the top score list with references to their current location on the scoreList array, which holds the pre-sorted rank of each element on the old top ten list along with the new player’s score, saved in the eleventh position in the array. All elements in the newLocation array are initialized to -1 when the changeList() function is called. This is relevant because the newLocation array plays an important role in processing lists that feature multiple players with the same score.

The tempScore and tempName variables are used to temporarily hold the re-sorted top score and top name lists. At the end of the chageList() function the scoreList and nameList arrays updated by being assigned the values from these temporary arrays.

There are two other variables that play a crucial role in this function: locCounter and locCounter reverse. These two variables are used to determine the new location of each element on the top score list. These variables are incremented each time that a score is found which is lower than the current one being processed. The locCounter variable is used to hold the location of valid scores (any number higher than zero). This variable holds a score’s position from the first location in an array. The locCounterReverse variable is used to hold the location of invalid scores (0’s and -1’s). This variable holds a score’s position from the last location in the array.

Now let’s take a look at the algorithm. An outer loop cycles through 11 times to go through each score in the highscore array. A secondary embedded in the outer loop is used to compare each score with the others on the highscore list. The sketch determines the pre-liminary new location of each highscore list item by counting the number of scores that are greater than the current score.

Once the preliminary location is determined, the next step is to check if the current player’s score is repeated, and if so to adjust its position accordingly. To determine if a player has a repeated score we check the position “locCounter” in the newLocation array. If the position is not available (it is not equal to “-1”) then we loop through subsequent positions, using a while loop, until we find one that is available. This available position is then set as the new position for this list element in the newLocation array.

Once each position in the newLocation array has been assigned, a loop is used to input data into the tempName and tempScore arrays. Then these arrays are used to reset the scoreList and nameList arrays with the updated top score list.

Here is the code for the PHPconnect class that I created:
class PhpConnect {

  // variables that hold the top 10 list of scores. Each is 11 values long to help resorting when a new high score is added
  String [] completeList = new String [11];          // holds the name and score that are read from the file online
  String [] nameList = new String [11];              // holds the name of the players on top 10 list, the 11th spot holds the current player's player
  float [] scoreList = new float [11];               // holds the score of the players on top 10 list, the 11th spot holds the current player's score

  // base list URL
  String baseURL;                                    // holds the base URL that will be used to access the high score file online

  // data associated to current players' performance
  float playerScore;                              // score of current player
  float highScorePos;                             // holds the position of the player in top 10 list, or -1 if player did not reach high score list
  boolean highScore;                              // set to true if player sets a high score
  boolean setCaptureName;                         // set to true when Processing should capture a name from user
  String playerName;                              // holds the current players name (if they have a high score)
  int playerIndex;                                // holds the current letters location within the playerName string
  int nameLength = 6;                                 // holds the length of the name
  boolean ready2save;                             // set to true when Processing sends the new top score list to php application

  int [] newLocation = new int [11];              // holds the new location of each element on the top 10 list

  PhpConnect(String tURL) {
    baseURL = tURL;                               // set base URL to the parameter passed into object
    playerScore = 0;                              // score of current player
    highScorePos = -1;                            // holds the position of the player in top 10 list, or -1 if player did not reach high score list
    highScore = false;                            // set to true if player sets a high score
    setCaptureName = false;                       // holds when Processing should capture a name from user
    playerName = " ";                             // set player name to a space
    playerIndex = 0;                              // initialize the playerIndex variable
    ready2save = false;                           // holds when processing should send the new top score list to php application

void loadList() {
  // create the URL used to make a high score list request
  String loadURL = baseURL + "?type=load";
  // load the top 10 list into the webPageArray (a name and score will be added to each position on the array)
  String [] webPageArray = loadStrings(loadURL);

  // loop each element in the array and breaks it down into separate name and score arrays
  for (int loadLoop = 0; loadLoop < completeList.length-1; loadLoop++) {
    // capture the top 10 elements of the webPageArray variable (in case any garbage is included at the end of the data received)
    completeList[loadLoop] = webPageArray[loadLoop];
    // split each element in the array into a name and score 
    String [] tListRecord = split(completeList[loadLoop], ' '); 

    // check if the tListRecord array has more than one element before initializing the nameList and scoreList arrays
    if (tListRecord.length > 1) {
      nameList[loadLoop] = tListRecord[0];             // save name to nameList array
      scoreList[loadLoop] = int(tListRecord[1]);       // save score to scoreList array

    // DEBUG Statements
    print("name: ");
    print(" - score: ");

  }   // close the for loop
}     // close the function loadList()

// to move the ARRAY count the number of figures that are larger or smaller than the current one
// checks if the current player's scores is in the top 10 and set highScore and setCaptureName to true
void checkList(float tPlayerScore){
  playerScore = tPlayerScore;                  // set player score variable
  setCaptureName = false;                      // initialize setCaptureName variable to false

  // loop through each element in the high score list to compare against current player's score
  for (int checkLoop = completeList.length-1; checkLoop >= 0; checkLoop--) {
    // tell application to capture the player's name if their score is better than the score of the player in the current array position, or if the current position is not set
    if ((playerScore < scoreList[checkLoop] && playerScore > 0) || scoreList[checkLoop] <= 0) {
      // set variable to tell application to capture name
      setCaptureName = true;
}     // close the checkList function

// function that captures the name of the user. The names for the list can be up to 5 characters long
// this function needs to be called from the keyPressed() function in the main sketch
void captureName() {
  // if current player has a high score as set by function checkList() then listen to keys
  if(setCaptureName) {
    // if delete or backspace are pressed
    if((key==char(8) || key==char(127))) {
      // and the location on the string is greater than 0
      if (playerIndex > 0) {
        playerName = playerName.substring(0, (playerName.length()-1));        // cut the last character from the name
        playerIndex--;                                                        // set the current location of the playerIndex
      } else {
       playerIndex = 0;                                                       // don't let current location get below 0
    // if return or enter keys are pressed
    } else if (key==char(10) || key==char(13)) {
      // don't do anything if the playerName variable does not contain information
      if (playerName.equals(" ") || playerName.equals("")){}
      // if the variable contains information then set highScore variable to true to notify application to sort highScore list
      else {
        setCaptureName = false;
        highScore = true;          // set high score to true
        playerIndex = 0;           // re-initialize the location on string to 0
    // if a letter key is pressed then add it to the string
    } else if (key > char(48) && key < char(123)) {
      if (playerIndex == 0) {                          // if playerIndex equals 0 then initiate string
        playerName = str(key);
      } else if (playerIndex < nameLength) {                    // only accept input if character location is lower than 5
        playerName = playerName + str(key);

  print("Capture Name - index number: ");
  print(" player name: ");

// function that re-sorts the top 10 list to include the new player's score
// this function should be called continuously in the draw loop
void changeList() {
  // loop through all of the elements on the list and change the values based on the change rate
  if (highScore) {
      float [] tempScore = new float [11];                                    // temporarily holds re-sorted score list 
      String [] tempName = new String [11];                                   // temporarily holds re-sorted name list
      int [] newLocation = { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};     // holds the location in the current array of each element on the list
      int locCounter = 0;                                                     // temporarily holds a scores new location on the array
      int locCounterReverse = 10;
      scoreList[10] = playerScore;                                            // add current player's score as the last element on the list
      nameList[10] = playerName;                                              // add current player's name as the last element on the list

      // go through each item in the array to determine its new location
      for(int change = 0; change < scoreList.length; change++) {
          locCounter = 0;                                                     // initialize the locCounter variable
          locCounterReverse = 10;
          boolean locFound = false;                                           // declare and initialized the locFound variable
          // compare this item in the array with all other numbers in the array
          for(int subChange = 0; subChange < scoreList.length; subChange++) {
            // if this item in the array is greater than another then add one to locCounter variable
            if (scoreList[change] > scoreList[subChange] && scoreList[subChange] > 0) {
        // loop to adjust the locCounter variable when dealing with scores that are repeated on the list
        // loop through following steps until the location is found
          if (scoreList[change] > 0) {
              while (locFound == false) {
                    // if the location at array index [locCounter] has not been assigned yet then set locFound to true
                    if (newLocation[locCounter] == -1) { 
                       locFound = true;
                    // else if the locCounter variable has exceeded the size of the array set locFound to true
                    } else if (locCounter > scoreList.length) {
                       locFound = true;
                    // otherwise add one to the locCounter variable
                    } else {
              newLocation[locCounter] = change;

          } else {
              while (locFound == false) {
                  if (locCounterReverse <= 0) {
                       locFound = true;
                    // else if the locCounter variable has exceeded the size of the array set locFound to true
                    } else if (newLocation[locCounterReverse] == -1) { 
                       locFound = true;
                    // otherwise add one to the locCounter variable
                    } else {
                newLocation[locCounterReverse] = change;
        // set this spot on the list to the entry at the "change" location on the current array 

      // loop to set the new values into the array
      for (int update = 0; update < scoreList.length; update++) {
        tempScore[update] = scoreList[newLocation[update]];
        tempName[update] = nameList[newLocation[update]];

    // set the scoreList and nameList array using the temporary arrays    
    scoreList = tempScore;
    nameList = tempName;
    // tell the application that it can save the information to the server
    ready2save = true;    
    // re-initialize the highScore variable to false
    highScore = false;

// function that saves the new top 10 list to the server
// it should be called contiously in the draw loop
void saveList() {
  if (ready2save) {
    String saveURL = baseURL + "?type=save";

    // loop through all of the 10 elements of the list and add them to the URL
    for (int saveLoop = 0; saveLoop < 10; saveLoop++) {
      saveURL = saveURL + "&name_" + saveLoop + "=" + nameList[saveLoop] + "&score_" + saveLoop + "=" + str(scoreList[saveLoop]);
    // call URL in order to upload new data to php application
    String [] loadStringArray = loadStrings(saveURL);
    // DEBUG: debugging code to view status of application
    print("saveURL: ");

    // reset all variables to their initial state
    playerName = " ";
    playerScore = 0;
    ready2save = false;
    highScorePos = -1;

// function that initializes the scores on the server.
void initHighScores() {
   String initializeURL = baseURL + "?type=save";
   for (int saveLoop = 0; saveLoop < 10; saveLoop++) {
       initializeURL = initializeURL + "&name_" + saveLoop + "=" + " " + "&score_" + saveLoop + "=" + "-1";
    // call URL in order to upload new data to php application
    String [] loadStringArray = loadStrings(initializeURL);


No comments: