We still get straight paths sometimes. I have an idea …

When the cells we’re connecting are not directly opposite each other, we tend to get nice-looking wandering paths. But when they are directly opposite, either horizontally or vertically, we still get straight paths. The reason is that when cells are somewhat offset diagonally, there is more that one minimal path, but when they are directly opposed, there is only one.

My idea is this: we’ll break up the path into three sub-paths. We build the basic capability last time. The path finding code can accept “waypoints”, and it will run a path via those extra points:

class Cell:
    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))

Perhaps always, or perhaps only if the path seems insufficiently diagonal, we’ll pick two points, one about a third of the way along the path, and upward some small number of cells, perhaps 5, and, about two-thirds of the way along, pick a point about 5 cells downward.

I say “upward” and “downward”. If the path is horizontal, up and down. If vertical, left and right. We’ll finesse that question simply: we’ll compute the points as if the path were horizontal and then rotate them to the path’s actual angle. Rounding, truncation, etc.

There is one more possible issue: it is possible that the points we’d like to use are not available. Our path could be going through some narrow region. So we’ll have to check the points to be sure they’re accessible.

Seems like a lot …

It does. I almost don’t have the energy to do it. Is an occasional straight path that big a deal? Well, we’re going to pretend that someone here thinks it is a big deal and wants us to try this idea. So, OK, we’ll do our best.

Let’s work with some tests. I think the work will mostly involve Cell, so we’ll set up our tests there. I think I’ll start with some plain “code” tests and then see what looks like it belongs where. I often start that way when creating a new class, or a capability that is a bit tricky. This is a bit tricky, it’s going to involve tangents, sines, and cosines.

Ah. I forgot that we have a separate file ‘TestPaths’. We’ll use that.

With a little more trouble than I’d have liked, this passes:

def rotate(xy, angle):
    x, y = xy
    x_rot = x * math.cos(angle) - y * math.sin(angle)
    y_rot = x * math.sin(angle) + y * math.cos(angle)
    return x_rot//1, y_rot//1


    def test_path_offsets(self):
        space = CellSpace(30, 30)
        source = space.at(5, 5)
        target = space.at(5, 25)
        vec = source.vector_diff(target)
        assert vec == (0, 20)
        angle = math.atan2(vec[1], vec[0])
        length = source.distance(target)
        up = (length//3, 5)
        down = 2*length//3, -5
        up_rot = rotate(up, angle)
        down_rot = rotate(down, angle)
        assert up_rot == (-up[1], up[0])
        assert down_rot == (-down[1], down[0])

Since the source-to-target line is vertical, the rotation swaps and negates as shown. Because we don’t have a vector type in this app, I had to do the math by hand, with help from Cell:

class Cell:
    def vector_diff(self, target):
        return target.x - self.x, target.y - self.y

I was able to convince myself that a method on two cells could legitimately return the vector difference between their coordinates as a tuple, and I freely grant that’s a bit of a reach. I don’t see how to make the case at all for the rotate method, which here is an operation on two tuples. And that’s before even thinking about the //1 bit to truncate them back to cell integer coordinates.

Maybe we need a little object to contain these ideas. Let’s try that, with a new test, still in the TestPaths file.

    def test_path_helper(self):
        space = CellSpace(30, 30)
        source = space.at(5, 5)
        target = space.at(5, 26)
        up_expected = space.at(-5, 7)
        down_expected = space.at(5, 14)
        helper = PathHelper(source, target)
        via = helper.compute_via()
        assert via == [down_expected, up_expected]

Maybe that’ll do what we want. It should be close, anyway. Let’s find out by writing PathHelper.

OK the test was wrong in two regards. Correct test:

    def test_path_helper(self):
        space = CellSpace(30, 30)
        source = space.at(5, 5)
        target = space.at(5, 26)
        up_expected = space.at(0, 12)
        down_expected = space.at(10, 19)
        helper = PathHelper(space, source, target)
        via = helper.compute_via()
        assert via == [up_expected, down_expected]

I had the order of the return backwards, and the expected values were not offset by the starting points.

The PathHelper that works looks like this. (Look with caution, it’s not pretty.)

class PathHelper:
    def __init__(self, space, source, target):
        self.space = space
        self.source = source
        self.target = target

    def compute_via(self):
        sx, sy = self.source.xy
        tx, ty = self.target.xy
        dx = tx - sx
        dy = ty - sy
        length = math.sqrt(dx*dx + dy*dy)
        theta = math.atan2(dy, dx)
        up_offset = rotate((length//3, 5), theta)
        up = self.source.at_offset(*up_offset)
        dn_offset = rotate((2*length//3, -5), theta)
        dn = self.source.at_offset(*dn_offset)
        return [up, dn]

We are green, and I am somewhat wrung out. Commit: Path offsetting in progress. PathHelper initial class.

Let’s bring rotate into PathHelper as a method, probably static.

class PathHelper:
    @staticmethod
    def rotate(xy, angle):
        x, y = xy
        x_rot = x * math.cos(angle) - y * math.sin(angle)
        y_rot = x * math.sin(angle) + y * math.cos(angle)
        return int(x_rot), int(y_rot)

Green, commit: add rotate method to PathHelper.

I’m definitely tired after the mashing. Let’s sum up, starting with a description of why I’m tired.

Summary

The objects are not helping enough. When that happens, we need to write things out longhand that could be written more compactly, clearly, and easily, if the objects were more helpful.

In the compute_via above, we had to dissect the Cell to get coordinates, do two calculations that look very much alike on each coordinate, several times, and then reassemble the coordinates to get Cells back, which are what we needed.

Along the way we needed to make sure to get down to integer values for the coordinates. We don’t really care whether we round or truncate: we’re just trying to mess up the coordinates a bit, but we had to do it right. I was using //1, which seems not to work in Python. Probably that’s a Lua thing. In Python we say int().

Now, our dungeon is really built from cells in an array. There aren’t really x and y coordinates in the vector sense. It’s just that here, we wanted to do a bit of vector arithmetic.

I’m not sure at this moment what I’d like to do about this. Options include:

  • clean it up a bit, leave it alone;
  • refactor to provide the few vector operations we need;
  • use Python numpy, which surely has everything we need, plus everything we don’t.

My guess is that when I come back, not so beat, I’ll press hard on cleaning up, including possibly creating some additional classes, maybe vector-like. We’ll begin by just mushing things around to see if we can get them to fit together better. Then we’ll see where that leads.

But the good news is that we’ve made a step in the direction we wanted: we’re computing small offset waypoints from a straight path.

By way of proof of that, here’s a map drawn using the new compute_via:

map with a couple of offsets

Not bad for clear across the screen. I think that most of our paths will be shorter than that, and we could readily change our compute_via to make more bumps if the path is long.

Progress. Inch by inch. Still work to do, including making sure the points are usable, but we are moving forward. That’s all we ask.

See you next time!