It is certainly no surprise that the day after something first works, there is plenty of room for improvement. We’ll be looking for some of those things this morning. We learn from a small step.

As GeePaw Hill puts it, we are in the business of changing code. Among the implications of that notion, for me, is the fact that the code is never done. We are always open for making it better. We wouldn’t generally make some sweeping rewrite the universe kind of change, but we’ll often make small changes. Sometimes those small changes will have significant effect, but gaining significant effect with small changes is generally the only way we can proceed: no one wants to wait while we dig away for days, weeks, months. That’s how projects fail and get cancelled.

So it is never a surprise when there are improvements to be had, and today is one of those days. In addition, there is a problem.

I noticed while making pictures of maps yesterday that once in a while main would crash. A quick glace at the error told me that it was failing to find a path between two Suites. A little thought tells us how that might happen: imagine four suites, one in the middle of each side of the game space, touching the edge. If we happen to build a path from the top one to the bottom one, no path between the side ones is possible. That won’t do.

How might we resolve this issue? I already have a plan and I’ll list it first, but let’s see what else we could do instead:

  • Allow paths to cross each other.
  • Detect the error, toss out that dungeon, try again.
  • Devise some way to try alternative connections until one works.
  • Use some kind of maze-solving algorithm to maintain connection always.
  • Use some ad-hoc method to maintain connection always.
  • Come up with some idea that we don’t even have yet.

There is probably some aphorism somewhere that suggests always thinking of a few alternatives before deciding what to do, instead of fixating on the first idea that comes to mind. There is also my possibly perverted version of Kent Beck’s famous question: “What is the simplest thing that could possibly work?”

I have been heard to say “Do the simplest thing that could possibly work”. You’d think this was a guaranteed way to get into deep trouble, but I find that, in the small, doing the simple thing and then improving it works out rather well. Improving needs to include getting all the capability into the right classes and methods, but after that, when something needs to be changed, the changes generally affect only one or two classes, not all the code everywhere.

Of the list above, the only alternatives that really appeal to me are to allow paths to cross, and using some scheme to maintain connection always, which I only thought of just now.

As things stand now, we build our rooms, generally in random locations, and then connect them. What if instead we were to build a room, then build a random path of some random length possibly including zero, and then build another room? We would certainly be connected always, and if we allowed zero-length paths we could even get the room-against-room look that we kind of like.

However, it won’t always work well. It would be possible, for example, to build a room near top right, touching the top, make a path, build a room in middle right, touching the side, build a path north, build a room in the corner … and that room is isolated and we are stuck.

Of course if we tried a second path out of room 1 or room 2, we could reach down toward lower left and be OK, but that starts to get kind of messy and hard to imagine how we’d code it. Sure, we could figure it out, but the complexity feels a bit higher than the original idea suggests.

Let’s do this: let’s try the path-crossing idea, because it does seem simple, and see how we like it. If we don’t like it, or get a better idea, we should be able to change it fairly readily.

There is a picture from yesterday that shows an issue:

map with crossing path

Look at the crossing near the center. There are red and green walls there, indicating that you can’t move from the vertical path into the horizontal path. The paths are separate rooms, you may recall, so the wall finding logic wants to put a wall where they cross.

We haven’t dealt with doors yet, and perhaps we should prioritize that, but today we need to fix the trapped path issue and we want to fix it by allowing paths to cross. I have an idea:

Currently, each path is a separate room:

class Suite:
    def __init__(self, room_set):
        self.room_set = room_set

    def find_path(self, suite):
        source, target = self.find_closest_pair(suite)
        finder = PathFinder()
        cells = finder.find_path(source, target, [source.room, target.room])
        on_path = cells[1:-1]
        room = Room(on_path, on_path[0], 'path')
        return room

We currently call that method with this code from main:

    for s1, s2 in zip(suites, suites[1:]):
        path = s1.find_path(s2)
        dungeon.add_room(path)

My idea is to make all the paths be a single room. It would be a disconnected room, but I don’t see why that would be a problem.

Let’s refactor find_path and rename it along the way:

