Cleaning up Cell fixed a big design issue. Now we are left with a smaller one. We’ll see what we can do about that.

While you weren’t watching, I did a bit of work, changing this:

class DungeonLayout:   
    def is_available(self, cell) -> bool:
        return self.xy_is_available(cell.xy)

    def is_in_a_room(self, cell) -> bool:
        return self.xy_is_in_a_room(cell.xy)

    def xy_is_available(self, xy):
        return not self.xy_is_in_a_room(xy)

    def xy_is_in_a_room(self, xy):
        cell = self.at(*xy)
        return any([cell in room for room in self.rooms])

    def get_room(self, cell):
        for room in self.rooms:
            if cell in room:
                return room
        return None

To this:

class DungeonLayout:
    def is_available(self, cell) -> bool:
        return not self.is_in_a_room(cell)

    def is_in_a_room(self, cell) -> bool:
        return self.get_room(cell) is not None

    def get_room(self, cell) -> Room|None:
        for room in self.rooms:
            if cell in room:
                return room
        return None

I decided that having both the xy form and the Cell form wasn’t helping. Instead, one always had to decide which to use. Better to have one way and avoid the cognitive load of remembering more methods and choosing between them.

Design Issues

Looking at this code raised some design issues in my mind. Let us reason together:

It is, of course, slightly irritating that we have to search all the rooms to decide which one has the given cell, and — this may not be obvious — we are not protected from more than one room “having” a given cell. A Room is now little more than a set of cells:

class Room:
    def __init__(self, cells, name=''):
        self._cells:set[Cell] = set(cells)
        self.name = name
        self.color = "grey22"

Both name and color are only there to allow us to identify rooms in prints and tests, and the color is only there to allow us to color a given room differently on screen, again for debugging purposes. So, if something were to go awry, we could easily wind up with the same cells in more than one room.

It gets worse more odd

Since a Room holds Cell instances, and since cells are now just coordinates, a Room is not bound to any particular DungeonLayout. It joins a layout only when we tell a layout to add it:

class DungeonLayout;
    def __init__(self, max_x=10, max_y=10):
        self.cells = dict()
        for x in range(max_x):
            for y in range(max_y):
                self.cells[(x,y)] = Cell(x, y)
        self.rooms = []

    def add_room(self, room):
        self.rooms.append(room)

    def remove_room(self, room):
        self.rooms.remove(room)

We do not check the cells in any way whatsoever. In principle, we could add a room all of whose cells were outside the alleged dimensions of the layout. I’m rather sure that that would be bad.

Now, it is my general practice not to write much defensive code, instead relying on my tests to ensure that things are being done right. I’ll be more defensive on the periphery, user input or APIs, but not internally. If my code were intended for a real product, I might be a bit more defensive, but as things stand, explanations and examples go better without all those fences.

However, the “good” design idea of removing back pointers from Cell has led to the Cell being an abstract coordinate kind of thing, and to the Room being a collection of those, and the Layout having a collection of those … and a separate collection of Cell instances which may be the same as the ones in a Room — will be, if we do things right — but might be coordinates originally assigned from other Layouts.

Even more odd is the fact that there is a specially-created room in our test dungeon in main, a diamond room inside a round room:

map showing small diamond room inside round room

That’s created with some very “special” code:

main.py
def make_diamond_in_round_room(layout: DungeonLayout, maker: RoomMaker):
    origin = layout.at(32, 28)
    diamond = maker.diamond(number_of_cells=13, origin=origin)
    round = maker.round(radius=5, origin=origin)
    diamond.reclaim_cells_from(round)
    layout.add_room(diamond)
    layout.add_room(round)

class Room:
    def reclaim_cells_from(self, other):
        for cell in self._cells:
            other.forget(cell)

    def forget(self, cell):
        self._cells.remove(cell)

We make the diamond room, allocating that little cross of cells. We do not add it to the layout. Then we create the round room, allocating the entire round area around the diamond, and do not add it to the layout.

Then we go through the diamond’s list of cells, telling the round room to forget them. The result is a round room with a hole in it where the diamond room is. Neither room is in the layout. Then we add them to the layout.

Aside:
I think we could do this more simply, since the _cells are sets. I’ll make a note of that.

On the one hand, this is rather nifty. On the other hand, if it were to be done incorrectly, we could have the same cell in more than one room and that would certainly not be what we have in mind and might be very bad: it’s hard to know.

But it gets even more odd. Since all we care about in Cell is xy, what is the point of having a collection of them in the Layout? We do use the at method to get a cell, but what if we just created a new one instead?

We are fully committed just now. I think I’ll just try that. With just a few changes, all the tests pass:

