Yesterday’s experiment successfully showed me that I had a terrible idea. Today … a similar success!

Added in Post
Today’s experiment shows me that the world isn’t ready for today’s idea. Feel free to read on, skip forward, or return to your other daily activities. Inside you’ll see me work up a decent little class only to discover that I can’t quite wedge it in where it should go.

So weaving all the cells together seems to be a non-starter. Arguably we knew that going in but I really did want to try it. I think that if the structure were to exist, it would be easy to traverse and process. But building it was so messy that, well, no, let’s not do that.

Today, I think I’ll work with the scheme I mentioned yesterday, basing all the cells in a “space”, probably just a 2d array of cells. That should allow a cell to find its neighbors quickly, assuming that either a) each cell has the space, or b) we pass the space into operations as a parameter. Conventional wisdom would have it that the space should be passed in, and I plan not to follow that advice and try having the cell know its space.

At this writing, I’m working toward a cell having an owner, which it will also know. An owner might be the room or path that the cell is “in”. My current intention is that a cell in what we’re now calling the CellBank will have no owner, and the CellBank will become unused for its current purpose, holding available cells. We may find that we want to use the class elsewhere, such as to hold the cells in a room. We might reuse it, or just borrow the form of its implementation. Depends what the code wants.

I’ve committed yesterday’s separate GraphNode tests and class, and will remove the file now and recommit, so as not to have random stuff hanging about, smoking reefers and cat-calling the other classes.

How to Proceed?

I propose to improve Cell in place, refactoring to use a new member variable, space. We’ll TDD that as well, but first we’d better improve Cell’s tests a bit.

We have essentially no direct tests for Cell, although it is of course well exercised by our other tests. Here’s the whole class. I think we’ll begin with a test for neighbors, because with our new scheme that will change.

class Cell:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __eq__(self, other):
        if isinstance(other, Cell):
            return self.x == other.x and self.y == other.y
        return False

    def __hash__(self):
        return hash((self.x, self.y))

    def __iter__(self):
        return iter([self.x, self.y])

    @property
    def neighbors(self):
        deltas = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        neighbors = []
        for dx, dy in deltas:
            neighbors.append(Cell(self.x + dx, self.y + dy))
        return neighbors

    def manhattan_distance(self, target):
        return abs(self.x - target.x) + abs(self.y - target.y)

The rudimentary test below passes while I pause to think:

    def test_neighbors(self):
        cell = Cell(2, 3)
        neighbors = cell.neighbors
        assert len(neighbors) == 4

My first thought was to create the four expected cells and check them for being in the neighbors list, but I’m a bit concerned that I’ll just have to fix up the test later. I guess all of them will need to be fixed up, so we’ll just do the obvious thing:

    def test_neighbors(self):
        cell = Cell(2, 3)
        neighbors = cell.neighbors
        assert len(neighbors) == 4
        for n in [Cell(1,3), Cell(3,3), Cell(2,2), Cell(2,4)]:
            assert n in neighbors

Passes. Note that the test creates new Cells here, and that they are found in the list. That’s because of the __eq__ and __hash__ methods on Cell. I’m not sure if we’re going to retain that aspect or not. We’ll worry about that later.

We’re green, commit: test neighbors.

Space

Let’s TDD up a CellSpace, which will be little more than a 2D array for now, although we’ll probably find that it needs more capabilities as we work.

class TestCellSpace:
    def test_exists(self):
        space = CellSpace(3,5)
        c23 = space.at(2,3)
        assert c23.x == 2
        assert c23.y == 3

This demands:

class CellSpace:
    def __init__(self, x_size, y_size):
        self.rows = []
        for y in range(y_size):
            row = []
            self.rows.append(row)
            for x in range(x_size):
                row.append(Cell(x, y))

    def at(self, x, y):
        return self.rows[y][x]

I actually did that in two phases but found myself initializing the Cells, so I enhanced the test and continued. Test passes. Standard 2D array in Python. Naturally, I got x and y reversed the first time through. I always do.

Tests are green. Commit: initial CellSpace.

