Adjacent Rooms

Thinking about how we could detect rooms that are adjacent. Warning: contains Philosophy of Programming as this old guy does it.

Saturday Afternoon

I’m in an online meeting that doesn’t seem to need all my attention, so let’s think about adjacency a bit.

As part of connecting rooms, I’d like to know when rooms are adjacent. How might we determine that?

Rooms now have that periphery member, consisting of all the cells that have not yet been shown to be interior (although some of them may be: we don’t remove them from periphery until we try them for room expansion).

What might we want to have? Something like a dictionary of adjacent rooms to this one, pointing to all the cells that are adjacent? Then we’d iterate the rooms, finding adjacent borders. Maybe keep track of the direction / directions of connection. A given cell in one room could have as many as three border cells in common with another room. Think of a single cell jutting out from the room’s border.)

Something like:

class Room:
def find_adjacent_rooms(self):
    for cell in self.periphery:
        adjacent = cell.cells_in_adjacent_rooms()
        for adjacent_cell in adjacent:
            self.adjacents[cell].append(adjacent_cell)

Not quite like that. Roughly the right shape but need to consider what result we actually want, how we’re going to use it.

Something like this:

For each adjacent room, identify at least one pair of adjacent cells and mark them as a connection. (Both rooms should have that same connection.) Use the connections to define open passages, visible doors, lockable doors, secret doors, whatever kind of connections there might be.

So perhaps this logic resides in the Dungeon class somehow, generating a list of border cells and then picking one (or more) from each discrete border to mark as a connection.

It seems that there should be a “simple” set operation to do this. Needs more cogitation.

Sunday

My thoughts above were interrupted when it became necessary to pay attention to the meeting. Such is life. Last night, I did a little thinking and sketched this page:

I wouldn’t recommend trying to read my scribbling, but what is on that page is some sketches of a room-adjacency situation, an idea for a data structure defining where a door might go ((room1,direction1),(room2,direction2)), a sketch of the code we might have in Dungeon, Room, and Cell to find doors, and a red note saying “Double Dispatch”, which is there to remind me to consider, when processing a cell from Room 1, not to interrogate details about a neighboring cell, but to send it a message asking it what we want to know.

Diversion: Programming Philosophy¹

It is tempting, always, when dealing with some object we have access to, to pull out its member variables and inspect them. I do that far too often. It is better, almost always, to improve that other object so that it can answer whatever question we are trying to resolve over in the first object.

If we do the work in the first object, we do often avoid changing the second one at the same time as we change the first, and that feels right. But the effect is that we have, in our first object, code that is actually very much about the second, and when we repeat this practice over and over, we wind up with code in many objects that is tightly bound to the specific structure of the second one. That makes it difficult, often impossible to improve that second object, because people are relying on its intimate details.

There is much advice out there, telling us to improve the second object rather than rip its guts out and examine them: the Law of Demeter² and “Tell, don’t ask” are two popular angles. In the particular case of an object of type T inspecting another object of type T, sending the second one a message instead of inspecting it is often called “Double Dispatch”, and it is Chet Hendrickson’s favorite technique. We see double dispatch often in implementing arithmetic or similar operations where when an object of type T receives plus(another), it sends plus_with_t(self) to the other, which now knows the type of both operands and can thus do the right thing.

I wrote “double dispatch” on the sheet in the hope of remembering not to spend too much time looking at the object that I’m not processing. But I digress.

Be all that as it may, I spent some time yesterday thinking about how to determine where rooms are adjacent, and thus where doors might go. There are additional concerns, not on that scribbled page, including but not limited to:

1. Determining the borders around rooms seems to me to be a similar problem to determining adjacency. We should look at that code and see if it gives us any ideas.
2. I’m sure that the border code predates the periphery, so it can probably be improved by using that smaller collection of room cells.
3. Cells know that they are not owned by the CellBank, but they do not know the object that owns them: it’s just that they init with owner==space and when taken, they clear owner. We will need them to know their owner for doors to work.
4. Paths will also need doors. Are paths just a weird kind of room?
5. We won’t know what paths are needed until we have determined the “continents” made up of adjacent rooms, so that we can draw paths between the continents.But if paths get doors, we need the paths first. Or maybe paths create doors as part of their construction.
6. We might want paths between rooms in a continent, just for interest or shortcuts or something. How would that be handled?

Isn’t it wonderful? We are nowhere near running out of things to work on. I’m sure there are more. That’s fine: we are in the business of changing code.

