The Scent of a ... Block?

The Repo on GitHub

My demon-dispelling thoughts this morning turned up what I think is a very nice-smelling idea. I must try it.

In the early mornings, before I get up, my thoughts can turn dark, very dark. The only antidote I’ve found is to find something to occupy my mind. For a while, if I’m programming on something during the day, I can think about that. And soon, if I get a decent idea going, I will get up, freshen up, and work on the idea.

Today’s idea is about scent, and Bot behavior. The current Bots are, in our minds, like ants. They can’t see very well, and they have very simple rules of behavior. As you’ve seen, they mostly wander around wishing that they had a Block, or wishing that they could get rid of the block that they have. This much behavior, plus some very simple rules on when they can pick up or drop a block, results in them grouping blocks in growing piles.

Let’s modify the game so that it will run very fast, and I’ll show you a picture of what they do.

That’s the result of a few hundred or a thousand decision cycles for the twenty bots who are running around. There are only about 50 blocks to start with.

It would be nice if the bots would gather all the blocks into one big pile. (OK, I admit, that’s not the nicest thing we could think of, but at least relative to the bot world, it would be nice.)

My idea is this:

What if blocks had a scent? So blocks close together would have more scent than blocks far apart. And suppose that bots were inclined to drop blocks only where the scent was stronger and not to pick up blocks where the scent was stronger, compared to some memory of the strongest and weakest scent they had ever noticed. Some rule like that. This is an early morning idea, keep that in mind.

It seems, though, that big piles would attract more blocks, and small piles would tend to lose blocks. And maybe, with not much tuning, we could get one big pile of blocks.

So that’s my idea.

Scent

Let’s suppose that the only time a Bot pays attention to scent is when she is otherwise able to pick up or drop off a block. And presumably scent trails off with distance. So let’s consider a small range around the a given cell. I’ll show the Manhattan distance from the center of a small square:

43234
32123
21012
32123
43234

This is kind of the opposite of what we’d like scent to do. We want further away to provide less effect. So let’s look at four minus Manhattan distance:

01210
12321
23432
12321
01210

And suppose the scent of a cell was the sum of the scents around it. Let’s see if we can test-drive a scent feature.

TDD Scent

I start with my standard hookup test and then begin to think about how to test this. I get this far:

class TestScent:
    def test_hookup(self):
        assert 2 + 2 == 4

    def test_empty_world(self):
        w = World(10, 10)

I think Scent is like Vision. Vision considers cells directly surrounding a center cell. This is certainly similar.

Let’s see what we have for tests of Vision. We might get an idea.

I quickly discover that there are no tests that create a vision directly. So that’s weird. I make a note to look into that. Not much joy there. But anyway let’s see if we can write some tests about what we wish scent would do. The way vision works, if I recall, is that the World always sends a vision list to the bot, looking like this:

class World:
    def set_bot_vision(self, bot):
        bot.vision = self.map.create_vision(bot.location)

class Map:
    def create_vision(self, location):
        result = []
        for dx in (-1, 0, 1):
            for dy in (-1, 0, 1):
                found = self.entity_at(location.x + dx, location.y + dy)
                if found:
                    result.append((found.name, found.x, found.y))
        return result

We do have tests for create_vision, but only minimal ones. Let’s suppose that Map will do a scent map for us, around a given cell, as it does with create_vision.

I’ll TDD that.

    def test_empty_map(self):
        map = Map(10, 10)
        scent_map = map.create_scent_map(Location(5, 5))

That’s enough to drive out the method. What is the scent_map? I don’t know. What do I want? I think I want a list, of 25 cells, showing the scent contribution of that cell, which is an integer from 0 through 4. Actually, of course, what I really want is the total of those. Why can’t map provide that. Yes. Change the test:

    def test_empty_map(self):
        map = Map(10, 10)
        scent = map.scent_at(Location(5, 5))
        assert scent == 0

Note

