3
\$\begingroup\$

I'm asking here rather than on SO/SE/CS because I'll probably have less to explain what I'm talking about...

I hope a lot of the users here are familiar with how many games implement modding (or sometimes even their own add-ons, levels etc.) Conceptually, what I've seen most often is a data structure that acts like a layered dictionary. With no mods, there's lookup in the base dictionary layer; whenever a mod is added/enabled, it comes with its own dictionary layer from which lookups are served first, with fallback to the underlying layers if a key is not found. (Note that I'm not talking about a nested dictionary.)

So, my question is simply if there's a generic name for this data structure. (Googling for "layered dictionary", which is how I dubbed it, doesn't turn up anything useful...) In the world of file systems, the closest thing that probably resembles it is a union mount. Alas "union dictionary" doesn't get any useful results either... (Also the word "union" is rather misleading in this context because there's an order in the layers of a "union mount".)

Added: By the way, I'm not asing how to implement it, as that's rather obvious from the description. Perhaps that's why no name have been devised for it... Also most game engines I've seen implement multi-layer (not just two) and some allow the (top) layers to be removed at any time so you can do (game) "levels" that way; others require an engine restart so it's only usable for "global mods", i.e. they optimize lookup time by "flattening" the layers down to one as they are added, which is basically why they need an "engine restart" to remove a layer.

Also, it seems the R (statistical) programming language basically has this its get functions:

These functions look to see if each of the name(s) x have a value bound to it in the specified environment. If inherits is TRUE and a value is not found for x in the specified environment, the enclosing frames of the environment are searched until the name x is encountered.

So I guess something like "environments and their enclosures" is one term...

\$\endgroup\$
2
  • \$\begingroup\$ Reminds me of MultiValueDictionary. But if you ask me, this sounds like something you can do by checking your dictionary, and if it has no key assigned, resort to a second dictionary which you check after that. If you use it multiple times, you could create your own LayeredDictionary<TKey, TValue> class. Now there is nuance - it's either a dictionary with variable layers (which does not guarantee a default value) or a dictionary with a default value (2 layers) or both. That depends on you. \$\endgroup\$
    – Battle
    Mar 5, 2020 at 12:00
  • \$\begingroup\$ @Battle: I'm not asing how to implement it, as that's rather obvious from the description. Perhaps that's why no name have been devised for it... Also most game engines I've seen implement multi-layer (not just two) and some allow the (top) layers to be removed at any time so you can do (game) "levels" that way; others require an engine restart so it's only usable for "global mods", i.e. they optimize the whole thing by "flattening" the layers down to one as they are added, which is basically why they need an "engine restart" to remove a layer. \$\endgroup\$
    – Fizz
    Mar 5, 2020 at 14:15

2 Answers 2

1
\$\begingroup\$

The most generic concept seems to be variously called a spagetti/cactus stack or in-/parent-pointer tree of symbol tables.

Now the first part of this "thing" is also generic, in the sense that the "nodes" can be other things that have a notion of look-up. Come to think of it, "union mounts" and how they're implemented in some game engines actually cactus-stack nested dictionaries, in the sense that they both stack layers and allow path-like ("segmented") keys.

N.B. I've not seen a game engine that allows forks in its look-up structures, i.e. in the full sense of a cactus stack. I've only seen linear stacks of nested dictionaries as the most complex look-up structure actually used for modding/levels support.

\$\endgroup\$
1
\$\begingroup\$

Steve Yegge calls this the Properties Pattern. It's a pattern that shows up in so many places that we may not even notice it. He's using it in his game Wyvern.

It shows up in scopes:

int x = 5, y = 7;
if (…) {
    int x = 3;
    /* x is 3 here! but y is 7 */
}

Here the inner scope has {x: 3} and the outer scope has {x: 5, y: 7}. Any name not found in the inner scope will look in the next outer scope, and this will chain all the way up to the global level.

Class inheritance works this way. If a class Base defines methods a and b, and a subclass Derived defines a, it will find Derived.a when looking for a, and Base.b when looking for b. In Self, LambdaMOO, and JavaScript, object inheritance works this way.

SVG attributes work this way. If you have a <g fill="red" stroke="blue"> and then a <rect fill="green"> inside of it, it will use green for the fill and blue for the stroke. The OS/2 operating system had properties defined this way. I'm sure there are plenty more examples.

Each level has a key-value mapping, plus a "parent" or "inherit" or "default" pointer to another such mapping, which can itself have another pointer, etc. Typically writes go to the current mapping, but reads can go up the chain.

I've been looking for a more authoritative name for this pattern than Steve Yegge's blog post, but that's the best I've found so far.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .