Far, Far Away

We have a test that seems to compute what we want. Let’s try to see where it should go, and put it there.

We want to find Cells that are maximally distant from other cells, using rooms and paths within the dungeon. Our approach to that is to do a flood fill starting at the given cell, and to associate with each cell in the Dungeon, its distance from the given cell. We’ll then find a cell whose distance is the maximum distance found.

So far we have the flood filling in the distance values, with a test that passes, with the code built directly in the test:

    def test_max_path_distance(self):
        layout = DungeonLayout()
        Cell.create_space(5, 5)
        map = '''
        11111
        '''
        layout.add_rooms_from_map(map)
        given = Cell.at(0,0)
        in_a_room = lambda c: c.is_in_a_room
        for cell in given.generate(in_a_room):
            cell.path_distance = None
        given.path_distance = 0
        for cell in given.generate(in_a_room):
            for neighbor in cell.neighbors_in_rooms():
                if neighbor.path_distance is None:
                    neighbor.path_distance = cell.path_distance + 1
        for x in range(5):
            assert Cell.at(x,0).path_distance == x

As we look at that code, it seems pretty clear where it must belong: it refers only to cells. And it pretty clearly does two things, not one: it clears the path_distance values to None, and then it calculates new ones. So let’s extract two methods, right here in the test. That will give the test roughly the right shape to be testing things on Cell, and the methods will be close to what we want in the Cell class.

After a look at the situation, just about to do the extract, I decide to in-line the lambda first:

        given = Cell.at(0,0)
        for cell in given.generate(lambda c: c.is_in_a_room):
            cell.path_distance = None
        given.path_distance = 0
        for cell in given.generate(lambda c: c.is_in_a_room):
            for neighbor in cell.neighbors_in_rooms():
                if neighbor.path_distance is None:
                    neighbor.path_distance = cell.path_distance + 1

I see no reason why we’d want to pass a lambda into these two methods: we intend this capability to use only room cells (which include path cells, as they are just a wiggly room).

Now extract two methods:

        given = Cell.at(0,0)
        self.clear_path_distance(given)
        self.generate_path_distance(given)

    def clear_path_distance(self, given):
        for cell in given.generate(lambda c: c.is_in_a_room):
            cell.path_distance = None

    def generate_path_distance(self, given):
        given.path_distance = 0
        for cell in given.generate(lambda c: c.is_in_a_room):
            for neighbor in cell.neighbors_in_rooms():
                if neighbor.path_distance is None:
                    neighbor.path_distance = cell.path_distance + 1

Now we want the work to be done in Cell. We want the test to look like this:

    def clear_path_distance(self, given):
        for cell in given.generate(lambda c: c.is_in_a_room):
            cell.path_distance = None

    def generate_path_distance(self, given):
        given.path_distance = 0
        for cell in given.generate(lambda c: c.is_in_a_room):
            for neighbor in cell.neighbors_in_rooms():
                if neighbor.path_distance is None:
                    neighbor.path_distance = cell.path_distance + 1

No. I don’t like this path. There’s no good reason to break out the clear. Reset.

Inline the lambda again. Should have committed. Now extract the whole megillah:

    def test_max_path_distance(self):
        layout = DungeonLayout()
        Cell.create_space(5, 5)
        map = '''
        11111
        '''
        layout.add_rooms_from_map(map)
        given = Cell.at(0,0)
        self.generate_path_distance(given)
        for x in range(5):
            assert Cell.at(x,0).path_distance == x

    def generate_path_distance(self, given):
        for cell in given.generate(lambda c: c.is_in_a_room):
            cell.path_distance = None
        given.path_distance = 0
        for cell in given.generate(lambda c: c.is_in_a_room):
            for neighbor in cell.neighbors_in_rooms():
                if neighbor.path_distance is None:
                    neighbor.path_distance = cell.path_distance + 1

Commentary

I’m somewhat proud of myself for deciding that I didn’t like the dual extract and just resetting. When I saw those two methods, I started thinking about possibly forgetting to call the first one before using the second. And I realized that we should just have one method that does both, even if we do break that method up later. So now we’re green again. Commit: refactoring