Much of TDD’s value comes from working out what the interface of an object “should” be. I see no reason why the map can’t do this job directly … well, almost no reason … we do have this odd rule that we want to sum four minus the Manhattan distance for cells with blocks. That’s got a lot of domain in it. But for now, we’ll go with it.

PyCharm adds a dummy method for me, and I work with it. And I go entirely off course: I write what I think is the whole method. Following strict TDD, I should probably have returned a zero. Anyway, now I have this:

    def scent_at(self, location):
        total_scent = 0
        for dx in (-2, -1, 0, 1, 2):
            for dy in (-2, -1, 0, 1, 2):
                current = location + Location(dx, dy)
                found = self.entity_at(current.x, current.y)
                if found:
                    scent = 4 - location.distance(current)
                    if scent < 0:
                        scent = 0
                    total_scent += scent
        return total_scent

Note

The “fake it til you make it” trick, per Kent Beck, is a nice one that produces the minimum possible code to pass the current test, pt can put in place some of the infrastructure we need for the full method. I often use it. It would have just given us a method scent_at that returned a literal zero here.

I didn’t do that. I had code at my fingertips, so I wrote it. As we’ll see … it mostly worked OK.

I think that might actually be correct. Let’s do some tests, like we should have before we coded quite this much.

Hey! I have an idea! We could factor out that calculation of the scent of a given cell. Let’s get some help from PyCharm and we might get something easier to test.

I have to fiddle my method to make it refactorable:

    def scent_at(self, location):
        total_scent = 0
        for dx in (-2, -1, 0, 1, 2):
            for dy in (-2, -1, 0, 1, 2):
                current = location + Location(dx, dy)
                found = self.entity_at(current.x, current.y)
                scent = 0
                if found:
                    scent = 4 - location.distance(current)
                    if scent < 0:
                        scent = 0
                total_scent += scent
        return total_scent

Now I can do an Extract Method:

    def scent_at(self, location):
        total_scent = 0
        for dx in (-2, -1, 0, 1, 2):
            for dy in (-2, -1, 0, 1, 2):
                current = location + Location(dx, dy)
                scent = self.relative_scent(location, current)
                total_scent += scent
        return total_scent

    def relative_scent(self, location, current):
        found = self.entity_at(current.x, current.y)
        scent = 0
        if found:
            scent = 4 - location.distance(current)
            if scent < 0:
                scent = 0
        return scent

We can clean this up a bit, but let’s defer that and see how we can test our new relative_scent method to our benefit.

    def test_relative_scent_right_here(self):
        map = Map(10, 10)
        loc = Location (5, 5)
        block = Block(loc.x, loc.y)
        map.place(block)
        scent = map.relative_scent(loc, loc)
        assert scent == 4

That passes. How about scent_at? It should also get 4.

    def test_scent_right_here(self):
        map = Map(10, 10)
        loc = Location (5, 5)
        block = Block(loc.x, loc.y)
        map.place(block)
        scent = map.scent_at(loc)
        assert scent == 4

That fails. I thought I saw why, but I don’t. What did we get?

Expected :4
Actual   :100

Well! Where did that come from? 100 … interesting … 4 times 25 … 25 cells being checked. Got 4 all the time?

What does entity_at return?

    def entity_at(self, x, y):
        point = Location(x, y)
        for entity in self.contents.values():
            if entity.location == point:
                return entity
        return None

OK, it can return None, which means that my check for found should be OK. Check the code again:

    def scent_at(self, location):
        total_scent = 0
        for dx in (-2, -1, 0, 1, 2):
            for dy in (-2, -1, 0, 1, 2):
                current = location + Location(dx, dy)
                scent = self.relative_scent(location, current)
                total_scent += scent
        return total_scent

    def relative_scent(self, location, current):
        found = self.entity_at(current.x, current.y)
        scent = 0
        if found:
            scent = 4 - location.distance(current)
            if scent < 0:
                scent = 0
        return scent

