Continents? Paths?

We’ll start with a review of existing code, possibly clean up the border logic a bit. But we’ll at least start thinking about “continents” and paths between them.

Our maps seem to me to rather clearly show “continents”, two or more rooms that are touching, as well as single rooms:

So when it comes to connecting rooms together, we’ll probably put some kind of opening or door between adjacent rooms, the green borders, and we’ll need paths between the isolated continents. There are other possibilities for travel between rooms, such as magical doors or stargates, but generally there will be paths.

It seems to me that what one wants is for all the existing rooms to be connected, in the simple sense that there is, in the map, a way to get from any room to any other, There is probably some well-known algorithm, or many such algorithms, for determining whether a graph is connected or not, and our dungeon map is “obviously” a graph with rooms as nodes and doors and paths, if we had them, as the graph’s paths. We might explore that topic, but it’s more fun, and suits my purposes, to find our own way with these things.

We are here for two related purposes: I am programming for fun, and sharing with you the thoughts, ideas, discoveries, and practices that make up how I do things, in the hope that you find it entertaining and perhaps even useful.

Last night I drew up a couple of notes to help focus my thinking on the subject of identifying adjacent rooms and connecting them:

Digression

You may notice the red rectangles in those drawings. I have devised a “chop mark” in the past few days, and I’ll tell you why. Some of you may know that in my book The Nature of Software Development every chapter has a crude drawing, hand crafted by me for your amusement, enlightenment, and delectation. I continue to try to entertain myself by practicing drawing. I am still not very good at it, but I am better than everyone who doesn’t draw at all, which is good enough for me. I find drawing to be mentally relaxing, except for the final outburst of anger when I just can’t seem to draw what I’m thinking. I tend to scribble “Farquhar” on drawings that do not satisfy me, since crumpling up my iPad would get costly.

As I browse for ideas and help with the details of Procreate, my current favorite drawing app, I run across all kinds of interesting things, such as Celtic knots, floral decoration, and, most recently, Zentangle®. Zentangle is a semi-ritualistic practice of drawing patterns that are more structured than plain doodles, and very meditative through repeated patterns of drawing. Yet there are enough options that every drawing comes out unique.

One element of the Zentangle practice is to mark a completed tangle with a mark, one’s initials or a chosen pattern, like a Chinese or Japanese chop mark. So, in the spirit of things, I have created a chop mark, which is a stylized R, the letter that I commonly initial things with, because, well, let’s face it, my name starts with R. If you think you see a J also in the mark, well, I can’t stop you, but that just happened, it wasn’t part of my “design”.

So that’s what the red mark is, kind of my guarantee that these things are my product. More just a bit of fun, really. But I digress …

Continents

In the Connecting Continents diagram, I show a rudimentary data structure that might represent the continent structure shown in the picture:

[ [1], [2, 3], [4, 5, 6], [7] ]

That’s just a list of lists of room numbers. Of course our rooms don’t have numbers, so by the time we build something, it would be a list of lists of Room instances. And it might be better to have it be a list of Continent objects, each of which has a list of the Room instances that make it up.

Why, Ron?

My betters, such as the great Ward Cunningham and Kent Beck, told me that using native collections is generally inferior to creating smart collections that may contain native collections, but that provide a place to put meaningful, useful methods relating to the objects contained. My own experience, often painful experience, bears this advice out.

If we have a naked collection of, say, Rooms, then to find all the rooms containing a dragon, we have to write code in our own class to iterate the rooms, interrogate them, and accumulate the result. This tends to leave code all over that is peering into the collection and making assumptions about how it operates. The approach is error-prone and tends to make the code difficult to change.

If, instead, the RoomCollection class had a method satisfying(predicate), we could pass a predicate in and no matter how the collection is organized, that method would work.

dangerous_rooms = rooms.satisfying(lambda room: room.has_dragon())

We see above that the room, which is itself essentially a collection of all kinds of things, also benefits from having useful methods such as has_dragon. (I’m not saying that we’d do quite that. It’s an example, not a design.)

