A nudge from a friend impels what seems like a much better idea. But appearances deceive: it’s more tricky than I thought. We build an interesting new capability.

We’re working toward finding cells of maximal distance from a given cell. The current scheme traverses all cells in the Dungeon and assigns them an associated value of their distance from the given point. We have methods in Cell and elsewhere for this:

    def furthest_cells(self):
        max_distance = self._compute_path_distances()
        return [cell
                for cell in self.space.cells
                if cell.is_in_a_room and cell.path_distance == max_distance]

    def _compute_path_distances(self) -> int:
        self.path_distance = 0
        max_distance = 0
        for cell in self.generate_in_rooms():
            for neighbor in cell.neighbors_in_rooms():
                if neighbor.path_distance is None:
                    one_further = cell.path_distance + 1
                    neighbor.path_distance = one_further
                    if one_further > max_distance:
                        max_distance = one_further
        return max_distance

As I look at this, I think I see a defect, because there are these methods:

    def generate_path_distances(self) -> int:
        self._clear_path_distances()
        return self._compute_path_distances()

    def _clear_path_distances(self):
        for cell in self.generate_in_rooms():
            cell.path_distance = None

If we use furthest_cells, we’re not going to get the clear done. I’d prove that, but the fact is we are here to replace all this anyway.

What follows was triggered by friend Bill Wake, who has some really interesting Swift Twitch sessions that you should check out. Bill tooted:

@RonJeffries To me, feels a little weird to have the distance attribute in the cell since it’s sort of only valid temporarily and only in reference to a sometime “global variable” target.

I certainly agree with Bill’s observation. It seemed convenient to tag the distance in there, and I didn’t have a better idea, and it’s clearly more or less working. I think part of my concern, that led me to the current scheme with the tag in Cell, was fear of creating a lot of objects along the way, plus I didn’t see a good way of creating the answer incrementally.

So I was thinking, and I thought of a way, and sketched it in Juno, one of a couple of nice Python implementations for iPad, and tooted it. Today, we’ll try to do it well.

Here’s the idea
My first glimmer of an idea was to have a sort of queue, where we’d append cells to it if they were further away and pop them off if they were no longer furthest. It quickly became clear that a queue wasn’t quite it. So the idea evolved:

Imagine a tiny object, probably a dataclass instance, with a value and, well, anything else, but in our case, a Cell. As we generate cells starting at given, we create one of these for each cell as we generate, associating the cell and its distance from given. We feed these into a little Maximizing Machine. The machine knows the maximum distance it currently holds. If the new cell has a lower distance, it is ignored. If the new cell has a larger distance, the machine clears itself and holds just the new cell. If the new cell has distance equal to the max it is added to the machine.

When we’ve scanned all the cells, the machine will hold all the cells at max distance.

There is an issue with this. The cells are not generated in distance order, so we really do need to retain a distance d for every cell we generate, so that we can associate d+1 with the cells generated. It would be nice not to have to keep a complete copy of the Dungeon’s cells with this value.

I think we can beat this rap. Let’s look at our generate.

    def generate(self, condition=None, randomness=0.0):
        def accept_any(_cell):
            return True
        cond = condition or accept_any
        frontier = [self]
        examined = {self}
        while frontier:
            next = frontier.pop(0)
            yield next
            examined.add(next)
            if random.random() < randomness:
                neighbors = next.random_neighbors
            else:
                neighbors = next.neighbors
            for neighbor in neighbors:
                if neighbor not in examined and cond(neighbor):
                    if neighbor not in frontier:
                        frontier.append(neighbor)

As we generate, we are processing some cell that we have popped off the frontier. We would like to have that cell’s distance value, but once it is popped and added to examined we really don’t need it any more. Ah, but we can’t really discard much, as we will add the cell to examined, because we never want to examine them again once they’ve been through the mill.