class Suite:
    def find_path_room(self, suite):
        on_path = self.find_path_cells(suite)
        room = Room(on_path, on_path[0], 'path')
        return room

    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 suspect we want a set of cells here but we can wait for that. Commit this, we are green: provide find_path_cells.

Now an experiment in main:

def main:
...
    suites = dungeon.define_suites()
    path_cells = []
    for s1, s2 in zip(suites, suites[1:]):
        path = s1.find_path_cells(s2)
        path_cells.extend(path)
    path_unique = list(set(path_cells))
    path_room = Room(path_unique, path_unique[0], 'path')
    dungeon.add_room(path_room)
...

We accumulate all the path cells, scrunch them for uniqueness, because we probably shouldn’t be putting duplicates in a room collection, and make a room named ‘path’ from the cells. Here are a couple of maps that come out.

map with crossing paths

map with crossing paths

The crossings are no longer blocked. The vagaries of path selection give us some interesting wide paths and little niches along the path. The surprise, which should not be a surprise, is that all the paths seems straighter than they did before. That will be due to the fact that we can cross them now and before this, sometimes a path had to wind all around to avoid a crossing. (And sometimes, we’d be trapped. That’s why we’re doing this.)

Let’s reflect.

Reflection

We have now had two rather different approaches to connecting the rooms. This one draws rather direct paths between rooms, finding a close pair of cells to connect. Previously we were drawing those random cave-like rooms, with a bias for moving in one direction for a long time, which gave us very natural-looking caverns, like this one:

very cavern-like map

We set out to produce these more rectangular paths based on this sentence from a previous article:

As close to good as this is for a cavern, we want to be able to support other kinds of layouts such as a rectangular castle kind of thing or a sort of village arrangement or whatever we might come up with, so I think we’ll have to be able to create paths between suites, and perhaps even to control what kind we want, straight lines where possible, and so on.

That concern got us working on the “little language” idea to make it easier to specify what sort of dungeon we created. That idea fizzled out, because, so far, the facility I imagined wasn’t easier or more capable than just coding in Python. Perhaps we should revisit that topic and try to come up with a better idea.

As for the wandering cavern-like paths, I really do like the look of those, and would like to make them a bit more capable without losing their attractive randomness.

We have, in Dungeon, the notion of “fully-connected”, which creates a suite starting in the first room and determines whether that suite contains all the rooms. If it does, the dungeon is fully connected. We’re not using that in main, but we could. I wonder if it would be difficult. Let me take a look.

No. I made a couple of swings at a hack and got some infinite loops and some crashes. Needs a bit more brain than I have left, or, better yet, a better approach than grotesque hackery. We’ll try again later.

I’m ready for an iced chai. Let’s break and sum up.

Summary

A simple refactoring gave us a method to produce the cells of a path, pulled out of a method that produced a room containing those cells. Then a reasonably simple change to main showed that if we make a single room containing all the path cells, the paths can cross, which will avoid trapping and being unable to connect a dungeon. That change, in my view, shows feasibility but does not show a good way to do it.

My failed hackery just above tells me that we probably can build the path incrementally, with just enough connections to fully connect the dungeon, and it tells me that it is more tricky than I thought, since three or four quick slashes didn’t work.

Based on today’s experience, plus the preceding six and a half decades, I think I’d like to have things rigged so that we can do at least these things:

  • Choose readily between simple paths like today’s, and the more random ones from before;
  • Choose to build in connectivity after rooms are created or as we go;
  • Be certain that we will never loop or crash while building the dungeon.

I’d like also to come up with some kind of “style” notion that guides dungeon building either toward regular-shaped rooms with paths, compact regular shaped rooms like a castle, irregular rooms like a cavern, and so on. At this writing I don’t even have an idea about what that would look like. Maybe it’s just a dispatch to a few different algorithms: maybe it could be some kind of weighted semi-intelligent dynamic thing. I don’t know, I just think we’d like to have it.

For today, we have paths that will clearly work, and they’re not entirely boring. A decent small step.

See you next time!