Robo Prototype

I’ve been working on a prototype for an idea I’ve had for a while that I’ve nicknamed Robo. It’s inspired by the Karel J Robot tool that I was first introduced to programing with. The idea is essentially a puzzle game where you can graphically program a robot and use it to solve a map and collect the needed items. In my prototype the goal is to collect all the gold that’s on the map but that’s not enforced. You can try the prototype yourself through the jar version. You can also try to run it from source.

robo

The UI is simple: there’s a left panel with the world you are operating in. The world is infinite in size and you can pan around by clicking and dragging the world and zoom in and out with the mouse wheel (sorry people without mouse wheels).

The right panel contains the programming UI. Programming of the robot is controlled by placing 14 icons in the top right corner in the control grid below. The control grid is infinite in length and can be scrolled down by clicking and dragging it. Program flow starts on the top left and goes in reading order: right and then down. Empty spaces are allowed and are skipped over. The meaning of the icons are as follows:

move Moves the Robot one tile in whatever direction it is facing
turn_left Rotates the robot 90 degrees counter clockwise
turn_right Rotates the robot 90 degrees clockwise
drop_detector Drops a detector to the tile in front of the robot if there’s a detector in the robot’s inventory and nothing in the spot the robot is dropping it in
routine Indicates the start of a routine. When this tile is placed a pop-over comes up asking you to name the routine. If I were to implement the prototype more, this name would be used in configuring other tiles as well. Execution of other routines don’t flow into later routines. Currently the name of the routine should be A, B, or C to be useful.
call_a Jumps execution flow to the routine labeled as A. If no routine exists labeled A, this does nothing. After routine A completes, flow continues in the calling routine
call_b Jumps execution flow to the routine labeled as B. If no routine exists labeled B, this does nothing. After routine B completes, flow continues in the calling routine
call_c Jumps execution flow to the routine labeled as C. If no routine exists labeled C, this does nothing. After routine C completes, flow continues in the calling routine
look_detector Looks at the tile immediately in front of the Robot and sees if there is a detector there. The result of the look is stored in the memory buffer.
look_gold Looks at the tile immediately in front of the Robot and sees if there is gold there. The result of the look is stored in the memory buffer.
look_wall Looks at the tile immediately in front of the Robot and sees if there is a wall there. The result of the look is stored in the memory buffer.
go_a_if Jumps to A like the earlier jump command if and only if the value in the memory buffer is true. Otherwise it does nothing
go_b_if Jumps to B like the earlier jump command if and only if the value in the memory buffer is true. Otherwise it does nothing
go_c_if Jumps to C like the earlier jump command if and only if the value in the memory buffer is true. Otherwise it does nothing

The binary version has a few different worlds attached to it and you can toggle between them by pressing the F1-F4 keys. These worlds are solvable meant to give an idea of some of the things you can program the robot to do. These would probably be more intermediate level puzzles as I expect they would be challenging to a non-programmer and trivial to a programmer. The prototype includes level editing capabilities so you can try making some maps yourself:

W: Move forward
A: Turn Left
D: Turn right
S: Go backwards
U: Drop a detector in front of you
I: Drop gold in front of you
O: Drop a wall in front of you
Backspace: Erase anything in front of you:
Arrows: Place a wall in a direction from you
Home: Increase gold inventory
End: Decrease gold inventory
Page up: Increase detector inventory
Page down: decrease detector inventory
Ctrl-F1 (through Ctrl-F6): Save world
Escape: Exit:
F12: Clear world
Ctrl-z: Undo a world load

I think you can get an idea of the things I was considering from the prototype, however I am unsure of whether the idea is worth pursuing further or which way to pursue it. Thanks to the wonder of Turing Completeness it’s possible to make a system that is very powerful and follow the example of Minecraft Redstone. That’s to say, create a more sandbox type of system with puzzles to provide specific challenges and guidance but with a goal of being more open-ended and powerful. Alternatively I could try to hold truer to my original idea of the game being more of an educational tool by focusing on simplifying it and providing good puzzles with powerfulness being a ‘nice to have.’ This decision also pertains to the platform decision. Were this to be a sandbox, there is much more of an argument to be made about it having a pc/mac platform than with an educational game. For an educational game, the goal of simplicity with the current drag-heavy interface lends itself well to a touchscreen, though perhaps more towards tablets than phones.

The prototype was implemented in Java with libgdx, which provides platform abstraction, allowing you to run on both PC and Android. This was probably a mistake. With it being my first venture with libgdx, I found out that it is poorly documented and lacks some basic features and libraries compared to the Android API. While libgdx is a great tool for its purpose, its purpose is not prototyping. Granted, Java itself was a bad choice for that too. Oh well.

For the prototype I used art assets from opengameart.org, a great resource for game assets. I still managed to programmer art it up with my lack of animations and lack of design, but that’s what a prototype is for. Specifically, I used some assets from IconDock, a basic airship by Alex Pineda, and a few Dungeon Crawl tiles.

Redditgifts challenge

