Hello, loves!

Once we build a passage between two rooms, we want never to change or replace it. Seems easy enough … and, surprisingly, it is!

Why do we need that? Well, when stepping the dungeon build, we need to update the view on every step, and part of updating the view is flooring, and flooring is sensitive to passages, and we do want to see the passages, so we want to continue to create them when we update the view, but passages are created randomly along borders, and as things stand we get more and more passages on the same border and we do not want that, that’s why.

I’m starting to think, well, not exactly starting, because I’ve thought it before, but I’m thinking that this might be a good time to have some kind of passage-related objects. Currently, there’s just this kind of thing:

class DungeonLayout:
    def __init__(self, max_x=10, max_y=10):
        ...
        self.passages: dict[tuple[Cell, Cell], bool] = dict()

    def add_passage(self, passage):
        if passage:
            c1, c2 = passage
            self.passages[(c1, c2)] = True
            self.passages[(c2, c1)] = True

    def has_passage(self, cell, neighbor):
        if self.passages.get((cell, neighbor)):
            return True
        else:
            return False

It is my consistent practice to use system collections like the dict shown here, at least in the early stages of the program, until it becomes more clear what we might really want. This may not be ideal: I know people who will almost never settle for a system collection, turning immediately to building specialized collections. If you were to argue that my practice is less than ideal, I wouldn’t fight hard for my position. It’s what I do: I don’t claim that it’s the best thing for anyone to do, including me.

But we can see here the sort of thing that goes on when we use a system collection: we get code in an object like the Layout that is all about something that isn’t the layout. And the code knows an awful lot about what’s going on inside that rather odd dictionary.

Let’s take this occasion to make at least one, possibly two new objects. We’ll make the PassageCollection object, and perhaps we’ll have a Passage object inside, or perhaps we won’t. We’ll see if one seems to be needed and useful.

We have a few tests for passages, so let’s just build our new class and plug it in. It needs to offer two methods, it seems, add_passage and has_passage.

I’ll just type it in, plug it in, and see what breaks. It’s really just a matter of moving some code, for now:

class PassageCollection:
    def __init__(self):
        self.passages: dict[tuple[Cell, Cell], bool] = dict()

    def add_passage(self, passage):
        if passage:
            c1, c2 = passage
            self.passages[(c1, c2)] = True
            self.passages[(c2, c1)] = True

    def has_passage(self, cell, neighbor):
        if self.passages.get((cell, neighbor)):
            return True
        else:
            return False

class DungeonLayout:
    def add_passage(self, passage):
        self.passages.add_passage(passage)

    def has_passage(self, cell, neighbor):
        return self.passages.has_passage(cell, neighbor)

Nice. Now the layout doesn’t know how passages work, it just knows how to ask about them.

Tests are all green. Test the game just because. All is well. Commit: Initial PassageCollection.

Now let’s see what we want to do about the rooms and passages. We want not to build a passage between two rooms if there already is such a passage. I think we’ll do that in a nasty way and then find a better way, just for fun.

So who’s using add_passage?

class DungeonLayout:
    def make_passages(self):
        for r1, r2 in itertools.combinations(self.rooms, 2):
            passage = self.random_passage(r1, r2)
            self.add_passage(passage)

Let’s do some Wishful Thinking. It would be nice if our passages could tell us whether there is a passage between two given rooms. Hm. It would also be nice to have a test for this. Let’s do that.

    def test_passages_arent_recreated(self):
        layout = DungeonLayout(10, 10)
        room_1 = Room([Cell(0,0), Cell(0,1), Cell(0,2)])
        room_2 = Room([Cell(1,0), Cell(1,1), Cell(1,2)])
        layout.add_room(room_1)
        layout.add_room(room_2)
        for _ in range(10):
            layout.make_passages()
            passages = layout.passages
            assert len(passages.passages) == 2