Now, wishful thinking, change the test:

        layout.add_rooms_from_map(map)
        given = Cell.at(0,0)
        given.generate_path_distance()

We want that method on Cell. So we grab the generate_path_distance from the test, cutting it out so that we can’t accidentally use it, then move it over to Cell and edit:

class Cell:
    def generate_path_distance(self):
        for cell in self.generate(lambda c: c.is_in_a_room):
            cell.path_distance = None
        self.path_distance = 0
        for cell in self.generate(lambda c: c.is_in_a_room):
            for neighbor in cell.neighbors_in_rooms():
                if neighbor.path_distance is None:
                    neighbor.path_distance = cell.path_distance + 1

And we are green! Commit: Cell:generate_path_distance

Now in the spirit of Composed Method, we really ought to pull out the two components of generate_path_distance. Along the way to the two private methods, I realize I prefer the plural name on the method:

class Cell:
    def generate_path_distances(self):
        self._clear_path_distances()
        self._compute_path_distances()

    def _clear_path_distances(self):
        for cell in self.generate(lambda c: c.is_in_a_room):
            cell.path_distance = None

    def _compute_path_distances(self):
        self.path_distance = 0
        for cell in self.generate(lambda c: c.is_in_a_room):
            for neighbor in cell.neighbors_in_rooms():
                if neighbor.path_distance is None:
                    neighbor.path_distance = cell.path_distance + 1

Green, commit: refactoring

I notice the duplication in those two methods:

        for cell in self.generate(lambda c: c.is_in_a_room):

We could have a method generate_in_rooms covering that lambda. I suspect there are other places where that would be convenient. There are in fact five for statements using that lambda.

Let’s do it:

class Cell:
    def generate_in_rooms(self):
        return self.generate(lambda c: c.is_in_a_room)

    def generate_path_distances(self):
        self._clear_path_distances()
        self._compute_path_distances()

    def _clear_path_distances(self):
        for cell in self.generate_in_rooms():
            cell.path_distance = None

    def _compute_path_distances(self):
        self.path_distance = 0
        for cell in self.generate_in_rooms():
            for neighbor in cell.neighbors_in_rooms():
                if neighbor.path_distance is None:
                    neighbor.path_distance = cell.path_distance + 1

I take the time to look for the other places who could use this method. Found, changed, each goes red during editing and then back to green. Commit: use new generate_in_rooms

One last check, I think there might be other uses of generate that can be converted, so I search them all out. There are none using is_in_a_room but there are two that use is_available. That’s not on our present course, so I’ll just make a note and maybe fix them later.

Reflection

We now have the ability to associate with each cell its distance along existing paths from some given cell. We propose to use that to find a cell that is maximally distant from the given cell.

Along the way, we refactored a bit to make the code a bit better over in Cell, and that allowed us to notice the duplication of generate with the is_in_a_room lambda, so we provided a method and simplified five occurrences of that generate.

It’s small quick improvements like this that keep the code alive, and I don’t mind saying that making the code a bit better gives me a little jolt of happiness. I enjoy doing good work.

Unlike an LLM, which really doesn’t care if it does good work, or even correct work. But I digress.

What’s Next?

We are here to find a cell whose distance from a given cell is maximized. We have, in each Cell, its distance from the given cell. We do not know the maximum value, and we do not know which cells have that value. The result we want it any of the cells with the maximum value. It would be mice to do that with no more than one more pass over the cells.

I think it would help if we return the maximum value from our new generate function.

Here’s our current test:

    def test_max_path_distance(self):
        layout = DungeonLayout()
        Cell.create_space(5, 5)
        map = '''
        11111
        '''
        layout.add_rooms_from_map(map)
        given = Cell.at(0,0)
        given.generate_path_distances()
        for x in range(5):
            assert Cell.at(x,0).path_distance == x

Let’s call for the max to be returned:

        max_distance = given.generate_path_distances()
        assert max_distance == 4