Our next step will be to modify Cell to have space, so we’d better move the class to the ‘src’ folder.

    def test_cells_know_space(self):
        space = CellSpace(3, 5)
        c14 = space.at(1, 4)
        assert c14.space == space

Fails, of course. Code:

class CellSpace:
    def __init__(self, x_size, y_size):
        self.rows = []
        for y in range(y_size):
            row = []
            self.rows.append(row)
            for x in range(x_size):
                row.append(Cell(x, y, self))

Change signature of Cell __init__:

class Cell:
    def __init__(self, x, y, space):
        self.x = x
        self.y = y
        self.space = space

I expect green but my test is failing, with None coming back:

    def test_cells_know_space(self):
        space = CellSpace(3, 5)
        c14 = space.at(1, 4)
>       assert c14.space == space
E       assert None == <cellspace.CellSpace object at 0x103216f90>
E        +  where None = <cell.Cell object at 0x1032c2d50>.space

I am confuse and disappoint. What silly mistake have I made? Oh! PyCharm fixed my setting inside CellSpace, replaced the self with None. With the code set back to look like the above, we’re green. Commit: Cells know their space.

Issues

We have at least two:

  1. We have cells being created all over with no space. The tests all run, but we should look at what’s going on.
  2. We want to change neighbors in Cell to use the space to find the actual neighbors, which are soon going to have more memory than they currently do.

We’ll do 2 first, changing this:

    @property
    def neighbors(self):
        deltas = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        neighbors = []
        for dx, dy in deltas:
            neighbors.append(Cell(self.x + dx, self.y + dy, None))
        return neighbors

I notice, looking at that, that we’ll happily create neighbors that are outside the CellBank we have been using but presumably CellBank won’t return anything. We want that behavior in space as well. Let’s do a new test for that.

    def test_missing_cells_return_none(self):
        space = CellSpace(3, 5)
        c_outside = space.at(-1,6)
        assert c_outside is None

Fails, thus:

    def at(self, x, y):
>       return self.rows[y][x]
               ^^^^^^^^^^^^
E       IndexError: list index out of range

We code:

    def at(self, x, y):
        try:
            return self.rows[y][x]
        except IndexError:
            return None

Test passes. PyCharm helped me a bit too much with the test. I may have to turn off some of its predictions: sometimes it is reasonable but wrong and I don’t notice.

Commit: CellSpace at returns None for out of range requests.

I think we should have a new neighbors test, because if we are on the edge or a corner we want to return only the non-None neighbors.

    def test_edge_neighbors(self):
        space = CellSpace(2,3 )
        cell = space.at(0,0)
        neighbors = cell.neighbors
        assert len(neighbors) == 2

This is failing, returning 4. Time to change neighbors. WHen we do, at least one other test is going to fail: the initial neighbors test isn’t using space yet.

    @property
    def neighbors(self):
        deltas = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        neighbors = []
        for dx, dy in deltas:
            cell = self.space.at(self.x + dx, self.y + dy)
            if cell is not None:
                neighbors.append(cell)
        return neighbors

I’m mistaken about a test failing. Eleven fail. Let’s review a couple:

Whoa! My most recent one is still coming back with 4. No need to look further yet.

Oh! Darn! -1 is a valid index into a list. My try/except solution (not shown) won’t cut it.

    def at(self, x, y):
        if 0 <= x < self.x_size and 0 <= y < self.y_size:
            return self.rows[y][x]
        else:
            return None

My new test passes (yay!) but still ten are failing, presumably because now we must have a space. Let’s check some of them and see what we’ll have to do.

I fix up the other neighbors test first:

    def test_neighbors(self):
        space = CellSpace(5,5)
        cell = space.at(2,3)
        neighbors = cell.neighbors
        assert len(neighbors) == 4
        for n in [space.at(1, 3), space.at(3, 3), space.at(2, 2), space.at(2, 4)]:
            assert n in neighbors

