Untrusted, level 13

Spoiler warning:

This will contain my solutions and explanations for the various levels in the game Untrusted. If you have not played yourself, I highly recommend doing so without reading through this post. Half the fun (and learning potential) of the game is experiencing it yourself and getting the satisfaction of the “Ah ha!” moment. </spoilerwarning>

Level 13: robotMaze.js

Whew! This level was a good challenge, and it took me a couple of days coming back to it after work and unrelated study to finally come up with a solution. I am not entirely satisfied with my solution, but I have determined that it is repeatable and will, with enough persistence, eventually succeed. It reminds me of some of the probabalistic exploits used in penetration testing, where due to the changing nature of the platform to be attacked, it may take two three, or more attempts before the exploit is successful. That said, I would still prefer to figure out a solution that was cleaner and more deterministic than this one.

As previewed in the last post, this level provides us with a randomly-generated maze that needs to be navigated by a robot in order for us to obtain the blue key:

Out of the gate we are given a robot who moves randomly based on the adjacent cells that are empty on each ‘turn.’ If we assume that the PRNG used to select a move from the possible moves is unbiased, then eventually the robot should solve the maze, if we give it enough turns. In reality, that is not the case: since the function, as written, does not consider the space containing the key to be “empty,” the robot will never move into that space!

This became important later on when I was relying on the pre-built function to reintroduce some randomness to the robot’s movement.

Interestingly, my original assumption that I needed a pathing algorithm to solve this level turned out to be incorrect. I honestly could not figure out, within the constraints of the code provided, how to implement any of the pathing/maze solving algorithms that I was researching. The main confounding factor was the inability to declare arrays without resetting them. Since the robot’s behavior executes every turn, any new arrays that we declare as empty to begin with would be reset every turn. What I had in mind was an array to store the spaces the robot had already visited in order to prefer new spaces, but I couldn’t make it work. Maybe somebody else has hacked together a solution to that in this context? If so I would love to hear from you.

I won’t go into details on all the unsuccessful approaches I tried, but suffice it to say there were multiple attempts. I tried very complex, branching “if” statement trees; I tried figuring out a way to delcare new variables that could be used to navigate properly; I tried stealing the existing variables from the code to re-use them in a manner different than what they were intended for (variables ‘i’ and ‘autoGeneratedMaze’ were the most interesting, but still ended up being dead ends for me). I struck out on all these approaches, and it turns out that the overall goal I had in mind - namely, implementing a pathing algorithm such as a breadth-first search or A* search - was over-thinking the problem. While either of those would certainly yield a more optimal solution, that is assuming full control of the code, which we don’t have. I have no doubt it is possible to get one of those algorithms working in this game, but the hoops we would have to jump through to make it work are more effort than they are worth. The ultimate goal is to get the key, regardless of how we do it.

With that in mind, I went back to the tools I knew I had at my disposal from earlier levels. The introduction to drones provided a very simple but dynamic decision tree for pursuing the player on an open, unobstructed field. I knew this wouldn’t, by itself, be a solution, but I decided to use that as my starting point. To begin with, I commented both the existing pieces of starter code, and implemented a modified version of the drone code from level 6:

    //Determine the distance between the robot and the player as (x,y) values
    var leftDist = me.getX() - player.getX();
    var upDist = me.getY() - player.getY();
    //Set a direction based on the distance values, with a bias based toward the greater value in the pair, and a slight bias for 'up' and 'left' when distances are equal
    var direction;
    if (upDist == 0 && leftDist == 0) {
        return;
    } if (upDist > 0 && upDist >= leftDist && me.canMove('up')) {
        direction = 'up';
    } else if (upDist < 0 && upDist < leftDist && me.canMove('down')) {
        direction = 'down';
    } else if (leftDist > 0 && leftDist >= upDist && me.canMove('left')) {
        direction = 'left';
    } else if (leftDist < 0 && leftDist < upDist && me.canMove('right')) {
        direction = 'right';
    }
    if (me.canMove(direction)) {
        me.move(direction);
    }

The only real change here is that the if statements also check whether the move is valid or not, so as not to waste moves with the robot bumping against walls. This code gives us a decent start. The player can now influence (though not directly control) the robot by moving to different locations on the level. If the robot needs to move right or left, the player can move further in that direction to encourage it: Come on, buddy! That’s it, c’mere! Who’s a good boy?

… Sorry. It’s a robot, not a puppy. Serious business.

