The PathFinder code now uses Cell.generate, but there are signs that make us wonder.

As I mentioned yesterday, my way of working, in small mostly local steps, seems generally to lead to more substantial net improvements, including new classes, new capability in existing classes, and placing capabilities in better places than they were originally found. That happens, I believe, because there are “signals” in the code that we can recognize and pay heed to, suggesting improvements.

Today, with PathFinder.generate and Cell.generate, we’ll see some signals and begin to respond to them. Here is the current PathFinder:

class PathFinder:
    def __init__(self):
        pass

    def find_path_between_rooms(self, source_room: Room, target_room: Room):
        room_list = [source_room, target_room]
        source_origin = source_room.origin
        target_origin = target_room.origin
        reached = {source_origin: None}
        self.generate(source_origin, target_origin, room_list, reached)
        path = []
        start = target_origin
        while start is not None:
            path.append(start)
            start = reached.get(start)
        return path

    @staticmethod
    def generate(self, source, target, rooms, reached):
        def can_use(cell):
            return cell.is_available() or cell.room() in rooms
        for c in source.generate(can_use):
            neighbors = c.neighbors
            for neighbor in random.sample(neighbors, len(neighbors)):
                if neighbor not in reached and can_use(neighbor):
                    reached[neighbor] = c
                    if neighbor == target:
                        return

And here is Cell.generate:

class Cell:
def generate(start, condition=None):
    def accept_any(_cell):
        return True
    cond = condition or accept_any
    frontier = {start}
    examined = {start}
    while frontier:
        next = frontier.pop()
        yield next
        examined.add(next)
        for neighbor in next.neighbors:
            if neighbor not in examined and cond(neighbor):
                frontier.add(neighbor)

Here are some signs and portents that we might observe here:

Similar Names
It is of course no accident that I named PathFinder’s operational method generate: It used to be a precursor of the one in Cell, and when we changed it to use Cell.generate, the similarity between the two was clear and I chose the name aware of that. I don’t think I foresaw combining them, but they were the same concept and I gave them the same name.

That said, when things have similar names we do well to consider why that might be happening and whether there is some improvement hiding there.

Duplication
The two methods both iterate over neighbors. True, PathFinder randomizes them, but still the code shape is very similar. When the same or similar code appears in multiple places, that’s a clue that there may be a common element or other consolidation of the copies.
Feature Envy
When a method in one class seems interested only in values in other classes, with little or no use of the class’s own members, it is highly probable that the code is actually implementing something that could be a feature of the class it’s actually manipulating.

Our PathFinder.generate is static, with no references to PathFinder members. In fact, PathFinder has no members any more: we refactored all of them out yesterday.

Alternate Design Ideas
As we create code, we often think of various ways it might be done, and at some point, somehow we pick one. But we keep the others in mind. And sometimes, we’re discussing the code with someone and they wonder about alternate designs. That happened here, when @blackoverflow mentioned feeling that the PathFinder code might belong on Cell.

All these are hints and allegations that there’s room for improvement. Some call them “code smells”, a term which I have used but never loved. But whatever we call them, PathFinder has all of them and we would do well to start paying attention. Of them all, probably the most obvious is FeatureEnvy, signaled by PyCharm by suggesting that the method be marked static.

One more thing …

I was thinking about the dictionary that PathFinder creates. Recall that its purpose is to find a shortest path between two cells, and it does that in two passes. First it builds a dictionary for each cell inspected, pointing to the cell that found it during the flood. The dictionary value for a cell is the cell to which you should step if you want to get to the starting point of the flood as expeditiously as possible. We happen to create the path from what we call source to what we call target, but the path is just an array of cells from one to the other, so you could traverse it in either direction.

By my point is that the dictionary created includes more than just the one path. If includes, for every cell inspected, a pointer to that cell’s best path to the origin. The structure we have created is … something. On one creation, it could be used to find many paths to a given location. Perhaps it would be used to cause monsters all over the dungeon to head toward the party when they accidentally make a loud noise.

I’m not sure what the thing is called. It’s sort of like a gravity well, pulling each cell toward the origin. It might be a sort of “cone”, showing which direction is downhill toward the origin. It’s a sort of shortest path map of all the cells searched.

I may not know what to call it, but I’m pretty sure that whatever it is, it’s the thing that we want Cell to build for us, and we want PathFinder to ask for it and then use it in its find method to produce the particular path that we’ve asked for.

Now we don’t have to do it that way. We could just as easily have cell go ahead and give us the single path we’re asking for. And we have no other use for this thing (PathMap?) yet, and that argues for not creating it yet, just keeping it inside Cell (or PathFinder) for later use.

Hm. I’m glad we had this chat. Maybe the thing is the insides of a PathFinder, so that from the outside it is PathFinder.

Design Thinking …

Well, the above is certainly design thinking but now I’m thinking about something a bit more specific. Suppose we create a PathFinder with a given cell of interest (the bottom of the cone: we should probably call it target). PathFinder uses cell to get the dictionary PathMap thing, and holds onto it. Then you can ask PathFinder for path_from(cell) and it delivers that path, currently just an array of cells. You can hold onto a PathFinder and ask it for multiple paths to the target if you have reason to. (Those monsters again.)

It begins to seem to me that we have two distinct things we’re asking Cell to do. The current generate produces all the adjacent cells meeting some criterion. It finds an area in the dungeon. The new idea is to produce all the adjacent cells, with their associated downhill cell.

