next »

[Gimym TILBERT]

A lot of work have been done on permanent lock and key generation, it's fairly easy, for a given level tree be sure that the key is before the subgraph it open. The same rules apply to small keys but is not enough, small key disappear when used and can open any door. Depending on connectivity you can quickly create impossible situations where despite having all keys some door remain inaccessible due to misuse, blocking further progression.

Does anyone tried or solved that problem already?
What are the design rules to observe to create good lock and key with Zelda like small key?

[ThemsAllTook]

Hmm, tricky...you could always brute force it by checking every possible sequence of door opening and making sure all nodes are accessible by the time you run out of keys or doors. If you don't have too many doors, this should be viable. Off the top of my head, I can't think of a cleverer way to do it that's likely to work, but presumably there'd be some better way I haven't thought of. The above only gives you validation, of course; not sure how you'd go about generation, other than maybe generating a random number of keys and doors and then pruning nodes if you find inaccessible ones during validation.

[Sir Wolf]

--for a given level tree be sure that the key is before the subgraph it open. The same rules apply to small keys but is not enough, small key disappear when used and can open any door. Depending on connectivity you can quickly create impossible situations where despite having all keys some door remain inaccessible due to misuse, blocking further progression.

Okay, I'm a little slow, can someone describe a situation where the progression is blocked when using the same approach as for big keys? I'm sure it's possible, I just can't quite figure out how, if for each door you make sure a key is generated before the area behind it.

I'm probably thinking too simple level layouts and not coming up with things like rooms forming a circle where paths behind two doors later merge and lead to the same area, to a small door, which key has been generated to the other path you didn't take, behind locked doors you don't have a key for... I just came up with that while typing, I'm not sure if that's even correct. So, what kind of situations would lead to the player's progress being blocked?

[baconman]

You could always safeguard somewhat by making at least one (extra?) key generate pretty early on in each dungeon, or making them purchasable in shops. The OG game did this, so in spite of Level 9 blatantly not having enough keys to complete it without the Master Key, you could still buy enough keys to win it without acquiring that either. In fact, IIRC it was a REQUIREMENT to buy at least one key (or skip an unnecessary keyhole!) to complete the Second Quest.

Other simple but doable solutions:

- Use A* to track room depth, and use a target depth to place all keys early, and all locks later (like locked doors only appearing in depth 4 or greater, having an equal number of keys appear in depths 4 or less).

- Have every locked room generate a key on one side of the door or the other, and start the player off with one key. This way, even if you use the key, you'll have the ability to earn another presented by doing so.

- You can also have "locked rooms" generate walls that can be bombed through, unless they're key rooms like the equivalent of a Triforce fragment or major item. So this way if you don't have the key to get inside, or you'd rather conserve your keys, you could expend a bomb and work around it.

Matter of fact, last playthrough of TLoZ (see Game Club), I finished Level 1 with an excess of 3 keys, and Level 3 with a whopping FIVE, mostly from utilizing bombable walls. Clearly, you can constrain this in proportion to the level difficulty, or even be crafty and pull a Level 8 "must bomb to proceed" trick.

Where fun factor is concerned, a little imprecision can go a long way.

[C.A. Sinner]

- Use A* to track room depth, and use a target depth to place all keys early, and all locks later (like locked doors only appearing in depth 4 or greater, having an equal number of keys appear in depths 4 or less).

you don't even have to do that. just autoassign depths during level gen and store them in an array. it's always better to write an algorithm that is "aware" of your design intentions.

if your levels use a tree structure, just generate at least 1 key on every locked branch so that spending a key always comes with the possibility to get a new one, though i guess that's not a very "elegant" solution either.

[Gimym TILBERT]

Tree structure is mostly for analysis, it can loop on itself, assuming the graph links are always bidirectional.

http://garethrees.org/2004/12/01/ocarina-of-time/

The main idea come from this analysis

[baconman]

I think the concern is this:

If key A opens branch A, that gets you key B, which opens branch B, that gets you key C, that opens branch C, which then finishes the level, what's to stop players from using key A to go to branch C directly, which not only finishes the level, but in a way that prevents players from accessing branches B and C from that point on.

What I was posting before was a few methods of circumventing that style of level design. Ultimately, older Zelda dungeons only have two kinds of points of interest - the key item of the level (some like Levels 1 & 8 have two of those), and the boss/end. Things like extra bombs, keys, passageways, secret treasure rooms, and the map and compass were usually tucked in one-to-two room tangents; but on the whole, many levels (1/2/3/7 come to mind especially) had a core section that allowed relatively free movement within the rooms which connected it to those. Even Level 9 was less restrictive in it's design, just more mazelike due to abundant use of passageways that fragmented it's layout - once you know what you're doing you can skip half the rooms in it!