Last summer (Summer 2012), Reddit posted to their blog with a couple job openings, including a programming position with the redditgifts team, the group behind the Reddit Secret Santa and Arbitrary Day exchanges. As a participant in those exchanges who had recently graduated and not yet found a job, this posting was of interest to me. As is common with programming job postings, especially those expected to garner a lot of attention, there was a programming challenge associated. The problem’s goal was to provide a solution to the problem of matching who would give to who for the exchanges. There were a few qualifiers to this, which I paraphrase below:

  • When possible, participant preferences about shipping domestically or internationally should be followed
  • When possible, participants should receive internationally if they ship internationally and receive domestically when shipping domestically
  • When possible, participants should not receive and send a gift from/to the same person
  • Every participant must be matched.

The core algorithm for this was a bit dry for my tastes so I decided I wanted to add my own touch to the problem. Instead of implementing a command line program in python or c++, I decided to implement a fully client-side webpage for the program using standard HTML/CSS/Javascript. My page supplied a textbox for the inputting the participant data and a few preset datasets for trying it out. When you run a scenario, the matching result is generated in the output requested and verbose information about the results is generated including statistics and warnings about each non-ideal matching and when it would occur.

Redditgifts Challenge


One of the common degenerate cases I encountered while implementing the core matching algorithm was that of countries with only one or two participants willing to ship domestically. The problem here being that it’s one of the few cases where it’s impossible to qualify all of the preferences of participants, you must either force them to ship internationally or mutually match them such that they both ship to each other. The challenge didn’t state which is preferred to violate so I chose to match people mutually and perhaps even force someone to ship domestically even when they stated a preference to ship internationally due to the reasoning that international shipping might be a cost a participant can’t afford, thereby possibly leading to a participant to fail to send a gift.

loopOnce those degenerate cases are handled, the general tool I used for matching participants was a series of loop matches where we iterate through a list of participants. The current participant is added as the giver to the next participant and then we step to the participant we just added as the recipient and add him as the gifter for the next participant. We repeat this process until all we have left is the original gifter, who is then added as the recipient to the last participant. This creates a closed loop of giving between the list of participants that as long as the number of participants in the list is more than 2, never creates a mutual match. In psuedocode:


My solution generates one closed loop for the set of participants who are in the same country and all prefer to ship domestically as well as one closed loop for all international shippers across all countries. Generating the loops for domestic shippers is a trivial implementation of the closed loop described above, however doing international shippers is a little bit more complicated. Initially you just need to be careful when iterating through the set of participants to avoid matching participants from the same country, in simple terms you need to interleave countries to avoid subsequent participants being in the same country. However due to how lopsided matches tend to be, with the number of American participants dominating any other country, interleaving them naively will potentially cause more participants to be unable to ship internationally. For example, if there are 3 participants in country A, one in country B, and one in country C, a naive approach could lead to (B->C, C->A1, A1->A2, A2->A3, A3->B) which has two matches with participants in the same country. Meanwhile a proper ordering could lead to (A1->B, B->A2, A2->C, C->A3, A3->A1), which has the minimal number of non-ideal matches: 1. To solve this I simply modified how the next participant is picked in the closed loop to not just take a random participant in a different country than the current participant but to take a random participant in the country with the most number of participants that is not the current participant’s country. This has the side effect of leading to a large number of matches between the largest countries (a lot of exchanges between the US and Canada for example) and few between the largest and smallest countries, but for an interview question I think this is a fair compromise.

I also implemented unit testing for my matching, which you can run by pressing the T in the top-right corner. As I wanted to keep my solution light-weight and free of a need for third party libraries I didn’t use a standard Javascript unit testing framework like Jasmine and instead just constructed an array of test functions that returned true on success and false on failure and rendered whether it passed to the div.

Were I to make improvements to the page my main concern would be how data is entered and retrieved into the page. My input format is not flexible, it would be preferable to be able to choose a number of formats, perhaps even allowing the user to enter a template or regular expression to pick out the data. After that I would like to improve the appearance. I wasn’t too concerned about making the page look good since the job was a programming position and I’m not a designer but I do think it could be improved. Perhaps I might also add in some configuration to it to choose relative priority of and disable different requirements and add other fields to match using to vary results as needed.

Time

Every month Experimental Gameplay posts a new theme. The goal for participants is to create a game using this theme sometime during the month while spending less than one week on the game. This challenge was born out of a project by a group of students at Carnegie Mellon to each create a new game every week. I used to follow the blog during the original project in order to play the games they produced, including a really fun one called Tower of Goo, which Kyle Gabler later expanded on in the slightly better known, World of Goo.

The theme for Experimental Gameplay in August and September of 2012 was Time Manipulation. Unfortunately I did not get a proper game finished, however I did make a basic puzzle game based on a more technical interpretation of the theme.

Time screenshot

The game is written in classic HTML, Javascript, and CSS. As it uses a simple text interface there’s no need for any advanced HTML5 features, though it does use the CSS3 feature, font-face. The puzzle mechanic is simply to figure out what time you want to find based on the text. The twist is in how you enter your result, there’s no textbox, you need to manipulate the time manually. The bad side of this is that the mechanic fails on mobile devices. The other problem of the game is that it’s in the minority of games that you can beat by letting it run in the background. I didn’t get to writing too many puzzles for it so it’s quick to play through.