Our minimal paths are too straight for most purposes. Is there a nice way to make them adjustably not so good? Is ‘adjustably` a word? It is now. A nice discovery arises.”

So far, we’ve come up with two ways of making our dungeons be fully connected. The first was just to throw random erratically-shaped rooms into the mix until the result was connected. The second, which we’ve been working on the past few days, is to create a minimal path between two points deemed to be the closest together between the two suites we’re trying to connect.

Neither of these is ideal. The irregular room idea makes a very full-looking dungeon, which might be good sometimes but I’m not comfortable with making so many more rooms just to connect up. In addition, it’s not guaranteed to work, although I think we could probably fix that.

The minimal paths are just too square. They have a strong tendency to go straight over then straight down:

map with very straight paths

Ideally …

Ideally, it would be quite nifty to find a single path-finding algorithm that could be given a single parameter controlling it, such that at the low end, we got these square paths, and at the high end we got very irregular paths, not even constant width, that eventually get where we sent them. That’s ideally. Right this moment, I do not know how to do that.

I have a few p-baked ideas—for very small values of p—that might be productive:

  • Take a minimal path and subject it to some kind of function that messes it up;
  • Calculate the flood fill and then follow it imperfectly;
  • Write some kind of new target-seeking function that tends to move toward the target cell but only randomly.

A bit of searching turns up some interesting pages, including this one on procedural generation. And this Reddit post is a complete treatise on the subject. Unfortunately, the TinyKeep product and site seem to be somewhat defunct, as are many of the other links starting from the above. Still, we get some ideas and keywords for further study, should we care to go in the serious technical direction.

Clearly there is a lot of interesting stuff out there, minimal spanning trees, Voronoi Tessellation, Delaunay Triangulation, and so on. As it happens, I have a couple of degrees in mathematics, so probably somewhere in my history I became facile enough to learn about those things and implement them. And maybe, at some point, we’ll go that way.

Delaunay Triangulation has the interesting property that it defines paths between rooms such that all the rooms are connected, but no paths have to cross. Now, I kind of like paths that cross, as they seem more interesting, but crossing-free paths might be desirable as well. That bumps up my interest in that algorithm. My recollection is that you build the complete tree of connections and then eliminate connections until any further eliminations would disconnect the rooms.

All that is useful if we decide to proceed down the path of well-defined algorithms. And, in a real dungeon product, we might well do that. However, my purpose here is a bit different. Most of the time, I like to follow my nose, evolving the code, showing again and again how we can make well-structured code out of cruft, without the need for a massive rewrite of the universe. And, sometimes, along that path, we might replace some ad-hoc scheme with a better, more formal scheme, again to show that we can do it without too much disruption.

We might do that at some point here. We might not.

Our Code …

I wanted to review how we create our irritatingly square paths. I think we might be able to make them less square, perhaps even in more than one way. So let’s belay the speculation and look at how we find our current square paths.

It all begins in Dungeon:

class Dungeon:
    def add_path_room(self):
        room = self._straight_path_room()
        if room:
            self.add_room(room)

    def _straight_path_room(self):
        cells = self._straight_path_cells()
        if cells:
            return Room(cells, cells[0], 'path')
        else:
            return None

    def _straight_path_cells(self):
        cells = []
        suites = self.define_suites()
        for s1, s2 in zip(suites, suites[1:]):
            cells.extend(s1.find_path_cells(s2))
        return list(set(cells))

From Dungeon we use Suite’s find_path_cells:

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

That drops right into PathFinder’s find_path. Pretty soon we’ll find out who does the work here, I’m sure.

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)
        path = []
        start = target
        while start is not None:
            path.append(start)
            start = reached.get(start)
        return path

Getting closer. Let’s look at path_map:

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

Starting from the cell in hand, we generate its immediate neighbors (that we can_use) and for each neighbor, we make an entry in the reached dictionary pointing back to its predecessor. The cells one step away from our initial cell point to it; the cells two steps away point to whichever one-step cell leads to them, and so on. We accept the first occurrence of neighbor, but we generate the neighbors in random order. That sample thing was supposed to make the paths more random but it doesn’t seem to have much effect. I remove it, committing: removed random sample from cell path_map, seems to have no useful effect.

So the path_map produces a dictionary of cells pointing to a predecessor cell, leading back to the starting point. PathFinder find_path just tracks backward, producing the minimal path.

I’m pretty sure that the random.sample bit was supposed to make the algorithm less likely to choose a straight line but has no effect, because no matter what order we look at neighbors in, we’ll give each one the right predecessor.

I think I’m going to have to draw a picture of this to see whether there is something clever to be done here. In aid of that, let’s have a glance at generate:

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)

What if we were to randomize generate? Let’s try it, we’re at a save point.

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)

Oh yes! That’s what I’m talkin’ about!

map with nice jagged paths

map with nice jagged paths

Well, that’s interesting. By generating cells in random order, we have a still-minimal path that isn’t so bloody square and has a pleasing random aspect. Paths between rooms with either horizontal or vertical overlap will still generate straight paths, since we have already selected two directly opposing cells as closest, which they are.

I have a bagel to eat and a chai to drink, so let’s sum up.

Summary

We have considered some very technical solutions to our path issue, none of which really promised more randomness, just more certainty of minimality. And minimal connectivity might still be interesting: we might follow those paths later, if we need to or if they seem amusing. But what we found was that a one-line change to how we generate neighboring cells produced some very attractive paths. We would find it easy enough to switch from square to jagged: I don’t see how to adjust how jagged they are … unless … unless the generator only randomized the collection sometimes … hmm … interesting …

I think that some of this code may not belong quite where it is, but we’ll explore that in a code review session sometime soon. I’ve made a note of one idea for that, moving the randomization down a level into cell.neighbors. We’ll see.

Is there some kind of lesson here? I’m not sure. Certainly we’ve found a very simple solution to our actual need, rather than trekking down some minimal spanning Voronoi Delaunay thing. There may be valuable meat in those algorithms, and in our copious free time we might study them, and we might find them desirable. But today, we change half a line of code to get an effect that we quite like. That’s rather nifty. Can’t chalk it up to any particular wisdom: it’s just nice.

See you next time!