Looking Around

Some small refactoring steps, very small. One rollback, no idea what happened.

Well, of course we need a bit more design improvement: we can always find something to improve. However, this little program surely still has a few sharp edges that need to be smoothed. Let’s make a list of new capabilities that seem near the top of the list, and then review some code.

Border Spaces: I think I’d like rooms not to touch each other. I think it’ll make a better dungeon, and that it might help avoid isolated rooms that might confuse path-finding. At some point, we’ll probably experiment with reserving a few cells around the periphery of each room. If we do that, we’ll need to put them back before path-finding.
Paths Between Rooms: The point of the path finding code is to create paths between rooms. We need to complete that capability, which will require a slightly smarter pathfinder algorithm. It also seems wise, when pathfinding, to stop the flood when we reach the target. Presently, I think, the flood continues until we’ve scanned the whole space.
Dungeon Intelligence: The dungeon class will need to be enhanced to understand paths, and doubtless many other capabilities.
Game Play: If this is going to turn into an actual game, there will be plenty more to do.

Looking Around

I’m going to start this morning’s “looking around” phase with Manhattan distance, since I made a note of that yesterday: It’s only needed in a test right now, but even so, I want it done by the Cell, because the less people know about cells the better.

So the test:

    @staticmethod
    def manhattan(source, target):
        return abs(source.x - target.x) + abs(source.y - target.y)

    def test_path(self):
        bank = CellBank(10, 10)
        finder = PathFinder(bank)
        source = Cell(3,3)
        target = Cell(7,6)
        dist = self.manhattan(source, target)
        assert dist == 7
        path = finder.find_path(source, target)
        assert len(path) == dist + 1
        assert path[0] == target
        assert path[-1] == source
        distance = sum(self.manhattan(s1, s2) for s1, s2 in pairwise(path))
        assert distance == dist

Ah, as we look at this we see two uses of manhattan. Let’s just change one:

dist = source.manhattan_distance(target)

PyCharm knows that Cell does not have that method and offers to create a method on Cell. Let’s see what it offers: it’ll at least give us the shell.

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

It created the shell with a pass. As soon as I typed the r in return, it offered that code, which is correct. Test. Green. Commit: implement and use manhattan_distance.

Now use it in the other place:

distance = sum(s1.manhattan_distance(s2) 
    for s1, s2 in pairwise(path))

Green. Commit: use manhattan_distance.

Looking in this same test file, I see this code, which I do not like much:

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

It’s that last bit, where we create the cell by taking the tuples apart. I can think of at least two ways to improve this:

Add a from_tuple method to Cell;
Make Cell(…) accept either one tuple or two values.

The latter seems a bit fancy but I think we’ll try it, to see how nasty it gets.

Again, wishful thinking, I’ll write the code the way I want it and deal with the situation

No, wait. I could have written this in the test:

for x, y in [(1,2), (2,1), (3,2), (2,3)]:
    assert Cell(x, y) in cells

That’s easy enough and expressive enough. We’ll just do that and avoid the cuteness.

Two places found. Commit: tidying test code.

But now I find this:

    def test_flood_uses_bank(self):
        bank = CellBank(5, 5)
        taken = [(3,3), (1,4), (2,1)]
        for t in taken:
            bank.take(*t)
        finder = PathFinder(bank)
        finder.put(Cell(1,2))
        finder.flood()
        assert len(finder.reached) == 25 - len(taken)
        for t in taken:
            assert t not in finder.reached

The bank.take(*t) caught my eye. The bank is a CellBank, containing cells. It seems to me that we should be taking cells, not coordinates. Let’s look into that further.

class CellBank:
    def __init__(self, max_x, max_y):
        self.cells = set()
        for x in range(max_x):
            for y in range(max_y):
                self.cells.add(Cell(x,y))

    def __iter__(self):
        return iter(self.cells)

    def has_cell(self, x, y):
        return Cell(x,y) in self

    def take(self, x, y):
        self.cells.discard(Cell(x, y))