In the same way, if the robot needs to move down, the player can vertically line up with the robot and it will move straight toward the player:

Great! So we are making progress… but no doubt the impending problem is obvious, especially on the map in the above screenshots. It only takes a single obstacle to stop the robot in its tracks: Come on, you can do it! Or… maybe not… Yeah, ok… bye, I guess.

This is to be expected, of course: we haven’t given our robot any instructions on why it would ever need to move away from the player, so of course it does not.

Some of my earlier attempts focused on creating a decision tree for what to do when the robot is in a corner. For single-block obstacles, we could use that code to force the robot ‘up’ over such an obstacle. The challenge is a little more complex if the wall is 2 blocks or more vertically. Either way, there is a simpler alternative from a code standpoint: reintroduce some randomness to the robot’s actions. Remember the default code we commented out to begin with? Let’s borrow some of that and append it to the ‘else if’ statements above:

else {
    //Select a random adjacent direction
    direction = moves[map.getRandomInt(0, moves.length - 1)];
}
var moves = ['up','down','left','right'];

A couple of notes, here:

1. We delcare our own array with all four directions instead of relying on the default code to determine empty spaces. More on this in a moment.
2. Notice that the array declaration is coming after its use in the code? In many languages that wouldn’t work, but thanks to JavaScript hoisting it is actually legal and will function. It’s still sloppy code, though, so for cleanliness all declarations should come earlier in the code. I have done it in this example to keep the code snippets brief.

With this new code, we can still lead the robot to a general area, but then if it gets stuck, a few presses of the ‘R’ key will send the robot moving around randomly, similar to the original code. This randomness is just enough to solve obstructions with a little bit of persistence. Simply guide the robot along the map, and if it gets stuck, let it move randomly until it is in a more advantageous position, and continue to success: Congratulations, you now have a blue key! … You are also married to a robot. Seriously. Little guy will NOT leave your side.

Fun fact: if you cross over the robot again the message that you have been given the key will replay, along with its little “ding” sound effect.

There are two important details that I mentioned above, that I want to clarify now, because I actually had a couple of code iterations prior to this final version where I was very close, but couldn’t quite obtain the key.

Recall that I said the robot would never move into the space with the key, based on the original code? I confirmed that the hard way, first: just holding ‘R’ for a good five straight minutes until the robot got near the key. It bubmbled around the key for a while, never quite touching it. Inconclusive, but it led me to wonder initially whether success was possible with the default code. After coming up with the decision tree above, I originally re-used the default random-move code based on ‘empty’ spaces. With that combination I was able to conclude confidently that the robot will never enter the key space based on the default code. I could quickly return the robot to a space adjacent to the key and let it move randomly dozens or hundreds of times, and it would never enter the space. This is why we instead declare the moves array statically. We are actually relying on the random move there at the very end, because due to a movement bias in the movement algorithm, the robot will never end up above the key without a random move, nor will it enter the key space unless it is above the key. With those being the case, we need a random move to either place the robot on the key space, or one space above it. Once it is there, the movement algorithm will direct the robot to the player (assuming the player is just outside the barrier).

So there we go: a working, repeatable solution. In my opinion, this code still suffers from imprecision: there are some wasted moves and it relies on some sloppy randomness. A little trial and error is often necessary on the player’s part, but it ultimately gives us the key.

As I worked through this problem, there were multiple times when I realized I wasn’t getting anywhere, threw out my code, and started fresh. This can be discouraging, but the willingness to do so grants a level of flexibility that has value in solving an unfamiliar problem. The frustration that builds when having to start from scratch is ultimately what leads to the “Ah ha!” moment upon success.

This illustrates the value in being willing to come at a problem from a new angle. Being willing to go back to the drawing board, so to speak, and look at the problem from a different perspective can spell the difference between success and failure. For me, it also illustrates the value of an appropriate amount of time to solve a problem. If I had been rushed and not willing to put iterative effort into the challenge over the course of a few days, I would not have reached my solution.

One final tidbit: while I ultimately ended up not needing it, because my solution was simpler in the end than some of my interim code, I determined a way to get some limited debug information out of the game. Even on levels with no attackDrone objects or other dangerous entities, the ‘player.killedBy’ function always seems to work. A simple debug statement can be set up to determine if your logic is triggering by adding a line like this to your if statements or loops: player.killedBy('debug'); Similarly, to check the value of a variable in the code, place that variable name in the function parameter: player.killedBy(leftDist); This will reset the level, but it also outputs the value or confirms your code is firing: