I want to complete the path finding, and I think some of these objects would appreciate being better designed. Includes: a Great Lie wasn’t … this time.

I try to think about design all the time, although I am easily distracted.

shiny squirrel, most distracting object in the universe

What could be more distracting than a shiny squirrel?

Nonetheless, there are some current issues and upcoming issues that make me think we could use a little design improvement, including:

Cell
Our representation of a square in the map, or its coordinates, is just a base tuple, which by convention contains the x coordinate followed by the y. We’re continually splitting these into components, doing arithmetic on the bits, and so on. We almost certainly will benefit from a Cell class or Coordinates class. I think Cell.
in
Our CellBank is really little more than a slightly intelligent set of cells. In Python we can generally use the in syntax to determine whether something is in a collection. It would be more Pythonic, I think, to have that facility instead of our current awkward has_cell method.
Room = CellBank?
A Room is, among other things, a set of cells. It has a bit more capability on top of what a CellBank might have, in that it can grow itself. And it has a color. In our implementation of paths, we are going to want to accept cells that are in the bank … but also cells that are in the rooms we are trying to connect. So we might find it useful if Room had CellBank behavior. It might be a subclass or contain a CellBank.
Path
A path just now is just a collection of cells. It seems likely that there is an object hiding here. And we’ll surely want a PathView object to paint the paths.
General Considerations
A bit of mostly received wisdom that I have is that inheriting from system collections is undesirable, if only because that results in a very wide set of methods that pop up, tempting us, and our particular kind of collection probably has constraints or policies that make that dangerous.

My betters, and experience, tell me that inheritance of concrete classes is generally problematic and that it’s usually better to use has-a rather than is-a.

Let’s get to it. Let’s start with a Cell class, since that one has been popping up in my mind since almost the very beginning of this little project.

Cell Class

I’m tempted to just start changing things to refer to a new class, Cell, and then fix everything up, but that seems a bit chaotic. Let’s do at least a few tests. I think it’ll pay off, because there are some features of Cell that really deserve to have a test.

class TestCell:
    def test_cell(self):
        assert False

Unsurprisingly, this fails. Let’s make it fail better.

class TestCell:
    def test_cell(self):
        cell = Cell(2,3)
        assert cell.x == 2
        assert cell.y == 3

PyCharm would like to create a class. So would I.

class Cell:
    def __init__(self, x, y):
        self.x = x
        self.y = y

Green. Commit: initial Cell class.

I think the most important aspects of our new object include, but are not limited to:

  • can be used in a set, for CellBank
  • can behave as a tuple, so that code can say x,y = cell

I don’t really know for sure how to do either of those. I have a guess at the second one, so let’s write that test first:

    def test_unwrap(self):
        cell = Cell(2,3)
>       x,y = cell
        ^^^
E       TypeError: cannot unpack non-iterable Cell object

I think we “just” need to implement iter. I’ll try that and if that doesn’t work, I’ll see what the Internet thinks.

class Cell:

    def __iter__(self):
        return iter([self.x, self.y])

PyCharm suggested the return statement. I was going to use a tuple. List should be fine.

Now what about using it in a set?

    def test_set(self):
        cell = Cell(2,3)
        s = set()
        s.add(cell)
        assert cell in s
        cell2 = Cell(2,3)
        s.add(cell2)
        assert len(s) == 1

This fails with two Cells in the set. Not OK. We want all cells with the same integers to be the same.

We have to implement __eq__ and __hash__. This should suffice:

    def __eq__(self, other):
        if isinstance(other, Cell):
            return self.x == other.x and self.y == other.y
        return False
    
    def __hash__(self):
        return hash((self.x, self.y))

I was going to do exactly that, but PyCharm prompted most of it. Amazing. And I still have not, and will not, turn on its “AI” feature. I expect green. I get it. Commit: Cell is hashable and iterable. Move Cell to its own file under ‘src’. Test, commit again.

What now? I think it’s time to use Cell in CellBank. I think we’ll just try this and see how badly things break. If it’s too awful, we’ll do something else. Here’s CellBank … it’s pretty simple just now:

class CellBank:
    def __init__(self, max_x, max_y):
        self.cells = set()
        for x in range(max_x):
            for y in range(max_y):
                self.cells.add((x,y))

    def has_cell(self, x, y):
        return True if (x, y) in self.cells else False

    def take(self, x, y):
        self.cells.discard((x, y))

Hm. This makes me want to look at the users of has_cell and take to see what they are up to.

class Room:
    def build(self, bank, length, start_cell):
        new_cell = start_cell
        for _ in range(length):
            bank.take(*new_cell)
            self.add_cell(*new_cell)
            new_cell = self.find_adjacent_cell(bank)
            if new_cell is None:
                return

    def find_adjacent_cell(self, bank):
        for cell in sample(self.cells, len(self.cells)):
            neighbors = self.neighbors(cell)
            for x, y in sample(neighbors, len(neighbors)):
                if bank.has_cell(x, y):
                    return x,y
        return None

    @staticmethod
    def neighbors(pair):
        x, y = pair
        return [(x+dx,y+dy) for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]]

OK, it’s pretty clear that we don’t care about x and y in the find... method, and that it would be nice if Cell could produce neighbors.

Let’s first change neighbors to use Cell to get the neighbors, and return them as Cells. This may be too much, but I am hopeful.

PyCharm seems to understand what I’m trying to do, and we quickly get this:

    @staticmethod
    def neighbors(pair):
        cell = Cell.from_tuple(pair)
        return cell.neighbors

We’ll probably wind up inlining that method soon. Now in Cell, PyCharm offered this, which I agree with:

    @classmethod
    def from_tuple(cls, pair):
        return cls(*pair)

Now we need neighbors, a property.

    @property
    def neighbors(self):
        deltas = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        neighbors = []
        for dx, dy in deltas:
            neighbors.append(Cell(self.x + dx, self.y + dy))
        return neighbors

That will do for now, we’ve changed ten or fifteen lines already, it’s time to see how much trouble we’re in.

The tests all run. I am not comfortable with this. Turn on main to see if it explodes. It does not. I will commit this, since it works, but then I want to examine why it works. Commit: neighbors produces Cells.

Ah!

    def find_adjacent_cell(self, bank):
        for cell in sample(self.cells, len(self.cells)):
            neighbors = self.neighbors(cell)
            for x, y in sample(neighbors, len(neighbors)):
                if bank.has_cell(x, y):
                    return x,y
        return None

We unwrap the Cells, so no harm done. What if we changed add_cell in Room:

class Room:
    def __init__(self):
        self.cells:list[tuple[int, int]] = []
        r = random.randint(0, 255)
        g = random.randint(0, 255)
        b = random.randint(0, 255)
        self.color = pygame.Color(r, g, b)

    def add_cell(self, x, y):
        self.cells.append((x,y))

Now the cells member in Room is presently a list of tuples. Let’s make it a list of Cells.

class Room:
    def __init__(self):
        self.cells:list[Cell] = []
        r = random.randint(0, 255)
        g = random.randint(0, 255)
        b = random.randint(0, 255)
        self.color = pygame.Color(r, g, b)

    def add_cell(self, x, y):
        self.cells.append(Cell(x,y))

Test to see what else needs touching. test_build breaks, in verification:

