I’m working on a crafting system similiar to Terraria’s, where the system examines your inventory and displays a list of possible objects that can be crafted with what you’re carrying. I’m currently representing each crafting ingredient as some enum ECraftingIngredient, and each recipe as a pair of (array, resultingitem).
To brute force this, I could just iterate down a list of every crafting recipe in the game and return whichever recipes can be assembled from your inventory contents, but that’s an extremely blunt brute force approach that will quickly become nonperformant as the number of recipes grows. Is there an obviously better way to quickly match ingredients to recipes that I’m missing?
you really won’t have a problem with going through a list
terraria is huge and it still “only” hass 3500 items, it would take months just coming up with ideas for that many not to mention the art for them, so for now you could do it, and you have time to think about a better solution later
Huh, it’s really not that big of a performance drag? I always thought that iterating across large lists was a really bad idea (although granted, nothing’s worse than premature optimization ).
Iterating over large lists IS a bad idea.
First off, your data structure needs reviewing. You’re in an object oriented language, which means you need to work in an object oriented way.
Enums are not the right way to do this; I know a lot of tutorials use them for small games, but this isn’t really the right way to use them.
Instead, an Ingredient needs to be a class, and a recipe needs to be a class.
public class Ingredient
{
public string Name { get; set; }
public int Id { get; set; }
}
public class Recipe
{
public IList<Ingredient> Ingredients { get; set; }
public Item CraftedItem { get; set; }
public Recipe()
{
Ingredients = new List<Ingredient>();
}
That’s easy enough to do, but wouldn’t making them classes instead of enumerations only increase the amount of work each comparison would require? It would be more elegant, since I could directly compare each recipe’s ingredient list with a target inventory, but at some point I would still have to systematically compare recipes with ingredients to determine what I was capable of assembling.
It’s the beginning to something more efficient. You can set up a cross reference with a Dictionary<Ingredient, HashSet> to have an O(1) way to look up all the recipes an ingredient can be used for. You just have to fill out the dictionary when the game starts.
Oh, I hadn’t thought about starting the map with the ingredient, I stuck thinking about it in terms of going recipe>ingredient. Thank you for the suggestion!
This would be a good way to approach it. If you wanted to you could iterate through your (array, resultingitem) at runtime to produce the collection. Thinking in terms of recipes is probably easier for design, but thinking in terms of ingredients will be better at runtime.
The other structure that might be worth considering is building a graph, where each node represents an ingredient. The edges leading to a node represent the recipie. This type of structure could be useful if you have a multi generational crafting system
I’m definitely going to try and think in terms of recipes on the design side, because that leads to an absurdly simple data-driven workflow where I can just create a CSV/JSON file containing a collection of Ingredients and one Recipe per line.
Assuming I take your suggestion and do something at runtime to convert that into an ingredient-based reference system, would I be headed in the right direction if I aimed to end up with a map of (Ingredient, array) for each ingredient (presumably compiled and cached when the game starts, since assembling it would be the closest I get to a computationally expensive step), then deal with the player selecting multiple ingredients by comparing ingredient maps for common recipes?
).