Filtering?

Hello, loves!

We’re looking at building the dungeon in sections. To do that, I think we need filtering. How might we do that?

The base issue that we’re dealing with is how to be sure that the solution to a dungeon problem is possible within the presently-accessible part of the dungeon. Oversimplified: how to ensure that the key Dot needs is on the right side of the door that it unlocks. The scheme we’re trying will allow the dungeon creation code to define a sub-region of the whole cell space, and build one or more rooms in that sub-region, and then connect them. Then we’ll place all the necessary components of the puzzle that lets us exit the sub-region. Probably we’ll identify where to put the exit at this point: I’m not sure. Then we define another sub-region and create more rooms. Solution components to that region’s exit can be placed anywhere in the existing sub-regions. Rinse, repeat.

There is a lot of hand-waving there, and some aspects are almost certain to break parts of the existing design, which is just great, because we’re here to show that when our design cannot support some new need, we can support the need and get the design back into proper shape without massive rewriting. There may be a lot of refactoring to do, but it will be able to be done in small steps.

Of course, this could be the case that breaks the streak, but I have come to believe that a decent design for the features up until now can be modified smoothly to support upcoming features [almost?] invariably.

We’ll find out, won’t we, assuming that I last that long.

Filtering? Why?

Oh, right, filtering. We need to be able to define a sub-region of the dungeon layout, and confine building to that sub-region. There are a few ways we might do that. I’ve thought of two, let’s see if I can come up with a third here.

1. Create a separate layout for each sub-region and merge them to create larger ones.
2. Set up a “filter” on Cell access that makes all cells outside the current sub-region seem not to exist.
3. Hmm. Maybe we could just create a few rooms, connect them, treat them as a sub-region, lock them somehow, then repeat.

Of these, the plan at this moment is to experiment with #2, because it offers a side benefit, which is that we might be able to give the dungeon an interesting macro play, as suggested by the 9¹and 21² forms of the five-room dungeon articles we linked yesterday.

Idea #1 above does not appeal to me because merging layouts seems more complex than making some cells seem to be unavailable, and in order to get the 9/21 layout notion we’d have to solve most of the filtering issue anyway.

Idea #3 is actually something that I tried in an earlier experiment with dungeon building in steps. The Stepper object is used to build a dungeon bit by bit, displaying at we go, used in debugging. My experience with that was mostly positive but the way things work at present, whenever we go to connect rooms together, all the existing passages get redefined, which seems right out for what we’re doing now. Suffice to say that my experience toying with that one makes it feel undesirable.

So let’s see what “filtering” might be.

Filtering? What Is It?

Our overall dungeon shape is a square. It need not be that and could be any contiguous collection of Cells, but square is a nice base for our window. From the viewpoint of the Dungeon and its Views, the dungeon is a collection of Cell instances, with the ability to produce the neighbors of any given Cell. It is convenient to ensure that all references to Cell(x,y) are identical for given x and y. The alternative seemed to be to create and destroy Cell(x.y) instances very frequently, and that seemed wasteful.

So there is a two-phase process for creating the Layout. First, Layout and Cell collaborate to produce a new Cell instance for every x-y pair in the Layout. Then, Cell enters a state where when you ask for Cell(x,y), Cell class asks the current Layout to fetch that cell. Here’s the relevant code:

class DungeonLayout:
    def _create_cells(self, max_x, max_y):
        with Cell.creating(self):
            Cell.layout = None
            for x in range(max_x):
                for y in range(max_y):
                    self.cells[(x, y)] = Cell(x, y)

class Cell:
    layout = None

    @classmethod
    @contextmanager
    def creating(cls, layout):
        Cell.layout = None
        try:
            yield
        finally:
            Cell.layout = layout

    def __new__(cls, x, y):
        if cls.layout:
            # noinspection PyProtectedMember
            return cls.layout._at_xy((x,y))
        else:
            return super().__new__(cls)

    def __init__(self, x, y):
        self._xy = (x,y)

So when creating, there is no layout class variable in Cell, so the __new__ method creates a new Cell. But after creating, there is a layout class variable, and __new__ switches to fetching the already existing cell from the layout. A bit arcane, arguably too clever, but it was the best idea I had and it works marvelously. Here’s what happens in DungeonLayout in _at_xy:

class DungeonLayout:
    def _at_xy(self, xy):
        return self.cells.get(xy, None)

We return the cell if we have one, otherwise None. Everyone who fetches a cell is either sure that they’ll get one (and tested to be correct, generally speaking) or is prepared to receive a None.

So the filtering idea is this: change things so that when anyone tries to fetch a cell, if a sub-region is in effect, only cells in the sub-region will be returned, otherwise None.

Spike: Experiment

Let’s do a quick experiment with this idea to see if it works. Let’s try to do it with tests, tempted though I am to just put it in and look at the result. I think what we’ll do is provide an optional rectangle as the sub-region, for our experiment.

