None of my notes on cards appeal. Let’s look at the code and see what it suggests.

It’s Sunday morning, there will be bacon in the offing, and I don’t have anything particularly in mind to work on. The must interesting two card notes are:

  1. Cell class is large;
  2. Change CellSpace to sparse?

The CellSpace data structure is a list of lists of cells, Python’s best shot at a 2D array. There’s not much reason to go to a sparse structure, it seems to me. We might save half, maybe even 2/3 of the cell instances, depending on how full the dungeon space gets. How big is a level going to be? I’m building 64x56 cells, because it happens to fit my screen well, and we get nice dungeons at that size, maybe a dozen or twenty rooms. We allocate 3,584 cells at that scale. If we doubled the size, about 7,000. My MacBook Air only has 16 gigabytes of memory, and it’s still difficult to get excited about 7,000 cell instances. So that seems like something we don’t need.

As for Cell being large, it is about 150 lines counting white space, which is a bit large by my usual standards. Let’s have a glance at that class. I’ll just show you what catches my eye.

I notice that we have __eq__ and __hash__ defined. I think we don’t need that any more, that we have rigged things so that no one creates raw cells, we always use the ones in the space. I’ll remove those two methods and see if any tests break. None do. I’ll run main. It works. That reminds me to remove the random.seed used to pin things down for the bug search. We’re green. Commit.

I notice the init:

class Cell:
    def __init__(self, x, y, space):
        self._x = x
        self._y = y
        assert space is not None
        self._space = space
        self._room = None

Are we using _space for anything now?

class Cell:
    deltas = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    space = None
    
    def at_offset(self, dx, dy):
        new_x, new_y = self.x + dx, self.y + dy
        return self._space.at(new_x, new_y)

But we have that class variable space. Can’t we just use that? That works, but I’m not happy. Revert.

First, let me bring one class method up where we can better see it:

class Cell:
    deltas = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    space = None

    @classmethod
    def create_space(cls, max_x, max_y):
        cls.space = CellSpace(max_x, max_y)
        return cls.space

    def __init__(self, x, y, space):
        self._x = x
        self._y = y
        assert space is not None
        self._space = space
        self._room = None

Now, in CellSpace, I think we are passing self to all the Cell, and we are about to make them ignore that, so let’s see what gives and then change the signature of Cell creation.

class CellSpace:
    def __init__(self, max_x, max_y):
        self.cells: list[Cell] = list()
        self.cell_array: list[list[Cell]] = list()
        self.width = max_x
        self.height = max_y
        for x in range(max_x):
            col = []
            self.cell_array.append(col)
            for y in range(max_y):
                cell = Cell(x, y, self)
                self.cells.append(cell)
                col.append(cell)

There in the antepenultimate line, we see the passing of self, the CellSpace. We are working to have no need of that, so it’s best to start here and remove the attempt, because of the way the word space is used in Cell.__init__. I’ll look for other creators of cell. Just that one. OK.

Something that has caused me trouble is the fact that as written, CellSpaces knows how to create a Cell, and Cell knows how to create a CellSpace. This makes hinting and importing difficult. CellSpace only has three methods, __init__, at, and random_available_cell.

Let’s sort of reverse direction, and instead of making Cell smaller, let’s make it larger, but lose the entire CellSpace class.

I’m pretty sure that I could just recode some stuff in Cell and pretty soon be all better, but since this code is pretty central to everything we’re doing, I’d prefer to get as much help from PyCharm as possible. Let’s see the rest of CellSpace:

    def at(self, x, y) -> Cell|None:
        if 0 <= x < self.width and 0 <= y < self.height:
            return self.cell_array[x][y]
        else:
            return None

    def random_available_cell(self) -> Cell | None:
        available: list[Cell] = [cell for cell in self.cells if cell.is_available]
        if available:
            return random.choice(available)
        else:
            return None

It is a bit odd that CellSpace keeps two copies of each Cell, one in the 2D list of lists and one in the separate list cells. Presumably I did that for “efficiency”, or, perhaps more likely, because I didn’t want to take the time to work out a generator.

Musing …

I’ve been supposing that we’d just add a class variable to Cell, holding the list of lists of Cell instances. This might be a good time to rethink what data structure we want. A dictionary from (x,y) to Cell would work fine. It could even be sparse if we wanted, subject to working out when to make a new Cell.

A case could be made that it’s not a good idea to keep the instances of a class in a class variable, and that a separate structure, an instance of some specialized collection class is better. That is what we have in CellSpace, with the somewhat irritating fact that a Cell knows its space, whether via the member variable _space we just removed, or via the class variable space, which we have kept.

