PathFinder?

Now let’s see if PathFinder can benefit from the new generate method on Cell. Saturday: absolute debacle. Sunday: perfect.

Note

Warts and all is kind of the motto of my writing. I am not here to show you some god-like perfect process: I am here to show you what really happens. What really happened on Saturday is that I made no real progress, reset many times, and went away with my tail between my legs.

That said, last night clear thinking arrived and I saw my mistake, and today went swimmingly.

This article would be much longer if I were to include all of Saturday’s work as well as Sunday’s quick production of the solution, because I bashed my head against the problem for at least two hours without solving it. I was missing one key thought, which in its most basic form was “generate cannot do this on its own”.

I’ve deleted a bunch of mistaken speculation about what was wrong, because the speculation was wrong and therefore the work I did based on it was wrong. Most of the screaming is left in.

Read with skipping in mind. Sunday’s work is good. Saturday’s, not so much

Saturday

The PathFinder object finds a shortest path between two cells, subject to the constraint that it only uses cells that are either available (still in free space) or in either of the rooms in which the cells reside. As we’ll see, it does that by flooding the space with an expanding frontier, just as our generator does. However, PathFinder keeps track of a bit more information.

Our generator keeps track of cells that have already been visited, so as not to process them again. PathFinder does that, but also keeps track of the first cell to find a visited cell. The result is that when the search ends, PathFinder has a shortest path available to it, by tracking back from the target to the first cell that found it, to the first cell that found that cell, etc.

We’ll have to find a way to build that information structure.

PathFinder also stops searching when it finds the target. We’d like to have that same behavior. I think we can probably just exit whatever loop we use to call generate, since it only produces a new cell on demand.

And, of course, to use generate, we’ll need a cell-examination condition that expresses “is free or in one of these two rooms”. I think that should be easy enough.

So, with those thoughts in mind, let’s take a look at PathFinder:

class PathFinder:
    def __init__(self, bank):
        self.bank = bank
        self.queue: list[Cell] = []
        self.reached: dict[Cell, Cell] = dict()
        self.room_list = []

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

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

    def flood(self, target):
        while self.queue:
            self.expand(target)

    def expand(self, target):
        next_cell = self.queue.pop(0)
        for neighbor in next_cell.neighbors:
            if neighbor not in self.reached and self.can_use(neighbor):
                self.put(neighbor, next_cell)
            if neighbor == target:
                self.queue = []
                return

    def can_use(self, neighbor) -> bool:
        if neighbor.is_available():
            return True
        for room in self.room_list:
            if neighbor in room: # isn't this searching the whole room?
                return True      # can't we just check neighbor.room() now?
        return False

    def put(self, cell: Cell, former=None):
        self.queue.append(cell)
        self.reached[cell] = former

There’s quite a lot there but most of it is much like our generate, which should come as no surprise, since we started with Red Blob Games’ search ideas and code, and generate is an intellectual descendant of PathFinder, which predates generate.

So some of what’s above is familiar. can_use is an expression of the notion of the cell being free or in one of the two rooms. put is the standard handling of a discovered cell, including keeping the reached object as a dictionary with each cell knowing former, the cell that fist discovered it.

We have quite a few tests for PathFinder. We’ll not explore them, at least not until they fail. I do have some concern about them because I’m pretty sure that at least some of the tests are checking the particular path returned from PathFinder, and there is more than one “shortest” path and our generate might find another. We’ll burn that bridge when we come to it.

I think the thing will be just to try to plug generate in and see whether we can just make it work. If we can, good. If not, maybe that will suggest another idea.

The main action is here:

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

    def flood(self, target):
        while self.queue:
            self.expand(target)

A better person might have refactored find_path differently: the first two lines are about flooding and the rest are about constructing the final path from the dictionary. The path is a list of cells from one end to the other. target to source, I guess. I’m planning to ignore that, because all we care about is getting the right cells and we’re going to try to replicate the behavior not improve it.

Because generate just gives us cells, we’ll need to maintain the dictionary ourselves. Here goes my first attempt. I think I’ll try re-coding flood.

First, let’s move that initial put down into flood, where it belongs.

Ah, can’t quite do that, because other tests are calling flood. I think we need to fix that up, to keep our tests running, as they are our clue as to whether we’re ok.

A Change Signature fixes them up. I didn’t even look. Now move that line. Unfortunately that breaks four tests. I think this time I’ll look.

Grr. Something about when the queue gets set up. I’ll work around the issue but it’s going to require me to do more work, thus a bigger chance of error. I’ll go ahead, mostly to learn more about why what I’m thinking won’t work.

Meh. Not good. Roll back and start again. git reset –hard

Note

Here lies a couple of hours and a half dozen more git reset –hard. Note that I knew I should stop and rethink but didn’t. And it was worse than what is written here, because I finally stopped writing and just kept trying and resetting. Bold italics below are the indications that I should have been dragged away from the machine.

I think that when I changed the signature on flood I did something wrong. I wanted both source and target so that I could stop the search when done. Somehow I wound up with too many None types and I lost the thread.

