"Mixing" systems.

ID:151574
 
Mar 3 2010, 1:41 pm
Has anyone here ever come up with an elegant solution to handling mixing systems? That is, things like what ingredients form a certain type of food, what metals and items are needed to make a weapon, what items are needed to cast a spell, etc. I haven't ever been able to come up with anything except the obvious choices of a list containing possible combinations, variables indicating a general feature of the ingredients and then requiring some sort-of bruteforce lookup of the final result, or breaking down items into component items which then determine the final result. All of these are, in my opinion, pretty bad, and I'm sure there has to be a better method.
Mar 3 2010, 7:48 pm
There probably is not many other methods you could use to handle an item creation system.
Unless the system is similar to that used in The Elder Scroll games, where you throw a bunch of items into a pot, and the resulting potions effects are based on those ingredients and their properties.

Other than that, you'll probably have to keep a list of ingredients needed to make an item, or what items an ingredient can be made into.


One system I made basically had ingredients as types. And each item you could make was made of various item types.
All ingredients had properties, and like in The Elder Scroll games, if you mixed these properties together, the final item was altered.
An example was a healing potion, it needed 1 container, 1 herb, and 1 water like item.
By mixing and matching items the final potion could inherit properties, such as being more powerful, or healing a group of people, maybe even healing status effects and so on.

But yeah, even that system was still basically keeping a list of ingredients and then looping through the items being used to make the final product to see if they were the right type of ingredient.
Mar 4 2010, 6:58 am (Edited on Mar 4 2010, 11:47 am)
2 dimensional array method:

if a wooden handle's item ID is 4 and a iron blade's item ID is 8, the item at Combination[4][8] is the result of the mixture.
Mar 4 2010, 7:00 am
Other than the 'brute force' method you are talking about, you could always take out the 'mix whatever stuff you want' aspect and do a recipe system where it tells you what you need and then you go get it.
Mar 4 2010, 11:42 am
In response to Techgamer
That's 2-dimensional, not 3-dimensional.

3-dimensional would be including the phase of the moon, so Combination[4][8][6] would be the result of combining a wooden handle and an iron blade while the moon is waxing gibbous. Obviously, the result of this would be a sharpened stick, as opposed to a sword ([4][8][1]) or a spear ([4][8][8]).
Mar 4 2010, 11:48 am
In response to Garthor
Garthor wrote:
That's 2-dimensional, not 3-dimensional.

3-dimensional would be including the phase of the moon, so Combination[4][8][6] would be the result of combining a wooden handle and an iron blade while the moon is waxing gibbous. Obviously, the result of this would be a sharpened stick, as opposed to a sword ([4][8][1]) or a spear ([4][8][8]).

Ah, my mistake, I really haven't been using arrays for anything recently, I like Linked list's flexibility.
Mar 5 2010, 8:50 am (Edited on Mar 5 2010, 8:56 am)
In response to Techgamer
The trouble with a system like that is the array would likely be rather sparse and a waste of memory, since, for instance, it's useful to combine a sword hilt with a blade, but not to combine it with an apple, a puppy, or a pile of rocks. This becomes even worse if you want an N-dimensional array for combining N items.

Instead I'd use an associative list based method. You just need a method for ordering the ingredients (such as alphabetical order), and create a key based on it. Then create an associative list matching the key to the desired outcome:
var/list/mixlist = new()
mixlist["all things nice+sugar+spice"] = /mob/little_girl
mixlist["sword blade+sword hilt"] = /obj/weapon/sword

Then when combining ingredients, sort a list of the ingredient names, create the key, and see if there is a matching list entry for it:

proc/get_mix_result(var/list/ingredients)
  ingredients.Sort() // sort the objects in the list by name alphabetically
  var/key = ""
  for(var/obj/O in ingredients)
    key += "[O.name]+"
  key = copytext(key, 1, lentext(key)) //strip the trailing +
  return mixlist[key]
  // will return null if no matching recipe was found


The sort is needed so that you can be sure the ingredient list is always in the same order; implementing it is an exercise for the reader.

This method also has the benefit that you can have any number of ingredients in a recipe. You could also extend it to amounts of ingredients by embedding that into the key string.
Mar 5 2010, 9:46 pm
In response to Hobnob
If you haven't used a language where you actually have to manage memory yourself, you really shouldn't be talking about wastes of memory. I wouldn't be surprised if your solution ended up using MORE memory, as each character in each of those strings takes up as much memory as a single empty cell in a two-dimensional array. Of course, it isn't even worth my time to figure out whether that's true or not, because even if you had a thousand items (items that you can craft with, mind you), that's a whopping... one megabyte, which is about two cents worth of memory.

Of course, it MIGHT get out of hand if you start talking about combinations of more than two objects at a time. However, it's easy enough to just use the types of the objects as keys for an N-dimensional array... though they aren't arrays anyway (binary trees, I believe).
Mar 5 2010, 11:50 pm
In response to Garthor
Just as a pre-empt, he has.
Mar 6 2010, 6:43 am
In response to Garthor
Garthor wrote:
Of course, it MIGHT get out of hand if you start talking about combinations of more than two objects at a time. However, it's easy enough to just use the types of the objects as keys for an N-dimensional array... though they aren't arrays anyway (binary trees, I believe).

