Wandering Thoughts

We can make most of our paths wander, except for the straight left-right or up-down ones. I’ve had an idea. Is it a good one? I decide to use a prior idea, in an interesting spike.

When we compute a path, we generate a “flood fill” of the usable cells, starting from one of the desired end points of the path. As we generate those cells, we create a “path map”, which is a dictionary of cells, where each cell cell points to a predecessor of that cell in the flood fill, leading back to where we started. When the flood reaches the other end point, we can use the path map dictionary to track back from there to the starting cell.

When the path between source and target is somewhat diagonal, there is generally more than one minimal path: we can go north and then west, or west and then north. However, when the path is vertical or horizontal, there is only one minimal path, straight as an arrow from source to target.

And we like that, except when we do not like it. We’d like to have a way to perturb such a path, making it wander a bit, even if it is a bit longer than the minimum. Until about 11 PM last night, I had no good ideas for how to randomize that path. I had a couple of OK ideas:

• From the path map first created, select a small number of waypoints, cells off the straight path. Then map paths between those points, in series. The result should wander nicely.¹
• Given the path, devise transformations of the path to make it more wandersome. Wanderish. Make it wander more. Apply some of those transformations.

The latter of these does not appeal to me much at all. I’m not quite sure why: I think it has to do with the fact that one would have to verify that the path-warping transformation was legitimate given available space. Anyway, I don’t like it much.

Until I typed it above, I had shelved the first idea, but I’m not quite sure why. I think it was that I didn’t see quite how to wire it in. This morning, just now, I have a better sense of how to do that one, and it may win out.

The idea that I had last night goes like this:

Given that we have a straight path, and given that we want to make it wander, use a different algorithm for tracing the path. Instead of just stepping from cell to dict[cell], every now and then, at random, step instead to an unused neighbor of cell, and continue from there. That would put a little kink in the path, and depending on the randomness setting, should do a pretty decent job of wanderizing² the path.

What shall we do?

I’m trying now to decide between the waypoint idea and the one above, which needs a name, unless I decide not to do it.

The waypoint idea, it seems to me, could be applied all the time. We call for a path between two points, specifying how many waypoints to use, zero or up to some small number like one or two, and just apply it no matter whether the path would have been straight or not. It does have the disadvantage of needing to compute more than one path map, which is slightly costly, but it’s not like we have to compute a million dungeons per minute.

I’m leaning toward waypoints. It seems to me to be more algorithmic, more elegant, more technically correct, less ad hoc, I don’t know, I like it better.

I’m envisioning a new method on cell. My first thought is something like

find a path from source to target via [waypoint_1, waypoint_2, …]

That would unwind to finding a path from source to waypoint_1, from waypoint_1 to 2, etc. Oh, and we know how to do that zip thing to get the adjacent pairs.

Let’s do a spike …

Before committing too deeply to this, I’d like to see what it might look like, and to get a sense of what the code might be like. Let’s hammer main to try it.

def main():
    space = CellSpace(64, 56)
    # random.seed(234)
    dungeon = Dungeon()
    maker = RoomMaker()
    start = space.at(5, 28)
    s = maker.diamond(number_of_cells=5, origin=start)
    dungeon.add_room(s)
    target = space.at(60, 28)
    t = maker.diamond(number_of_cells=5, origin=target)
    dungeon.add_room(t)
    waypoint = space.at(32, 8)
    path = start.find_path_via_waypoints(target, [s, t], [waypoint])
    room = Room(path, path[0], 'path')
    dungeon.add_room(room)
    view = DungeonView(dungeon)
    view.main_loop()

class Cell:
    def find_path_via_waypoints(self, t, rooms, via):
        return self.find_path(t, rooms)

So far we just call the regular path, so we get a nice straight path across:

But now let’s try this:

    def find_path_via_waypoints(self, t, rooms, via):
        points = [self] + via + [t]
        cells = []
        for p1, p2 in zip(points, points[1:]):
            cells += p1.find_path(p2, rooms)
        return list(set(cells))

We just go through the list from self to target with all the via points in between, pairwise. The result is delightful:

I want to try something more bizarre:

    waypoints = [space.random_available_cell() for _ in range(5)]
    path = start.find_path_via_waypoints(target, [s, t], waypoints)

That should give us a path that wanders all over, even possibly crossing itself, and it does. For example:

That’s with 5 intervening waypoints. I couldn’t resist trying 30 and 50:

Those are rather interesting all on their own, it seems to me.

What have we learned?

I think we have learned that this simple scheme is quite good for making formerly straight paths be more wanderful. It appears to me that we can, if we choose, default the list of waypoints and always use this function, keeping find_path private should we wish to.

It seems clear that we can still get irritating straight segments unless we place enough waypoints, close enough together. It’s really not so good to place them too far away from the minimal path.

I recall something I read about making wandering paths by adding a sort of sine wave to the nominal path. Suppose we did something like this:

• Consider the geometric line between source and target;
• At suitable intervals along that line, select points off the line by a small distance;
• Use those as waypoints.

“Suitable” probably means “around ten cells”, and “small distance” is probably around five to ten. Random guesses, but our space is just 64x56 cells.

Anyway an interesting spike experiment. Let’s sum up.

Summary

Perhaps most interesting—at least to me—is that what seemed to be the best idea when I sat down, turned out not to seem best when I set out the few ideas that I had. It helped that I had a glimmer of the waypoint idea turning out to be simple, though I didn’t really see until I tried to write it, just how simple it was.

If there is a lesson for me here, it is that I do better when I have more than one possible solution in mind. And it’s clear that this is the case. If we only have one solution in mind it is clearly the worst idea we have. When we have more than one we can choose a relatively good idea.

Something like that, anyway. OK, I jest, but in fact having more ideas is surely always better than having fewer, unless we let ourselves be stalled in the decision process. I am impatient enough, and have been punished enough for not getting things visible, and for speculating instead of trying, that I am not likely to get stuck deciding. I am probably a bit more susceptible to trying too many things, but so far that doesn’t really seem to be a problem.

The spike illuminates the fact that the number of waypoints, and their positions relative to the “true path”, will be important. Too few, or too great a distance away from the true path, makes for less interesting wandering, and more straight segments than we might like.

I think we would like to have the waypoints “tend” in the direction from source to target, rather than zig-zagging back and worth. We could sort the waypoint list by distance. Might try that later, just to see what we get. Distance from waypoint to target would still allow a lot of zigzag. Sorting them for shortest distance from the prior might be good. Something to think about.

We have not addressed the selection of legitimate waypoints, ones that are accessible from the source and target. Not all available cells are accessible, because they could be isolated or walled off by one or more rooms surrounding them. However, the path map between source and target only contains accessible points, so we can use that, at the cost of one additional path map.

I did notice that the 30 and 50 pictures take discernible time to create, a second or two. But we create a map only rarely, so a second or two to do it shouldn’t be a problem.

So. A very interesting thought twist, again leading me to work on something other than I had expected, and, again, something very likely better. I think that means I should hold on to my ideas lightly. It might, however, suggest that I’m just a terrible planner. Works for me: I really don’t believe we can effectively plan a software project. I believe we can track its progress and determine whether we are still happy. I believe we can steer it to deliver more value rather than less. But predict it? Not in my very long experience.

A fun morning, with an interesting demonstration of an idea, and I’m sure we’ll use this scheme going forward. Until we stop.

See you next time!