We implemented __iter__ to allow use of in. There are senders of has_cell. Let’s root them out.

class Room:
    def grow_randomly(self, bank):
        for cell in sample(self.cells, len(self.cells)):
            neighbors = self.neighbors(cell)
            for x, y in sample(neighbors, len(neighbors)):
                if bank.has_cell(x, y):
                    bank.take(x, y)
                    self.add_cell(x, y)
                    return
        return

Oh we can do much better than that. neighbors returns Cell instances and we are disassembling them unnecessarily.

However. The slight but significant messiness here runs a bit deep:

class Room:
    def add_cell(self, x, y):
        self.cells.append(Cell(x,y))

    def has_cell(self, x, y):
        return (x,y) in self.cells

We’ll have to be careful. We just have the one use of has_cell, so that should be OK to change:

Wait. Do we even use grow_randomly?? We do not. Super, remove it, problem solved. While doing that, however, I find a static neighbors method in Room. Time to get rid of it? No, let’s finish the in first.

Here’s one:

# main.py

def random_available_cell(bank: CellBank) -> tuple[int, int]:
    while True:
        x = random.randint(0, 63)
        y = random.randint(0, 55)
        if bank.has_cell(x, y):
            break
    return x, y

Let’s have CellBank provide a random cell. This function is used here:

def main():
    bank = CellBank(64, 56)
    # random.seed(234)
    dungeon = Dungeon()
    number_of_rooms = random.randint(12, 12)
    for _ in range(number_of_rooms):
        room = Room()
        size = random.randint(90, 90)
        x, y = random_available_cell(bank)
        room.build(bank, size, (x,y))
        dungeon.add_room(room)
    dungeon.find_path(Cell(0,0), Cell(63,55), bank)
    view = DungeonView(dungeon)
    view.main_loop()

Shouldn’t room.build be expecting a Cell, not a tuple?

    def build(self, bank, length, start_cell):
        new_cell = start_cell
        for _ in range(length):
            bank.take(*new_cell)
            self.add_cell(*new_cell)
            new_cell = self.find_adjacent_cell(bank)
            if new_cell is None:
                return

It comes down to take again. We’ll proceed carefully, just removing the in for now, so that our steps are small and we don’t break (too many) things. We will, however, do the random available cell method since it is easy:

def random_available_cell(bank: CellBank) -> tuple[int, int]: 
    x,y = bank.random_avaialble_cell()
    return x, y

Again PyCharm offers to create the method. It also corrects my typo.

    def random_available_cell(self):
        return random.choice(list(self.cells))

I am a bit irritated at the need to convert my set of cells to a list for this but it’ll do for now.

Green. Commit: create and use random_available_cell.

Where were we? Oh, right, removing need for has_cell. Are there any more senders? No. Remove, test, green, commit: remove unused has_cell

Now we only use add_cell locally in Room:

class Room:
    def add_cell(self, x, y):
        self.cells.append(Cell(x,y))

    def build(self, bank, length, start_cell):
        new_cell = start_cell
        for _ in range(length):
            bank.take(*new_cell)
            self.add_cell(*new_cell)
            new_cell = self.find_adjacent_cell(bank)
            if new_cell is None:
                return

Let’s convert this to think in Cells. I’ll add some type hints, because PyCharm makes pretty good use of those.

I’ve broken something. Not sure what. Roll back. Proceed again, differently.

Rename CellBank take to take_xy:

    def take_xy(self, x, y):
        self.cells.discard(Cell(x, y))

Refactor to have a new method take for Cell instances.

    def take_xy(self, x, y):
        self.take(Cell(x, y))
        
    def take(self, cell: Cell):
        self.cells.discard(cell)

