Still nerd-sniped by dungeon allocation, I begin to get a sense of an approach. Let’s see what happens. Python fits my hand. What’s your preference?

I paired, well, mostly observed, though I may have been slightly helpful, with GeePaw Hill yesterday. He’s implementing a tiling solution to dungeon allocation, following this article. I have a different sort of plan—I emphasize “sort of—and it goes like this:

We’ll have a collection of “cells”, representing each of the fundamental blocks of the dungeon, probably squares but possibly hexes. We’ll have some limits on how small and large we want our rooms to be, such as between 10 and 20 cells.

We’ll pick some unused call and form a “room” around it, like this: pick a size between the limits. If the room is less than that size, search its existing cells in random order, looking for a cell that has a free cell beside it. If we find one, add it to the room, rinse, repeat adding cell, else stop building that room. If there are still unused cells, build another room.

If this works as I imagine, we’ll wind up with a collection of rooms containing all the cells available, and most of the rooms will be in the desired size range. Some may be smaller, due to accidental isolation of small groups of cells.

We’ll be left with the issue of making doors between the rooms, but my vague reflection on that makes me think we can search for room cells with a neighbor in a different room and make doors between some of them. Anyway, I’m deferring that issue for now.

It might be desirable, when making room N+1, to start with a cell adjacent to room N rather than a random one. It might even make sense to make that pair have a door. I am inclined somewhat to go this way, not least because once I start injecting too much randomness, things will get hard to test.

What else? Right now we have no Cell class. We have Dungeon, Room, and CellBank. CellBank is just a set of coordinates for now but presumably it becomes a collection of Cell objects, as will each Room.

Review of “Process”

Yesterday I didn’t have even this much design in mind, or at least had it less clearly. So I “just” created some tests and objects, and started some simple manipulations. I do that to try to build up a sense of the problem space and possibly useful objects. If these particular classes remain useful, we’ll keep them. If not, we’ll thank them for their service and replace them with others.

Review of Code

Since that was literally twenty-some hours ago, I have no specific recollection of what we have, so we’ll begin with a quick review of the tests and code.

We have three tests that actually do something, plus two, test_dungeon_exists and test_room_exists that just drove out the class statements. I’ll remove those two, leaving:

    def test_adding_rooms(self):
        dungeon = Dungeon()
        assert dungeon.number_of_rooms == 0
        room = Room()
        dungeon.add_room(room)
        assert dungeon.number_of_rooms == 1

    def test_cell_bank(self):
        bank = CellBank(10, 10)
        assert bank.has_cell(3, 4) is True
        bank.take(3,4)
        assert bank.has_cell(3, 4) is False

    def test_room_adds_cell(self):
        bank = CellBank(10, 10)
        room = Room()
        bank.take(5,5)
        room.add_cell(5,5)
        room.grow(bank)
        assert room.has_cell(5,5)
        assert room.has_cell(4,5)
        assert bank.has_cell(4, 5) is False

So far, the Dungeon just amounts to a container for rooms, though it has no collection behavior:

class Dungeon:
    def __init__(self):
        self.rooms = []

    @property
    def number_of_rooms(self):
        return len(self.rooms)

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

The CellBank is a container for cells and it can answer whether a given set of coordinates is in there, and can remove a given set of coordinates:

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.remove((x, y))

CellBank inits itself to contain all the coordinates in some rectangular range.

I had forgotten that we have some grow behavior in Room already, and the class looks like this:

class Room:
    def __init__(self):
        self.cells:list[tuple[int, int]] = []

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

    def has_cell(self, x, y):
        return (x,y) in self.cells

    def grow(self, bank):
        sx,sy = self.cells[0]
        for nx, ny in [(-1,0), (0,1), (1,0), (0,-1)]:
            check = (sx + nx, sy + ny)
            if bank.has_cell(*check):
                bank.take(*check)
                self.add_cell(*check)

The grow method only considers the first cell’s neighbors, and it considers them in order left, top, right, bottom. It seems clear to me that we need to check things in random order, so that different shapes emerge from different runs. If the whole thing runs deterministically, we’ll get the same layout every time. Boring.

Let’s divert for a moment and see what we can do about iterating in random order. First things first, we’ll search for it, because almost everything that can be done has been done in Python.

Sure enough, random.sample will create a list in random order, based on an input collection, and with lots of neat weighting options.

Let’s write a test to try this out a bit. I think this will be a printing test, at least to begin with.

I wrote this test with a different print and then changed to a print method on Room, but otherwise this is pretty much what I started with:

    def test_random_growth(self):
        bank = CellBank(10, 10)
        room = Room()
        room.add_cell(5,5)
        print()
        for _ in range(5):
            room.grow_randomly(bank)
        room.print_cells()
        bank2 = CellBank(10, 10)
        room2 = Room()
        room2.add_cell(5,5)
        for _ in range(5):
            room2.grow_randomly(bank2)
        room2.print_cells()

The test prints two different room allocations:

(4, 5), (5, 3), (5, 4), (5, 5), (5, 5), (6, 5), 
(5, 4), (5, 5), (5, 5), (6, 5), (6, 6), (7, 5),

Which is, of course, what we’d hope for. With five random selections odds are strongly against a duplicate result. Here’s the new code:

from random import sample
...
    def grow_randomly(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):
                    bank.take(x, y)
                    self.add_cell(x, y)
                    return
        return

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

    def print_cells(self):
        for cell in sorted(self.cells):
            print(cell, end=', ')
        print()

This just goes through the existing cells randomly, checking each cells four neighbors, randomly, to see if they are available in the bank. If the cell is available we take it from the bank, add it to ourself, and return. If the loop runs out, we just return: there were no adjacent cells to add.

I’m not sure what we should do to convert this to an actual test, and anyway I am confident enough that it’s working. We could certainly do some tests in constrained situations to check the end play but that seems clearly OK.

I think this is a good time to break. Tests are green. Commit: added grow_randomly.

Summary

Four commits this morning, three basically tidying, and the one just above with the new feature.

I wrote 16 lines, all in one go, in two methods. That seems like a lot, but they were pretty straightforward, once I gave up on writing neighbors as a one-line generator. We might go back to that but it’s clear now and would be less so as a generator.

Wait. I tried this and will go with it:

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

Test, green, commit: use list comprehension.

I’m feeling good about Python this morning, compared to a more strict language, because all these iterations and conversions from sets to list and so on “just work”, and because Python is rich with useful things like the sample function. To do what we’ve done here in Kotlin or Java or Swift or C# would likely have required a lot of type declaration and coercion. Here, we just say what we want and we get it.

That’s not to say that Python is “better” in any absolute sense. We use the tools we’re required to use, and from the tools we’re allowed to use, we choose the ones that fit our hands. Python fits my hand nicely, and I enjoy using it. If you enjoy something else, that’s just fine by me.

Anyway, we have a nice feature, or sketch of one, and that’s good enough for any morning.

See you next time!