class DungeonLayout:
class DungeonLayout:
    deltas = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    def __init__(self, max_x=10, max_y=10):
        self._max_x = max_x
        self._max_y = max_y
        self.rooms = []

    def at(self, x, y):
        return self.at_xy((x,y))

    def at_xy(self, xy):
        x, y = xy
        if 0 <= x < self._max_x and 0 <= y < self._max_y:
            return Cell(x, y)
        else:
            return None

    @property
    def cells(self):
        for x in range(0, self._max_x):
            for y in range(0, self._max_y):
                yield self.at(x, y)

    def unused_cell_or_none(self):
        available = [cell for cell in self.cells if self.is_available(cell)]
        if available:
            return random.choice(available)
        else:
            return None

class Cell:
    def __eq__(self, other):
        return self._xy == other._xy
    def __hash__(self):
        return hash(self._xy)

Since we create new Cell instances all the time, we had to add __eq__ and __hash__ to Cell, and a few tests needed to change from cell_a is cell_b to use ==.

What the …?

Aside:
I just realized that in the old comic books I used to read in my youth, when a character said “what the …”, they had a word in mind after “the”. At the time I was too naive to know what that word even was. I thought they just said “what the”. But I digress.

As I was saying, “What the …”. We have just removed a large array of Cell instances, instead creating Cells when we need one and tossing then away when we don’t love them any more. Is this a good change, or a bad one?

The main argument against is that we’ll be creating and destroying many more Cells, with impact on the memory management. How many? Let’s find out. A quick print informs me that it is millions, because, of course, we are drawing the Dungeon 60 times a second and we therefore create and destroy about twelve million cells per minute.

I think we’ll belay that change and continue to save our Cell instances in an array, on the grounds that twelve million dictionary accesses is probably better than twelve million object creations and deletions.

Still odd, though …

We still have our central issue of the morning, which is that since Rooms can exist without being in a Layout, Rooms can easily be created with cells shared between them, and this is not something we want.

I have a tentative idea. We clearly do not want to raise an exception when two rooms collide. We can’t crash the program. But we do not want any two rooms to contain the same cell. So what if, as we add a room to the layout, we verify each cell as being available, and if it is not, we tell the room to forget that cell. First come, first served.

I think that makes some sense. We might want to check the room, after the check is done, to see if it has zero cells but we’ll see if that’s even necessary.

I have a test for the diamond within round algorithm, let’s see if we can change it to handle this new idea:

    def test_diamond_in_round(self):
        layout = DungeonLayout(64, 56)
        maker = RoomMaker(layout)
        origin = layout.at(32, 28)
        diamond = maker.diamond(number_of_cells=13, origin=origin, name='diamond')
        diamond_cells = diamond.cells.copy()
        round = maker.round(radius=5, origin=origin, name='round')
        diamond.reclaim_cells_from(round)
        layout.add_room(diamond)
        layout.add_room(round)
        assert len(diamond_cells) == len(diamond.cells)
        for cell in diamond_cells:
            assert cell in diamond.cells
            assert cell not in round.cells
        for cell in round.cells:
            assert cell not in diamond.cells

When this idea works, we can remove the reclaim_cells call (and method), because adding the diamond first gives it its cells and the round room will have them forgotten by the new code we’re about to write. So remove that line and have the test fail. It does. Now in DungeonLayout, we have add_room:

    def add_room(self, room):
        self.rooms.append(room)

We want to limit the incoming room to available cells, so, Wishful Thinking:

    def add_room(self, room):
        self._limit_to_available(room)
        self.rooms.append(room)

And then we code:

    def _limit_to_available(self, room):
        for cell in room.cells.copy():
            if self.is_in_a_room(cell):
                room.forget(cell)

Our test passes. We have correctly limited the round room not to include the diamond room’s already-allocated cells. We can change how main works, and remove the reclaim method.

Green. Commit: Rooms added to layout only retain available cells. Allows construction of rooms containing other rooms: caveat emptor.

Summary

We have simplified Room, and allowed for creation of rooms that overlap others without containing duplicate cells, more easily than we could before (via reclaim, now no longer needed). Layout creation is now safer, in that we ensure that rooms do not overlap as we add them.

We experimented with not creating the array of cells, and determined that it can readily be made to work but that the naive implementation results in creation and destruction of literally millions of cells per minute of display time. Probably not what we want.

However … we could probably arrange to allocate Cells only when first added to a room, if we were to change the way we display the Dungeon. If we iterated, not across the cell array, but through the rooms, we would access only existing cells instead of thrashing about creating and destroying them. Something to consider. Dr Ian Malcolm once advised me to consider whether I should do things, not just whether I could do them, and we’ll keep that in mind as we go forward.

As an experiment, however, it showed that the Layout / Room / Cell objects are pretty well separated, with all the things we care about being handled in just one place, and that place seeming right. The easy of making that rather substantial change gives me confidence that we’re on the right track in moving things up toward the Layout, away from the Cell.

Same with the overlap discovery: it all came down to one simple method. The only tricky bit was that we did need to copy the cell collection, since we are modifying it on the fly. There were at least two other ways to do that, but that’s the one I picked.

So, some learning, some improvement. Now for some Chai and a granola bar. See you next time!