Better Floods
Hello, loves!
We need to improve Flooder, to allow constraining it to follow legitimate pathways. I am expecting it to be straightforward.
Let’s review, for my benefit, how Flooder works. Flooder is an object that generates a sequence of cells and values, with the cells starting at a provided origin cell and expanding outward, producing candidate cells, each a single steps in the north, south, east, or west direction from a parent cell. Each such candidate may or may not be selected as part of the “frontier”, the set os cells that have bee produced and thus can act as sources for the next generation.
Flooder acts as a generator and is intended for use in a for statement, such as we had this morning. We’ll look at that in just a moment.
As production proceeds, a value function is called, provided the cell that is about to be produced, and the prior value, and it can return a new value. So far the only use we’ve had for the value has been to calculate a cumulative distance, such as we did this morning, but it could be used, for example, to count how many cookies are saved in the given cell, so that one could find the cell with the most cookies. Not a very strong example, I know: like I said, so far it has only had one use.
Let’s look at the code.
class Flooder:
def __init__(self, *, layout, origin):
self._layout = layout
self._delivered = None
self._to_be_delivered = None
self._origin = origin
self._select = lambda cell: True
self._next_value = lambda cell, value: value + 1
self._initial_value = 0
self._randomness = 0.0
If I am not mistaken:
- delivered = a cumulative list of all the cells delivered
- to be delivered = a temporary list of the “frontier”, cells which have not yet been delivered or expanded
- origin = the cell from which to start flooding expansion
- select = a function returning True if a given cell is to be accepted and expanded
- next value = a function returning the next value to be delivered, given the cell to be delivered and the previous value
- initial value = the value to be associated with the origin cell
- randomness = the probability that the order of cells to be generated in the next expansion will be randomized.
As we saw this morning, Flooder has a “fluent interface”, allowing a cascade of options all in one go:
class Dungeon:
def maker_flood(self):
def further(c, n):
return n + 1
if len(self.flood_dictionary) > 0:
self.flood_dictionary = dict()
return
for cell, distance in (Flooder(layout=self.layout, origin=self.player_cell)
.in_any_room()
.initial_value(0)
.next_value(further)
.flood()):
self.flood_dictionary[cell] = str(distance)
The works is in the for loop, where, at the bottom, we make a dictionary entry for very generated cell, with the cell pointing to the distance value. Let’s see how we got there.
Flooder needs a layout and an origin, which in our example here is Dot’s location. The selection criterion is in_any_room, which means what it says. available cells will not be returned only, the ones in rooms. Dot’s location gets the initial value of zero.
The next_value function is further, which, given a distance n, returns n + 1. Probably I’d do well to name those parameters better, but I was on a roll.
The “fluent interface” just means that each of those specifier functions returns the original object, so they can be appended one after another until we’ve specified the kind of flood we want. Let’s look at some details.
def in_any_room(self):
self.select(lambda cell: self._layout.is_in_a_room(cell))
return self
def select(self, function):
self._select = function
return self
def next_value(self, function):
self._next_value = function
return self
def initial_value(self, result):
self._initial_value = result
return self
the last three of these are the base methods for specifying behavior, while in_any_room calls select with a function that, given a cell, returns True if the cell is in a room. I think we could simplify that code now, because cells can answer that question themselves.
We see that the other three just store whatever function they are given into the associated instance variable. Let’s see how flood() uses those:
def flood(self):
self._to_be_delivered = {self._origin: self._initial_value}
self._delivered = set()
while self._to_be_delivered:
current_cell, current_value = self.next_to_deliver()
yield current_cell, current_value
self.enqueue_relevant_neighbors(current_cell, current_value)
We maintain _to_be_delivered as a dictionary from cell to value, starting with the origin cell and its initial value. We keep a set consisting of all the cells that have already been delivered. Since the expanding edge of generation can reach the same cell more than once (northwest can be reached by going north then west, or west then north), we use _delivered to ensure we only deliver a cell once, the first time it is encountered.
So while there are still cells to be delivered, we get the current cell and value (which I suppose we could call next_cell and next_value) and yield them. Having done that, we generate all the relevant neighbors, putting them into _to_be_delivered.
Let’s see the details:
def next_to_deliver(self):
current_cell = next(iter(self._to_be_delivered))
current_value = self._to_be_delivered.pop(current_cell)
self._delivered.add(current_cell)
return current_cell, current_value
I’m not sure if we could just pop the dictionary in one go here. Might be worth looking. Anyway we grab the next cell from _to_be_delievered, look up its corresponding value, add the cell to _delivered and return them. Then we enqueue the relevant neighbors:
def enqueue_relevant_neighbors(self, current_cell, current_value):
for neighbor in self._relevant_neighbors(current_cell):
self._to_be_delivered[neighbor] = self._next_value(current_cell, current_value)
For each “relevant” neighbor, we add it and the corresponding _next_value to _to_be_delivered. What are _relevant_neighbors?
def _relevant_neighbors(self, cell):
return (neighbor
for neighbor in self._get_neighbors(cell)
if self.is_relevant(neighbor))
Of course they are just the neighbors such that each is_relevant (and why is that method not private?). What _is_relevant?
def is_relevant(self, neighbor):
return (neighbor not in self._delivered and
neighbor not in self._to_be_delivered and
self._select(neighbor) )
We don’t deliver anything that has already been delivered, nor anything that is already set up to be delivered, but that does return True from _select.
So, I hope that’s clear enough.
Our issue is that we would like to return cells such that Dot could traverse them. We already know the expression for that, because when she tries to move we check this:
class Cell:
def _get_connection(self, cell):
if not cell:
return NoConnection(self, cell)
elif self.room == cell.room:
return OpenConnection(self, cell)
elif self.has_passage(cell):
return OpenConnection(self, cell)
else:
return NoConnection(self, cell)
We want a selection criterion considering the new cell that we might generate, and the parent cell from which we are generating it. We can write the selection function: but it won’t work yet. Let’s write it in the F command:
def maker_flood(self):
def can_traverse(new_cell, parent):
if new_cell.room == parent.room:
return True
if new_cell.has_passage(parent):
return True
return False
def further(c, n):
return n + 1
if len(self.flood_dictionary) > 0:
self.flood_dictionary = dict()
return
for cell, distance in (Flooder(layout=self.layout, origin=self.player_cell)
.in_any_room()
.select(can_traverse)
.next_value(further)
.flood()):
self.flood_dictionary[cell] = str(distance)
This will not work because currently the select function requires only one parameter, not two.
This next move will break things.
def _relevant_neighbors(self, cell):
return (neighbor
for neighbor in self._get_neighbors(cell)
if self._is_relevant(neighbor, cell))
def _is_relevant(self, neighbor, parent):
return (neighbor not in self._delivered and
neighbor not in self._to_be_delivered and
self._select(neighbor, parent) )
PyCharm knows we can’t pass two arguments:
class Flooder:
def __init__(self, *, layout, origin):
self._layout = layout
self._delivered = None
self._to_be_delivered = None
self._origin = origin
self._select = lambda cell: True
self._next_value = lambda cell, value: value + 1
self._initial_value = 0
self._randomness = 0.0
Change that lambda and our local definitions:
class Flooder:
def __init__(self, *, layout, origin):
self._layout = layout
self._delivered = None
self._to_be_delivered = None
self._origin = origin
self._select = lambda cell, parent: True
self._next_value = lambda cell, value: value + 1
self._initial_value = 0
self._randomness = 0.0
# fluent interface
def available(self):
self.select(lambda cell, parent: self._layout.is_available(cell))
return self
def in_any_room(self):
self.select(lambda cell, parent: self._layout.is_in_a_room(cell))
return self
Tests break. Fix required in just two places, passing two parameters to can_use:
def find_path(self, source, target, room_list):
def can_use(cell, _parent):
return self.is_available(cell) or self.get_room(cell) in room_list
reached = self.path_map(source, can_use, 1.0)
path = []
start = target
while start is not None:
path.append(start)
start = reached.get(start)
return path
def path_map(self, source, can_use, randomness=0.0):
reached: dict[Cell, Cell|None] = {source: None}
for c, _ in (Flooder(layout=self, origin=source)
.select(can_use)
.randomness(randomness)
.flood()):
for neighbor in self.neighbors(c):
if neighbor not in reached and can_use(neighbor, c):
reached[neighbor] = c
return reached
We are green. I think we can try the new flood.
That is exactly what we’d expect. Follow the path from Dot up and around the inner diamond, and back down to right above Dot. It shows eleven steps, not just one as it would be if we could pass through walls.
I hadn’t noticed this before but PyCharm and arcade gave me this warning:
PerformanceWarning: draw_text is an extremely slow function for displaying text. Consider using Text objects instead. warnings.warn(message, warning_type)
We already knew that, of course. But the solution sounds useful. Let’s commit what we have: Flooder now honors walls, with suitable select setting.
If the F command maker_flood were to create Text objects into the dictionary, then we could just draw them rather than re-render them every time around. That might speed things up.
Let’s try.
class Dungeon:
for cell, distance in (Flooder(layout=self.layout, origin=self.player_cell)
.in_any_room()
.select(can_traverse)
.next_value(further)
.flood()):
cx, cy = cell.center_position(cell_size)
text = arcade.Text(text=str(distance),
x=cx,y=cy,
anchor_x="center",anchor_y="center",
font_size=8)
self.flood_dictionary[cell] = text
class DungeonView:
def draw_flood(self):
for cell, text in self.dungeon.flood_dictionary.items():
text.draw()
Well, that works, and it might be a bit faster but it’s not flying. The scroller is still running at about 1/3 speed. I think we should make a sprite list here. We’ll save that for next time or maybe offline. It won’t be terribly interesting, if anything here is in fact interesting.
Summary
So. That was as easy as I expected. Were it not for the explication, there wouldn’t be much to say. However, what we have here is a more powerful version of Flooder, which we can use to find paths in the dungeon, and which, if my plans work out, we’ll also use to ensure that Dot can access the necessary tools to make her way around. I’m not sure how far we’ll push that notion. You can imagine needing the green key to open the green door and the red key to open the red door and the gold key to open the chest, so that, in principle, we could hide the gold key beyond the red door, the red key beyond the green door, and if the green key is before the green door, given where Dot it, it’s all good.
Saying that gives me an idea … imagine a structure consisting of all the cells that Dot can access without any keys. We presumably know that the green door, requires the green key. So we can see if the green key is in any of those cells. Then wee can expand the set of cells Dot can access by all the cells beyond the green door. We see the red door as the cork in the vessel of progress and check whether the red key is now in Dot’s purview.
Hm. We might actually be able to do something rather fancy. Turning that idea inside out, we place the obstacles wherever, then find all the cells Dot can access pick one far from Dot to hide the green key, etc.
Now it seems quite doable. Two days ago I had no idea but felt that a suitable flood capability played into it. Having that flood and seeing it on the screen has triggered some useful ideas.
Does that justify my speculative implementation of a better select? I don’t know, but I’m certainly not sorry that I did it.
See you next time!
P.S.
Converting to SpriteList was trivial. Creating the list takes maybe half a second, but once it is drawing everything runs at full speed. Not necessary but still desirable.
class Dungeon:
def maker_flood(self):
def can_traverse(new_cell, parent):
if new_cell.room == parent.room:
return True
if new_cell.has_passage(parent):
return True
return False
def further(c, n):
return n + 1
if len(self.flood_list) > 0:
self.flood_list = SpriteList()
return
for cell, distance in (Flooder(layout=self.layout, origin=self.player_cell)
.in_any_room()
.select(can_traverse)
.next_value(further)
.flood()):
cx, cy = cell.center_position(cell_size)
text = arcade.create_text_sprite(text=str(distance),font_size=8)
text.center_x = cx
text.center_y = cy
self.flood_list.append(text)
class DungeonView:
def draw_flood(self):
self.dungeon.flood_list.draw()