But admittedly, if going for a classic Zelda "small key" feel, OoT is not exactly the best source of design inspiration. They're FAR more item-puzzle focused and restrictive, and less exploratory. Plus, using a design tree in general is borderline bleah, because that isn't nonlinear level design, it's just linear level design broken up into multiple chunks that simply aren't end-to-end.

I suppose if you'd rather use the item-puzzle orientation of OoT, you could have "branch C" (the one that connects to the end) generate a key within it, then do an item-litmus-test with the last locked door on the other side. This way if you don't have the item yet (and you require it), you still have a key with which to try the other routes, one that can't be wasted if you can't pass the item-lock room.

[st33d]

I've already solved this myself.

Place a door. Flood fill on either side of the door. Check the colours on either side of the door.

If they are the same - the door does not fragment the level. If they are different colours then you have a lock puzzle.

Now place a key on any tile that is the same floodfill colour as the entrance to the area.

Bam.

Lock and key puzzle.

You can do it with fancy graphs and such, but the method above is probably the simplest. For multiple keys it would take a bit more logic, but the principle is still the same: 1. check for fragmentation 2. place a key on the accessible side of the fragmentation.

[Gimym TILBERT]

Thanks for the reply! It help me looking at it the right way, I have made a bunch of graph, but I'm on my sister phone, can't show anything, still no personal internet.

Steed you are describing item key, I'm talking about generic small key used in a network. I'm not sure linking this article was a good idea since he talk many things, mostly item key, small key are only a small part of it, the part I want to discuss.

However most Zelda level are simply a dag, it has an end and begin somewhere. It also have optional area to open, the main problem therefore is to never block the player for any sequence of keys door opening. One easy solution is to always have a key inside each subgraph, so any use lead to another key. However, unlike permanent items keys, it only work for tree graph, a permanent key could do a search into a network to create a tree, create a door at the root of the subtree, mark all node that branches outside the graph and place a door there too. This last trick would not work for consumable keys as they have only one use.

Generally we have only two significant case to handle, especially in a dag, divergence and convergence. Most people only address the divergent access of area. However if we are in a free network with no end, where the goal is completion (visiting all nodes), how would we generate it?

[DustyDrake]

This might prove to be helpful
http://www.squidi.net/three/entry.php?id=4

[PsySal]

A lot of work have been done on permanent lock and key generation, it's fairly easy, for a given level tree be sure that the key is before the subgraph it open. The same rules apply to small keys but is not enough, small key disappear when used and can open any door. Depending on connectivity you can quickly create impossible situations where despite having all keys some door remain inaccessible due to misuse, blocking further progression.

Does anyone tried or solved that problem already?
What are the design rules to observe to create good lock and key with Zelda like small key?

First reduce the graph into nodes, where each node is a set of rooms not separated by doors. However many doors each node has (i.e., how many edges reference the node) you need to have this many keys available somewhere in that node. So if a section of the map is reachable only through one door, you must have one key somewhere behind that door. If it's reachable by two doors (even if one leads to another area possibly connecting back in a circuit) then it needs two keys. And so on.

Finally, add one key in the start node (assuming the start node has one edge, i.e., a lobby) or if you prefer, just designate a node to be the start node. Recongize that using this algorithm you will always have one key left over, after all doors have been opened.

This will cover it because any time you use a key, no matter what door you entered from, you can for sure replenish it.

EDIT: Wanted to add, although this guarantees you are OK, it seems like it would be possible to do a bit "better" if you could analyze which nodes had to be open in order to reach other nodes. For instance, if node N needed to already be reachable in order for node M to be reachable, then would it be safe to move one or more of M's keys into N?

EDIT (2): For clarity.

[s_l_m]

I've already solved this myself.

Place a door. Flood fill on either side of the door. Check the colours on either side of the door.

If they are the same - the door does not fragment the level. If they are different colours then you have a lock puzzle.

Now place a key on any tile that is the same floodfill colour as the entrance to the area.

Bam.

Lock and key puzzle.

You can do it with fancy graphs and such, but the method above is probably the simplest. For multiple keys it would take a bit more logic, but the principle is still the same: 1. check for fragmentation 2. place a key on the accessible side of the fragmentation.

Thats... really smart actually.
I guess simple solutions really are best

[baconman]

No, I'm pretty sure st33d's solution applies to keys of any type, even interchangable ones like Zelda small keys. There's already a number of options to play with... try them all one at a time and see for yourself what ends up being funnest!

[DustyDrake]

...If you don't want to read my link, it basically sums it up as this:
Start from the end of the dungeon, and work your way back to the start of the dungeon.

but st33d's is smart too...

[st33d]

If I was smart then it wouldn't have taken a month to come up with that method, let alone the amount of bug fixes it required to finally be stable.

The important thing to focus on is fragmentation. When does your graph break into multiple graphs? Does it break into multiple graphs?

That is what keys and locks do. They break the graph apart into multiple graphs.

A good algorithm to learn that will help you walk through your graph is Prim's algorithm.