Shapes

FGNO Wants Better Shapes. We do an inadvertent spike. Along the way we discover an issue in generate, and learn the difference between a square and a circle. A superior day!

Last Tuesday night, amid all their other whining¹ about my code, the Friday Geeks Night Out (FGNO) group agreed that while the shapes of my rooms is cave-like, they could be better. I think it was Bill who suggested that they were all a bit too round, and that some might better extend more in one direction than another. It was Hill who thought that they’d look better if they were more jagged, with deeper incursions and longer excursions. So today, we’ll work on improving the room shapes, or at least providing more variety.

We’ll begin, in Bill’s honor, with a room that is as round as we can make it.

I thought about this last night as I was trying to go to sleep. When a flood fill runs, it draws wider and wider “frontiers” around the starting cell, and, if my mental picture and arithmetic is correct, the first frontier has one cell, the second has four, and the third has nine. I couldn’t picture the fourth, but the pattern surely is that the fourth frontier has sixteen, and so on, squaring the “radius” each time around.

Note

My reasoning in my head was faulty in two regards. First, the number of cells in each round is 1, 4, 8, 12, not 1, 4, 9, 16. Second, as we’ll see below, you get a diamond shape, not a round one. Kind of nice though.

It follows, if my reasoning is correct, that we can draw a symmetrical roundish room by generating a flood whose cell count is the sum of n squares. So I plan to do that, and I plan to look at the output to see if I got it right. I predict that when we see the code we’ll understand why that’s OK. If I get in trouble, you can berate me and make me figure out a test.

Here goes. I plan to make a new method in Room, maybe _build_round and use it instead of the current _build, if that’s the name. I think we’ll need to fiddle Room’s constructors a bit, so let’s take a look at it.

class Room:
    def __init__(self, space: CellSpace, size, origin, name = ''):
        self.space = space
        self.origin = origin
        self.name = name
        self.cells:list[Cell] = []
        self.growth_candidates: list[Cell] = []
        self.color = "grey22"
        self.probe_count = 0
        self._build(space, size)

Right. Are we ever using that name member? I change it to set fubar and nothing breaks. Let’s Change Signature to remove that parm. A few clicks, done, commit: remove unused parameter.

Now I propose to add a parameter, indicating what kind of room we want. We could either have some symbolic value, or pass in a function. Or, and perhaps this would be better, we could make constructors of useful names. Let’s do that.

We’re still working without tests here. Just because I don’t want to test the circle for roundness doesn’t mean I want to work without a net but just now I’m not sure what I even want, so I’ll push it a bit further all testless and in danger.

class Room:
    @classmethod
    def cavern(cls, space:CellSpace, size, origin:Cell):
        room = Room(space, size, origin, cls._build)
        return room

    def __init__(self, space: CellSpace, size, origin, builder):
        if builder is None:
            builder = self._build
        self.space = space
        self.origin = origin
        self.cells:list[Cell] = []
        self.growth_candidates: list[Cell] = []
        self.color = "grey22"
        self.probe_count = 0
        builder(space, size)

That wasn’t done without tests, because until I had it wired up, a raft of tests complained. But we have no tests for cavern. I’ll just fine some room creations and change them.

Oh sweet, removing the name was a mistake, it’s used in __repr__ to identify rooms when things go wrong in the tests.

Meh! That’s not working and I’m not sure why. We’re not here to work that out, we’re here to make a round room. Let’s roll back all the way to when we had the name. git reset –hard

I’m not sure what was wrong there, but I couldn’t find syntax that would run and compile.

Before I do anything else, I see that I can simplify _build, because while it is passed the CellSpace, it just passes it on to a method that ignores it:

    def find_adjacent_cell(self, bank: CellSpace):
        for cell in sample(self.growth_candidates, len(self.growth_candidates)):
            self.probe_count += 1
            neighbors = cell.neighbors
            for neighbor in sample(neighbors, len(neighbors)):
                if neighbor.is_available:
                    return neighbor
            self.growth_candidates.remove(cell)
        return None

We can remove that bank parm (old name too). No _build can change signature as well. Green. Commit a tidying save point.

I’m just going to go ahead and create a new method _build_round and see that it gets called from main as my check for the idea.

Ah! I have discovered that generate does not generate the cells in a FIFO order. Python set.pop returns a random element from the set. Do not like. I want them in the order found.

After some rigmarole, I do get the following picture, which is emphatically not round. I came to realize that not long ago, but put a note up at the top to warn you that I was operating with flawed assumptions

Not very damn round, is it? The good news is that that could be an interesting shape for some kind of treasure room or the like. So I’ll rename the method that builds it to _build_diamond:

    def _build_diamond(self, number_of_cells):
        count = 0
        for cell in self.origin.generate(lambda c: c.is_available):
            self.take(cell)
            count += 1
            if count == number_of_cells:
                break

That will do for now. I hacked main to draw it:

def main():
    bank = CellSpace(64, 56)
    # random.seed(234)
    dungeon = Dungeon()
    number_of_rooms = random.randint(1, 1)
    for _ in range(number_of_rooms):
        # size = random.randint(90, 90)
        size = sum((4*r for r in range(1,7))) + 1
        origin = bank.at(30,30)
        room = Room(bank, size, origin)
        dungeon.add_room(room)
    for room_1, room_2 in zip(dungeon.rooms, dungeon.rooms[1:]):
        dungeon.find_path_between_rooms(bank, room_1, room_2)
    view = DungeonView(dungeon)
    view.main_loop()

We’re going to treat this morning’s work as a Spike, an experiment to learn about something we want to do. I thought we’d just do it, but I was mistaken. We’ll save the build method, roll back the main. And to get the generate to generate in the order of nearest first, I changed it thus:

def generate(start, condition=None):
    def accept_any(_cell):
        return True
    cond = condition or accept_any
    frontier = [start]
    examined = {start}
    while frontier:
        next = frontier.pop(0)
        yield next
        examined.add(next)
        for neighbor in next.neighbors:
            if neighbor not in examined and cond(neighbor):
                if neighbor not in frontier:
                    frontier.append(neighbor)

I changed frontier to a list and pop it. That’s not as efficient as one might like, as it slides the array up one (down one? matter of taste.) and that’s a bit costly, though I suspect it’s done in C.

I’m not sure all my tests are passing with that change in place. Right, this one fails:

class TestRoom:
    def test_number_of_probes(self):
        random.seed(456)
        space = CellSpace(64, 56)
        start = space.at(32, 32)
        room = Room(space, 100, start)
        assert room.probe_count == 140

What even is that? Ah, I hadn’t yet changed Room to build the non-diamond shapes yet. All good now. Commit: saving unused _build_diamond spike code and FIFO generate.

Summary

Well, this idea turned out to be p-baked for p < 1/2 by quite a margin. The shape I envisioned was quite square, not round, and the number of cells in each layer was not r-squared but 4 times r. I wasn’t able to make a plug-in method work and still have no idea what to do about that. I do not know how to make a round room, so I’ll work on that because I think they would be nice to have. And, of course, I haven’t done any work at all on long thin rooms or more jaggy rooms.

I wanted to mention heuristics. A heuristic, in this sense, is an approach to solving a problem that is not complete but often useful. I am aware of algorithms for creating dungeons that are complete solutions, and that is exactly what I’m not doing. One very interesting one , however, was tooted at us on Mastodon from @bazzargh@hackyderm.io. @bassargh creates a maze and then removes parts of it, getting interesting rooms with guaranteed connectivity. Very nice!

But, as I say, that’s not what I’m doing. I’m intentionally experimenting with ideas on coding up shapes that look interesting paths that look interesting, and so on. The point isn’t perfection, it is in fact ideal if things look a bit messy sometimes. The point is the fun.

And the learning. I continue to learn things, such as not to be too sure that something is going to be round when any fool can see that it’s a square on its corner. Heh.

Enough fun for today. Got Chai to drink, books to read. See you next time!