Hm. I thought I was going to wind up with two separate things in Cell. But aren’t the keys of the path map or whatever it is, just the cells generated? Ah, yes, but no. The current generate produces the cells in nearest to furthest order. Well, maybe that’s still OK. A Python dictionary generates its keys in insertion order. So if you wanted to find the nearest monster to the party, you could iterate the keys and check the cells for containing a monster.

So … what if we change Cell.generate to produce the PathMap dictionary (perhaps soon promoting it to a class) and people who just want the cells just look at the keys? One drawback that I see is that currently, you can terminate the generation by simply breaking out of your iteration, if you’re calling generate directly. We do that in PathFinder when we see the target. (Of course if we want a full PathMap, we’d not want that anyway.)

I think that’s a feature that we can defer. It seems to me that a sufficiently clever generate condition could be used to return False, which would terminate the generate quickly.

We Have a Plan

I think we have a plan. Let’s modify Cell.generate to work on the dictionary instead of its current frontier set, and return that to our (two plus tests) users and let them deal with it. They might just deal automatically since iterating a dictionary iterates keys by default if I’m not mistaken. Which I frequently am.

Like right now: that’s not right.

The current generate yields cells one at a time and is used in a loop. the new thing will do the iteration internally and return the dictionary. They are not the same!

I think we just want to move the PathFinder.generate over to Cell and then see what we might do about any duplication.

I’ll create a new method on Cell and call it from PathFinder, moving the code in toto. (Not the little dog.)

Meh! Something went wrong in the translation. I rolled back, and wouldn’t you just know, I had failed to commit my last changes yesterday, so I had to reproduce those. Let me try the same thing again, maybe a bit differently.

Got It!

I apologize for skipping some steps here: I got excited and did a few without pausing to show them. Anyway, tests are now green with this working but not very lovely code:

class PathFinder:
    def __init__(self):
        pass

    def find_path_between_rooms(self, source_room: Room, target_room: Room):
        room_list = [source_room, target_room]
        return self.find_path(source_room.origin, target_room.origin, room_list)

    def find_path(self, source: Cell, target: Cell, room_list) -> list[Cell]:
        reached = {source:None}
        reached = self.generate(source, target, room_list, reached)
        path = []
        start = target
        while start is not None:
            path.append(start)
            start = reached.get(start)
        return path

    @staticmethod
    def generate(source: Cell, target, rooms, reached):
        def can_use(cell):
            return cell.is_available() or cell.room() in rooms
        return source.path_map(can_use)

class Cell:
    def path_map(self, can_use):
        reached = {self: None}
        for c in generate(self, can_use):
            neighbors = c.neighbors
            for neighbor in random.sample(neighbors, len(neighbors)):
                if neighbor not in reached and can_use(neighbor):
                    reached[neighbor] = c
        return reached

Let’s commit that: moving path map generation to Cell.

Now let’s clean up the mess in PathFinder a bit, essentially inlining generate:

    def find_path(self, source: Cell, target: Cell, room_list) -> list[Cell]:
        def can_use(cell):
            return cell.is_available() or cell.room() in room_list
        reached = source.path_map(can_use)
        path = []
        start = target
        while start is not None:
            path.append(start)
            start = reached.get(start)
        return path

PathFinder’s generate is gone. Commit. Pathfinder uses cell.path_map.

There’s more to do, but this is a good stopping point, I think, so let’s reflect.

Reflection & Summary

Perhaps a bit more blue sky thinking than was ideal, but I’d rather think too much than too little.

A bit of a stumble when I did something wrong and decided to roll back. But I did decide that quickly, and the second attempt went quite smoothly, What I did, and forgot to show, was to place a call to path_map into Pathfinder.generate, then look at the two dictionaries to see if they looked ok. Then I replaced reached with the path map, clearing reached and copying the path_map items into it. That worked, so I stripped out the duplication and had what I showed above.

I suspect, having written the above, that my mistake the first time was in not copying the dictionary over to reached. Had I done that, my first attempt probably was OK. No harm done, doing over is always much faster than the first time.

I see two issues still to consider. One will just be to revise PathFinder to cache the path map so that it can be used again, in principle. In addition, we may want to modify PathFinder so that it isn’t quite so committed to its room list. Needs consideration anyway.

Second is that there are two very similar methods now in Cell, generate and path_map, and we’d like to converge those if we can. I am cautiously optimistic about that, but freely grant that the situation isn’t clear in my mind. In the one case we want to yield the items and in the other we want to produce a dictionary. They might legitimately be two different things.

Those matters remain for another day. The effect this day is to move the cell-tracing code of PathFinder over to Cell, which Feature Envy told us was desirable. We haven’t saved much code in doing that, but things are better arranged. That’s a good thing.

Summary

The big payoff is just this: so often, following our nose through small changes leads us to significantly better design. Here, we have cell-tracing moved over to Cell, where it seems to fit nicely. And while we certainly did think about doing that early on, we waited until there was just one small change to make, pushing that one method over.

Is that better than some other more design-directed change? For me, it is. It tends to ensure that the code created over in Cell is actually useful, not speculative. And it tends to automatically identify opportunities via local code observations of naming, duplication, and feature envy. And, as always ideas from our friends!

See you next time!