Fails of course. We modify:

    def generate_path_distances(self) -> int:
        self._clear_path_distances()
        return self._compute_path_distances()

    def _compute_path_distances(self) -> int:
        self.path_distance = 0
        max_distance = 0
        for cell in self.generate_in_rooms():
            for neighbor in cell.neighbors_in_rooms():
                if neighbor.path_distance is None:
                    one_further = cell.path_distance + 1
                    neighbor.path_distance = one_further
                    if one_further > max_distance:
                        max_distance = one_further
        return max_distance

Green. Commit: generate_path_distances returns maximum distance set

OK, now we need to test-drive the method that finds all the max-distance cells. Let’s write a new test:

    def test_max_distance_cells(self):
        layout = DungeonLayout()
        Cell.create_space(5, 5)
        map = '''
        ..1..
        ..1..
        11111
        ..1..
        ..1..
        '''
        layout.add_rooms_from_map(map)
        given = Cell.at(2,2)
        max_cells = given.furthest_cells()
        assert len(max_cells) == 4
        max_xy = [c.xy for c in max_cells]
        assert (2,0) in max_xy
        assert (2,4) in max_xy
        assert (0,2) in max_xy
        assert (4,2) in max_xy

Notice that this time I’m doing “wishful thinking” and asking Cell to have a new method furthest_cslls. Turns out it doesn’t, so this test is red.

This works, but I don’t love it:

    def furthest_cells(self):
        max_distance = self._compute_path_distances()
        return [cell 
            for cell in self.space.cells 
            if cell.path_distance == max_distance]

We’re green, though, so let’s commit: Cell:furthest_cells

Reflection

What don’t I like about that little method? Two things. First, it is ripping the cells out of the space and iterating them, which is currently somewhat legitimate but somewhat not in the spirit of good design. Second, we’re not limiting the search to cells in rooms. There could conceivably be cells in the space with distances defined and equal to the max. Very unlikely but possible. Let’s get that last bit in there anyway:

    def furthest_cells(self):
        max_distance = self._compute_path_distances()
        return [cell
                for cell in self.space.cells
                if cell.is_in_a_room \
                and cell.path_distance == max_distance]

Commit again: bullet-proofing.

Reflection

Again today, I am reminded of the suggestion from Adrien Foucart on Mastodon, pointing out that one could use a dictionary kind of thing to have only cells that are actually in use. This is at least the third time that — I believe — that design would have made my job easier. It might well be time to look at making that change. It would essentially mean that the default situation is that if we have a Cell it is in fact in a room. We’d have to do something a bit special to get unallocated cells, but that probably won’t be a big issue.

Summary

Despite the fact that we only have one tiny step to take, randomly choosing one of our furthest cells, I think it’s time to stop for the morning. Take a little nourishment, have a nice iced chai, read some ultra-violent book. (Currently re-reading Neal Asher’s Ian Cormac series.)

In any case, we are one choice away from having the answer we want, though we’ll have to wire it into DungeonLayout or wherever we decide it belongs. And all has gone quite smoothly. We did things in two distinct ways:

Way 1 was to write the code we needed longhand inside a test method. When I have an algorithm in mind, I often do that. Then once we have the code, we extract it into one or more methods, still in the test, and then manually move them over to the target class. PyCharm isn’t quite smart enough to do that last step for us but it generally consists of removing a parameter and replacing its mentions with self. I think we used Way 1 twice in the current series.

Way 2 is what Kent Beck called “programming by intention” and what I have come to call “wishful thinking”. We write, in our test, the call that we wish we could make, to the object we wish could help us. We get an error, of course, and then we go over to the class in question and implement the method. I tend to use wishful thinking when I have a pretty good idea of how to do the method. But I don’t follow a hard and fast rule that could be stated. I just do what feels right: either one will generally work fine.

One particularly good move today, mentioned above already, was to revert when the changes I was making didn’t look as good in place as I had expected, so we backed up and went a different way. This is a practice that I think I’d do well to do more of detecting early on that the code isn’t quite the thing and stepping back to choose a different path.

It’s good to know that I can still think of a way to improve: it’s clear that I’m not perfect, so without any ways to improve I guess I’d just have to give up.

Never give up: there’s always a way to do better, and it feels good to do better.

Today, a couple of nice steps forward. Very pleasant.

See you next time!