Anyway, the question becomes, how might we generate a list like the one above, containing a list of Continents, each having a list of rooms in the Continent? And in that diagram we find the words “Flood Fill?” signifying my best and only idea so far, which is just to wait until all the rooms are laid out and then pick one from the list of rooms in the dungeon, and start a flood fill that will fill cells belonging to any room, but will not fill “available” cells that are still in the CellSpace. As the fill proceeds, I’m thinking that we’d ask each cell added for its owner and add that owner to the current list of continental rooms. We’d remove that room from the list we’re iterating, repeat until there are no more rooms to examine.

I think that this morning we should work on that process, aiming to add a method to Dungeon to create a list of continents. We’ll probably proceed starting with simple lists and then see about doing something more intelligent. Or—this is barely possible—we might do something more intelligent right away. It could happen.

We’ll want to do this with tests, and I think the hard part might be creating the test. Maybe we can fake up something pretty simple.

We begin by verifying that we can have a one-cell room:

    def test_can_make_one_cell_room(self):
        space = CellSpace(10, 10)
        origin = space.at(5, 5)
        room = Room(space, 1, origin)
        assert len(room.cells) == 1

I did this because I wasn’t certain whether the room building loop would build one more than the number of cells requested. It doesn’t.

Now I’ll create some tiny rooms for my list-making code:

    def test_make_continent_lists(self):
        space = CellSpace(10, 10)
        dungeon = Dungeon()
        o_0 = space.at(3,1)
        r_0 = Room(space, 1, o_0)
        dungeon.add_room(r_0)
        o_1 = space.at(4,1)
        r_1 = Room(space, 1, o_1)
        dungeon.add_room(r_1)
        o_2 = space.at(1,4)
        r_2 = Room(space, 1, o_2)
        dungeon.add_room(r_2)
        o_3 = space.at(5,1)
        r_3 = Room(space, 1, o_3)
        dungeon.add_room(r_3)
        o_4 = space.at(5,6)
        r_4 = Room(space, 1, o_4)
        dungeon.add_room(r_4)
        o_5 = space.at(4,6)
        r_5 = Room(space, 1, o_5)
        dungeon.add_room(r_5)
        continents = dungeon.find_continents()
        assert len(continents) == 3

That provides six tiny rooms, assuming I’ve not messed up, which assumes facts not in evidence.

  0123456789
0|          
1|   013    
2|          
3|          
4| 2        
5|          
6|    54    
7|          
8|          
9|          

I could certainly improve that test code. PyCharm was very helpful, picking up the pattern and doing almost all the typing. The test is now failing, for want of a find continents method. We provide a particularly weak one:

    def find_continents(self):
        continents = []
        return continents

Now we fail because there aren’t three continents. We need to code the flood loop.

Long Delay

I’ve descended into abject hackery, trying to write this flood algorithm. I haven’t created a save point, although I can certainly roll back a single file if I need to.

I’ve found the main issue. Going to take a break now. Might have it in hand. I’ve been here 2 1/2 hours and I have around 30 lines of code, not counting tests, to show for it. We’ll discuss that, and see if this really works, after a break.

OK, I couldn’t resist peeking: it did work:

test_dungeon.py:56 (TestDungeon.test_make_continent_lists)
[[Room(5), Room(4)], [Room(0), Room(1), Room(3)], [Room(2)]] != []

Expected :[]
Actual   :[[Room(5), Room(4)], [Room(0), Room(1), Room(3)], [Room(2)]]

We’ll figure out how to assert that later. Defects included not adding new cells to the frontier. Later, I want a rest.

