Hello, loves!

How can we ensure that a problem that unlocks part of the dungeon can be solved in the section Dot’s in? I don’t know—yet.

We can think of the problem in simple terms:

Suppose there is a set of one or more connected rooms within which Dot can move freely. Suppose that there is a passage from those rooms to another set of connected rooms, and that that passage requires a key. We need to ensure that the key is able to be found in the first set of rooms. The game would be no fun at all if the key were outside those rooms.

Our mission is to find a way to ensure that all the components of a problem that unlocks part of the dungeon can be found in the part of the dungeon that contains Dot.

Sounds easy enough, but as things stand, it is not:

Presently, we build the dungeon by randomly creating all the rooms and then connecting them. We connect them by finding “suites” of rooms that are already connected by accident, building walls between those rooms, and then adding additional passageway-like rooms between them. In each border between two rooms, we select one pair of cells to be the passage between those two rooms.

:There is no overall design or plan, just random rooms, with a scheme that ensures they are all connected. There is no guarantee that they aren’t already connected into one Suite right at the beginning. And, presently, the game doesn’t keep track of much in the way of structural information: it works at the cell level, moving from one cell to another, with little regard to what room Dot is in. and no memory of the Suites at all, which are just a temporary structure used during the connection process.

Constraints

I am assuming that we’d like to retain the essentially random character of the layout, but that we are prepared to make changes to the specifics of how that randomness is attained. I am assuming that we’ll need to retain some additional kinds of information about the dungeon.

Clearly, we’d like to find a solution that is close to what we have now, so that we don’t have to change a lot of code or write a lot of new code.

And there’s one more constraint, speed. It already takes too long to create a new dungeon. I suspect that the time is being taken up in determining the suites, because we use a flood fill to determine which rooms are already in contact. (And, offhand, I don’t know another way to determine that after the rooms are laid out. It might be possible to notice the condition as we create rooms, if that would be helpful.) But one way or another, we’d like to come out of this problem with the system at least as fast as it is now, preferable faster.

Possibilities

Let’s talk about possibilities. I have one possible scheme in mind, and would like to have at least two, so as to pick the one that seems better. Gives one a feeling of freedom rather than looming inevitability.

Possibility 1

The one I’ve thought of, and actually tried at some point in the past is basically this: For each problem you want to offer, there’ll be some objects that need to be accessible, in some number of accessible rooms. So layout the dungeon by creating that number of rooms (a Suite), then connect them if necessary, using the existing connection code. Then place the solution objects and Dot in that Suite. If there’s another problem, create another Suite. Allocate solution components for the second problem into the second Suite (and the first, if you care to). Repeat.

So in this scheme, one would grow the dungeon Suite by Suite, and all the necessary components would be guaranteed to be accessible.

Issues with this idea include: Suites are currently ephemeral. Presumably that could be handled by adding them to the Layout. In addition, the current connection logic allocates passages every time through, so that whatever locks a passageway would need to be moved. Presumably, we’d change that, so that the Dungeon is intentionally built up incrementally and decisions once made stay made.

My overall concern with this idea is that it seems like a fairly substantial set of changes to the system. Aside from that, this scheme seems appealing to me.

Possibility 2

Let’s see. If we do not solve the problem incrementally, then maybe we solve it after the layout is complete. Maybe something like this: lay out the dungeon entirely. Assume we have in mind a final “boss” room for the level. Assume a lot of hand-waving.

Place Dot as far from the boss room as possible (probably requires a flood fill). Decide how many rooms you want the first problem to consume. Do a flood fill to find all the cells around Dot until we have touched that many rooms. Place the objects needed for problem 1 in those rooms. Lock the door (doors?) with that problem’s solution. Repeat.

I have serious concerns about this idea. First, it is flood-fill intensive, and those are slow, and we’re already taking too much time to connect things. Second, if we use this scheme, it is entirely possible that the few rooms we find connect more than once to the rest of the dungeon, or to other areas. If the selected rooms connect more than once to the rest of the dungeon, don’t we have to lock all the exits, not just one? But some problems might consume the locking resource. For example, we can placate the Bear with the honeycomb … but if there were two or three Bears … we only have one honeycomb. This could be bad.

So far I prefer #1. What else might be possible?

Possibility 3

I just thought of this one. We could partition the cell space. Break it up into a few separate areas, and allocate rooms into those areas. Allocate exit solution components into each area. Connect the areas with simple paths and doors, fitting each door to match the solution for that partition.

If there were an order to the partitions, we could put problem 1 components into partition 1, problem 2 components into 1 and 2, and so on.

I am reminded now of this interesting article: The Twenty-One Forms Of The Five Room Dungeon

That article, and the original The Nine Forms Of The Five Room Dungeon offer an interesting abstraction that could be useful to us. We might focus on five rooms, or five suites of rooms, and perhaps even specify which Form we wanted, perhaps not all nine or twenty-one but some useful subset. Or, why not all of them, in for a penny sort of thing.

Given the Form, the flow from suite to suite is defined and the solution components could be placed with that flow in mind.

I like this possibility. It would provide for more meaningful layouts, still with the randomness we like, but since we can already draw round rooms and diamond-shaped ones and nothing stands in the way of rectangular ones, we could embed a bit more of a plan, a sense of progress, a bit more character into the game.

We’re gonna try #3.

Planning

I’m not ready to jump into code and tests for this idea, or for any of them. If we were going with #1, I’d suggest reviewing the existing code, since it would probably want something much like the existing Suite and connection logic. In the case of #3, I want to draw some pictures, get a sense of how we might allocate separate areas for the rooms and then connect them.

And I’ll just mull the idea around a bit, see what comes to mind. Might come back this afternoon, might come back tomorrow.

See you then!