That was enough to fail, because soon enough we’ll create a different one of the three possible passages between the rooms. Of course we could get unlucky, but we’re not going to stop here anyway. Let’s have a method like this:

    def test_passages_arent_recreated(self):
        layout = DungeonLayout(10, 10)
        room_1 = Room([Cell(0,0), Cell(0,1), Cell(0,2)])
        room_2 = Room([Cell(1,0), Cell(1,1), Cell(1,2)])
        layout.add_room(room_1)
        layout.add_room(room_2)
        layout.make_passages()
        assert layout.passages.can_pass_between(room_1, room_2)

And that’s easy though inefficient:

class PassageCollection:
    def can_pass_between(self, room_1, room_2):
        for c1, c2 in self.passages.keys():
            if c1.room == room_1 and c2.room == room_2:
                return True
            if c1.room == room_2 and c2.room == room_1:
                return True
        return False

Test passes, now let’s make it efficient:

class PassageCollection:
    def __init__(self):
        self.cell_passages: dict[tuple[Cell, Cell], bool] = dict()
        self.room_passages: set[tuple[Room, Room]] = set()

    def add_passage(self, passage:tuple[Cell, Cell]):
        if passage:
            c1, c2 = passage
            self.cell_passages[(c1, c2)] = True
            self.cell_passages[(c2, c1)] = True
            self.room_passages.add( (c1.room, c2.room))
            self.room_passages.add( (c2.room, c1.room))

    def can_pass_between(self, room_1, room_2):
        return (room_1, room_2) in self.room_passages

Test passes, woot! I just thought of the set in thing, and it seems that we could use a set in the other situation as well.

Of course, we could use one set for both, since we’re just making a set of tuples and a room is never equal to a cell.

Let’s try it and see how it looks.

class PassageCollection:
    def __init__(self):
        self.connected: set[tuple[Cell | Room, Cell | Room]] = set()

    def add_passage(self, passage:tuple[Cell, Cell]):
        if passage:
            c1, c2 = passage
            self.connected.add((c1, c2))
            self.connected.add((c2, c1))
            self.connected.add((c1.room, c2.room))
            self.connected.add((c2.room, c1.room))

    def has_passage(self, cell, neighbor):
        return (cell, neighbor) in self.connected

    def can_pass_between(self, room_1, room_2):
        return (room_1, room_2) in self.connected

Let’s extract a new method, are_connected:

    def has_passage(self, cell, neighbor):
        return self.are_connected(cell, neighbor)

    def can_pass_between(self, room_1, room_2):
        return self.are_connected(room_1, room_2)

    def are_connected(self, cell: Cell | Room, neighbor: Cell | Room) -> bool:
        return (cell, neighbor) in self.connected

I tried using are_connected everywhere and decided that I prefer a more explicit name and not to allow outside users to mix up the types. So I’ve wound up with this:

    def rooms_are_connected(self, r1: Room, r2: Room):
        return self._has_connection(r1, r2)

    def cells_are_connected(self, c1: Cell, c2: Cell):
        return self._has_connection(c1, c2)

    def _has_connection(self, cell: Cell | Room, neighbor: Cell | Room) -> bool:
        return (cell, neighbor) in self.connected

OK, this works, but it’s unnecessary to mix the types that way. Let’s go back to two sets. This is just too clever.

class PassageCollection:
    def __init__(self):
        self.cell_connections: set[tuple[Cell, Cell]] = set()
        self.room_connections: set[tuple[Room, Room]] = set()

    def add_passage(self, passage:tuple[Cell, Cell]):
        if passage:
            c1, c2 = passage
            self.cell_connections.add((c1, c2))
            self.cell_connections.add((c2, c1))
            self.room_connections.add((c1.room, c2.room))
            self.room_connections.add((c2.room, c1.room))

    def rooms_are_connected(self, r1: Room, r2: Room):
        return (r1, r2) in self.room_connections

    def cells_are_connected(self, c1: Cell, c2: Cell):
        return (c1, c2) in self.cell_connections

