When last we met, we had just discovered a nice way to make a wiggly path. Since then, I’ve improved the code a bit. We’ll look at that and then see what we see.

While you were watching, we found that randomizing in the generate function creates very nice wiggly paths. The code was this:

class Cell:

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)
        neighbors = next.neighbors
        for neighbor in random.sample(neighbors, len(neighbors)):
            if neighbor not in examined and cond(neighbor):
                if neighbor not in frontier:
                    frontier.append(neighbor)

All we changed was the random.sample bit in the for.

After a break, I played with creating separate methods for random and non-random generation, and didn’t much like that. Instead, I tried adding a randomness parameter, and refactored a bit. In the code above, generate is a free-standing function, not a method. While that’s OK with Python, it’s not OK with me. I inherit my objects, in large part, from Smalltalk, where there’s nothing that isn’t an object. So after a bit of refactoring, we have this:

class Cell:
    def generate(self, condition=None, randomness=0.0):
        def accept_any(_cell):
            return True
        cond = condition or accept_any
        frontier = [self]
        examined = {self}
        while frontier:
            next = frontier.pop(0)
            yield next
            examined.add(next)
            if random.random() < randomness:
                neighbors = next.random_neighbors
            else:
                neighbors = next.neighbors
            for neighbor in neighbors:
                if neighbor not in examined and cond(neighbor):
                    if neighbor not in frontier:
                        frontier.append(neighbor)

    @property
    def random_neighbors(self):
        n = self.neighbors
        return random.sample(n, len(n))

    @property
    def neighbors(self):
        return [neighbor
                for dxy in self.deltas
                if (neighbor := self.at_offset(*dxy))]

That’s profoundly long for a method. Maybe we’ll see about improving it soon. We already make some use of the new randomness parameter in other methods:

class Cell:
    def path_map(self, can_use, randomness=0.0):
        reached = {self: None}
        for c in self.generate(can_use, randomness):
            for neighbor in c.neighbors:
                if neighbor not in reached and can_use(neighbor):
                    reached[neighbor] = c
        return reached

This will give us either the well-ordered minimal path, or the more erratic but still minimal path, or anywhere in between, conditioned by the randomness parameter. I’ve patched in a value of 1.0 in PathFinder:

class PathFinder:
    def find_path(self, source: Cell, target: Cell, room_list) -> list[Cell]:
        def can_use(cell):
            return cell.is_available or cell.room in room_list
        reached = source.path_map(can_use, 1.0)
        path = []
        start = target
        while start is not None:
            path.append(start)
            start = reached.get(start)
        return path

It seems clear that we’ll want to pull the randomness parameter up, to make it available at the high levels where strategy for dungeon building will be determined. But I am concerned about PathFinder and this method. PathFinder now just has the method above, and find_path_between_rooms, which calls this method and which is no longer used other than in a test for that method.

As things stand now, we generate our paths between Suites, not Rooms:

class Suite:
    def find_path_cells(self, suite) -> list[Cell]:
        source, target = self.find_closest_pair(suite)
        finder = PathFinder()
        cells = finder.find_path(source, target, [source.room, target.room])
        on_path = cells[1:-1]
        return on_path

I think we could have a similar method to the PathFinder one in Cell, and eliminate the PathFinder class. An alternative might be to move the path map and such from Cell into PathFinder, which would give it more of a reason to live.

In a sense, it comes down to whether we would prefer to say, roughly:

cell_1.find_path(cell_2, ...)

Or

PathFinder().find_path(cell_1, cell_2, ...)

Design Thinking …

Generally one would think of a cell in the dungeon as little more than a location. There might be a kind of cell at the playing level, which could contain a treasure and a monster and such, but we might not expect a cell to have much behavior. That’s not the case with our Cell. It’s probably the second-largest class we have, at over 100 lines. The RoomMaker class is larger, if we count the helper classes it uses, DiamondCellCollector and so on.

Let’s take a quick look at the method names in Cell, see if they tell us anything interesting.

__init__
__eq__
__hash__
__iter__
__repr__
assign_to_room
at_offset
available_neighbors
border_at
borders
distance
generate
is_available
is_in_a_room
manhattan_distance
neighbors
neighbors_in_rooms
path_map
random_neighbors
room

There are at least these major classifications there:

  • individual cell properties, such as whether it’s available, or the room it’s in;
  • inter-cell methods, such as distance
  • adjacent cell methods, like neighbors, random_neighbors, etc
  • aggregate methods, generate and path_map.

We have another cell-related class, CellSpace. It holds a list of lists of cells, amounting to a 2D array, and is used primarily to find a cell at a given x, y. Its at method is used 72 times(!). Once in Cell, once in main, and seventy times in tests. It also supports random_available_cell, used currently three times in main and not otherwise, as part of placing rooms randomly.

Design Decision, For Now

I think we’ll create an equivalent method to PathFinder find_path in Cell, and eliminate the PathFinder. To do that properly, we should replace our PathFinder tests with new tests against Cell. No biggie, I think we only have two of them.

Cunning Plan …

