The flood method is my current darling. Should we kill it? Is it just too cool to live? Let’s examine it.

There are at least two reasons why I’d consider code “too cool to live”. The first reason is often triggered by recognizing that I want to show it off as particularly clever. It’s not that there is no place for cleverness: it can often pay off, in small enough, isolated enough cases. But if it’s also hard enough to need an explanation when I show it off, definitely a bad sign. Is flood too hard to understand?

The second reason that it might be too cool to live is if it turns out to be hard to use in what seem like ordinary cases. Is flood too hard to use?

Second Breakfast

I just deleted 200 input lines, probably 500 article lines of text. I had a semi-interesting sort of prosecution / defense trope going, not very well, because I can’t resist improving code that needs it. So we’ll start again, looking at flood with a critical eye but an attitude of making it better, not threatening to destroy it.

It is, however, a very cool method and even as currently refactored, it’s not entirely obvious. I don’t suppose it can be, but I’d like it to at least be reasonably clear how to use it and what it is.

Here’s flood as it stands right this moment:

class Cell:
    def flood(self, *,
              select=lambda cell: True,
              next_value=lambda cell, value: 0,
              initial_value=0,
              randomness=0.0):
        frontier = {self: initial_value}
        examined = {self}
        while frontier:
            current_cell = next(iter(frontier))
            current_value = frontier.pop(current_cell)
            yield current_cell, current_value
            examined.add(current_cell)
            neighbors = self._get_neighbors(current_cell, randomness)
            for neighbor in neighbors:
                if (neighbor not in examined and
                    select(neighbor) and
                    neighbor not in frontier):
                        frontier[neighbor] = next_value(current_cell, current_value)

    @staticmethod
    def _get_neighbors(next_cell, randomness):
        if random.random() < randomness:
            return next_cell.random_neighbors
        return next_cell.neighbors

It is my practice never to use the “docstring” capability of Python, but in this case, I’m considering it. I think I’ll try to describe flood here and see whether we’d like to put that description into the code as a docstring.

flood Description

Summary of flood:

flood produces all cells reachable from the given receiver cell, by orthogonal moves, subject to a function that can select which cells are accepted. For each cell returned, a next_value is be computed and returned, with parameters consisting of the first current_cell that has that neighbor, and its current_value.

Details of flood:

The flood method starts from the receiver cell and produces a sequence of cells and values “flooding” outward from the receiver cell. By default it will produce all the cells of the current CellSpace.

The select parameter can limit the cells considered, such as to cell.is_in_a_room or cell.is_available. The select function you provide can perform any test desired on the cell it is passed, and if select answers True the cell will be processed and returned in the generated sequence, or if False the cell will not be processed and not returned in the sequence. We’ll call the cells that pass select the “selected cells”.

The keys of the dictionary frontier are the cells to be returned, and the values of that dictionary are the corresponding value to be returned. Setting the value will be discussed below.

The generator loops, returning as current_cell and current_value, the next key and value from the frontier dictionary, initially the receiver cell and initial_value. It adds current_cell to the examined set, ensuring that it will not be processed again.

‘flood’ then considers all the orthogonal neighbors of the returned cell, but not diagonals. The randomness parameter will sometimes shuffle the order of consideration of the neighbors: otherwise it’s always left, right, up, down. Randomizing can make paths and rooms more jagged and random looking. Not randomizing tends to make for straight paths and more regular rooms.

flood only considers neighbors that have not been examined, that are selected, and that are not already in the frontier. Cells passing these three checks will be added to the frontier with their corresponding value, calculated by calling next_value, passing it the current_cell and current_value. (A future change may also pass in the neighbor itself: I suspect we need it for the path map.)

The next_value function is therefore called once for each accepted neighbor, passing in the cell that first “discovered” the neighbor and that cell’s value. next_value returns the value that will later be associated with that neighbor when it is finally yielded. If no function is provided, the values returned will be zero. The returned value can be any object, not just a number. At this writing we have no such case.

The process terminates because ultimately all cells will be in examined, no more cells will be accepted, and the frontier will empty out.

Summary of flood, redux:

flood produces all cells reachable from the given receiver cell, by orthogonal moves, subject to a function that can select which cells are accepted. For each cell returned, a next_value is be computed and returned, with parameters consisting of the first current_cell that has that neighbor, and its current_value.

Too Cool?

I think that the fact is that we need flood fills for various purposes. They are the only way to determine a path from one cell to another, such as for a monster to track an adventurer, or to be sure that the dungeon is fully connected. We use a flood to find a cell that is as far as possible from another, to place the adventurer randomly but as far from a specified target as possible.

So we need at least an elementary flood, and if we only have an elementary one, we wind up doing specialized ones the next time we have a need. We have a dozen uses of the existing method, including both tests and production uses, mostly tests. We use it in main to get the furthest_cells for placing Dot, and in RoomMaker for finding places to put rooms.

I think this is right on the edge of too cool, but the code we used to have was worse, and I think some of the code that we still have can be improved via flood. In aid of that, however, I think we’ll need to make it just a bit more complicated, adding a parameter to the next_value function. We’ll see.

Kill This Darling?

The origins of the advice “Kill your darlings” are shrouded in history, but the idea comes from writing, where often a particularly lovely bit doesn’t really serve the narrative, but you just love it so much you want to leave it in.

flood serves our narrative, and if there is a way to do it that is truly simpler, I don’t know it. We could write three or four different loops and generators for the different cases, but then each one of those would need to be tested and, inevitably debugged, and would likely get copy-pasted all around. And that, too, would be bad.

We’re going to let this darling live, at least for now.

Whew! I was worried. See you next time!