~~~python def verify_contiguous(self, room): start = room.cells[0] cell_set = set(room.cells) self.remove_cell_and_neighbors(start, cell_set)

  assert len(cell_set) == 0 E       assert 99 == 0 E        +  where 99 = len({<cell.Cell object at 0x1041c2ea0>, ... ~~~

What’s that remove method?

    def verify_contiguous(self, room):
        start = room.cells[0]
        cell_set = set(room.cells)
        self.remove_cell_and_neighbors(start, cell_set)
        assert len(cell_set) == 0

    def remove_cell_and_neighbors(self, cell, cell_set):
        cell_set.remove(cell)
        self.remove_neighbors(cell, cell_set)

    def remove_neighbors(self, cell, cell_set):
        x, y = cell
        neighbors = [(x-1,y), (x+1,y), (x,y-1), (x,y+1)]
        for neighbor in neighbors:
            if neighbor in cell_set:
                self.remove_cell_and_neighbors(neighbor, cell_set)

I think we need to make neighbors into Cells there in the last method.

    def remove_neighbors(self, cell, cell_set):
        neighbors = cell.neighbors
        for neighbor in neighbors:
            if neighbor in cell_set:
                self.remove_cell_and_neighbors(neighbor, cell_set)

Green. Commit: incrementally using Cells in Room.

Reflection

That last move was a risky one. Fortunately only one test broke and its correction makes sense: if we’re saving Cells, we need to test with Cells. However, it was possible that that change would have broken lots of things. If so, we’d have rolled back and looked for a simpler change to make.

There are, I suspect, two reasons why we just had to adjust a test. First, the program is still small, so there isn’t all that much that is sensitive to whether we have a tuple or a cell. Second, the design is fairly consistent, even though we are flinging tuples around a lot. We have implemented Cell so that it mostly behaves like a tuple, so we should, if luck continues, find that most things continue to work, and the rest are straightforward substitutions of Cells.

If that doesn’t happen—and it might not—we’ll be ready to roll back and take another path.

What’s next?

class Room:
    def find_adjacent_cell(self, bank):
        for cell in sample(self.cells, len(self.cells)):
            neighbors = self.neighbors(cell)
            for x, y in sample(neighbors, len(neighbors)):
                if bank.has_cell(x, y):
                    return x,y
        return None

I’d like to be able to say this, so I’ll say it and then see about making it work:

    def find_adjacent_cell(self, bank):
        for cell in sample(self.cells, len(self.cells)):
            neighbors = self.neighbors(cell)
            for neighbor in sample(neighbors, len(neighbors)):
                if neighbor in bank:
                    return neighbor
        return None

There are two issues here: make sure CellBank understands in, and then make sure that users of this function can accept a Cell coming back. We should get an iteration error for our use of in.

            for neighbor in sample(neighbors, len(neighbors)):
>               if neighbor in bank:
                   ^^^^^^^^^^^^^^^^
E               TypeError: argument of type 'CellBank' is not iterable

Sure enough. We know the drill. Er … these changes are more extensive than I like. We’ll see:

class CellBank:
    def __init__(self, max_x, max_y):
        self.cells = set()
        for x in range(max_x):
            for y in range(max_y):
                self.cells.add(Cell(x,y))
                
    def __iter__(self):
        return iter(self.cells)

    def has_cell(self, x, y):
        return Cell(x,y) in self

    def take(self, x, y):
        self.cells.discard(Cell(x, y))

I implemented __iter__ but also changed all the other methods to use Cell. That seems like a lot, four or five lines. Test. We are green but the main does fail:

~~~python def draw_colored_cell(self, cell, screen):

  dx = cell[0] * cell_size
         ^^^^^^^ E       TypeError: 'Cell' object is not subscriptable ~~~

That’ll be in DungeonView, I reckon. and we can use .x now. I find and fix those but now find_path is failing:

        while start is not None:
            path.append(start)
>           start = self.reached[start]
                    ^^^^^^^^^^^^^^^^^^^
E           KeyError: (63, 55)

PathFinder needs an upgrade. I am hopeful that it’ll be easy: a roll back is possible but I’d rather not.

Looking at this much …

class PathFinder:
    def __init__(self, bank):
        self.bank = bank
        self.queue = []
        self.reached = dict()

    def find_path(self, source, target):
        self.put(source, None)
        self.flood()
        path = []
        start = target
        while start is not None:
            path.append(start)
            start = self.reached[start]
        return path

Since bank is a CellBank, containing Cells, we should use Cells here. Let’s do some type hinting:

class PathFinder:
    def __init__(self, bank):
        self.bank = bank
        self.queue: list[Cell] = []
        self.reached: dict[Cell, Cell] = dict()

    def find_path(self, source: Cell, target: Cell) -> list[Cell]:
        self.put(source, None)
        self.flood()
        path = []
        start = target
        while start is not None:
            path.append(start)
            start = self.reached[start]
        return path

I think that’s right. Find senders of find_path and ensure that they are using Cells.

I fix up this test:

    @staticmethod
    def manhattan(source, target):
        return abs(source.x - target.x) + abs(source.y - target.y)

    def test_path(self):
        bank = CellBank(10, 10)
        finder = PathFinder(bank)
        source = Cell(3,3)
        target = Cell(7,6)
        dist = self.manhattan(source, target)
        assert dist == 7
        path = finder.find_path(source, target)
        assert len(path) == dist + 1
        assert path[0] == target
        assert path[-1] == source
        distance = sum(self.manhattan(s1, s2) for s1, s2 in pairwise(path))
        assert distance == dist

And make a note to put manhattan on Cell. There’s another caller:

class Dungeon:
    def find_path(self, start: Cell, end: Cell, bank: CellBank):
        finder = PathFinder(bank)
        self.path = finder.find_path(start, end)

And callers of find_path?

def main():
    bank = CellBank(64, 56)
    # random.seed(234)
    dungeon = Dungeon()
    number_of_rooms = random.randint(10, 10)
    for _ in range(number_of_rooms):
        room = Room()
        size = random.randint(60, 90)
        x, y = random_available_cell(bank)
        room.build(bank, size, (x,y))
        dungeon.add_room(room)
    dungeon.find_path(Cell(0,0), Cell(63,55), bank)
    view = DungeonView(dungeon)
    view.main_loop()

Let’s see what we get now. I’m getting nervous. Still the same error:

        while start is not None:
            path.append(start)
>           start = self.reached[start]
                    ^^^^^^^^^^^^^^^^^^^
E           KeyError: <cell.Cell object at 0x105fa6ab0>

What are we putting into reached? Ah:

class PathFinder:
    def expand(self):
        reached = self.reached
        cx, cy = self.queue.pop(0)
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            tx = cx + dx
            ty = cy + dy
            txy = (tx, ty)
            if txy not in reached and self.bank.has_cell(tx, ty):
                self.put(txy, (cx,cy))

That won’t do at all. Try this:

    def expand(self):
        reached = self.reached
        next_cell = self.queue.pop(0)
        for neighbor in next_cell.neighbors:
            if neighbor not in reached and neighbor in self.bank:
                self.put(neighbor, next_cell)

I am increasingly nervous. But we’ll follow the tests a bit longer.

There are just a few tests that do need fixing up, but the message shown above isn’t our problem. It occurs when there is no path from the top left to the bottom right.

I changed the subscripting to a get to avoid the exception:

    def find_path(self, source: Cell, target: Cell) -> list[Cell]:
        self.put(source, None)
        self.flood()
        path = []
        start = target
        while start is not None:
            path.append(start)
            start = self.reached.get(start)
        return path

The get will return None if there is no such key and the path will be truncated. Since we start at the target end, and it is never reached, we see just a single dot in the lower right corner. We’ll see whether we want to do something different … later.

map with red square on bottom right

Note the red dot.

Well past time for my iced chai. Let me sum up for now. Oh and commit: conversion to Cell in progress.

Summary

Our changes touched almost every file. This should be no surprise, as Cells are interesting most everywhere. For most of the commits, there were just a few changes and then we were back to green. In this last phase with the path, I was thrown off by the dictionary error, which wasn’t due to the changes we were making.

Note
“The changes I made couldn’t have affected that” is one of the great lies of programming, so I always assume that when I make changes and something breaks, I broke it. This time, it wasn’t a lie, and it took me a bit of time to see that, but there were other tests breaking and I fixed those as I went, finally realizing what was going on.

It did get a big ragged there, and the changes needed make me think that things aren’t quite right in the way the tests interface to the objects. There are references to the [0] and [1] elements of tuples in the tests and that’s nasty. We’ll want to deal with that next time.

We’ve already seen code get simpler with use of Cell, such as replacing has_cell calls with the more expressive in, and in use of the neighbors method on Cell:

    def expand(self):
        reached = self.reached
        next_cell = self.queue.pop(0)
        for neighbor in next_cell.neighbors:
            if neighbor not in reached and neighbor in self.bank:
                self.put(neighbor, next_cell)

That used to look like this:

    def expand(self):
        reached = self.reached
        cx, cy = self.queue.pop(0)
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            tx = cx + dx
            ty = cy + dy
            txy = (tx, ty)
            if txy not in reached and self.bank.has_cell(tx, ty):
                self.put(txy, (cx,cy))

So things are better. A bit ragged there at the end. Maybe there was a smaller step but despite some wobbling, things sorted out quickly enough.

The code is better, and that was the point. If there’s a lesson here, it might be that making the Cell class the first time I thought of it might have saved a lot of changes today. One doesn’t want to move too quickly to creating classes, but that one was pretty clear.

Live and relearn and relearn and relearn. We’re always trying to find the balance, and it’s no longer a surprise to me when I go a little too far or not quite far enough. I’m always pleased to have good tests and we’re in pretty good shape there. I don’t think there were any issues that weren’t caught by tests or the compiler. Perfect.

See you next time!