I’m back. Left at 1145, back at 1409. Let me complete the test and then we’ll see the code.

    def test_make_continent_lists(self):
        space = CellSpace(10, 10)
        dungeon = Dungeon()
        o_0 = space.at(3,1)
        r_0 = Room(space, 1, o_0, '0')
        dungeon.add_room(r_0)
        o_1 = space.at(4,1)
        r_1 = Room(space, 1, o_1, '1')
        dungeon.add_room(r_1)
        o_2 = space.at(1,4)
        r_2 = Room(space, 1, o_2, '2')
        dungeon.add_room(r_2)
        o_3 = space.at(5,1)
        r_3 = Room(space, 1, o_3, '3')
        dungeon.add_room(r_3)
        o_4 = space.at(5,6)
        r_4 = Room(space, 1, o_4, '4')
        dungeon.add_room(r_4)
        o_5 = space.at(4,6)
        r_5 = Room(space, 1, o_5, '5')
        dungeon.add_room(r_5)
        continents = dungeon.find_continents()
        assert len(continents) == 3
        sets = [set(c) for c in continents]
        assert {r_0, r_1, r_3} in sets
        assert {r_2} in sets
        assert {r_4, r_5} in sets

That setup could be refactored but it’s OK as is. I added an optional field to Room, a string to serve as a name, and changed the __repr__ to display it:

class Room:
    def __repr__(self):
        if self.name != '':
            return f'Room({self.name})'
        return f'Room(unknown)'

That helped me decode the various printouts that I used to find why my perfectly clear code wasn’t working. Here is that perfectly clear code:

class Dungeon:
    def find_continents(self):
        continents = []
        rooms = self.rooms.copy()
        while len(rooms) > 0:
            start_room = rooms.pop()
            found = self.find_connected_rooms(start_room)
            continents.append(found)
            for r in found:
                if r in rooms:
                    rooms.remove(r)
        return continents

    def find_connected_rooms(self, room):
        room_set = {room}
        frontier = [room.cells[0]]
        reached = []
        while len(frontier) > 0:
            cell = frontier.pop()
            neighbors = [n for n in cell.neighbors if n.unavailable()]
            for n in neighbors:
                room_set.add(n.owner)
                if n not in reached:
                    frontier.append(n)
                    reached.append(n)
        return list(room_set)

Let me explain. In find_continents, we are creating a list of “continents”, where, for now, a continent is a list of rooms. (It could be a set of rooms, and perhaps should be, as we’ll see below.) We make a copy of our list of rooms, as we intend to consume the list as we search for continents, groups of rooms that are connected.

We start with the first room in the list and call find_connected_rooms, passing it. We get back a list (could have been a set) of rooms connected to the one we started with. We remove all those rooms from the rooms list, because they are already processed. We’re done when there are no more rooms to process.

In find_connected_rooms, we are doing a pretty standard flood fill of the connected area. Our result set, room_set automatically includes the starting room. We start the fill frontier with the zeroth cell of the room, and initialize the set of reached cells to empty. I think that could be a set as well.

In finds loop we get all the current cell’s neighbors that are unavailable, i.e. not still in the CellSpace, i.e. therefore in a room. We add the cell’s owner, the room it’s in, to the result set and if we have not already reached this cell, we add it to the reached cells, and enqueue it for further study in frontier. This is a standard flood fill.

When there are no more cells in the frontier, we have examined all the cells in all the rooms that are connected, and we return the resulting room_set as a list.

We’ll stop coding now, and reflect and sum up.

Summary

It took me longer than I would care to admit to get this working. My main mistakes were not updating the frontier, and various errors about removing things that had already been removed. I also became confused by the room vs the name of the room, and at least once used a cell where I meant to use a room. It wasn’t a debacle but it was definitely a debugging session, not just typing in the code and seeing it work.

From a testing standpoint, I think this first test is pretty solid, though I would like to try it with more than one cell in some of the rooms, mostly to be sure we don’t get an error removing something that has already been removed or the like.

It seems to me that sets lend themselves well to this effort, so far, and that we should probably use them where we can.

The code could almost certainly be improved by some judicious refactoring … and since we have another flood fill in PathFinder class, we might want to look to see whether there is benefit to collapsing those together. They use different criteria for cells to accept, but are otherwise pretty similar, I think.

A detail: there’s a method is_available and one unavailable on Cell. Their names should be more consistent.

Still, we have a solid test that is passing, and the feature is not in production use, so it is harmless. We commit: Dungeon is finding lists of rooms that are adjacent, “continents”.

I’ll be showing the FGNO Zoom¹ this code tonight and will see how they rip it to shreds. I’ll report back if anything really good shows up.