Let’s look at how the room boundaries are drawn. That’s just done in a view, there is no boundary structure. We have seen this before, didn’t love it then, don’t love it now:

    def draw(self, screen):
        cells = set(self.room.cells)
        for cell in cells:
            self.draw_colored_cell(cell, screen)
            self.draw_border(cell, cells, screen)

    def draw_border(self, cell, cells, screen):
        x, y = cell
        cx0 = cell.x*cell_size
        cy0 = cell.y*cell_size
        cx1 = cx0 + cell_size
        cy1 = cy0 + cell_size
        neighbor_count = 0
        for neighbor in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            dx, dy = neighbor
            n_x = x + dx
            n_y = y + dy
            check = self.room.cell_at(n_x, n_y)
            if check not in cells:
                neighbor_count += 1
                if neighbor == (0,1):
                    #bottom
                    self.line(cx0, cy1, cx1, cy1, screen)
                elif neighbor == (0,-1):
                    #top
                    self.line(cx0, cy0, cx1, cy0, screen)
                elif neighbor == (-1,0):
                    #left
                    self.line(cx0, cy0, cx0, cy1, screen)
                elif neighbor == (1,0):
                    #right
                    self.line(cx1, cy0, cx1, cy1, screen)

Note

A curious thing happens here. I think I’m not going to refactor this code. In reviewing it, ideas start to bubble up for improving it. As you’ll see below, this thing I didn’t intend to do results in some small but nice improvements to the whole scheme of things.

We could refactor that a bit for clarity but I’m not sure it would help. We spent some time on that an couple of articles back, if I recall, and didn’t find anything great. One thing that might help, in view of the discussion above, would be to ask the cell to draw its border instead of doing it at the room level. We’re not really here with that in mind but it is worth considering, because determining the border seems to me to be quite like determining where doors go: the border goes on any side that leads outside the room, and a door goes on any side that leads outside the room to another room.

Hm. Tempted to make the border different between rooms than it is between rooms and space. Might lead to some learning.

But first, let’s use the periphery to see what happens there.

    def draw(self, screen):
        cells = set(self.room.cells)
        periphery = self.room.periphery
        for cell in cells:
            self.draw_colored_cell(cell, screen)
        for cell in periphery:
            self.draw_border(cell, cells, screen)

That should be all we need.

Unpleasant Discovery

My periphery theory does not hold water. When I draw borders only on cells that are in the periphery, we see missing borders:

When we loop over all cells, we do not:

Ah. My mistake is that the periphery does not contain cells that cannot grow, i.e. cells that we discover are completely surrounded. So, randomly, some border cells that have neighbors in other rooms will get culled. My bad. Undo that change.

It’s Sunday, so I have bacon to consider but let’s look at that border code with the remarks above in mind, about the Law of Demeter and all that.

    def draw_border(self, cell, cells, screen):
        x, y = cell
        cx0 = cell.x*cell_size
        cy0 = cell.y*cell_size
        cx1 = cx0 + cell_size
        cy1 = cy0 + cell_size
        neighbor_count = 0
        for neighbor in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            dx, dy = neighbor
            n_x = x + dx
            n_y = y + dy
            check = self.room.cell_at(n_x, n_y)
            if check not in cells:
                neighbor_count += 1
                if neighbor == (0,1):
                    #bottom
                    self.line(cx0, cy1, cx1, cy1, screen)
                elif neighbor == (0,-1):
                    #top
                    self.line(cx0, cy0, cx1, cy0, screen)
                elif neighbor == (-1,0):
                    #left
                    self.line(cx0, cy0, cx0, cy1, screen)
                elif neighbor == (1,0):
                    #right
                    self.line(cx1, cy0, cx1, cy1, screen)

I try defining the lines and unpacking them:

    def draw_border(self, cell, cells, screen):
        x, y = cell
        cx0 = cell.x*cell_size
        cy0 = cell.y*cell_size
        cx1 = cx0 + cell_size
        cy1 = cy0 + cell_size
        bottom = (cx0, cy1, cx1, cy1)
        top = (cx0, cy0, cx1, cy0)
        left = (cx0, cy0, cx0, cy1)
        right = (cx1, cy0, cx1, cy1)
        neighbor_count = 0
        for neighbor in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            dx, dy = neighbor
            n_x = x + dx
            n_y = y + dy
            check = self.room.cell_at(n_x, n_y)
            if check not in cells:
                neighbor_count += 1
                if neighbor == (0,1):
                    self.line(*bottom, screen)
                elif neighbor == (0,-1):
                    self.line(*top, screen)
                elif neighbor == (-1,0):
                    self.line(*left, screen)
                elif neighbor == (1,0):
                    self.line(*right, screen)

That works and lets me eliminate those left/right comments. Let’s make a dictionary:

    def draw_border(self, cell, cells, screen):
        x, y = cell
        cx0 = cell.x*cell_size
        cy0 = cell.y*cell_size
        cx1 = cx0 + cell_size
        cy1 = cy0 + cell_size
        bottom = (cx0, cy1, cx1, cy1)
        top = (cx0, cy0, cx1, cy0)
        left = (cx0, cy0, cx0, cy1)
        right = (cx1, cy0, cx1, cy1)
        lines = {(0,1): bottom, (0,-1):top, (-1,0): left, (1,0):right}
        neighbor_count = 0
        for neighbor in lines.keys():
            dx, dy = neighbor
            n_x = x + dx
            n_y = y + dy
            check = self.room.cell_at(n_x, n_y)
            if check not in cells:
                neighbor_count += 1
                self.line(*lines[neighbor],screen)

