Welcome, Guest. Please login or register.

Login with username, password and session length

 
Advanced search

1411196 Posts in 69314 Topics- by 58380 Members - Latest Member: feakk

March 18, 2024, 06:00:35 PM

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsDeveloperDesignprocedural small Zelda key placement?
Pages: [1]
Print
Author Topic: procedural small Zelda key placement?  (Read 4490 times)
gimymblert
Level 10
*****


The archivest master, leader of all documents


View Profile
« on: July 07, 2012, 05:08:04 PM »

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?
Logged

ThemsAllTook
Administrator
Level 10
******



View Profile WWW
« Reply #1 on: July 07, 2012, 07:56:54 PM »

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.
Logged

Sir Wolf
Level 0
***


A wolf cub growing up


View Profile
« Reply #2 on: July 08, 2012, 02:03:43 AM »

--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?
Logged

"We don't stop playing because we grow old; we grow old because we stop playing."
-George Bernard Shawn
baconman
Level 10
*****


Design Guru


View Profile WWW
« Reply #3 on: July 08, 2012, 02:34:02 AM »

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.
Logged

s0
o
Level 10
*****


eurovision winner 2014


View Profile
« Reply #4 on: July 08, 2012, 05:33:38 AM »

Quote
- 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.
Logged
gimymblert
Level 10
*****


The archivest master, leader of all documents


View Profile
« Reply #5 on: July 08, 2012, 06:23:38 AM »

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
« Last Edit: July 08, 2012, 06:39:21 AM by Gimmy TILBERT » Logged

baconman
Level 10
*****


Design Guru


View Profile WWW
« Reply #6 on: July 09, 2012, 01:23:44 AM »

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.
Logged

st33d
Guest
« Reply #7 on: July 09, 2012, 03:44:20 AM »

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.
Logged
gimymblert
Level 10
*****


The archivest master, leader of all documents


View Profile
« Reply #8 on: July 09, 2012, 07:44:32 AM »

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?

Logged

DustyDrake
Level 10
*****



View Profile
« Reply #9 on: July 09, 2012, 08:38:37 PM »

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

PsySal
Level 8
***


Yaay!


View Profile WWW
« Reply #10 on: July 09, 2012, 09:01:15 PM »

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.
« Last Edit: July 09, 2012, 09:07:18 PM by PsySal » Logged
s_l_m
Level 8
***


Open to collabs


View Profile
« Reply #11 on: July 09, 2012, 09:33:43 PM »

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
Logged

Think happy thoughts.
baconman
Level 10
*****


Design Guru


View Profile WWW
« Reply #12 on: July 09, 2012, 09:37:16 PM »

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!
Logged

DustyDrake
Level 10
*****



View Profile
« Reply #13 on: July 09, 2012, 11:00:02 PM »

...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...
Logged

st33d
Guest
« Reply #14 on: July 10, 2012, 02:02:51 AM »

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.
Logged
ஒழுக்கின்மை (Paul Eres)
Level 10
*****


Also known as रिंकू.


View Profile WWW
« Reply #15 on: July 10, 2012, 07:04:49 AM »

st33d's solution doesn't account for this: what if two doors to the same area exist, both blocking off the same new area? then there would be a superfluous number of keys to get into that area. but otherwise it sounds good, it'd be fun to play a game that used that

anyway i myself don't really like single key single door level layouts. i prefer when there are many different "types" of doors and keys (not necessarily color-coded like in doom, but just in the sense that there are different obstacles that require different usable items to get past). so i think levels composed mainly of keys and doors would probably get a bit old if there were not alternative ways to access new areas besides collecting keys

for instance, think of zelda3: it had holes that drop you to the floor below, keys and doors yes, but also "shutter" doors that open when you kill all the enemies in a room, and "master key" doors that you need a specific big key for, and walls that you could bomb, as well as other things specific to each dungeon (vines to cut, puzzles to push blocks and reveal stairways, all kinds of stuff). just keys and doors isn't enough, this algorithm should be able to support multiple ways to access new areas
Logged

