I feel sure that I know just what to do next with paths, but I’m not sure how to test it in a reasonable fashion. Results: Happy!

The current PathFinder object passes these tests:

class TestPaths:
    def test_small_flood(self):
        bank = CellBank(5, 5)
        finder = PathFinder(bank)
        finder.put((2,2))
        finder.expand()
        cells = set(finder.queue)
        assert len(cells) == 4
        for c in [(1,2), (2,1), (3,2), (2,3)]:
            assert c in cells

    def test_second_phase(self):
        bank = CellBank(5, 5)
        finder = PathFinder(bank)
        finder.put((2,2))
        finder.expand()
        for _ in range(4):
            finder.expand()
        expected = [(0,2), (1,1), (2,0), (3,1), (4,2), (3,3), (2,4), (1,3)]
        assert len(expected) == 8
        for c in expected:
            assert c in finder.queue
        assert len(finder.queue) == 8

We’ll discuss those in a moment, but first let’s see the class as it stands so far:

class PathFinder:
    def __init__(self, bank):
        self.bank = bank
        self.queue = []
        self.reached = set()

    def put(self, cell):
        self.queue.append(cell)
        self.reached.add(cell)

    def expand(self):
        reached = self.reached
        cx, cy = self.queue.pop(0)
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            tx = cx + dx
            ty = cy + dy
            txy = (tx, ty)
            if txy not in reached and self.bank.has_cell(tx, ty):
                self.put(txy)
What It Iz?

As usual in these recent articles, a cell is just a tuple of integers, representing the position of a floor element in the dungeon. There is no notion of size: the dungeon is just a big array of floor things indexed by cells. There are unquestionably objects wanting to be born here, but we are where we are.

The PathFinder will visit all the cells that are accessible to it via the bank. It needs at least one cell in the queue to start, and generally we only provide one. I know of no use offhand for more than one. The core method expand considers each element of the queue, and if it has not been reached already, and it is in the provided CellBank, it is added to the set of reached cells, and put in the queue.

If expand is called often enough, it will visit every accessible cell in the bank, and will add them all to reached. Because reached is a set, each cell only occurs once.

I’m glad we’ve had this little chat, because now I can think of at least one testing angle I’ve missed: checking reached. That will help us a bit as we go forward.

What It Wants To Be

We don’t really want a list of all the cells we can reach. We want the shortest path from a given cell to another given cell. The cells we have in mind will be the centers of two rooms that we want to connect. We want the shortest path between those cells, avoiding anything that isn’t available in the CellBank. Since all the rooms will be in the CellBank, we’ll avoid the other rooms, thus providing a somewhat winding road. At least that’s the vision.

How We’ll Do It

We’ll change the reached set to a dictionary with the key being the cell reached, and the value being the cell we were expanding when we reached it. Thus each cell in the dictionary will point to the first cell that found it during expansion. If we follow those pointers from the target back to the source, we’ll have a shortest path between the target and source.

I say “a shortest path” because there might be more than one. The one we find will be whichever one our iteration through neighbors finds first.

Our cell selection will want to accept cells in the two rooms we’re connecting, and available cells from the cell bank. That’s pretty much all there is to it.

How Can We Test It?

When I came in here, I had no good ideas for tests other than some huge test that drew a picture that we could look at, using that cell-printing thing that I did in the Game of Life code. But explaining to you, as my official rubber duck, it comes to me to write some tests about reached. We can probably even write a test to check that the path at least does connect the points we have in mind.

I’ll remind you, and myself, that the tests are there to provide confidence. They can never “prove” that things work perfectly. We’ll try to test until we’re legitimately confident that the code works, and so that someone not quite so personally invested wouldn’t think of another test to write. Let’s get to it, by enhancing the second test.

No. Change of plan. Let’s write a new test, one that should flood the whole space, except for things not in the bank. That will drive out a new method, which we’ll call flood.

    def test_flood(self):
        bank = CellBank(5, 5)
        finder = PathFinder(bank)
        finder.put((1,2))
        finder.flood()
        assert len(finder.queue) == 0
        assert len(finder.reached) == 25

Not a terribly difficult test, which is just fine. Small steps, y’know.

class PathFinder:
    def flood(self):
        while len(self.queue) > 0:
            self.expand()

Test is green. Commit: initial flood method.

Time to move PathFinder to its own file. I develop classes inside the test file when they’re small and move them out when they’re big enough. PathFinder is ready.

Let’s test that PathFinder doesn’t use cells that are not in the bank.

    def test_flood_uses_bank(self):
        bank = CellBank(5, 5)
        taken = [(3,3), (1,4), (2,1)]
        for t in taken:
            bank.take(*t)
        finder = PathFinder(bank)
        finder.put((1,2))
        finder.flood()
        assert len(finder.reached) == 25 - len(taken)
        for t in taken:
            assert t not in finder.reached