If we create the method we want in Cell, essentially by copying the method over from PathFinder, and then have PathFinder call it, our existing tests will tell us when we have it right. Then we can unwind the tests, and then remove PathFinder. Let’s do it.

class PathFinder:
    def find_path(self, source: Cell, target: Cell, room_list) -> list[Cell]:
        def can_use(cell):
            return cell.is_available or cell.room in room_list
        reached = source.path_map(can_use, 1.0)
        path = []
        start = target
        while start is not None:
            path.append(start)
            start = reached.get(start)
        return path

That gives us:

class Cell:
    def find_path(self, target, room_list):
        def can_use(cell):
            return cell.is_available or cell.room in room_list
        reached = self.path_map(can_use, 1.0)
        path = []
        start = target
        while start is not None:
            path.append(start)
            start = reached.get(start)
        return path

Now we call from PathFinder:

class PathFinder:
    def find_path(self, source: Cell, target: Cell, room_list) -> list[Cell]:
        return source.find_path(target, room_list)

Green. Commit: moving path-finding to Cell.

The two tests are easily converted:

class TestPaths:
    def test_path(self):
        bank = CellSpace(10, 10)
        source = bank.at(3, 3)
        target = bank.at(7, 6)
        dist = source.manhattan_distance(target)
        assert dist == 7
        path = source.find_path(target, [])
        assert len(path) == dist + 1
        assert path[0] == target
        assert path[-1] == source
        distance = sum(s1.manhattan_distance(s2) for s1, s2 in pairwise(path))
        assert distance == dist

    def test_path_with_rooms(self):
        bank = CellSpace(30, 30)
        size = 5
        source = bank.at(10, 10)
        target = bank.at(25, 25)
        source_room = RoomMaker().cave(number_of_cells=size, origin=source)
        target_room = RoomMaker().cave(number_of_cells=size, origin=target)
        path = source.find_path(target, [source_room, target_room])
        assert len(path) == 1 + source.manhattan_distance(target)
        assert path[0] == target
        assert path[-1] == source

There are no references to its methods but a few references to PathFinder. Ah, Suite needs a touch:

    def find_path_cells(self, suite) -> list[Cell]:
        source, target = self.find_closest_pair(suite)
        cells = source.find_path(target, [source.room, target.room])
        on_path = cells[1:-1]
        return on_path

We are green. Remove PathFinder. Still green. Run main as an extra check. Commit: remove PathFinder, work done in Cell.

main gave me this lovely map:

map with nice paths

So there’s a nice hour’s pleasant cruising, let’s sum up.

Summary

An experiment down at the bottom, in the generate function that generates a flood of cells outbound from a source cell, gave us a pleasingly random path for more or less diagonal paths. (Horizontal and Vertical paths are still quite straight. We might want to change that.)

Inserting a randomness parameter allows us to adjust the intensity of the randomness, and offers the prospect, as yet unfulfilled, of pulling that parameter up to allow dungeon creators to adjust that parameter as desired.

Inspecting the code led to identifying PathFinder as not bearing its weight. We found a very smooth path to moving PathFinder’s capability to Cell, eliminating PathFinder entirely.

Emphasizing That …
There was a very nifty trick in that sequence, and I’m proud enough of it that I want to underline it. We moved the operational code for pathfinding over to Cell, modifying it to make it suitable as a method there. Then we changed PathFinder to call that code. Voila! All the tests and all the production code are using the new method.

Then, at our convenience, we changed tests to speak directly to the new method, and when that was done, which could have taken place over days or weeks, PathFinder had no more references and we snipped it.

Forwarding from the old class to the new method is what made that go nicely. I don’t always remember to look for that possibility, so I underline it here to wedge it into my mind.

Along the way, we have noticed that generate is rather a large method by local standards: 19 lines long. We’ve made a note to consider it for refactoring. We also noticed that Cell is rather a large class, with around 20 methods. We’ve made a note to look into that as well.

It might be OK to have Cell be that powerful: dungeon creation is all about finding, allocating, examining, and searching cells. But it might be that there are some helper classes or something that would simplify things, if you swing that way. At some point in the past, I must have been thinking that PathFinder would bear more weight, but that doesn’t seem to be the case. Perhaps some other subset of cell behavior will appear. We’ll see.

Finally, I think we have some “story” work that we should do. Ideas might include:

  • rectangular rooms
  • partitioned rectangular rooms (castle interiors?)
  • standard cavern rooms (we can build them but they’re not integrated well)
  • those long cavern-like path rooms seem promising. could they be made more capable?

I still feel that there should be some easier way to create rooms in various styles. The idea of a “little language” didn’t pan out, but I haven’t given up on the idea.

And, of course, there is the larger question of what this thing is good for, if anything. Are we going to build a little dungeon-crawling game on top of it? Or is it time for something completely different? We’re here for fun and exercise, and so far I’m happy with both. Tomorrow or next week? Who knows, anything could happen.

But for now, new capabilities are easing into the code and the code remains alive and easy to change. Life is good here in the dungeon.

See you next time!