I was thinking that if we could somehow associate the distance with the cells as we generate, such as with a tuple or tiny dataclass, we could just let them tag along and get discarded when the cell was popped. But the generator doesn’t know what we’re doing. Is there a way we could pass in a lambda?

One possibility would be to write a custom generate for this purpose. Then we might see the commonality and remove it, possibly with a passed-in function or strategy.

Here’s a p-baked idea with very low p:
Suppose we pass in a function to generate, a function of two cells, nominally a cell and a neighbor, and instead of keeping the cell alone in the frontier, we store a tiny object consisting of the cell and the function result. And when we yield, we yield the call and the function value, which we can then process in the little Maximizing Machine or whatever.

By convention, the function needs to accept None as the predecessor, so as to init the given cell’s value, as it is the first one returned.

This may be a very red herring but I think I’d like to try it. We have a few cases where we process the neighbors during generate, so this might even be more useful than just for maximizing.

We’ll do an experiment, with at least one test, probably more than one.

Experiment

After one attempt to munge the capability into the existing generate, which of course broke everything, I decided to create a new generate function. This test passes:

    def test_cell_function(self):
        def f(neighbor, value):
            return value + 1 if neighbor else 0

        Cell.create_space(10, 10)
        cells = [Cell.at(x,0) for x in range(10)]
        cells.extend([Cell.at(4,y) for y in range(1,10)])
        room = Room(cells)
        result = dict()
        for cell, value in Cell.at(0,0).generate_with_function(func=f):
            result[cell.xy] = value
        assert result[(0,0)] == 0
        assert result[(4,0)] == 4
        assert result[(4,1)] == 5
        assert result[(5,0)] == 5
        assert result[(9,0)] == 9
        assert result[(4,9)] == 13

The space is a big T shape across the top at 0 and down the middle at 4. So those values are the distances we want.

The method, as it stands now, is:

    def generate_with_function(self, func=None, condition=None, randomness=0.0):
        def accept_room(_cell):
            return _cell.is_in_a_room
        def nothing(cell, value):
            return 0
        f = func or nothing
        cond = condition or accept_room
        frontier = [(self, 0)]
        examined = {self}
        while frontier:
            next, value = frontier.pop(0)
            yield next, value
            examined.add(next)
            if random.random() < randomness:
                neighbors = next.random_neighbors
            else:
                neighbors = next.neighbors
            for neighbor in neighbors:
                if neighbor not in examined and cond(neighbor):
                    if neighbor not in frontier:
                        frontier.append((neighbor, f(next, value)))

As it’s written, we’re fudging the first pair that goes into frontier, because it was one ball too many in the air for me to sort it out. Thereafter, we yield the two values in frontier, and when we put a new value into frontier, we set the second parameter to the value of func, passing the current cell (whose name is next, sorry) and current value.

This is doing what we asked of it. We have a generate that can associate a function with each element it produces, where that function is based on the cell that is the “parent” of the current one and the corresponding value.

I think I see how this generate and the main one could be merged. I also sense that I need a break, for this code to settle in and to clear my head. We’ll commit: generate_with_function passes initial test.

Summary

We’ll continue this in the next article. This one is weird enough for any of us.

I had this nice idea of the Maximizing Machine, which I still think is a good thought. But there was no existing way to produce the values that it needs, unless we continued to store them in the Cell, and Bill’s observation was enough to tip me away from doing that.

I think it’s a bit of a leap to guess that a generate could be written that maintains a running function value as it goes. The implementation is actually pretty simple: Instead of the frontier of the generate being the cell that needs to be returned and then expanded, we make it consist of a tuple of that cell and the running function value.

Other than that, it’s “just” a matter of passing in the function, giving the function a suitable default, and such. Out of this, I think, will come a new generate that has a new parameter, the running tally function or whatever it is, and that is rigged to return only the cell if the function is not provided. (I think that’s possible: if not we’ll be better off with two functions, I think, rather than make everyone deal with an unnecessary value.)

But for now … a break. Feel free to toot questions, abuse, whatever. See you next time!