Hm. I think that’s getting better. Let’s extract:

    def draw_border(self, cell, cells, screen):
        x, y = cell
        lines = self.make_lines(cell)
        neighbor_count = 0
        for neighbor in lines.keys():
            dx, dy = neighbor
            n_x = x + dx
            n_y = y + dy
            check = self.room.cell_at(n_x, n_y)
            if check not in cells:
                neighbor_count += 1
                self.line(*lines[neighbor],screen)

    def make_lines(self, cell) -> dict[tuple[int, int], tuple[int | Any, int | Any, int | Any, int | Any]]:
        cx0 = cell.x * cell_size
        cy0 = cell.y * cell_size
        cx1 = cx0 + cell_size
        cy1 = cy0 + cell_size
        bottom = (cx0, cy1, cx1, cy1)
        top = (cx0, cy0, cx1, cy0)
        left = (cx0, cy0, cx0, cy1)
        right = (cx1, cy0, cx1, cy1)
        lines = {(0, 1): bottom, (0, -1): top, (-1, 0): left, (1, 0): right}
        return lines

Huh! I rather like that. One more thing: a better name:

    def draw_border(self, cell, my_cells, screen):
        x, y = cell
        lines = self.make_lines(cell)
        neighbor_count = 0
        for neighbor in lines.keys():
            dx, dy = neighbor
            n_x = x + dx
            n_y = y + dy
            check = self.room.cell_at(n_x, n_y)
            if check not in my_cells:
                neighbor_count += 1
                self.line(*lines[neighbor],screen)

I think we have improved things. If our cells knew their room, which as yet they do not, this code might be even a bit better, something like

if check.is_in_room(self.room)

Well maybe that’s better, maybe not. We’ll have to wait and see whether we come up with another improvement after we get the Cell to be a bit smarter.

It seems to me that we often(?) do that dx,dy n_x, n_y kind of thing, and I don’t like it. Here, we kind of need the direction information (0,1) and so on, but it’s just too messy to have to do more than once. Oh I see one small improvement:

    def draw_border(self, cell, my_cells, screen):
        x, y = cell
        lines = self.make_lines(cell)
        neighbor_count = 0
        for neighbor_offset in lines.keys():
            dx, dy = neighbor_offset
            n_x = x + dx
            n_y = y + dy
            check = self.room.cell_at(n_x, n_y)
            if check not in my_cells:
                neighbor_count += 1
                self.line(*lines[neighbor_offset],screen)

The loop index is an offset, not a neighbor. The name makes more sense now. What would make even more sense would be to ask the room for the cell at a given offset. Or, better yet, ask the cell itself, since it knows the space now.

class Cell:
    def at_offset(self, dx, dy):
        new_x, new_y = self.x + dx, self.y + dy
        return self.space.at(new_x, new_y)

Let’s use that in draw_border. I haven’t written a test for it but the map will tell us.

    def draw_border(self, cell, my_cells, screen):
        x, y = cell
        lines = self.make_lines(cell)
        neighbor_count = 0
        for neighbor_offset in lines.keys():
            check = cell.at_offset(*neighbor_offset)
            if check not in my_cells:
                neighbor_count += 1
                self.line(*lines[neighbor_offset],screen)

The map draws just fine. There is also code in Cell that could use this new method:

    @property
    def neighbors(self):
        deltas = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        neighbors = []
        for dx, dy in deltas:
            new_x = self.x + dx
            new_y = self.y + dy
            neighbor = self.space.at(new_x, new_y)
            if neighbor is not None:
                neighbors.append(neighbor)
        return neighbors

We refactor:

    @property
    def neighbors(self):
        deltas = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        neighbors = []
        for dx, dy in deltas:
            neighbor = self.at_offset(dx, dy)
            if neighbor is not None:
                neighbors.append(neighbor)
        return neighbors

Map is good. Tests are green. Commit: improvements to RoomView and Cell.

Enough. Let’s sum up reflectively:

Summary

Our medium range almost immediate goal is to deal with adjacency, so as to have places for doors. As part of preparing for that, I drew a picture and we reviewed a similar activity, the border calculations in RoomView. That let to a few quick improvements, each of which led to the next.

• Packing up the coordinates into line definitions simplified the code a bit.
• And that led to making a dictionary of offset to line, which removed a long if nest, replacing it with a single call.
• That offered an opportunity to extract around a dozen lines of code off to a separate method, simplifying the border drawing loop method.
• That made a weak name more obvious and we improved that.
• And the smaller code make the offset calculations seem wrong and out of place, and that led to a method in Cell that not only made our job easier in RoomView, but simplified some of Cell’s own code.

Each of these was a very small change, and everything continued to work correctly throughout.

Philosophy Again

This often happens. I want to say always, let’s settle for “nearly always happens”. We make a small improvement to the code and that improvement lets us see another improvement, and another and another, and after a handful of simple smooth operations, the code is discernibly better, and almost always offers new convenient handles for doing new things later on.

This is why we work this way, in small steps, often refactoring. The lesson I repeatedly learn is that I often wait longer than would be ideal to make these changes, but that even if I’m a bit late to the change, it is generally worth doing.

This is the way.

See you next time!