We see now that, conceivably, writing the whole method out of my, um, head, was perhaps not ideal. I see two options: I could roll back and recode the methods; I could debug, because I’m sure a print or two would get me out of this; or (wrong about the “two”) I could do some more detailed testing.

I take the coward’s way out and toss in some prints.

I get my answer: location and current are always equal in the relative_scent method. The + didn’t do what I expected!

class Location:
    def __add__(self, other):
        try:
            assert isinstance(other, Direction)
        except AssertionError:
            return self
        new_location = Location(self.x + other.x, self.y + other.y)
        return new_location

Location silently returns itself under addition, unless you’re adding a Direction.

Nice! I know I did that because I don’t want exceptions in the code, but a warning would have been nice.

    def scent_at(self, location):
        total_scent = 0
        for dx in (-2, -1, 0, 1, 2):
            for dy in (-2, -1, 0, 1, 2):
                current = location + Direction(dx, dy)
                scent = self.relative_scent(location, current)
                total_scent += scent
        return total_scent

Tests pass. A couple more and I’ll think this works.

    def test_scent_all_around(self):
        map = Map(10, 10)
        for x in range(11):
            for y in range(11):
                block = Block(x, y)
                block.id = 11*x + y
                map.place(block)
        scent = map.scent_at(Location (5, 5))
        assert scent ==  40

I summed up the square shown above, and got 40. Then I filled the plane with blocks¹, and checked the scent at the center. Got 40. I think this works. Well, almost. It’s not checking for things that are not Blocks. New test:

    def test_bots_dont_smell(self):
        map = Map(10, 10)
        for x in range(11):
            for y in range(11):
                block = Bot(x, y)
                block.id = 11*x + y
                map.place(block)
        scent = map.scent_at(Location (5, 5))
        assert scent ==  0

And fix:

    def relative_scent(self, location, current):
        found = self.entity_at(current.x, current.y)
        scent = 0
        if found and found.name == 'B':
            scent = 4 - location.distance(current)
            if scent < 0:
                scent = 0
        return scent

I find that convincing. Commit: Map can produce a summary scent of all the blocks near a given cell.

Let’s reflect and sum up.

Reflecto-Sum

This went well enough. I’m not proud, because I wasn’t saintly about testing, and I did a few prints to figure out what was going on. I felt it was expedient, but I think reaching for “expedient” is an admission that one could have been more on one’s game. But I think the result is a good start.

I think that there are a few things set constant that probably should be parameters. The scent is hard-wired to look for things named ‘B’, i.e. Blocks, and might want to be able to look for something else. (And checking an Entity type by name is a bit naff in itself.) The scent has a hard-wired range of -2 through 2, which could perhaps want to be variable. And the expression summed is hard-wired to be 4-distance, which we might also want to vary.

But we have no need for any of those variations now, so, for now, I observe those things, I reflect upon them, and I deem them OK for now. If we have further needs, we’ll see what to do at that time. The capability is nicely isolated.

Other than tests, it’s not even used. No point generalizing something that hasn’t come into use.

We’re two hours in, and I’m going to take a break. Next time we’ll take a look at how we’d like to use the thing, perhaps even starting in the state machine or Knowledge. We’ll look around and decide on the next small steps.

We’ve left the actual scent_at code a bit more messy than it could be. I’m tired and unwilling to chase it now. I’ll make a note and with luck, come back to this code. If not, then the next time we need to change it. If we never change it, it’s OK now.

I feel good about this idea and good enough about where we are. I could have adhered closer to my best habits, but I’m just a human being, not some kind of god-like figure that programs without ever going astray. Today, I didn’t go so far astray as to feel troubled … though I can see that, in principle, a path was possible that might have adhered more closely to those good habits. Easy to say in retrospect. When I was there, I chose the best alternative I saw in the moment.

Success today. Next time, try to succeed better. See you then!