Udacity CS373 – Homework 1.4: Part I

I have just been playing with this localization demo that pomber made in javascript here. It’s a little snowman that you move around with the arrow keys.

I was watching the probabilities move around; sometimes the snowman would be highly localized, but an incorrect reading or a missed move would delocalize the snowman again. And, then there were situations like the one below–where the only move to improve localization is a move to the right.

In fact, the situation could be even worse. From the above position, move right, then you will have no available moves to improve your localization. Move up or down, and you are guaranteed to see a dark color. Try to move left, and again you will definitely see a dark color. Every cell in that column is equally likely, with some additional chance that the move failed. Try to move right, and you will see a light color, again every cell in the column being equally likely. Any failure to move only worsens the situation adding more uncertainty to the localization.

Making a Game

All of this playing around got me to thinking, why not turn it into a game? Instead of showing where the snowman is, we can hide it. The object of the game could then be to move around until you know where you are and then make a guess.

Step 1: Remove the Snowman

The author of the demo, pomber, was kind enough to provide the source code so the first part was easy enough. On line 85, the robot char was set “☃”, so we just change that to “”:

85
var robotSymbol = "☃";

->

85
var robotSymbol = "";

Step 2: Guess the Cell

For the next step, we’ll want to add some handlers so that we can guess which cell we are actually on. Again, this is pretty easy because pomber has done a nice job creating clean, readable code. The boards are both labelled with a class of “board”, so I can easily add a listener to the click event of the enclosed td tags.

158
159
160
161
162
163
164
165
166
$(".board td").click(function (e) {
 
    var position = e.target.id.substr(2).split('-');
 
    var row = position[0];
    var col = position[1];
 
    guess(row, col);
});

My guess function will just contain some simple code alerting if the clicked cell matches the currentRow and currentCol.

202
203
204
205
206
207
208
function guess(row, col) {
    if (row == currentRow && col == currentCol) {
        alert('Correct');
    } else {
        alert('Incorrect');
    }
}

That’s mostly it. Some very simple changes, and we’ve made a simple game. However, I’m not done there. I’d like to add some additional features such as scoring, a leaderboard, and a way to make new games.

Step 3: Scoring

Any real game has high scores. A simple way to get points can be to track of the number of steps, how much time, and how many guesses were needed to find the robot. Let’s put all of that together.

First let’s add all of the necessary variables and util/helper functions. We need the movesLeft, livesLeft, and startTime vars.

3
4
5
6
7
8
var movesLeft = null;
var livesLeft = null;
var startTime = null;
 
var allowedMoves = 3;
var allowedLives = 3;

Set all of the defaults in the initializeWorld() function.