To back you up on your first statement I will poke a hole in your second. The problem here could be fixed by not combining the objects all at once. Though a fishing pole is just stick+thread, it is still an item itself and can therefore be in the 2-dimensional array. Then, if someone wants to create a "+1 automatic mobile fishing pole" and they put together a "+1 token" a "computer", "wheels", "stick" and "thread" you can look up list[fishing pole][thread] to get a fishing pole, list[pole][wheels] to get a mobile fishing pole that can drive around, list[mobile pole][computer] to get the automatic version of it, and list[+1 token][auto mobile pole] to get the full, buffed, auto, mobile fishing pole the person wants.

You could also minimize the required array space further if you have N item types by not making the array NxN. Figure out what the base materials are, and if you have M of those, make the array only MxN since you only need to compare an item to base materials to see what the next item in line is. This will still work even if you try to mix together to non-base items since a non-base item can either keep track of what it came from or you can just do a reverse lookup on the list to see what the components are.

If any of the additions in the queue don't work, the entire thing doesn't work. Simple way to do that is list[item1][item2] = null. So, if it makes sense to have a +1 auto-fishing-pole but not a mobile variant with wheels, then just have list[wheels][+1 auto pole] = null.

Of course, this doesn't work too well if you want to be able to disassemble items back into their base components and you have multiple ways to combine things into the item you have. That is, unless you keep track of where it came from. My fishing pole wasn't made of a stick+thread, it was made of a stick+yarn, so when I disassemble it, I would be surprised if I got sewing thread back instead of yarn, or vice-versa. It's simple to keep track of this though.

If we want to talk about memory usage, if the Byond byte code has an indexed table for item types, then in the end a 2D array will only use 2 or 4 bytes per item combination, so that's (2 or 4)*M*N bytes for the actual data (obviously this will be slightly higher for /list overhead, but it will be this much for this specific part). That will only be a megabyte if you have about 100 base item craft types and 2500 to 5000 higher-level types, or some similar pair that goes to 1M, obviously. 100 base types maybe but probably not, 2500+ higher-level types I doubt you have to worry about. But even if you have 1000 base types and 10000 higher-level item types, so what? That's 20 to 40MB. If your game is that big, then be prepared to use 50 cents worth of memory on the server for it.
Mar 7 2010, 7:23 am
Popisfizzy wrote:
variables indicating a general feature of the ingredients and then requiring some sort-of bruteforce lookup of the final result

I prefer a method that sounds strikingly similar to this. Basically, you have items that indicate several properties of what is to be mixed---for metals things like luster, density, ductility, etc. come to mind. Then you sum up those properties, some of which may be negative (mixing with ___ reduces luster). Next, turn the sum into an average, which may be optional really.

Finally, you would test a list of possible results against your sum|average object and find the first result for which the minimum requirements are met. This might be a descending list in terms of value (If I invest all kinds of precious metals that average out to meeting the minimum requirements for both copper and gold, give me gold).

A rough sketch of such a system might be:
mix_item
    var
        prop1 = 0
        prop2 = 0
        prop3 = 0
    
    proc
        Add(mix_item/m)
            prop1 += m.prop1
            prop2 += m.prop2
            prop3 += m.prop3
    
        Average(n)
            prop1 /= n
            prop2 /= n
            prop3 /= n
        
mix_result
    var/target = /obj   // some path
    proc
        Test(mix_item/m)    // TRUE if minimum requirements are met, false otherwise
                
        Make()  // pass the args you would pass to New()
            return new target(arglist(args))


/*
 *  mix_results should be a sorted list of /mix_result objects,
 *  where more valuable objects appear first (a descending list).
 *  This way if one mixes metals that could either result in gold
 *  or copper, they get the gold. :)
 */

var/list/mix_results

proc
    mix_result_cmp(mix_result/a, mix_result/b)  // a comparison for a DESCENDING sort
        if(/* a's worth > b's worth */)
            return -1
        else if(/* a's worth < b's worth */)
            return 1
        else
            return 0
            
    init_mix_results()
        mix_results = new
        for(var/mix_type in typesof(/mix_result)-/mix_result)
            mix_results += new mix_type
            
        ls_heapsort_cmp(mix_results, /proc/mix_result_cmp)  // from Kuraudo.ListSort
        
    mix(list/items) // "items" is a list of /mix_item objects to be mixed
    // Generate the "sum" item 
        var/mix_item/sum = new
        for(var/i in items)
            sum.Add(i)
            
        sum.Average(items.len)  // handle division of all properties by items.len
    
    // Make sure we have some result objects
        if(!mix_results)
            init_mix_results()  // initialize and sort list
            
    // Find a match, return null otherwise      
        for(var/mix_result/result in mix_results)
            if(result.Test(sum))    // if our sum meets the minimum requirements
                return result.Make(/* New() args */)

Though this should definitely be changed to some extent to meet any project's specific needs. As well, for clarity I've omitted all kinds of potential error-checking (divide-by-zero, null arguments, etc.) that one may wish to consider doing.

The nicety of this kind of design is that you don't have to list out all possible combinations of what could be mixed; you simply need to define the minimum properties of the results. Granted, this means you could theoretically mix three metals and a piece of cheese and come out with a nice piece of metal and no cheese, but that's up to your design.