Robot 9

Awakened by a strong rainstorm, I decided to get up and watch it. I’ll code a bit while I do. I’ll try to think before, during, and after coding.

Here’s a question that has been puzzling me. According to the game spec, if you are facing, say true East, and you scan, the information you get back will code anything in front of you as North. I suppose the rationale for that is that you have a forward-facing radar or something. Or maybe it’s just there to make the problem harder, as this is a teaching exercise at base.

Now I do expect that the screen would reflect the rotation of the robot, and I can see at least two ways to do it. One is simply to indicate the robot’s direction by giving it an arrow shape or something in the center of the display, and leave the objects in the display where they are. It would work like a dungeon crawl, which generally always faces the map “north up”.

The other way would be to keep the robot facing so that forward is up on the screen, and to rotate all the stuff. From a game-play viewpoint that’s probably less desirable, but an actual robot might expect his screen to always stay “forward up”. If he were sentient, which he is not.

I guess what we should do, because it is probably harder, is rotate the view.

Rotating the View

Needless to say, we’re going to do this with the Lens, which already translates the view, so it might as well rotate it. The big question is how, and it comes in at least two parts:

1. How do we rotate our view on the screen?
2. How do we ensure that info coming back from scan is properly placed?

These may come down to the same question, but the situation is made a bit more complicated by the spec’s planned return from a scan.

We’re not yet creating and using the spec’s proposed JSON-formatted information packets that go back and forth between World and Robot. When that day comes—and it may never come—the scan packet returns a fake direction, North for in front of you at your current rotation, a distance, and an indicator of what the item is. So, if that day comes, we’ll need to use NSEW kinds of coordinates, not our more convenient x,y.

Which is worth talking about. One reason why I wanted to start with a robot and world in the abstract is that since these are the main operational objects, I want them to have data structures that are as suitable to them as possible. So I am programming them, as best I can, to be built with information in the form they like.

If I were to start with the dare I say it strange format of the proposed JSON, there’s a risk that I’d fall into the trap of programming my objects to work directly with the JSON or the arrays and dictionaries into which we’ll decode it, rather that on information that is appropriate to the objects.

I think it is better to let your I/O objects be what I/O needs, and your programming objects be what they want to be. My current choice for the programming objects is essentially an array of x,y, and content. It happens to be sparse, but whatever it is, it’s encapsulated in the Knowledge.

Which brings a thought to mind. Currently, the Lens knows an x and y offset, and applies them when fetching or storing content. I expect that the Lens will soon know rotation, and deal with that as well. But the Lens could also understand N, S, E, W and distance. There’s no reason it couldn’t have that interface as well as x,y. Or, we could have another kind of Lens that does that transformation, and put one on top of the other Lens.

Worth remembering for that future day that may never come.

Let’s get to it. We want to implement robot turns.

Robot Turns

The robot can rotate left or right. It can only rotate one 90 degree angle per turn. We define the screen behavior to be that the robot is always facing screen top, and that we need, therefore, when it turns left, to put the objects that were formerly at the left of it, in front of it, that is, at the top of the screen.

Formally speaking, this comes down to a rotation of a vector. Something to our right at distance d has the coordinates (d,0). When we turn to face it, it’ll have the coordinates (0,d). Something that was behind us at d goes from (0,-d) to (d,0): it appears now on our right.

So when we turn right, what was at (x,y) now needs to display at (y,-x). (This may not be obvious, but I’m sure it is true.)

Similarly when we turn left, something in front (0,d) winds up on our right (d,0), and something behind us (0,-d) winds up on our left (-d,0). So a left turn changes (x,y) to (y,x).

Now you may ask yourself how do I know this? And, more importantly, how could you know this. Well, I know it because I’ve done a lot of rotations in my life, and because even so, I looked up 2D rotation on the internet, and I even used Codea’s rotate90 function to see what came out when I rotated some simple vectors. It turns out that the “real” answer involves a bunch of sines and cosines, but conveniently for us, the sine of 90 is one and the cosine of 90 is zero, so it all comes down to swapping the coordinates and sometimes negating.

But Papa didn’t raise no fools, and we’re going to TDD this anyway. Then we’ll see values that we understand. Let’s do a separate Lens, a RotatingLens.

Rotating Lens

Begin with a test. After making a new tab, TestRotatingLens, with a test frame in it, I write this first bit:

        _:test("Some Turns", function()
            local lens = RotatingLens()
        end)

