For a program with no point, there sure are a lot of interesting things we might do. I’ll try to make these articles more useful.

Mind you, the primary “use” of these articles is to keep what’s left of my mind functioning. I do the code for fun and I write the articles for fun. I do try to make them useful by showing approaches, showing how I think, and occasionally drawing lessons from the work.

Perhaps most interesting is that, let’s get real here, I am, by virtue of over six decades in the business, familiar with and somewhat practiced with every good idea since Dr Grace Hopper discovered that moths are not good for computers. And yet … and yet … I fall away from my best mode of operation quite regularly, then meet my comeuppance and need to renew my dedication to some elementary practice. My chief failure is large steps. Large steps and lack of testing. My two chief failures …

After we last were together, you and I, I tried a very simple notion of paths between rooms. Basically, I set up a data structure to allow drawing a straight line from the center of room N to room N+1, in the order of creation. I just wanted to see what it might look like.

Here’s an example.

map with connecting lines

There are really eight lines there, connecting the various centers. Because I only draw center to center, and because the lines are drawn in the order of creation of the rooms, the pattern is sometimes a bit hard to see. The code for the paths is simple enough:

class Dungeon:
    def __init__(self):
        self.rooms = []
        self.paths = []
        self._previous_room = None

    def add_room(self, room):
        self.rooms.append(room)
        if self._previous_room is not None:
            c1 = self._previous_room.any_cell()
            c2 = room.any_cell()
            self.paths.append((c1, c2))
        self._previous_room = room

That sets up a table from any_cell of the two rooms being connected, number zero to one, one to two, and so on. But, for my convenience:

class Room:
    def any_cell(self):
        x, y = self.cells[0]
        x = x//16*16 + 8
        y = y//16*16 + 8
        return x, y

any_cell, so far, just returns the first cell of the room, which due to the construction in main, is always the center coordinate of a fixed cell, because I was experimenting with forcing the rooms all to different cells of the grid. All good, I just wanted to see what it looked like.

And, just for completeness, in DungeonView, we draw the lines.

class DungeonView:
    def draw_rooms(self):
        for room in self.dungeon:
            self.draw_room(room)
            self.draw_paths()

    def draw_paths(self):
        for c1, c2 in self.dungeon.paths:
            d1 = (c1[0]*cell_size, c1[1]*cell_size)
            d2 = (c2[0]*cell_size, c2[1]*cell_size)
            pygame.draw.line(self.screen, 'red', d1, d2, 5)

OK, now that you’ve seen it, let’s reset to yesterday’s last commit.

One more thing … I was thinking last night about building a buffer zone around each room, just a couple of cells wide. If after we create a room, we were to go around and remove a couple of cells around the room from the bank, we could place rooms truly randomly and they would never quite touch.

No wait, another thing … building the map seems to take a second or two. One reason for that might be that when we add a cell to a room, we do so by selecting random room cells and if the cell has a neighbor that is not in the room, we grab that cell and add it to the room. An issue with this is that we aren’t culling the cells that are interior to the room, so when we draw a random cell, we are increasingly likely to get an interior cell and to have to draw again. d

We could improve that scheme by keeping the interior cells separate, at least during room building. Somehow. Ideally not by doing something even more costly.

I think that for now we’ll not worry about that delay. We’re making enough changes that chasing performance is almost certainly premature. We could waste hours saving seconds. Maybe not wise.

I think what would be most “interesting” at this point would be to carve paths between the cells. I think that for the best visual effect, we’d allocate all the rooms and only then find routes between them, using the remaining cells of the bank. I have a very rough idea of how we might do it:

Paths

There is a very simple flood-fill approach to finding paths: I’ve used it in the past, so I’m sure I can find the link. It’s just a few lines of code. So we might do something like this:

  • Draw paths in order of room creation, like my red lines. This will cause paths not to go between the closest rooms, which would be boring.

  • Pick points in each room. They could be random, or the room’s initial cell. I think it probably makes no important difference.

  • Pathfind from the one point to the other,allowing use of either rooms’ cells, and vacant cells, but no other cells. This will make the path stay outside the other rooms. (It will very likely go adjacent to other rooms. That’s what made me think about the buffer zones.)

  • When the path is on a room cell, ignore it and keep searching. When it hits vacant cells, add them to a special “room”, the paths. (We may want just one such path room, or one for each path.) The paths will need to cross, in general. I think the ideal thing will be to just let them do it: it’ll lead to choices in the game. It would be possible, I suppose to cross them without an intersection, as if one path tunneled under the other.

My intuition about this tells me that the paths thus created will appear to make some kind of sense, and that they will generally connect approximately the nearest points of the two rooms. Of course one might want a path that circles around the rooms the long way, but we’ll need to see how it gods before we decide anything like that.

So let’s do paths. I propose to do them from scratch rather than try to decode and reuse my Codea Lua code from 2021. I use as my reference Amit Patel’s Red Blob Games, a truly marvelous site. Frankly you might do better to ignore me and read his stuff.

Still here? OK. The pathfinding intro is here. There are a dozen or more increasingly details pages there for one to study. For our purposes, I think we’ll start with this page.

Let me sum up what I think I know based on memory and a little review and thinking about the Red Blob articles.

Starting somewhere, we build a collection of cells by expanding into the space around us: in cycles we inspect the neighbors of the cells we have, adding them to our collection. Each cell in the collection will point back to the cell that is its first parent: the cell that was being expanded when this one was added. (A cell can be found more than once by this scheme. The first finder has taken the shortest path to the cell.)

When this expanding wave finally hits our target coordinates, we can follow the back pointers, which will trace the shortest path between target and source.

The Red Blob site includes roughly the code that we want:

frontier = Queue()
frontier.put(start )
came_from = dict() # path A->B is stored as came_from[B] == A
came_from[start] = None

while not frontier.empty():
   current = frontier.get()
   for next in graph.neighbors(current):
      if next not in came_from:
         frontier.put(next)
         came_from[next] = current

I think I’d like to be able to watch this thing work. And I’d like to have it under test. This may be a bit tricky.

Let’s start with a simple flood-fill kind of test in a small Dungeon.

class TestPaths:
    def test_hook(self):
        assert False

Red. Change to True. Green. Commit: starting path tests.

    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

One expansion step should remove (2,2) and add those four cells, unless I miss my guess.

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

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

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

Green. Commit: initial PathFinder expand.

Now we need to test the next phase of the fill. I think we’ll discover, if we didn’t already know it, that we shouldn’t put things into the queue more than once. Let’s proceed naively.

    def test_second_phase(self):
        bank = CellBank(5, 5)
        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

This fails on the final assertion, telling me there are 16 items in the queue. I’m a bit surprised: I expected more than 8 but fewer than 16. Let’s see what the values are:

[(0, 2), (1, 1), (1, 1), (1, 3), (1, 3), 
(2, 0), (2, 2), (2, 2), (2, 2), (2, 2), 
(2, 4), (3, 1), (3, 1), (3, 3), (3, 3), (4, 2)]

Right, duplicates out the bird. Everyone duplicated the center. We need to track the ones we have already reached. (Red Blob would tell us that if we paid attention, but we’re trying to do our own learning here.)

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)

So far so good. I think I’m confident that the flood part is working. I think this will do for now, it’s time for an iced chai and perhaps a delicious granola bar.

Summary

We have the rudiments of a flood fill here. For a full version, we need a method that loops until the queue is empty, and for path finding, we need to change the reached set to include back pointers. Seems simple enough. But this is enough for now. Tests are green. Commit: satisfied that expand works. ~~~