Still Too Many

While I like the new bordered look, I still don’t like the rooms all packed together. I have an easy idea that comes with a puzzle.

Easy Idea

We’ll decide how many rooms we want, probably randomly in actual use, then select the room origin randomly in the space, then grow the room there. We can tune the sizes and number of rooms so that rooms rarely intersect, and if once in a while they do, that will be OK: sometimes a big cavern opens through a small hole to another.

Puzzle

We’ll then want to connect the rooms to make up our dungeon. One approach might be to connect them in order of creation. Another might be to connect the nearest ones somehow. Either way, we’ll want to make paths between them. And that’s where it may get tricky.

The two rooms being connected will (effectively) never be directly to the side or directly above one another. The most direct path between them will proceed at an angle. And the cells in the path need to be side-adjacent. I hear faint echos of Bresenham. I know I’ve implemented that before and it looks like maybe I’ll be doing it again.

Let’s Start Easy

We don’t really have a need for our line paths until we have rooms that need connecting. Let’s get that happening. My rough plan of operation for creating a room is:

1. Pick a random x,y in the drawing space;
2. Pick a room size;
3. Grow a room at that location;
4. Stop growing if there are no available spaces (existing rooms split, which turns out to be undesirable).

I think I’d like to do some decent testing off the code, not because we need it, since our results will be pretty clear on screen, but because things generally go better with tests, and I have a deplorable tendency to skip testing when things are visible or “obviously” correct.

We have some tests and code that may be applicable but that are not quite on point. Let’s quickly review and see what we might reuse, and what we might retire.

The current “production” way of building a room is this:

    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)
        return new_cell

    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 bank.available_cell()

We just have one test for the method:

    def test_build(self):
        random.seed(234)
        bank = CellBank(64, 56)
        room = Room()
        cell = room.build(bank, 100, (0,0))
        assert len(set(room.cells)) == 100
        assert cell == (10, 0)

Basically a very elementary approval test. What might we want to test? If we create a room in an open area we expect it to get all the cells asked for. If we build it somehow in an enclosed space, it should stop growing. We could fence an area and test that.

If we were fanatics, we’d test that every cell in the room is accessible from the center, that is, we haven’t somehow built a split room. And we don’t want a cell back from build any more.

I’ll start with this test, building in the middle of the plane and checking that we don’t return anything from build. It should fail by returning a tuple.

Expected :None
Actual   :(35, 22)

Perfect. Now adjust the code. Find adjacent cell should return None when there is no room to grow:

    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

And if we return no cell, we need to stop growing:

    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

I think we should be green. Yes. Commit: revising build.

Now, for my sins, I’d like to test that the room is contiguous, and that a constrained room stops growing. The former we can do in the current test. But how?

If we grab the cells from the room (we’re a test, we can do that), and start with one and remove it and remove its neighbors, repeat, we should wind up with an empty set. If we don’t, there is at least one cell that is inaccessible.

We could do this recursively. We almost have to, since if we ever grab another cell without first knowing that it was accessible, we might grab into a separate group of cells.

This will be fun. I start with this much:

    def test_build(self):
        random.seed(234)
        bank = CellBank(64, 56)
        room = Room()
        no_return = room.build(bank, 100, (32, 28))
        assert len(set(room.cells)) == 100
        assert no_return is None
        self.verify_contiguous(room)

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

    def remove_cell(self, cell, cell_set):
        pass

This fails nicely. Nothing done, 100 left in the set.

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

    def remove_cell(self, cell, cell_set):
        self.remove_safely(cell, cell_set)
        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(neighbor, cell_set)

    @staticmethod
    def remove_safely(cell, cell_set):
        if cell in cell_set:
            cell_set.remove(cell)

I have no explanation for how I wrote that. Well, maybe sort of:

We want to remove one cell from the set, and all its neighbors, and all their neighbors ad infinitum. We’ll encounter the same candidate more than once, so we …

No, wait, belay that. I’m going to improve this. We don’t need to remove safely, because we never try to remove a cell that isn’t in the set.

    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)

OK. To verify, we want to remove a cell and all its neighbors and grand-neighbors and great-grand-neighbors etc. We start with the first cell. Could start with any of them.

We remove the current cell. Then we remove its neighbors, which consists of generating the four neighbors, and if they are still in the set, we remove that neighbor and its neighbors, recursively.

And we wind up with an empty set, so the room is in fact contiguous.

Note

If we did not check membership in cell_set in remove_neighbors, we would recur infinitely. I know this because I did it. Well, python stopped after 1000. Close enough.

Note

We see again that things would probably go better if we had a Cell class that had a bit of intelligence, such as the ability to return its neighbors. But so far, the call isn’t strong enough for me to decide to do it.

Constrained Room

OK, Let’s build a constrained room and ensure that it stops growing. Let’s build a small rectangle of used cells, and then grow a room inside and ensure that we only get what was inside.

    def test_constrained_room(self):
        random.seed()
        bank = CellBank(10, 10)
        for c in range(10):
            bank.take(0, c)
            bank.take(9, c)
            bank.take(c, 0)
            bank.take(c, 9)
        start = (5,5)
        room = Room()
        room.build(bank, 100, start)
        assert len(room.cells) == 64

This passes, with this change:

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

I had remove, which throws if the cell is present, and when I draw the rectangle, I take the corners twice. discard doesn’t mind removing something that isn’t present.

We are green. I think the new room building is working well. Commit: new build does not split rooms.

New Room Allocation

Now I’d like to allocate some rooms randomly and see how it looks. Because see is critical to deciding what I like, I’ll do this in main.

def main():
    bank = CellBank(64, 56)
    # random.seed(234)
    dungeon = Dungeon()
    for _ in range(10):
        room = Room()
        size = random.randint(80, 100)
        while True:
            x = random.randint(0, 63)
            y = random.randint(0, 55)
            if bank.has_cell(x, y):
                break
        room.build(bank, size, (x,y))
        dungeon.add_room(room)
    view = DungeonView(dungeon)
    view.main_loop()

Let me refactor that a bit with an extract.

def main():
    bank = CellBank(64, 56)
    # random.seed(234)
    dungeon = Dungeon()
    for _ in range(10):
        room = Room()
        size = random.randint(80, 100)
        x, y = random_available_cell(bank)
        room.build(bank, size, (x,y))
        dungeon.add_room(room)
    view = DungeonView(dungeon)
    view.main_loop()


def random_available_cell(bank: CellBank) -> tuple[int, int]:
    while True:
        x = random.randint(0, 63)
        y = random.randint(0, 55)
        if bank.has_cell(x, y):
            break
    return x, y

So we created ten rooms of size between 80 and 100 and we got that map. Still seems like too many rooms are adjacent. I tweak the main a bit:

...
    number_of_rooms = random.randint(6, 9)
    for _ in range(number_of_rooms):
        room = Room()
        size = random.randint(60, 90)
...

Still not loving these results:

It seems to me that the space is on the one hand, too empty, and on the other hand, the rooms are too often adjacent. I’ll have to think about what might make for a better layout.

Maybe something like dividing the space into regions, and starting rooms at the center of those regions, or near there.

However … we don’t have to make a door between adjacent rooms. We could have a long and winding road between them even if they are really adjacent.

It might help to think about just what use this map has in the dungeon game that we are presumably working on.

And we do still have the paths between rooms to think about. We’ll probably do that next time.

Summary

We have a somewhat improved picture, a rather nice test for rooms being contiguous, and simpler code in the room building logic. Overall, a noticeable improvement!

I still have the vague feeling that a Cell class would like to exist. Maybe the thing to do would be to build it, use it, and see what sticks. We’ll see.

See you soon!