I’m still not sure if we’ll go ahead and fix the 9 remaining failures or roll back. Here are three that are failing:

    def test_adding_rooms(self):
        dungeon = Dungeon()
        assert dungeon.number_of_rooms == 0
        bank = CellBank(100, 100)
        size = 10
        origin = Cell(32, 28, None)
        room = Room(bank, size, origin)
        dungeon.add_room(room)
        assert dungeon.number_of_rooms == 1

    def test_build(self):
        random.seed(234)
        bank = CellBank(64, 56)
        size = 100
        origin = Cell(32, 28, None)
        room = Room(bank, size, origin)
        assert len(set(room.cells)) == 100
        assert room.origin == Cell(32, 28, None)
        self.verify_contiguous(room)

    def test_constrained_room(self):
        random.seed()
        bank = CellBank(10, 10)
        for c in range(10):
            bank.take_xy(0, c)
            bank.take_xy(9, c)
            bank.take_xy(c, 0)
            bank.take_xy(c, 9)
        origin = Cell(5, 5, None)
        size = 100
        room = Room(bank, size, origin)
        assert len(room.cells) == 64

Those all use CellBank. I think we might be able to finesse these with some clever changes to CellBank. We’re going to get rid of its use for determining availability, however, and perhaps remove it entirely. Let’s look at the other tests.

Note
I “know” that the right thing to do here is to roll back or otherwise remove my current Cell logic and proceed in a fashion that won’t break tests. I don’t want to do that: I want to “just” fix the failing 9 tests. But in a real situation it might be 90 and fixing them would be out of the question. So ideally, I’ll roll back and show that there’s a better way.

I’m glad we had this little chat. I hereby commit to try to go in smaller steps. Let’s review the other broken tests to inform our search for smaller moves to make.

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

CellBank again. That seems to be the crux. We use CelLBank everywhere, and unwinding it will be tricky.

OK, revert the last change to Cell, the neighbors method. Now the only failing test is my new one with the edge neighbors. Fix that because it’s wrong anyway, from this:

    @property
    def neighbors(self):
        deltas = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        neighbors = []
        for dx, dy in deltas:
            neighbors.append(Cell(self.x + dx, self.y + dy, None))
        return neighbors

To this, with two extract variable and an if: …

No. Can’t hack this to work. Ignore the test. Fold tests for today, creep away in the darkness.

Another Successful Experiment

Again we have succeeded in showing that a good-seeming idea wasn’t as good as it seemed. I think the space idea is a good one, it’s just that putting it in as we tried this morning wasn’t suitable. Furthermore …

CellBank is a lot like CellSpace, with two related differences:

  1. It uses a dictionary indexed by (x,y) rather than lists;

  2. We remove things from the bank to signify that they are not available, and the CellSpace thinking was that we’d ask the Cell whether it is available.

So, next time, I think we’ll try modifying CellSpace in place, to pass itself to the Cells (if that still seems to make sense) and to allow the cells to decide their status.

Unless … if I recall way back two or three days ago, we started on this quest because the objects, particularly Cell, if I recall, were not helping enough. It will probably pay off to start back at that starting point tomorrow, revise ideas in the light of these two experiments, and then decide on a way forward.

It’ll probably be worth thinking about our upcoming need for new capabilities, in case the best move is to leave things as they are and add some new capability.

Summary

Two ideas relating to the cell storage have turned up as not so good. The first was eliminated because building the structure was looking so arcane that it seemed not worth the complexity to do it. The second much simpler idea, a 2D array, turns out to work but the object wouldn’t slot easily into our existing tests and code. It would have been possible to fix everything up, but when that much breaks, it’s a good signal that the code isn’t ready for the new idea, or that the new idea isn’t well suited to the code. And why not both?

So another little experiment. I’ll commit and then delete the new object, so we’ll have it if we need it but not be tempted or confused by it. It’s important for me to avoid confusion.

Should we feel bad when an idea doesn’t work out? I myself do not: I consider trying ideas part of the thinking and decision process. Often we think that color would look good on the walls but it does not. With small experiments, we avoid painting the whole room before we find out why “puce” reminds us of another word.

We’ll hit it again tomorrow if the crick don’t rise. See you then!