Yes, that’s better. Commit: Passages uses two sets.

Now I’d really like to add a test to ensure that we don’t make a new path between two rooms if a path already exists. Maybe we can do that more directly, if we modify make_passages. Change this:

    def make_passages(self):
        for r1, r2 in itertools.combinations(self.rooms, 2):
            passage = self.random_passage(r1, r2)
            self.add_passage(passage)

Extract a method:

    def make_passages(self):
        for r1, r2 in itertools.combinations(self.rooms, 2):
            self.ensure_can_pass(r1, r2)

    def ensure_can_pass(self, r1, r2):
        passage = self.random_passage(r1, r2)
        self.add_passage(passage)

I don’t love that name, but … no, Belay that extract. It won’t help with the randomness issue. Here’s the code we need:

    def make_passages(self):
        for r1, r2 in itertools.combinations(self.rooms, 2):
            if not self.passages.rooms_are_connected(r1, r2):
                passage = self.random_passage(r1, r2)
                self.add_passage(passage)

But if there is no connection, we’ll run this code:

    def random_passage(self, room_1, room_2):
        b_d = self.border_dictionary(room_1, room_2)
        if not b_d: return None
        possibles = []
        for cell, neighbors in b_d.items():
            for n in neighbors:
                possibles.append((cell,n))
        return random.choice(possibles)

    def add_passage(self, passage):
        self.passages.add_passage(passage)

That seems kind of wasteful, although I guess it’ll only try multiple times if we’re stepping, and efficiency isn’t an issue in that case.

Remind me to look into why we create a dictionary and then only look at its items.

I guess I’ll leave the loop in the test and deal with the randomness that way. I don’t really feel like injecting a fake random number generator for code that obviously works.

    def test_passages_arent_recreated(self):
        layout = DungeonLayout(10, 10)
        room_1 = Room([Cell(0,0), Cell(0,1), Cell(0,2)])
        room_2 = Room([Cell(1,0), Cell(1,1), Cell(1,2)])
        layout.add_room(room_1)
        layout.add_room(room_2)
        layout.make_passages()
        assert layout.passages.rooms_are_connected(room_1, room_2)
        for _ in range(20):
            layout.make_passages()
            passages = layout.passages
            assert len(passages.cell_connections) == 2
            assert len(passages.room_connections) == 2

Enough already. Commit this: once a passage between rooms exists, no other passage between those rooms will be created.

Now it should be the case that when we step the builder, we only get one exit in the central area and other rooms, not many. And that’s what we get!

map showing just one exit from the central room

So that went smoothly, despite a few cycles deciding how much polymorphism to allow and settling on very little. Let’s be summing up.

Summary

Our mission was to modify passage making so that once two rooms are connected, we never add another connection between them. The purpose was to deal with the fact that we want the build stepper to show the real state of the dungeon, including passages, but we can’t abide having more than one created per boundary, because That Would Be Bad.

Creating a little object, PassageCollection, allowed us to hide the details of how the collection works, and in fact we changed it quite a few times fiddling with the idea of using just one internal collection of tuples, versus using the more obvious two. We decided that two made a better design.

Looking at the bigger picture, we see that, as usual, even though our code has broken our design rather badly, small changes to make it better are possible.

However, if you were to review the past few articles you would find that it has taken me many tries to find this simple idea. One possible explanation for that is my advanced age, I might be losing it. Another possibility is that my knowledge of the existing way was strong enough to keep dragging me back to bad ideas. Another is that I was taking the wrong approach, trying to make small patch changes down inside the objects, when what was needed was small changes at a higher level.

Another possibility is that it was a difficult question with a simple answer.

But the main lessons, I think, are two:

  1. It is very likely that any seemingly large design change can be made in small steps;

  2. It is not unlikely that finding those small steps will be difficult.

  3. It’s worth it to find them.

Next time, we go after the final connecting paths with the impervious walls. See you then!