Furthest Cells
Today we start by actually finding furthest points. We need also to remove the path map code. And maybe a “final” look at the new
generatecode. The morning goes well: geek joy FTW!
The point of our work over the past few articles has been to find cells that are maximally distance, along existing paths, from a given cell. The reason for passing a function into the generator was to allow such things to be done as part of the generation action, so that instead of having to process neighbors as a user of the generate, we can pass the action to be taken into the generator and have it done along the way.
Whether this will come in handy more than once, I do not know. Once, I’m sure of. Yesterday, while you were doing whatever you do during my afternoons, I created a new test, based on an old path map test, to find the furthest cells from a central cell in a small dungeon.
def test_max_distance_with_flood(self):
layout = DungeonLayout()
Cell.create_space(5, 5)
map = '''
..1..
..1..
11111
..1..
..1..
'''
layout.add_rooms_from_map(map)
given = Cell.at(2,2)
max_cells = []
max = -1
for cell, distance in given.flood(
select=lambda c: c.is_in_a_room,
function=lambda c, d: d + 1,
initial_value=0
):
if distance > max:
max_cells= [cell]
max = distance
elif distance == max:
max_cells.append(cell)
max_xy = [c.xy for c in max_cells]
assert (2,0) in max_xy
assert (2,4) in max_xy
assert (0,2) in max_xy
assert (4,2) in max_xy
That’s working. I don’t love it, because over on Mastodon a couple of days back, I posted a nicer way of doing this. I can’t quite replicate it here without more trouble than I’m willing to go to (yet) but we can get closer:
def test_max_distance_with_flood(self):
layout = DungeonLayout()
Cell.create_space(5, 5)
map = '''
..1..
..1..
11111
..1..
..1..
'''
layout.add_rooms_from_map(map)
given = Cell.at(2,2)
max_cells = [(given, 0)]
for cell, distance in given.flood(
select=lambda c: c.is_in_a_room,
function=lambda c, d: d + 1,
initial_value=0
):
current_max = max_cells[-1][1]
if distance > current_max:
max_cells= [(cell, distance)]
elif distance == current_max:
max_cells.append((cell, distance))
max_xy = [c[0].xy for c in max_cells]
assert (2,0) in max_xy
assert (2,4) in max_xy
assert (0,2) in max_xy
assert (4,2) in max_xy
That’s a bit more nasty than I had thought it would be, which was already going to be too nasty, but it shows the idea, which is to keep the cell and distance in the max_cells list, so that we don’t have to remember where to reassign the max value, which I did wrong yesterday, at least once.
OK in for a penny, we’ll make a tiny object.
def test_max_distance_with_flood(self):
@dataclass(slots=True)
class CD:
cell: Cell
distance: int
layout = DungeonLayout()
...
given = Cell.at(2,2)
max_cells = [CD(given, 0)]
for cell, distance in given.flood(
select=lambda c: c.is_in_a_room,
function=lambda c, d: d + 1,
initial_value=0
):
current_max = max_cells[-1].distance
if distance > current_max:
max_cells= [CD(cell, distance)]
elif distance == current_max:
max_cells.append(CD(cell, distance))
max_xy = [c.cell.xy for c in max_cells]
assert (2,0) in max_xy
assert (2,4) in max_xy
assert (0,2) in max_xy
assert (4,2) in max_xy
The cryptic slots=True causes Python to make the object without all the usual rigmarole of a dictionary for the data, resulting in a smaller object. The little object itself lets us refer to cell and distance, which makes the code a bit nicer.
A bit. Let me explain how this works, just to be sure we’re on the same page:
We have a list max_cells, whose invariant property is that it always contains all the CD instances that have been seen so far, that have the maximum value for distance that we have seen so far. Whenever a larger distance comes along, we set the list to just that maximal CD instance, and if any further come along with that same distance, we append them.
My idea, expressed in code on Mastodon, and referred to in these articles a few times, was for a Maximizing Machine that looks at all the cells and distances and accumulates the maximal ones,
A Plan Emerges
OK, I think I see what we’d like to do now. (About time, but how do we know what we want until we try to get it? (And, often, until after we get the thing we thought we wanted!))
We’ll write a new test that posits the existence of a Maximizing Machine, and uses it to get the cells we want.
Like this:
def test_maximizing_machine(self):
layout = DungeonLayout()
Cell.create_space(5, 5)
map = '''
..1..
..1..
11111
..1..
..1..
'''
layout.add_rooms_from_map(map)
given = Cell.at(2,2)
maxer = MaximizingMachine()
for cell, distance in given.flood(
select=lambda c: c.is_in_a_room,
function=lambda c, d: d + 1,
initial_value=0
):
maxer.process(cell, distance)
max_xy = [c.cell.xy for c in maxer.items]
assert (2,0) in max_xy
assert (2,4) in max_xy
assert (0,2) in max_xy
assert (4,2) in max_xy
And the test is satisfied by these two classes:
@dataclass(slots=True)
class CD:
cell: Cell|None
value: int|float
class MaximizingMachine:
def __init__(self):
self.items = [CD(None, -math.inf)]
def process(self, cell, value):
current_max = self.items[-1].value
if value > current_max:
self.items = [CD(cell, value)]
elif value == current_max:
self.items.append(CD(cell, value))
Note that we’re just returning a collection of CD instances, which contain cell and value. We should probably be checking value in our test, since it’s part of how the MM works.
max_values = set(c.value for c in maxer.items)
assert max_values == {2}
I think this test allows us to remove the less attractive one above, test_max_distance_with_flood.
Settle Down There, Ron
This is a good time to commit, then settle down and reflect. Commit: MaximizingMachine can find furthest cells.
Messy Tests
The first thing in my mind is that I really need better testing habits, because that setup with the cross-shaped room appears in at least two tests, formerly three, and the other test setups are similarly weird. However, in my defense, once I write a test and make it work, I rarely ever need to refer to it again, so leaving it the way it was built seems mostly OK. If I, or anyone, were going to read them, then I, or anyone, would probably wish that I, or anyone, had improved their readability.
Quite possibly the FGNO team would mention this if we ever look at my tests. For now, they serve well enough as they stand. In a team situation, probably not, and the team would be right to ask me to do better, and I’d deserve it.
Test Removal
As soon as we decide that the MM and the flood generator are well enough tested, a lot of existing tests should either be rewired as tests of the new scheme, or removed as redundant. It does not escape me that I could use this fact as an excuse for the messy tests, but that’s similar to arguing that I didn’t need to pick up my banana peel because no one slipped on it anyway.
Be that as it may, we do need to look at the tests and see which ones can be repurposed or removed.
furthest_cells
We have a method of that name, which looks like this:
class Cell:
def furthest_cells(self):
max_distance = self._compute_path_distances()
return [cell
for cell in self.space.cells
if cell.is_in_a_room and cell.path_distance == max_distance]
There is a test for that method. Presumably we intend it to be the Cell interface for all this neat stuff we’ve been doing. So we should rewrite furthest_cells as part of finishing up what we’re doing.
That’s about all I see. Let’s begin with furthest_cells:
class Cell:
def furthest_cells(self):
maximizer = MaximizingMachine()
for cell, distance in self.flood(
select=lambda c: c.is_in_a_room,
function=lambda c, d: d + 1,
initial_value=0
):
maximizer.process(cell, distance)
return [cd.cell for cd in maximizer.items]
That’s certainly more complicated in appearance, but all the horror in the first version is inside compute_path_distances():
def _compute_path_distances(self) -> int:
self.path_distance = 0
max_distance = 0
for cell, _ in self.flood_in_rooms():
for neighbor in cell.neighbors_in_rooms():
if neighbor.path_distance is None:
one_further = cell.path_distance + 1
neighbor.path_distance = one_further
if one_further > max_distance:
max_distance = one_further
return max_distance
We have no more use for that method. Let’s remove it and the single test that uses it. Done, green, commit: removing pathmap and tests
We can remove the path_distance horror from Cell now. Done, commit: remove path_distance member (yay!) Bill will be happy, and so am I.
Feature Done?
If I were a developer building the furthest cell notion for the team, I’d want to sit now with the developer who wanted the feature and work with them to use it. I think we’d do something in a visible dungeon. We’d perhaps want to change Dungeon populate:
class Dungeon:
def populate(self):
dot_room = random.choice(self.rooms)
dot_cell = random.choice(dot_room.cells)
self.place_player_at(dot_cell)
Or we might just place the player ourselves.
Let’s do that, for now. Our current dungeon creates that diamond in round room centered at (32, 28) so let’s set Dot as far away from that as we can.
main.py
...
dungeon = Dungeon(layout)
dungeon.populate()
target = Cell.at(32, 28)
options = target.furthest_cells()
chosen_cell = random.choice(options)
dungeon.place_player_at(chosen_cell)
view = DungeonView(dungeon)
view.main_loop()
We get this pretty picture:
A couple of runs later, we get this truly vicious one:
I call that satisfactory. We can place Dot as far as possible for a given cell, which was what we set out to do. We can imagine a similar feature that allows us to set a given distance rather than the max, and maybe we’ll work on that sometime. For now, it’s time to sum up.
Summary
We had what might have been an adequate scheme for getting our furthest cells, but it had the nasty property of setting a value into every cell in the space, and there’s no sensible reason to have the cells suddenly get slammed with a random value. Triggered by Bill’s gentle remark, we sought a better answer and flooding values into a MaximizingMachine came to mind. We then built a flooding scheme that let us pass in a function to be applied to each cell, and with just a bit more effort, folded that capability into our existing generate method.
We pay a small cost for that at present, which is that everyone using flood has to expect to get a cell and a value back, even if they haven’t asked for a value. They can just ignore it with _, and many do.
The tiny CD object, which I’ll rename to CellValue right now, might make sense as a standard return from our flood, and if I can figure out how to make it unwind automatically into a pair of return parameters, we might just do that. We might even do it anyway: we’ll see.
Now, my own assessment of the past few days is that we have done good work, taking a rough idea and a mediocre implementation to a much more clear set of ideas and an implementation that blends with and uses existing approaches instead of duplicating code in a copy-pasta kind of style. We could have “finished” sooner, shortly after getting the distance value jammed into all the Cell instances, but by my lights, that implementation was messy and weird and very likely to lead to even more messiness and more weirdness. Cruft creates more cruft, inevitably.
But I care about the craft. I care about the quality of the work that leaves my hands. I care about doing it better next time than the previous time. I hope that you care about this craft, or some other craft, and that you find the joy of doing something better, somewhere, somehow.
This is my way, and I enjoy it. I wish you similar joy in this sometimes dark-seeming world.
See you next time!