156
157
158
159
function initializeWorld() {
    livesLeft = allowedLives;
    movesLeft = allowedMoves;
    startTime = null;

Some util functions to help with calculating scores:

230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
function getLifeBonus() {
    return livesLeft * 100;
}
 
function getTimeBonus() {
    return Math.round(
        Math.max(
            0,
            300 - ((new Date()).getTime() - startTime) / 50
        )
    );
}
 
function getMoveBonus() {
    return Math.max(0, movesLeft * 25);
}

Add a place to show the current score:

15
16
<div id="result">
</div>

Update the movesLeft and livesLeft vars in the move and guess functions. Then, when the robot has been found, total up the scores, display them in the result div.

191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
function move(rowDelta, colDelta) {
    if (startTime == null) {
        startTime = (new Date()).getTime();
    }
    movesLeft--;
 
    moveRobot(rowDelta, colDelta);
    drawRobot();
    moveBelief(rowDelta, colDelta);
    drawBelief();
 
    if (autoSense) {
        sense();
    }
}
 
function guess(row, col) {
    if (row == currentRow && col == currentCol) {
        var timeBonus = getTimeBonus();
        var moveBonus = getMoveBonus();
        var lifeBonus = getLifeBonus();
        var totalScore = 100 + timeBonus + moveBonus + lifeBonus;
 
        $("#result").append(
            '<b>You got it!</b>' + 
            '<br/>Completion: 100 pts' + 
            '<br/>Time Bonus: ' + timeBonus + ' pts' +
            '<br/>Move Bonus: ' + moveBonus + ' pts' + 
            '<br/>Life Bonus: ' + lifeBonus + ' pts' +
            '<br/><b>Total: ' + totalScore + ' pts</b>'
        );
 
 
    } else {
        livesLeft--;
 
        if (livesLeft == 0) {
            $("#result").append(
                '<b>Game Over!</b>' + 
                '<br/>Try Again\n'
            );
 
        } else {
            alert(
                'Incorrect!\n' + 
                'Try Again\n' + 
                livesLeft + ' Lives Left'
            );
        }
    }
}

For some better formatting of the results, we’ll use a monospace font:

1
2
3
* {
  font-family: monospace;
}

Step 4: Replaying

The next enhancment will be a New Game button so we can play again without having to reload the page. First add in the button and a listener for it that will reinitialize the boards.

1
<button id="newgame">New Game</button>
191
192
193
$("#newgame").click(function(e) {
    initializeWorld();
});

However, that’s not enough because the initializeWorld function doesn’t clear the existing board before adding a new one:

We need a clearBoard function to start new games and a

91
92
93
function clearBoards() {
    $(".board").empty();
}
160
161
162
163
function initializeWorld() {    
    clearBoards();
    ...
}

Almost done, but the listeners on the $(“.board td”).click were disappearing on clearBoards()., I moved the handlers inside of initializeWorld() and everything worked like a charm.

Step 5: The Leaderboard

Add the leaderboard list and submit to leaderboard form. The form starts out as hidden and is only shown when a game is won.

25
26
27
28
29
30
31
32
33
34
35
<div id="leaderboard">
    <b>Leaderboard</b>
    <ul>
    </ul>
</div>
 
<form id="frmLeaderboard" style="display:none;">
    <label for="name" id="name_label">Name</label>  
    <input type="text" name="name" id="name" size="25" value="" class="text-input" />
    <button id="btnLeaderboard">Submit to Leaderboard</button>
</form>

First some cleanup on the guess function, moving the win/lose handling into their own functions. Then, showing the leader board form when winning a game.

95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
function guess(row, col) {
    if (row == currentRow && col == currentCol) {
        won();
    } else {
        livesLeft--;
 
        if (livesLeft == 0) {
            lost();
        } else {
            alert(
                'Incorrect!\n' + 
                'Try Again\n' + 
                livesLeft + ' Lives Left'
            );
        }
    }
}
 
function won() {
    var timeBonus = getTimeBonus();
    var moveBonus = getMoveBonus();
    var lifeBonus = getLifeBonus();
    totalScore = 100 + timeBonus + moveBonus + lifeBonus;
 
    $("#result").empty();
    $("#result").append(
        '<b>You got it!</b>' + 
        '<br/>Completion: 100 pts' + 
        '<br/>Time Bonus: ' + timeBonus + ' pts' +
        '<br/>Move Bonus: ' + moveBonus + ' pts' + 
        '<br/>Life Bonus: ' + lifeBonus + ' pts' +
        '<br/><b>Total: ' + totalScore + ' pts</b>'
    );
 
    //Show leadderboard form
    $("#frmLeaderboard").show();
 
}
 
function lost() {
    $("#result").empty();
    $("#result").append(
        '<b>Game Over!</b>' + 
        '<br/>Try Again\n'
    );
}

Add the click function to the submit button which adds the score to the leader board, clears the current, and rehides the form.

95
96
97
98
99
100
101
102
103
104
105
106
107
108
$("#btnLeaderboard").click(function(e) {
 
    var liNode = $("<li>");
 
    liNode.append(
        '<b>' + totalScore + 
        ' ' + $("#name").val() + '</b>'
    );
 
    $('#leaderboard ul').append(liNode);
    $("#frmLeaderboard").hide();
    $("#result").empty();
    return false;
});

Step 6: Finishing Touches

I also thought it would be nice to show the robot when finishing a game, successfully or unsuccessully. This was easily done by making a showRobot() and calling it in won() and lost() functions.

95
96
97
98
99
function showRobot() {
    robotSymbol = "☃";
    drawRobot();
    robotSymbol = "";    
}

Final Product

link: http://jsfiddle.net/u9xj6/embedded/result/

There are some pretty obvious bugs. Some ui/design work could certainly benefit the leaderboard/result section. The code could also use some clean up. Plus, some additional enhancements would also be easy, such as a larger board, adjustable parameters, or a third cell color. There would definitely be some interesting result from that, I have already tested out the board with higher sensor fail and movement stall rates and it became much more difficult to locate the robot. Another big win would be recalculating the probabilities on a miss, since we know that the guessed location definitely does not have the would also be a big win. However overall, I am quite happy with the results. We have a nice little localization game. It’s been a good test for me as well since I’ve never worked with jQuery before and rarely work with javascript anymore either. If anyone takes this project further, I’d like to hear about it, so let me know in the comments.

Part II

You may have noticed that this post is labelled Part I, meaning there is a part II. For part II, I’ll be moving back toward the focus of the class, machine learning. For part II, we will be looking at building an algorithm that will choose the best movements so that the machine will be able to localize itself in as few steps as possible. I’m most of the way through the first half of the algorithm. Now comes the difficult part.

Until next time.

This entry was posted in Data Analysis, Data Visualization, Machine Learning, Online Learning and tagged , , , , . Bookmark the permalink.

One comment on “Udacity CS373 – Homework 1.4: Part I

  1. Pingback: Udacity – CS101 & CS373 – Week 4 » Jacob Eggers

Leave a Reply

Your email address will not be published. Required fields are marked *

*

HTML tags are not allowed.