I plan to test all the turns in what will become a fairly long test. Some folx would do lots of little tests, but in this case, I don’t see the value. Perhaps I’ll learn otherwise.

This is enough to drive out the class:

1: Some Turns -- TestRotatingLens:16: attempt to call a nil value (global 'RotatingLens')

I’ll code just that.

RotatingLens = class()

The test should run. It does, so I’ll enhance it. I’m supposing that it’s going to have to have factAt and addFactAt, and a Knowledge or Lens underneath it. Let’s do that first, so that testing will be easier against a known Knowledge. So …

        _:test("Some Turns", function()
            local k = Knowledge()
            k:addFactAt(0,2,"0,2")
            k:addFactAt(1,0,"1,0")
            k:addFactAt(0,-3,"0,-3")
            k:addFactAt(4,0,"4,0")
            local lens = RotatingLens(k)
            _:expect(lens:factAt(0,2)).is("0,2")
        end)

I think I’m going to want more facts than that, some off-axis ones. I may wind up splitting this test after all. I’ve also got enough now to drive out a bit of code. The error will be factAt on lens.

1: Some Turns -- TestRotatingLens:22: attempt to call a nil value (method 'factAt')

I can do that almost trivially:

function RotatingLens:init(world)
    self.world = world
end

function RotatingLens:factAt(x,y)
    return self.world:factAt(x,y)
end

I expect the test to run. It does not:

1: Some Turns  -- 
Actual: nil, 
Expected: 0,2

I am surprised. Also I don’t think we should call the parameter world, it’s a knowledge. Fix that. The test still fails, and that’s because addFactAt, as its name clearly says, requires the fact first.

        _:test("Some Turns", function()
            local k = Knowledge()
            k:addFactAt("0,2",0,2)
            k:addFactAt("1,0",1,0)
            k:addFactAt("0,-3", 0,-3)
            k:addFactAt("4,0",4,0)
            local lens = RotatingLens(k)
            _:expect(lens:factAt(0,2)).is("0,2")
        end)

Test runs. Lesson there about the possibility of calling addFactAt incorrectly. Static typing buffs not and wag their fingers. OK, let’s do a turn and have a fail.

I’m wondering what the protocol should be for a turn. I don’t know, but I know the spec uses “left” and “right”, so let’s try that.

        _:test("Some Turns", function()
            local k = Knowledge()
            k:addFactAt("0,2",0,2)
            k:addFactAt("1,0",1,0)
            k:addFactAt("0,-3", 0,-3)
            k:addFactAt("4,0",4,0)
            local lens = RotatingLens(k)
            _:expect(lens:factAt(0,2)).is("0,2")
            lens:turn("right")
            _:expect(lens:factAt(0,1)).is("0,1")
        end)

Having learned my lesson about long tests, I’m going to remove everything from the test except for this one item. I’m also going to code the value correctly this time, I hope:

        _:test("Some Turns", function()
            local k = Knowledge()
            k:addFactAt("1,0",1,0)
            local lens = RotatingLens(k)
            _:expect(lens:factAt(1,0)).is("1,0")
            lens:turn("right")
            _:expect(lens:factAt(0,-1)).is("1,0")
        end)

The object “1,0” is in front of us. We turn right. It should now be on our left, i.e. at -1,0. Test is still wrong. Fix:

        _:test("Some Turns", function()
            local k = Knowledge()
            k:addFactAt("1,0",1,0)
            local lens = RotatingLens(k)
            _:expect(lens:factAt(1,0)).is("1,0")
            lens:turn("right")
            _:expect(lens:factAt(-1,0)).is("1,0")
        end)

I am also starting to suspect that my textual description of rotating up above may also have been wrong. I’ll check it later and mark it up if it is: getting the understanding right is really important, and if I have it wrong for a while, there’s value to you in seeing that happen. Good for a laugh if nothing else.

I think the test is good now, and I expect that …

No, the test is still wrong. The reason is that the starting object starts to my right!

One more pass at the test:

        _:test("Some Turns", function()
            local k = Knowledge()
            k:addFactAt("DA",0,1) -- dead ahead
            local lens = RotatingLens(k)
            _:expect(lens:factAt(0,1)).is("DA")
            lens:turn("right")
            _:expect(lens:factAt(-1,0)).is("DA") -- off to left
        end)