Test. Green. Commit: refactoring. OK, now can I improve the build?

    def add_cell(self, x, y):
        self.cells.append(Cell(x,y))

    def build(self, bank, length, start_cell):
        new_cell = start_cell
        for _ in range(length):
            bank.take_xy(*new_cell)
            self.add_cell(*new_cell)
            new_cell = self.find_adjacent_cell(bank)
            if new_cell is None:
                return

    def find_adjacent_cell(self, bank):
        for cell in sample(self.cells, len(self.cells)):
            neighbors = self.neighbors(cell)
            for neighbor in sample(neighbors, len(neighbors)):
                if neighbor in bank:
                    return neighbor
        return None

Now it seems to me that we have only cells here, and that I should be able to type hint them, but when I did something went wrong. Try again. With this much:

    def find_adjacent_cell(self, bank: CellBank):
        for cell in sample(self.cells, len(self.cells)):
            neighbors = cell.neighbors
            for neighbor in sample(neighbors, len(neighbors)):
                if neighbor in bank:
                    return neighbor
        return None

I can remove the neighbors method from Room. Do it, test, commit.

    def build(self, bank, length, start_cell):
        new_cell = start_cell
        for _ in range(length):
            bank.take_xy(*new_cell)
            self.add_cell(*new_cell)
            new_cell = self.find_adjacent_cell(bank)
            if new_cell is None:
                return

We should be able to use take here. But no. When I do that weird errors occur.

Ah. Some folx are sending us tuples. Let’s demand Cells. OK, found all the senders of build and fixed them to use a Cell. Now this works:

    def build(self, bank, length, start_cell: Cell):
        new_cell = start_cell
        for _ in range(length):
            bank.take(new_cell)
            self.add_cell(*new_cell)
            new_cell = self.find_adjacent_cell(bank)
            if new_cell is None:
                return

Green, commit. Now I can fix the add bit.

    def build(self, bank, length, start_cell: Cell):
        new_cell = start_cell
        for _ in range(length):
            bank.take(new_cell)
            self.cells.append(new_cell)
            new_cell = self.find_adjacent_cell(bank)
            if new_cell is None:
                return

And remove the now unused add_cell. Green. Commit.

I draw a map just to be sure that still works, and it is an interesting one:

map with huge tracts of land

Map with huge tracts of land

Those huge tracts of land concern me a bit, with regard to paths between the rooms. I guess we’ll probably allow paths to cross, which might actually make for some interesting choices in game play. And nothing is really isolated. So probably paths will work just fine here. We’ll see: that is for the future anyway.

It all makes me think that we need some classifications on the cells in rooms: are they interior or peripheral, are there paths going through them, things like that. Again, future issues. I don’t see any show-stoppers.

Where are we?

We started this recent quest chasing take(*t), which led us to replace that with take_xy and to have a take that expects a Cell. Generally speaking, I think we want our objects dealing with Cells and not with raw coordinates. What if cells were hexagons, for example? We’d want to be able to make that work without too much hassle, so the less people manipulate x and y, the better.

We seem to have a number of places where we iterate over some cells to find one or more that meet some condition, for example:

    def find_adjacent_cell(self, bank: CellBank):
        for cell in sample(self.cells, len(self.cells)):
            neighbors = cell.neighbors
            for neighbor in sample(neighbors, len(neighbors)):
                if neighbor in bank:
                    return neighbor
        return None

That finds a random cell in the room with a random neighbor that is available in the bank. That is, an available cell adjacent to the room. We do that sort of thing in a few places, and we might do well to provide better support for finding available cells that meet some condition.

In this particular case, if we were to cull out room cells with no neighbors (interior cells) the search would run faster, which would be nice. It takes a second or two to bring up the map window. I hate waiting.

Summary

We’ve improved the code a bit in Room and elsewhere, by providing better facilities on other objects, notable Cell and CellBank. And we’ve provided for further improvement, such as the replacement of calls to take_xy with calls to take, which will clean up some tests a bit, if nothing else.

All that is for another day. Next time, I think we’ll do some more work on path finding, in particular, connecting rooms with paths. That will require us to accept, as part of a path, cells that are available in the bank, and to take them, but also to accept cells that are in either of the rooms being connected. It’ll be a bit tricky, but just a bit.

For today, this will do. See you next time!