That’s an interesting concern, and I want to think about it. But our Cell instances can find their neighbors and in fact can produce cells more distant from themselves, and we make use of the neighbor concept often.

A quick diversion to look at the offset method and its callers tells me that 3 only ever ask for the cell one step away in some direction, but one, in PathHelper, looks for cells some distance away, which it uses to try to make a more wiggly path. We could probably deal with that if we needed to, but let’s not worry about it.

I think we should refactor CellSpace either to use just the list of lists, or to use a dictionary, and not to have the separate list of all cells. That will make moving its capability into Cell class easier.

class CellSpace:
    def __init__(self, max_x, max_y):
        self.cell_array: list[list[Cell]] = list()
        self.width = max_x
        self.height = max_y
        for x in range(max_x):
            col = []
            self.cell_array.append(col)
            for y in range(max_y):
                cell = Cell(x, y, self)
                col.append(cell)

    def random_available_cell(self) -> Cell | None:
        available = [cell for col in self.cell_array for cell in col if cell.is_available]
        if available:
            return random.choice(available)
        else:

That’s green, and it wasn’t until I got it right. Commit: remove cells member.

I don’t see a set of tiny steps for this. But I do think I can just make it work. Let me try.

First, I did this:

class Cell:
    deltas = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    space = None
    cell_array = list()
    width = 0
    height = 0

    @classmethod
    def create_space(cls, max_x, max_y):
        cls.width = max_x
        cls.height = max_y
        for x in range(max_x):
            col = []
            cls.cell_array.append(col)
            for y in range(max_y):
                cell = Cell(x, y)
                col.append(cell)
        cls.space = CellSpace(max_x, max_y)
        return cls.space

That works, since it just creates a bunch of class variables that we don’t use. Commit a save point.

Does anyone use the returned value from create_space? No one does. Remove the return. Commit again.

The result is this:

class Cell:
    deltas = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    cell_array = list()
    width = 0
    height = 0

    @classmethod
    def create_space(cls, max_x, max_y):
        cls.cell_array = list()
        cls.width = max_x
        cls.height = max_y
        for x in range(cls.width):
            col = []
            cls.cell_array.append(col)
            for y in range(cls.height):
                cell = Cell(x, y)
                col.append(cell)

    def __init__(self, x, y):
        self._x = x
        self._y = y
        self._room = None

    @classmethod
    def at(cls, x, y):
        if 0 <= x < cls.width and 0 <= y < cls.height:
            return cls.cell_array[x][y]
        else:
            return None

    @classmethod
    def unused_cell_or_none(cls):
        available = [cell for col in cls.cell_array for cell in col if cell.is_available]
        if available:
            return random.choice(available)
        else:
            return None

We are green. main works. Commit: remove CellSpace class, work done in Cell class methods

Let’s sum up.

Summary

After looking around, I started to look at simplifying Cell class. Instead of doing that, I decided to remove CellSpace class entirely, instead storing Cell instances in Cell class variables. To do that entailed:

  1. Removing a parameter from Cell creation, space;
  2. Adding three class variables and removing one for a net increase of two;
  3. Making create_space class method larger by subsuming what CellSpace did;
  4. Making at class method larger ditto;
  5. Making unused_cell_or_none larger ditto;
  6. Removing the entire CellSpace class.

The total number of lines in the program is probably a bit lower, just a few. Cell is unquestionably more complicated, but not distressingly so. We’ll look at it again, because it is still our largest class.

The program’s complexity is a bit lower, because we used to have a bidirectional connection between Cell and CellSpace, and that is gone. This may help us with imports: we’ll see.

I think Cell would be simpler, and not much slower if at all, if we were to use a dictionary to store the cells, indexed by (x,y) but that can wait.

I believe that the strongest objection to this structure is that we still have the situation where the cells, in effect, know their own collection. Folx would argue that we should have stuck with the separate Space to hold them, and given cells just their local knowledge. I might take this up with the Friday Geeks Night Out gang this coming Tuesday night, if we have time.

It seems to me to be very convenient to be able to deal only with the cells, accessing their neighbors as needed, and referring to the class only to create a new space, and to access a cell at a desired location. We presently do that 111 times, of which 107 are in tests, setting up or checking the details of arrangements.

What is most odd, is that we pretty much set out with making Cell simpler in mind and in fact made the overall program a bit simpler, and made Cell a bit more complex. But as for me, I am pleased to have CellSpace out of my face, and I think we’ll be able to make things ever better. As one does.

See you next time!