I expect this to work. It does. I think I forgot to commit the move, let’s commit that and the new test now: moved PathFinder to own file. New test.

We have at least two more things to add:

  1. Give PathFinder the ability to accept cells that are in provided rooms, but not in the bank;
  2. Produce the shortest back-trace.

Let’s do #2. I have an idea for a test.

    def test_path(self):
        bank = CellBank(10, 10)
        finder = PathFinder(bank)
        source = (3,3)
        target = (7,6)
        dist = self.manhattan(source, target)
        assert dist == 7
        path = finder.find_path(source, target)
        assert len(path) == dist

Our path should have length equal to the manhattan distance between the points, because there is no obstacle in the way. (Plus or minus one, depending on what we really put into the path when we create it.)

I think what we can do, inefficient though it will be, is flood the whole region and then find our path.

I think find_path goes roughly like this:

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

I’m starting to think I should have done a smaller test but we’ll see. We can always roll back if we get in trouble.

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

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

    def flood(self):
        while len(self.queue) > 0:
            self.expand()

    def expand(self):
        reached = self.reached
        cx, cy = self.queue.pop(0)
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            tx = cx + dx
            ty = cy + dy
            txy = (tx, ty)
            if txy not in reached and self.bank.has_cell(tx, ty):
                self.put(txy, (cx,cy))

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

I change the reached member to a dictionary, change put to store a cell former, which maybe needs a better name, and assign former to the cell we’re expanding. As written the test fails, with 8 cells rather than 7. Here’s the error:

>       assert len(path) == dist
E       assert 8 == 7
E        +  where 8 = len(
            [(7, 6), (7, 5), (7, 4), (7, 3), (
            6, 3), (5, 3), (4, 3), (3, 3)])

That, my friends, is the path down from 7,6 to 7,3 and then across to 3,3. It is exactly what we wanted and we can happily change the length to dist+1.

Now I am quite confident in this and am of course confident that it also honors the cell bank, so if we put obstacles in there it would skip go around them. We can improve the test, however, by checking the end points and measuring its length.

    def test_path(self):
        bank = CellBank(10, 10)
        finder = PathFinder(bank)
        source = (3,3)
        target = (7,6)
        dist = self.manhattan(source, target)
        assert dist == 7
        path = finder.find_path(source, target)
        assert len(path) == dist + 1
        assert path[0] == target
        assert path[-1] == source
        distance = sum(self.manhattan(s1, s2) for s1, s2 in pairwise(path))
        assert distance == dist

Green. I am even more comfortable. Commit: find_path looks good.

We could do a test with an obstacle but we already know that the PathFinder doesn’t consider cells that are not in the bank. That makes that test less interesting, so I’m not going to do it. I may turn out to be wrong: I often am.

I want to try something. I’m going to generate a bunch of rooms and then draw a path around them, in the main program.

def main():
    bank = CellBank(64, 56)
    # random.seed(234)
    dungeon = Dungeon()
    number_of_rooms = random.randint(10, 10)
    for _ in range(number_of_rooms):
        room = Room()
        size = random.randint(60, 90)
        x, y = random_available_cell(bank)
        room.build(bank, size, (x,y))
        dungeon.add_room(room)
    dungeon.find_path((0,0), (63,55), bank)
    view = DungeonView(dungeon)
    view.main_loop()

I posited a dungeon method find_path, then wrote it:

class Dungeon:
    def find_path(self, start, end, bank):
        finder = PathFinder(bank)
        self.path = finder.find_path(start, end)

And in DungeonView:

class DungeonView:
    def draw_path(self):
        for cell in self.dungeon.path:
            cx = cell[0]*cell_size
            cy = cell[1]*cell_size
            pygame.draw.rect(self.screen, 'red', [cx, cy, cell_size, cell_size])

And I get, for example, this:

map showing bright red path avoiding rooms

And that will be the capper for the day. A path, pretty much like I expected. It’s ALIVE!!!.

Commit: paths looking good.

Summary

Testing reached gave me a little jolt of confidence. In turn, confidence keeps me calm. In turn, calmness lets me code a bit better, remembering more details, making fewer mistakes.

Of course much credit goes to Amit of Red Blob Games, whose excellent articles showed me how to do this. I think I might have been able to invent the same solution but it would have taken longer and would have surely been more complicated, at least at first.

There are rough edges to deal with here, and we’re not allowing our PathFinder to use cells in the source and target rooms we want to connect. It still feels like a smarter Cell might be useful. It seems that Dungeon may want to know the CellBank rather than be passed it for the path work. We don’t really want a God object, but there are signs and portents that are saying the objects aren’t quite right.

It’s surely wrong to have a single path in Dungeon … unless we merge them as we build multiple ones … hmm … we’ll see.

Quite possibly next session should be for some general improvement. I think the basic operations are pretty much in place, except for the room inclusion in paths. We’ll see. For sure, we have a happy outcome today, a lovely bright red path.

See you next time!