st33d
Guest
« Reply #16 on: July 10, 2012, 07:40:34 AM »

My method was only for single doors.

For multiple you'd still be checking what the flood fill reached and how many colours you were left with (how many fragments the level is in).

I think that if you came up with a reasonably strong algorithm for generating your puzzles, then you can sprinkle in sequence breakers like bombs and such and not worry too much about an abundance of keys (just don't spawn them later on).

(Just realised I've got bombs in my game and I could be using them to destroy gates.)
Logged
gimymblert
Level 10
*****


The archivest master, leader of all documents


View Profile
« Reply #17 on: July 10, 2012, 10:25:22 AM »

@paul eres
By key I mean any gating mechanics, be it challenge or trigger or actual key. In the end what you say made a lot of sense, you may think about this as an algorithm for controlling progression by automatic placement of gating gameplay. key is just the abstract term for it. Instead of an algorithm you can also see it as a set of design requirements for navigation to actually works or to manipulate level design knowingly of pitfall or possibility.

Reading all answer, more notably psysal's one, helpt me to put this into a gameplay perspective. Why do we need key? Basically to control or promote navigation. Ideally I seek rules that always allow all door to be reach using all keys.

However, looking back from gameplay, keys are first a gating mechanism. I have mention 2 major cases: divergeance (choice) or convergence (chokepoint). Let's look at a generic case: a main room with many sub rooms.

I thought there was a third case of keys, star in mario 64, but it's really just clever way to hide progression and abstract it from the physical layout. Relation between space and progression is one of the biggest design tool to help giving illusion of freedom and control to players.

Permanent key promote divergeance when many keys are in the main room. But choosing the key is basically the room, thanks to one to one relationship. Special case is when another key is inside a sub room, which impose a sequence, of course there might be more than one key in a subroom such allow flexibility of navigation control. That's basically the trigger system in Zelda (that can be seen as instant permanent keys). By itself one permanent key promote gating and sequence. Only when multiple keys are available at the same time that it promote choice. Convergence is handle simply by using a door that need many keys.

Consumables keys (small key) promote divergeance through multiple doors as one key open any door, choice are only given by how many accessible door there is at anytime. If there is doors in a subroom we just opened the number of choice increase. Unlike the former type of keys it give more flexibility to players and encourage exploration, but the designer still have lot of control by using the depth of access. Small key are basically a navigation resource, money, stat point to distribute... However those observation mostly work for tree, I'm still unsure about convergence effect (backtracking a parallel path or multiple keys doors) in the pool of key resource and access.

However it also raise an interesting question about information flow as a player controlling tools. Basically the laying of information token can direct the player in a given sequence, leaving hidden sequence or choice as a puzzle or shortcut for experience players (cool things for tutorial, skipping might a sequence break puzzle or challenge). It allow us to dynamically check or place those sequence breaking as part of the generation.

Convergeance of small key layout is now my main area of thinking.
« Last Edit: July 10, 2012, 10:53:25 AM by Gimmy TILBERT » Logged

gimymblert
Level 10
*****


The archivest master, leader of all documents


View Profile
« Reply #18 on: July 18, 2012, 05:49:22 AM »

Ok I think I have solved convergence. For every one, one door became useless because the loop allow access to what it close (even in case where the point of interest is fully closed behind many doors). This feature might be useful for shortcuts as the door might lead to shorter path.

For generation the thumb of rules us that there should never be more doors accessible to user than accessible keys.

Now I start looking to more complex case like "swap" doors (close one, open another, think water height puzzle in Nintendo games) or one key open multiple doors.

I had realise that network is no different than a regular forward level, completion can be seen as an end and there is always a starting place, player can be seen as a random traversal algorithm.
Logged

Pages: [1]
Print
Jump to:  

Theme orange-lt created by panic