5
$\begingroup$

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?

Initial Thoughts

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ What does better mean? Faster? Lower memory footprint? Guaranteed $O(1)$ search instead amortized? $\endgroup$
    – Evil
    Mar 30, 2016 at 18:48
  • $\begingroup$ Let's say lower memory. $\endgroup$
    – JesseTG
    Mar 30, 2016 at 19:10
  • $\begingroup$ So, the "game" is basically just Doodle God with a differently bad user interface. $\endgroup$
    – David Richerby
    Apr 2, 2016 at 1:17
  • $\begingroup$ @DavidRicherby Apparently, yes, though I hadn't heard of that game until just now. $\endgroup$
    – JesseTG
    Apr 2, 2016 at 1:31

2 Answers 2

Reset to default
2
$\begingroup$

A hashtable is asymptotically optimal. Your analysis led you astray.

The relevant parameter is the number of rules that exist (where each rule specifies a combination of two elements and what new elements that combination produces). Call this $m$.

It's easy to see that any data structure will need at least $\Omega(m)$ space. You can't do better than that, because you're going to store something about each rule.

Moreover, a hashtable does achieve $O(m)$ space, so it is asymptotically optimal. Also, a hashtable achieves $O(1)$ expected lookup time, so it is asymptotically optimal in that respect as well.

None of this means that it will be optimal in practice, because it ignores constant factors. But speaking pragmatically: I expect a hashtable will be fine. The size of the table will be small enough that it probably takes up only a tiny fraction of the overall memory usage of the program, so most likely there's little point in trying to optimize it to the max.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Since there are no modifications at runtime takinkg minimal perfect hash changes expected $O(1)$ to true $O(1)$, which leads to optimal memory usage. $\endgroup$
    – Evil
    Apr 2, 2016 at 15:29
0
$\begingroup$

Sounds like you'd want a 1:1 mapping of elements to numbers, starting at 1 (using an enumerated type or something similar, depending on the implementing language), then use a sparse matrix to store the combinations. It'd be a symmetric sparse matrix, so that might allow further compression, depending on how exactly it's implemented.

Improve this answer
$\endgroup$
3
  • $\begingroup$ How does this account for combinations that produce multiple elements? $\endgroup$
    – JesseTG
    Mar 31, 2016 at 3:45
  • $\begingroup$ @JesseTG That's a good question; I didn't see that part of the problem. Maybe instead of enumerating the elements as 1, 2, 3, ... you could use bit flags: 1, 2, 4, 8, ... and multiple outputs are the sum of the flags of all output elements. $\endgroup$
    – DylanSp
    Mar 31, 2016 at 10:41
  • $\begingroup$ So now we've got guaranteed constant lookup, but we're assuming we can use arbitrarily large integers (though they'd be of a fixed size anyway, since the number of overall Elements doesn't change at runtime). There are 560 Elements as I write this, so we need 560 bits. Memory is still $O(n^2)$, as we need to store $\frac{n^2}{2}$ numbers. $\endgroup$
    – JesseTG
    Apr 1, 2016 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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