I wonder, could we just refactor PathFinder a bit so that it uses generate and does everything else just as before?

Meh squared. I’m very close. Also not there. I’ve built a loop in the path. The searching is working fine and the dictionary isn’t quite right. Need a break. Will return anon.

I couldn’t resist one more look. I think that generate generates the starting cell.

Meh, no. Take your break. Return fresh. (Finally took break, didn’t help.)

Git reset –hard again. Need to think clearly about what the form of the desired dictionary is. I’m generating a cell that points to itself.

Looking at the path creation, it goes like this:

An hour or more is spent here.

I have put in various attempts and done about sebenty-leben hard resets. I think I need a better idea. Taking another break. Maybe tomorrow will be a better day.

Sunday …

And I do in fact have a better idea. I was assuming that my PathFinder could be solely driven by fetching cells from the generate. That is not the case, because PathFinder wants to find adjacent cells and link them together in its dictionary. generate does not produce cells in a fashion that would make that possible, and in fact, it cannot. PathFinder needs to accept the flow of generate, and then to fetch the neighboring cells for each cell that generate provides, and deal with them.

I finally realized that at some point last night, in between Zentangle® and other diversions. So I am confident that, this morning, we’ll get it working promptly. If we do not, you will never see this article, so if you are reading this, it worked.

Experience yesterday tells me that changing the flood method, so I plan to change the find method to call a new method, maybe generate, so that the actual path tests will test the new code, and the old flood tests can be reviewed later and perhaps just removed, depending on what they’re doing.

Our generate method will want both source and target, and will include the neighbor-handling. That might want refactoring later: we’ll see.

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

Two tests break, since there is no generate. I don’t even look at them. Let’s see if we can do the work.

And …

class PathFinder:
    def generate(self, source, target):
        for c in source.generate(self.can_use):
            for neighbor in c.neighbors:
                if neighbor not in self.reached and self.can_use(neighbor):
                    self.reached[neighbor] = c

We are green. It was just that easy. We would like to short-terminate the search when we find target. I think that when the for loop produces the target, we have already processed it as a neighbor, and we can terminate. Arguably, if in the inner loop, neighbor==target, we can terminate. I think we’ll save doing that until we have a test for it. This being Sunday, with bacon in the offing, we’ll save that improvement for later.

Oh, OK, I’ll try it just for fun.

    def generate(self, source, target):
        for c in source.generate(self.can_use):
            for neighbor in c.neighbors:
                if neighbor not in self.reached and self.can_use(neighbor):
                    self.reached[neighbor] = c
                    if neighbor == target:
                        return

The tests all pass. I’ll leave it in. I do want to run the main and see the paths on screen.

There is a thing that I do not like here, which is how square the paths are. They tend to go in long straight lines. I think that is because we produce the neighbors always in the same order so we tend to select the same direction every time until we are directly beside or above the target and then hang a left or right and proceed straight there.

Just for fun, let’s try randomizing the neighbors:

    def generate(self, source, target):
        for c in source.generate(self.can_use):
            neighbors = c.neighbors
            for neighbor in random.sample(neighbors, len(neighbors)):
                if neighbor not in self.reached and self.can_use(neighbor):
                    self.reached[neighbor] = c
                    if neighbor == target:
                        return

That produces a slightly more jagged set of paths:

Summary

I’m going to commit things as they are and call the morning a success. We’ll just forget about yesterday’s debacle. It was all due to my failure to recognize that generate just can’t do all of what PathFinder needs, and it has to do some of the work. Once that recognition occurred, the rest was, as we see above, pretty simple.

There is now a lot of mostly dead code in PathFinder. We’ll clear that up later, when we review the tests that are still using the old code.

I don’t like that deeply-nested method, but if it’s going to short-terminate, the easiest thing was to leave it that way. We can look at refactoring it some other time: I think we’d just call a processing method that returns True/False depending on whether it finds the target. Anyway, this is good, just not entirely to my taste.

Lesson relearned again.

I learn this over and over and still fall into the trap. You can see above that I knew I needed a break and finally, after a few resets, took one. When I came back I still had the same mistaken idea and kept trying to make it work. More resets. Finally I gave up for the day.

Should I have stopped sooner? It’s hard to say. Certainly last night the solution came to me, and who knows what part of the head-bashing earlier may have produced the realization? I try not to should all over myself, but I do suspect that had I been able to recognize, not just that I needed a break, but that I needed to rethink my solution, I might have saved a bit of frustration.

In my defense: when I’m in real programming trouble, I get tense and can feel the tension. Yesterday I did not feel tense. Instead I had that feeling that there was just a simple mistake somewhere and a few more prints would find it. I think it was the print that I expected would show a few items and instead showed me a huge number that finally got me to realize my idea must be wrong. I’ll never know: rarely if ever do we really know what would have happened had we made some other decision.

But when I resort to multiple resets, I think it’s a clue that I need a better idea. I’ll try to relearn my lesson. (Constant readers shake their heads in doubt.)

Now I’m going to back away from the computer, hands out, saying “Steady, girl, steady”.

See you next time!