Better, I hope. What tipped me off was that I was thinking about the turns, and I “know” that a 90 degree turn always swaps x and y, possibly negating, and my test didn’t swap x and y. I expect this to fail on turn.

1: Some Turns -- TestRotatingLens:20: attempt to call a nil value (method 'turn')

Whee, back on track. Implement turn and get the wrong answer.

function RotatingLens:turn(direction)
    
end

1: Some Turns  -- 
Actual: nil, 
Expected: DA

I think I’ll tag those checks:

        _:test("Some Turns", function()
            local k = Knowledge()
            k:addFactAt("DA",0,1) -- dead ahead
            local lens = RotatingLens(k)
            _:expect(lens:factAt(0,1),"0 degrees").is("DA")
            lens:turn("right")
            _:expect(lens:factAt(-1,0), "90").is("DA") -- off to left
        end)

The error should be the 90 one, not the 0 degrees one:

1: Some Turns 90 -- 
Actual: nil, 
Expected: DA

Now let’s implement. We’re basically going to do a matrix multiply here. Unfortunately for me, and perhaps fortunately for the reader, there is no 2D matrix in Codea, so we’ll do it by hand.

A rotation matrix looks like this:

And when we multiply a vector (x,y) by that, we get (ax+by, cx+dy), unless I am mistaken. And when the rotation is a multiple of 90, two of those values are zero and two are plus or minus 1.

You know what? I don’t want to do this with matrices. I want to do it ad-hoc. I may regret this. In particular, I may regret doing it right in the real program instead of in a Spike, but I can treat this as an experiment and toss it, probably.

Let’s try something. I’m envisioning that we’ll store our current turn status as 0,1,2, or 3, the number of right turns we’ve taken. A left is of course three rights, as everyone knows. And we’ll just adjust the coordinates that many times. Weird but easy? We’ll see:

function RotatingLens:init(knowledge)
    self.knowledge = knowledge
    self.turns = 0
end

function RotatingLens:turn(direction)
    if direction=="right" then
        self.turns = self.turns + 1
    elseif direction=="left" then
        self.turns = self.turns + 3
    end
    self.turns = self.turns%4
end

And …

function RotatingLens:factAt(x,y)
    xa,ya = self:adjust(x,y)
    return self.knowledge:factAt(xa,ya)
end

And …

I’ve done this by sheer hackery. In part, the issue is, I think, that I have to undo the rotation. Anyway, this works so far:

function RotatingLens:adjust(x,y)
    local xa,ya = x,y
    local turn = self.turns
    while turn > 0 do
        xa,ya = ya,-xa
        turn = turn - 1
    end
    return xa,ya
end

Let’s do another test. I think this might be good and I am tempted to RORA¹.

        _:test("Left turn moves dead ahead to right", function()
            local k = Knowledge()
            k:addFactAt("DA",0,1) -- dead ahead
            local lens = RotatingLens(k)
            lens:turn("left")
            _:expect(lens:factAt(1,0),"270").is("DA")
        end)

Test runs. I am vindicated, but need to understand better. Let’s test some more. First, two turns.

        _:test("Two left turns move dead ahead to read", function()
            local k = Knowledge()
            k:addFactAt("DA",0,5) -- dead ahead
            local lens = RotatingLens(k)
            lens:turn("left")
            lens:turn("left")
            _:expect(lens:factAt(0,-5),"180").is("DA")
        end)

Let’s do some off-axis points:

        _:test("Off-axis points", function()
            local k = Knowledge()
            k:addFactAt("1,1",1,1)
            k:addFactAt("-2,2",-2,2)
            k:addFactAt("-3,-3",-3,-3)
            k:addFactAt("4,-4", 4,-4)
            local lens = RotatingLens(k)
            lens:turn("right")
            _:expect(lens:factAt(-1,1)).is("1,1")
            _:expect(lens:factAt(4,4)).is("4,-4")
            _:expect(lens:factAt(-2,-2)).is("-2,2")
            _:expect(lens:factAt(3,-3)).is("-3,-3")
        end)

All these tests run. They are devilishly hard to write. For that last one, I resorted to drawing the original layout on paper and rotating the paper to read off the new values.

All that said, I think this works. Let’s commit and then think some more. Commit: Implemented RotatingLens to accommodate turns.

Reflection

First of all, why is this righteous?

function RotatingLens:adjust(x,y)
    local xa,ya = x,y
    local turn = self.turns
    while turn > 0 do
        xa,ya = ya,-xa
        turn = turn - 1
    end
    return xa,ya
