I’ve had what seems like a good idea. Let’s find out.

Our mission, and we do choose to accept it, is to find a cell in the dungeon which is maximally distant from a given point, using manhattan distance within the dungeon, no shortcuts allowed. My very rough plan for this feature has been to do a flood fill starting from the given cell, retain some kind of information that maps cell to distance, and select one of the cells with distance equal to the largest we find. (There could be more than one such cell.) I’ve spent a bit of time thinking of how we could minimize the information kept, keeping track only of the current largest ones. Somehow, an idea came to me that seems much better:

As we generate the cells, which will be in an expanding wave from the given cell, each new cell that we add is one step further away than the cell whose neighbors we are expanding. So, I thought to myself, I thought, “Why not just store the distance in the cell itself?” When we encounter a cell, if it already has a distance, we don’t override that value, keeping always the smallest distance. That’s because as we expand the wave front, we can encounter a cell more than once, having taken a longer path to get there. We want the maximal direct path, not the longest path you could take if you were really bad at dungeons.

This seems to me to be a really straightforward way to build our feature:

  1. Clear the distance value in all cells;
  2. Build new distance values for all cells, starting from given;
  3. Scan all cells, collecting the ones with maximal value.
  4. Select one randomly.

I think there is probably a small miracle in item #3, where we find all the maximal ones, but it’s probably a one-liner or something once we figure it out.

Now let’s over-design a bit.

We could just add a new member to Cell, called distance or something, and use it. And I think we should do that, but it does seem clear that as the game grows, there will be lots of occasions to keep things in cells, such as treasures or traps. And there will be an arbitrary number of these things, and we really won’t want to add an instance variable for each. Instead, we’ll have some kind of list or dictionary.

So, we think to ourselves, we think “We might as well do a dictionary now, we’re gonna need it”. But then we think, “No, that is not our way. Our way is that we design for what we need now, not for some future possible need.”

Besides, everyone enjoys seeing me get my comeuppance when I don’t provide some robust big facility and then later need it after all. Except that that never seems to happen: instead, it always seems that I can readily refactor to put in the new capability without a lot of trouble. So let’s do it the simple way this time and see if we get in trouble later.

Let’s test drive a capability on Cell to clear, set, and reference a variable we’ll call path_distance.

This seems almost inane:

    def test_path_distance(self):
        Cell.create_space(5, 5)
        cell = Cell.at(2,0)
        assert cell.path_distance is None
        cell.path_distance = 37
        assert cell.path_distance == 37

I’m not sure if we want a clear_path_distance or not. None seems pretty clear. We’ll see what we want when we use it.

class Cell:
    @property
    def path_distance(self):
        return self._path_distance
    @path_distance.setter
    def path_distance(self, value):
        self._path_distance = value

Test passes. Commit: add path_distance to Cell.

Now I begin to think about how we want to do the path thing. I think I’ll work it out in a test and then move the code after I know what it is.

    def test_max_path_distance(self):
        layout = DungeonLayout()
        Cell.create_space(5, 5)
        map = '''
        11111
        '''
        layout.add_rooms_from_map(map)
        given = Cell.at(0,0)
        in_a_room = lambda c: c.is_in_a_room
        for cell in given.generate(in_a_room):
            cell.path_distance = None
        given.path_distance = 0
        for cell in given.generate(in_a_room):
            for neighbor in cell.neighbors_in_rooms():
                if neighbor.path_distance is None:
                    neighbor.path_distance = cell.path_distance + 1
        for x in range(5):
            assert Cell.at(x,0).path_distance == x

Just a straight path across the top. Should be good enough, we trust generate to work.

The test passes. Let’s reflect about what we should really do.

Reflection

This code, as we can see, is using Cell.generate, with the condition in_a_room to restrict the search to cells that are in the dungeon, not the many unallocated cells. This may be a case for maintaining a spare collection of cells instead of the complete collection we now use, with what amounts to a flag saying that a cell is in use.

A friend on Mastodon suggested that idea, which I claim I had also thought of and decided against. I can’t find their name just now but they were onto something with the idea.

Anyway we’re here now, with the full collection and our lambda to check only room cells and that’s certainly working, for values of “certainly” approaching 1.0.

I think that before we go further with this idea, we need to decide where the fundamental notion resides. My guess is that it will be in Dungeon as a stub calling into DungeonLayout, which owns the cells. It’ll probably be part of Dungeon.populate():

class Dungeon:
    def populate(self):
        dot_room = random.choice(self.rooms)
        dot_cell = random.choice(dot_room.cells)
        self.place_player_at(dot_cell)

We have not yet addressed the larger issue of generating interesting layouts populated with various creatures and treasures, presumably respectively more deadly and more desirable as daring Dot delves dauntlessly deeper into the depths of the dungeon. However those work, it seems fair to expect that they’ll be sending messages to Dungeon to get most of the work done.

I am about ready to stop for the morning. In fact, I see that it is nearly 11 AM, time to have a bit of breakfast and watch Sunday Morning. We’ll stop here.

Summary

In just a few minutes, we have open code that (p>0.9) will find the in-dungeon path distance from any point to all others. We should probably create a better test of that, but I really am quite confident. That code seems to have two aspects, the clearing of the variable and setting it. We do need to clear it because we use the absence of a saved value as the indicator that we should record the current distance.

I note an odd thing, and this is not the first time it has happened: we have code that generates the cells and then we do something to the provided cell’s neighbors. I don’t recall where else we do that, but I’m sure that we do. That suggests to me that there may be an opportunity to consolidate that duplication somewhere. Note made.

We should have little or no difficulty moving the code over to Layout and certainly wiring up a connection through Dungeon will be trivial. I just don’t want to do it right now and after all, bacon is important.

See you next time!