This question is not about game development or about actual implementation details.
I was playing Little Alchemy yesterday. (Warning: Productivity hazard.) You start with the four classical Elements of earth, air, fire, and water. You can combine them to produce other "Elements" (wood, humanity, time, cities, etc.), combine those to produce even more, etc. All of the relationships are predefined, so the game is less about crafting and more about lateral thinking.
I got curious about how exactly the game could store and query the various combinations optimally. Whether the developer actually does so under the hood is a different story, and not what I'm asking about.
Consider the following game mechanics:
- There is no limit to the number of Elements, but it's decided in advance by the game's designer and thus does not change at runtime.
- All Elements are made by combining exactly two other Elements, possibly of the same kind (Fire + Water = Steam).
- Even the four base Elements can be created (Fire + Ice = Water).
- Some Elements can be created through more than one combination. (Fire + Water = Energy + Water = Steam)
- Some combinations produce more than one Element (Human + Cow = Minotaur and Milk)
- Some Elements are "final" and cannot be combined to produce any other, though they may in future updates. (Jedi + Swamp = Yoda)
- Order of combination does not matter (e.g. Water + Fire = Fire + Water).
The game presumably needs fast lookup and low memory usage. More specifically:
- Given exactly two elements, look up the result of their combination, if any. This should be fast.
- There is no insertion or removal except by the game's designer in advance. This can safely be slow.
Given these, what data structure might Little Alchemy use to store the various combinations that can be used to produce elements?
Back-of-the-envelope guess? A big ass-hash-table that maps
(Element, Element) pairs to
Element lists. For $n$ Elements, this results in amortized $O(1)$ lookup and $O(n^2)$ memory, because theoretically any combination can produce every other Element at once. Can we do better?