Hello, loves!

I need a little something to do. Here’s something that could be done. Better code, not as easy to understand as it might be.

There is absolutely no reason to work on this, except that I want to. There is this odd code in DungeonLayout:

class DungeonLayout:
# how does this relate to Flooder?
    def find_path(self, source, target, room_list):
        def can_use(cell, _parent):
            return self.is_available(cell) or self.get_room(cell) in room_list
        reached = self.path_map(source, can_use, 1.0)
        path = []
        start = target
        while start is not None:
            path.append(start)
            start = reached.get(start)
        return path

    def path_map(self, source, can_use, randomness=0.0):
        reached: dict[Cell, Cell|None] = {source: None}
        for c, _ in (Flooder(layout=self, origin=source)
                .select(can_use)
                .randomness(randomness)
                .flood()):
            for neighbor in self.neighbors(c):
                if neighbor not in reached and can_use(neighbor, c):
                    reached[neighbor] = c
        return reached

OK, what is in the “path map” that the method returns? We are trying to build a path between the rooms in room_list. We use it to find a path between two suites of rooms, so we allow the path to use any available cell or any cell in either of the suites. (This is odd, in that we cannot really wind up using cells that are in other rooms but if we do find any they’ll just be deleted and the path will still connect the suites.)

(I wonder if the resulting path room might be split into discrete segments. I don’t think so, as we start with two cells that are nearest together.)

Anyway, in path_map, starting from source, we generate all the cells that are available (not in other rooms) or in the rooms we are trying to join. As each cell is generated, curiously, we locally create the neighbors and set a dictionary entry with that new cell pointing back to the one just generated - a path back from wherever we end up to the source.

It seems to me that the value function itself ought to be able to do that, simplifying our problem. Hm.

We wish we had this:

    def path_map(self, source, can_use, randomness=0.0):
        reached: dict[Cell, Cell|None] = {source: None}
        for cell, parent in (Flooder(layout=self, origin=source)
                .select(can_use)
                .randomness(randomness)
                .flood()):
            reached[cell] = parent
        return reached

OK, what if we provide this initial_value and next_value:

    def path_map(self, source, can_use, randomness=0.0):
        reached: dict[Cell, Cell|None] = {source: None}
        for cell, parent in (Flooder(layout=self, origin=source)
                .select(can_use)
                .initial_value(None)
                .next_value(lambda c, _v: c)
                .randomness(randomness)
                .flood()):
            reached[cell] = parent
        return reached

The tests pass, and there are in fact tests for this, which fail with other functions for next_value. The only issue is that I sort of stumbled into this working. I thought we’d need to pass the parent cell into the next_value function, to kind of pay it forward. Anyway, this test passes.

    def test_find_path(self):
        layout = DungeonLayout(5, 1)
        map = '''1   2'''
        origin = Cell(0,0)
        target = Cell(4, 0)
        path = layout.find_path(origin, target, layout.rooms)
        assert path == [Cell(x,0) for x in reversed(range(5))]

If we print the result list, just for humans, we get this:

[Cell(4, 0), Cell(3, 0), Cell(2, 0), Cell(1, 0), Cell(0, 0)]

Which is certainly what we had in mind. It also works if the DungeonLayout isn’t just a line, such as with DungeonLayout(5,4), although in that case the path_map will be much larger as it’ll map the distance to every cell it can access.

I still don’t quite see why lambda c, _v: c doesn’t produce every cell looking at itself. Clearly it is producing every cell looking at its predecessor in the generation. And that’s what we want. Let’s stare at the code a bit more:

    def flood(self):
        self._to_be_delivered = OrderedDict([(self._origin, self._initial_value)])
        self._delivered = set()
        while self._to_be_delivered:
            current_cell, current_value = self._next_to_deliver()
            yield current_cell, current_value
            self._delivered.add(current_cell)
            self._enqueue_relevant_neighbors(current_cell, current_value)

Ah, maybe it is coming to me. We begin the production by yielding (origin, initial_value) which in our case is (origin, None). Then we produce the selected neighbors into _to_be_delievered:

    def _enqueue_relevant_neighbors(self, current_cell, current_value):
        for neighbor in self._relevant_neighbors(current_cell):
            self._to_be_delivered[neighbor] = self._next_value(current_cell, current_value)

So when we evaluate _next_value the first time, we call lambda c,v: c with origin, None and we return origin as the value for each of the neighbors. Got it. Now I’m convinced that it works, and once again am reminded that recursive thinking is not for humans.

The tests say it works, my head says it works, so let’s sum up.

Summary

There are quite a few uses that one might have for flooding, but the primary two are getting the distance to things, and finding a path to things. While one usually only wants one distance or one path, you kind of have to run the whole flood to be sure of getting what you want, and of course what we have in the path map essentially embodies the path from anywhere to where you want to be. (I think it is actually the reverse of what the code says, but that’s for another day.) With today’s changes, we managed to fold the path-finding bits into Flooder itself, using the new lambda that returns a cell’s parent as the lambda’s value.

We should probably fold those two primary uses into the Flooder’s fluent interface. Manhattan Distance is the default, but we could provide a convenience method for the parent version. We may look at that at some other time.

For now, we have again simplified some code and only slightly confused YT. And I am now convinced that it’s right, just that things like that are tricky. Possibly there is a less tricky way to express it in our code, but we’re not going to find that today. Today, we’re going to take a final break from coding, until next time!