I think I’ll experiment with a kind of cell that has x and y but really only as data for display, using just neighbors to show relationships. This may get weird. Experiment succeeds: Not a good idea.

Here is a picture I sketched to settle my thoughts a bit:

graph of cells

This represents, in my mind, a small area of cells or nodes. The inner ones have four neighbors, the edge ones have three, and the corners only have two. I have no good idea how to build such a thing. Let’s imagine a new class GraphNode, and work up to a web of them.

After just a bit of work, I have this test running:

    def test_row(self):
        y = 0
        left = None
        nodes = []
        for x in range(6):
            current = GraphNode(x, y)
            nodes.append(current)
            if left is not None:
                current.add_neighbor(left)
                left.add_neighbor(current)
            left = current
        assert len(nodes) == 6
        node_03 = nodes[3]
        assert node_03.x == 3
        assert node_03.y == 0
        assert node_03.has_neighbor(2, 0)
        assert node_03.has_neighbor(4, 0)

With this code:

class GraphNode:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.neighbors = set()

    def add_neighbor(self, node):
        self.neighbors.add(node)

    def has_neighbor(self, x, y):
        return any((n.x ==x and n.y ==y) for n in self.neighbors)

All the work is being done in the test loop where we create a row of backward and forward linked GraphNode instances. I think we can improve that slightly:

    def test_row(self):
        y = 0
        left = GraphNode(0, y)
        nodes = []
        nodes.append(left)
        for x in range(1,6):
            current = GraphNode(x, y)
            nodes.append(current)
            current.add_neighbor(left)
            left.add_neighbor(current)
            left = current
        assert len(nodes) == 6
        node_03 = nodes[3]
        assert node_03.x == 3
        assert node_03.y == 0
        assert node_03.has_neighbor(2, 0)
        assert node_03.has_neighbor(4, 0)

We avoid the if by initializing left with the 0th element and iterating from 1.

We can check a couple of other interesting cells. 0 and 5 should have just one neighbor each:

        assert node_03.y == 0
        assert node_03.has_neighbor(2, 0)
        assert node_03.has_neighbor(4, 0)
        assert len(nodes[0].neighbors) == 1
        assert nodes[1].has_neighbor(2, 0)
        assert len(nodes[5].neighbors) == 1
        assert nodes[5].has_neighbor(4, 0)

Passing. So I can create a row. How about linked rows? I’ll have to think about that.

Reflection

The list manipulation needed to link them up is a lot. At some cost in performance, we could make them look up their links by arithmetic, if they knew some basic “bank” kind of object, in fact maybe just a list of lists. If we’re going to let the owners be either None or an object (room, path, whatever) maybe we don’t need a slower lookup in the CellBank.

How would we handle the edges? One nice property that the GraphNode is trying to have is that edge nodes only get one neighbor along the edge dimension. Maybe something like:

    def neighbor_cells(self):
        possible_addresses = [(-1,0),(1,0),(0,-1),(0,1)]
        possible_neighbors = [(self.x+n.x, self.y +n.y) for n in possible_addresses]
        return [p for p in possible_neighbors if self.in_range(p)]

    def in_range(self, p):
        x_max = 64
        y_max = 56
        return 0 <= p[0] < x_max and 0 <= p[1] < y_max

I’d rather have p.x and p.y there at the end than p[0] and p[1], but the idea is there anyway. Even so, it’s rather messy. I think the two-dimensional array supported by lists of rows (or columns) is likely a better way forward.

Summary

So, the experiment succeeded in telling me that linking things four ways is probably not what I want to do, and leads me to think basing the space on a simple array may be just the thing. We might be able to work in small steps, putting the array inside a CellBank and then backing slowly away from it.

I’ve committed the test and code and I expect to mostly ignore it going forward, but it is there if we ever want it.

See you next time!