end

Let’s take the case of a single right turn, which will do this code just once:

        xa,ya = ya,-xa
        turn = turn - 1

Suppose there is a thing at 1,1 before we turn. When we turn right, that thing appears at -1,1.

This example tells me that my tests are too easy, I’m using equal coordinates. We’ll fix that shortly. Reason with me here:

Suppose there is a thing at 1,2 before we turn. One to our right, up two. When we turn right, that thing now appears one up and over to the left two. So when we look at (-2,1) we should find the thing that is at (1,2) in the real knowledge. So we need to set xa to y and ya to -x. That’s what the code does. The one-liner is a bit hard to read but it saves using a temp to do the swap. So our code is unwinding the right turn.

Still too hard to think about? I know. Just wait though. But first, let’s make the last test harder.

        _:test("Off-axis points", function()
            local k = Knowledge()
            k:addFactAt("1,2",1,2)
            k:addFactAt("-2,3",-2,3)
            k:addFactAt("-3,-4",-3,-4)
            k:addFactAt("4,-5", 4,-5)
            local lens = RotatingLens(k)
            lens:turn("right")
            _:expect(lens:factAt(-2,1)).is("1,2")
            _:expect(lens:factAt(5,4)).is("4,-5")
            _:expect(lens:factAt(-3,-2)).is("-2,3")
            _:expect(lens:factAt(4,-3)).is("-3,-4")
        end)

Test runs. Commit: harder rotation lens test.

That loop is odd. It’s saving us a matrix multiply. I’ll have to think about that. No matter how we parse it, this code is hard to think about, the picture is hard to visualize. But I’m rather sure that the code is good.

Let’s see if we can test it in the game. We set up the visible game in Robot:setUpGame():

function Robot:setUpGame()
    local world = World:setUpGame()
    return Robot("Louie", world)
end

function Robot:init(name,aWorld)
    self._world = aWorld
    self._x, self._y = aWorld:launchRobot(name, self)
    self._name = name
    self.knowledge = Knowledge()
end

We’re still not updating the robot’s knowledge with the scan results, we’re just replacing it. I think the update will be a bit tricky. I’d like to do a simple test just to see the rotate occur. Let’s try this:

function Robot:keyboard(key)
    if key == "s" then
        self:scan()
    elseif key == "1" then
        self:move(0,1)
    elseif key == "r" then
        local lens = RotatingLens(self.knowledge)
        lens:turn("right")
        self.knowledge = lens
    end
end

That gives me this film, of a single scan and then several right turns:

The first turn to the right places the black pit obstacle in front of us, just as it should. The RotatingLens is doing its job as intended.

Commit to save that version of the game, it’ll demo better than the other one. We’ll have to be careful, though, because we can’t move after we rotate yet. I’m starting to want to do this with matrices.

Enough hackery for the morning. Let’s sum up and think seriously about what I’ve done here. (I say “I” because I don’t want you feeling any blame for this.)

Summary

In a real 2D rotation, we need a matrix like this. For a rotation of angle A, we need a matrix:

And that, times a vector (x,y) is

(xcos A + ysin A, x(-sinA) + ycos A)

Unless I’ve typed it in wrong. The nice thing about this format is that given the matrix for rotating by A as mA and the matrix for rotating by B as mB, the matrix for rotating by A and then B is mA*mB.

Even better, in most decent graphical systems, the transformation matrices are built into the system, so that you can just set up matrices, multiply them and everything takes place in your graphics card. And we could do that in this app, rotating the actual picture on the screen, instead of rotating the data internally, as we are now.

My plan has been that we’re not going to do that. I’m thinking that it is too advanced a topic for the students who will be working on this app. But I don’t know, of course, who’ll be reading this, so I’m not sure when or where I might plug in rotations. Since the rotations we have are all by 90 degrees, it may be best not to use matrices at all.

Then again … I’m far from in love with this current implementation. I don’t hate it, but I certainly don’t love it. The looping to back out the rotations is particularly odd. Clever, perhaps, but unclear. Without matrices, I don’t see a better way to do it. But I am reluctant to rely on Codea’s matrices, because the reader may not have them in their system.

Here’s a plan. Let’s wrap this here, acknowledging that we have our walking skeleton and it can even almost handle rotations, and see what we can do about matrices in a separate article.

Right, we’ll do that. See you in Robots 10.