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\$
  • \$\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 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 at 14:15
0
\$\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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.