Tendencies?

FGNO had some ideas. I’m not ready to work on holes. What about paths? A weird solution emerges.

As always Tuesday night is Friday Geeks Night Out and while topics ranged wildly, we did spend a little time looking at my maps and talking about how to identify holes and how to get paths as nice as some of the more jaggy bits that the new ExperimentalCellCollector draws seemingly easily:

That map is fully connected already but take a look at that shape in the upper left. If it had extended just a bit further, it would have made a very interesting path from the spaces on the right to the ones on the left. I’d like to be able to use the same growth technique to build intentional paths from one place to another. Jaggy and random, but starting at a given location and finishing at another.

We looked at one partial path last night where the rule “don’t go south” would have done the job. With the one above, “don’t go west” would probably suffice. Sometimes, we might want something more definitive, like “don’t go south, go north more frequently than you go east or west”. If you can call that definitive. More specific? More controlling? Whatevs.

Thinking, We Do It …

The current Experimental scheme selects the next room cell with this code:

    def _build_cave(self, number_of_cells, origin):
        new_cell: Cell = origin
        for _ in range(number_of_cells):
            self.take(new_cell)
            self.growth_candidates.append(new_cell)
            new_cell = self.find_adjacent_cell(new_cell)
            if new_cell is None:
                return

    def find_adjacent_cell(self, previous):
        if random.random() < 1.0:
            available = previous.available_neighbors
            if available:
                return choice(available)
        for cell in sample(self.growth_candidates,
                           len(self.growth_candidates)):
            available = cell.available_neighbors
            if available:
                return choice(available)
            else:
                self.growth_candidates.remove(cell)
        return None

Every time build_cave uses a cell, it passes it to find_adjacent_cell, which will use it to find the next cell, using the available neighbors of that cell. Since it has just been added to the room, it has at most three usable neighbors and they’ll all be in a direction more or less “away” from the current room that we’re building. Of course, we’re constrained by our surroundings, and affected by randomness, but we definitely see long excursions.

I think I mentioned a few articles back that some new friend on Mastodon had built a nice-looking map by taking a maze and removing walls. That scheme had the advantage that since the maze was originally fully connected, the rooms were all guaranteed to be accessible one from another. We want that same property but we don’t start with a fully connected graph. Or do we?

What if, instead of building our rooms at random locations, as we do now, we always started a new room on the periphery of an existing room? We’d certainly be fully connected.

What if we always started with the last cell added? Ah: that could trap us, and we’d never get out.

I believe that this line of thinking leads me to recognizing holes again. Need better idea.

Another Idea, Perhaps Better

With the settings as they are now, maps seem to come out fully connected around half the time, perhaps a bit more than half the time.

What if we created a map, checked to see if it was fully connected, and just threw it away if not and created another? What if we created a map, checked it for fully connected, and kept adding rooms until it was fully connected?

Hm, those both sound interesting. The first idea is easy and we know what the result would look like, though not how long it would take. So let’s see if we can do the second idea: add rooms until fully connected.

Round Tuit

Presently, the dungeon is actually being built in main. We should probably work to move dungeon building out of main and into classes, but for experimentation is has been fine so far.

Here’s main:

def main():
    space = CellSpace(64, 56)
    # random.seed(234)
    dungeon = Dungeon()
    number_of_rooms = random.randint(10,10)
    maker = RoomMaker(space)
    for _ in range(number_of_rooms):
        origin = space.random_available_cell()
        size = random.randint(100, 200)
        room = maker.experimental(size, origin)
        dungeon.add_room(room)
    view = DungeonView(dungeon)
    view.main_loop()

What we’ll try is to make number_of_rooms, and then enough more to make the dungeon connect up. We need to determine whether it is connected, and we have some code that addresses that somewhere. Ah yes, here it is in Dungeon class:

    def define_suites(self):
        self.suites = []
        unexplored = self.rooms.copy()
        while unexplored:
            suite = self.find_suite(unexplored[0])
            self.suites.append(suite)
            unexplored = [room for room in unexplored if room not in suite]
        return self.suites

    @staticmethod
    def find_suite(room):
        suite = set()
        start = room.cells[0]
        for cell in start.generate(lambda c: c.is_in_a_room):
            suite.add(cell.room)
        return suite

My plan with suites was to connect them rather than rooms, but we have not yet moved further in that direction. But I think we can readily adapt this to answering whether the map is fully connected. If we take any room and build its suite, if the map is fully connected, the suite size will equal the number of rooms in the dungeon.

You could make a case for testing this but I consider it easy and just an experiment anyway, so sue me.

class Dungeon:
    @property
    def is_fully_connected(self):
        suite = self.find_suite(self.rooms[0])
        return len(suite) == len(self.rooms)

We’ll just print that result in main to begin with. That immediately revealed that I had written len(self.rooms)==len(self.rooms), not too clever. I think PyCharm helped me with its guesses and I was careless in reading it. Imagine what happens with AI enabled.

Testing … a few runs tell me that the check works. Now to adjust main to add more rooms.

def main():
    space = CellSpace(64, 56)
    # random.seed(234)
    dungeon = Dungeon()
    number_of_rooms = random.randint(10,10)
    maker = RoomMaker(space)
    for _ in range(number_of_rooms):
        origin = space.random_available_cell()
        size = random.randint(100, 200)
        room = maker.experimental(size, origin)
        dungeon.add_room(room)
    while not dungeon.is_fully_connected:
        origin = space.random_available_cell()
        size = random.randint(100, 200)
        room = maker.experimental(size, origin)
        dungeon.add_room(room)
    print(f'{dungeon.is_fully_connected=}\n{len(dungeon.rooms)=}')
    view = DungeonView(dungeon)
    view.main_loop()

This worked perfectly and with some very interesting maps:

Map with some large area rooms and some very path-like rooms

Map with rooms containing rooms, some very small

Intricate map requiring 22 rooms before connected

Summary

This is an interesting result, so let’s sum up. I’ve been thinking about paths as different from rooms, and drawing paths between rooms. What we have stumbled on here is that there are just rooms, and some of them look very much like paths to our eyes. And, instead of drawing some number of rooms and connecting them, we just keep creating rooms until they are all connected.

I really enjoy this kind of outcome, and that’s why you can take your vibe coding and your LLM and insert them well out of my sight. I got into this business because I found it fascinating that a computer could become anything we could imagine, if only we could imagine in clearly enough, and it is the joy of continually rediscovering that that kept me in the business all this time.

The current scheme probably can be improved. We should probably throw away small rooms, which have probably emerged in some enclosed area and become trapped.

What about doing it “right”?

There is much art and probably some decent theory out there about how to do this “right”, with graph decompositions and maze disassembly and probably there is something with quaternions or tensors or something. Would any of those be “better”? It’s not clear. These maps are pretty fine, and the code is understandable, even if the results are delightfully random.

That said, if we want our scheme to be able to draw more regular maps, such as classical dungeons with connected mostly rectangular rooms, or building floor plans, again mostly rectangular perhaps with secret passages, our current scheme might not serve. We will almost certainly have to find or devise other room-building algorithms, and there might well be knowledge “out there” that we could make use of. And perhaps we’ll do that and perhaps we won’t.

There’s something quite fine, to me, in a simple heuristic approach like we have here.

The big question is …

What’s next? Should we draw more rooms or kinds of maps? Should we turn this into an actual game of some kind? Should we do something completely different?

I honestly don’t know, but I can’t wait to find out: I’m sure it’ll amuse me, and I hope it’ll amuse you.

See you next time!