Standard data structure for binary recipes?

[sethmachine]

Hi,

What is the standard data structure (in WC3 mapping) for doing binary recipes with order, i.e.

A + B = C

but B + A = D

I was thinking of using a 2-D array, and thus TableArray from Bribe's Table.

TableArray twoD = TableArray[0x2000]
...
set twoD[A].integer[B] = C
set twoD[B].integer[A] = D
set twoD[X].integer[Y] = Z
set twoD[Y].integer[X] = Gamma
...

Note that the recipes are arbitrary, so it's impossible to generate the combinations automatically or via macro.

 

[Dr Super Good]

Binary tree (preferably balanced) where the full recipe is used as the value of the nodes. This may require several sequential integer tests per node but you should only need to traverse very few nodes.

 

[PurgeandFire]

Hashtables are convenient because you have two items for input and one output.

Otherwise, you would have to form a tree structure, but that would have higher complexity depending on the potential recipe combinations with the first item.

 

[sethmachine]

Aye and what's the problem with TableArray, then? A 2-D array has 2 (integer) keys which it maps to a third value, just like Blizzard's hashtable API? AFAIK (in previous discussion I think you said hashtables can act as 2-D arrays). The "search" time for a 2-D array would be constant (assuming array access is constant time) = O(1).

AFAIK to search a tree doesn't the time have to logarithmic as a lower bound?

How would I set up this binary tree? e.g. what would the tree look like if these were the combinations.

(A,B --> C)
(B,A --> D)
(X,Y --> Z)
(Y,X --> U)

 

[PurgeandFire]

Nothing is wrong with TableArray. TableArray is just using a hashtable. I should've phrased it better, I was just agreeing with your approach.

You would have separate trees for each source item. In your case, you would have 4 separate trees. But if you had something like this:

(A,B --> C)
(A,C --> D)
(A,X --> Y)

You could have a tree with 3 nodes, root is A. If you want a binary tree, you would have to sort based on the rawcodes. Rawcodes map to integers, so you would sort them using that and then form a tree. Let's say C < D < A < Y. It may look like:

........ A
......./...\
......D....Y
...../
....C

(er, well, it doesn't necessarily have to be sorted to be a binary tree, but if you want an optimal search, you should consider sorting). But anyway, this gets a little complicated to translate over to JASS. Use a hashtable to save yourself an annoying implementation.

 

[sethmachine]

Ah I see. I guess my confusion was from my misunderstanding of the wording, which made it sound like all my combinations I listed could be done in a single binary tree.

So there would be a tree for each source item, and then nodes corresponding to the output, which are traversed based on the strict ranking of the second item in the recipe (left corresponds to the lowest value and right is higher, from the tree you gave, right?).

From Dr Super Good's post though, is using trees the standard data structure in video game industry for combinations/recipes?

It would definitely seem annoying to have make O(n) trees if I have n source items.

 

[Nestharus]

What about a tree in which all of the children for any given node are stored in a table instead of a list and retrieved with a key? That's how i would do it if i were to make a recipe system like what you want. This would support any number of items in a recipe, not just 2. If you want only 2, just use a hashtable. If you want order to not matter, then do the tree still, but check every item in the inventory, not just the newly added one.

 

[Dr Super Good]

From Dr Super Good's post though, is using trees the standard data structure in video game industry for combinations/recipes?

I do not know but it is a pretty standard structure in computer science in general for any kind of search. A hashtable of sorts can also be used but WC3 hashtables are only limited to 64 bits (2 * 32 bit integers) so this would translate into only 2 items. A custom hashtable approach could also be used and may even be faster. The idea is you get your entire recipe and use that as a unique identifier to some product. If it was say 6 items long that would need 192 bits or 6 integers in series. If it is just two items long (64 bits) the standard hashtable would suffice.

In any case the idea is to use a data structure with better than O(n) complexity. Binary trees provide O(log2(n)) complexity while hashtables provide O(1) complexity but can fall back to O(n) if saturated.