class TestSubRegion:
    def test_low_region(self):
        assert False

Fails. Perfect. Now let’s try something. How about this:

class TestSubRegion:
    def test_low_region(self):
        layout = DungeonLayout(10, 10)
        layout.subregion_LRBT(0, 5, 0, 5)
        for _ in range(100):
            cell = layout.unused_cell_or_none()
            assert 0 <= cell.x <= 5
            assert 0 <= cell.y <= 5

We need that method:

class DungeonLayout:
    def subregion_LRBT(self, l, r, b, t):
        pass

Test fails, finding a number outside the range. No surprise.

Thinking

I’m trying to decide whether to include the end point or not. I think not. Change the test to < 5.

Ah. This wasn’t as easy as I had thought it’d be because, for example:

class DungeonLayout:
    def unused_cell_or_none(self):
        available = [cell for cell in self.cells.values() if cell.is_available]
        if available:
            return random.choice(available)
        else:
            return None

class Cell:
    @property
    def is_available(self):
        return self.room is None

I wonder what other methods may be side-stepping the _at_xy. Here’s what I have installed so far:

class DungeonLayout:
    def __init__(self, max_x=10, max_y=10):
        self.max_x = max_x
        self.max_y = max_y
        self.lr = range(max_x)
        self.bt = range(max_y)
        ...

    def subregion_LRBT(self, l, r, b, t):
        self.lr = range(l, r)
        self.bt = range(b, t)

    def _at_xy(self, xy):
        x, y = xy
        if not x in self.lr:
            return None
        if not y in self.bt:
            return None
        return self.cells.get(xy, None)

Let’s extract a method from the _at_xy to use elsewhere. Had to do this by hand like some kind of barbarian:

    def subregion_LRBT(self, l, r, b, t):
        self.lr = range(l, r)
        self.bt = range(b, t)

    def _no_access(self, x, y):
        return x not in self.lr or y not in self.bt

    def _can_access(self, x, y):
        return not self._no_access(x, y)

    def _at_xy(self, xy):
        if self._no_access(*xy):
            return None
        return self.cells.get(xy, None)

    def unused_cell_or_none(self):
        available = [cell
                     for cell in self.cells.values()
                     if self._can_access(*cell.xy) and cell.is_available]
        if available:
            return random.choice(available)
        else:
            return None

I don’t think we want to commit this simple idea, but I do want to try it in main.

main.py

def main():
    layout = DungeonLayout(55, 55)
    dungeon = Dungeon(layout)
    stepper = make_build_table(layout, dungeon)
    screen_multiplier = 16
    screen_width = screen_multiplier*dungeon.max_x
    screen_height = screen_multiplier*dungeon.max_y
    arcade.Window(screen_width + 8*screen_multiplier, screen_height, 'Caveat Emptor')
    make_diamond_in_round_room(layout, dungeon)
    layout.subregion_LRBT(0,27, 0, 27)
    make_a_cave_room(layout, dungeon)
    make_a_round_room(layout, dungeon)
    make_a_diamond_room(layout, dungeon)
    layout.subregion_LRBT(29,55, 29, 55)
    make_a_cave_room(layout, dungeon)
    make_a_round_room(layout, dungeon)
    make_a_diamond_room(layout, dungeon)
    layout.subregion_LRBT(0,55, 0, 55)
    finish(layout, dungeon)
    populate(layout, dungeon)
    add_content(layout, dungeon)
    view = DungeonView(dungeon)
    dungeon.run()
    view.run(stepper)

There’s a lot of hacking in here, but what this should do, if it works, is to put three rooms in the lower left, three in the upper right, and the standard center layout. And guess what:

So that is perzackly what we intended. I did have to bash some things to make that work, since we really need to use the Stepper and I didn’t take the time to implement all the new functions that we’d need. But all the bashing was in main, everything else “just worked”. While playing, I noticed something odd: when Buzz gives Dot the honeycomb, a honeycomb appears off to the lower left, as if it were in a cell, but unless my eyes deceive me, it’s not even aligned with cell boundaries.

I don’t think our current work caused that but it’s interesting and I’ve made a note to look into it.

Summary

Time to pause and sum up. I’ll not commit the code just now, even the test, though I suspect we might keep the subregion_LRBT method as one of a few sub-region methods we might devise. Clearly the final filtering will need to be more than a simple rectangle … or maybe not … depends what we want our layouts to be.

I didn’t try connecting the sub-regions internally, and I think we’ll want to have a new scheme for interconnecting them. Currently we are forcing a loop into the dungeon linking 1 to 2, 2 to 3, n-1 to n, n to 1. We will want better control over the paths between sub-regions. That will need some thought and inventing.

What we have here is a tiny proof of concept, telling us that we can probably restrict room definition and general layout creation to work in a sub-region without invasive changes. So that’s good news about the idea, so far. There are a lot of loose ends to tie up, and I don’t think we’ve even identified all of them.

But … so far so good! See you next time!