游戏组件合成算法咨询：递归逻辑优化与合成路径溯源

我开发了一款可采集组件的游戏，组件能通过已知配方合成奖励或新组件。想要实现的功能是：输入持有的组件及数量，获取可合成的奖励列表（包括合成组件后再合成的情况）。我写了递归的craft函数，但不确定它的准确性，还希望能溯源合成路径（比如合成3个component5的完整前置步骤），现在对递归逻辑很困惑，求技术指导。

现有代码 #

配方与初始库存 #

const recipes = {
        "recipe_1": {
          "components": [
            "component1",
            "component2"
          ],
          "type" : "reward",
          "result": "reward1"
        },
        "recipe_2": {
          "components": [
            "component1",
            "component3"
          ],
          "type" : "component",
          "result": "component4"
        },
        "recipe_3": {
          "components": [
            "component3",
            "component4"
          ],
          "type" : "component",
          "result": "component5"
        },
        "recipe_4": {
          "components": [
            "component4",
            "component5"
          ],
          "type" : "reward",
          "result": "reward2"
        }
    }
    
const inventory = {
    "component1" : 23,
    "component2" : 12,
    "component3" : 6,
    "component4" : 3,
    "component5" : 7
}

craft(recipes, inventory)

递归craft函数 #

function craft(recipes, inventory){
    // Loop over all recipes
    for (let recipe of Object.entries(recipes)){
        //Make a modifiable copy of inventory
        let inv = JSON.parse(JSON.stringify(inventory))
        let count = 0
        // Loop for count how many craft we can make
        while(((inv[recipe[1].components[0]]) > 0 ) && ((inv[recipe[1].components[1]]) > 0)){
            count++
            // Remove used components
            inv[recipe[1].components[0]] -= 1
            inv[recipe[1].components[1]] -= 1
            // Add component if recipe craft a component
            if(recipe[1].type == 'component'){
                inv[recipe[1].result] += 1
            }
        }
        // if we can craft, output what we can craft
        if(count > 0){
            console.log(`Can Craft ${count} ${recipe[1].result} / ${recipe[0]} / ${recipe[1].components}`)
        }
        // Delete recipe to avoid infinite loop
        delete recipes[recipe[0]]
        // recursive function
        craft(recipes, inv)
    }
}

问题分析与改进方案 #

现有代码核心问题 #

1. 递归逻辑混乱：直接修改全局recipes对象（delete recipes[recipe[0]]）导致后续递归丢失配方，且递归时机错误——应该在合成新组件后，基于更新的库存重新遍历所有配方，而非删一个配方就递归一次。
2. 无合成路径追踪：仅记录单次合成数量，未保存每一步的依赖关系，无法回溯完整合成链。
3. 合成次数计算不合理：while循环只处理当前库存的直接合成，未考虑合成新组件后能继续合成的情况，且不支持配方需要多数量组件的场景。

改进思路与实现 #

1. 重构递归逻辑：深度优先搜索（DFS）遍历合成路径

通过复制库存和配方的方式，避免修改原始数据，每次合成后递归检查所有可能的后续合成，直到无新合成可能。

2. 添加路径追踪

给递归函数传入path参数，记录每一步的合成信息（配方ID、消耗组件、合成数量），合成奖励时保存完整路径。

3. 正确计算合成次数

对每个配方，计算当前库存能支持的最大合成次数（取各组件库存与配方需求的比值最小值），批量更新库存后再递归。

示例改进代码 #

const recipes = {
    "recipe_1": { components: ["component1", "component2"], type: "reward", result: "reward1", requires: { component1: 1, component2: 1 } },
    "recipe_2": { components: ["component1", "component3"], type: "component", result: "component4", requires: { component1: 1, component3: 1 } },
    "recipe_3": { components: ["component3", "component4"], type: "component", result: "component5", requires: { component3: 1, component4: 1 } },
    "recipe_4": { components: ["component4", "component5"], type: "reward", result: "reward2", requires: { component4: 1, component5: 1 } }
};

const inventory = {
    component1: 23,
    component2: 12,
    component3: 6,
    component4: 3,
    component5: 7
};

// 存储所有可合成的奖励及完整路径
const availableRewards = [];

function findCraftPaths(currentInv, currentPath = []) {
    let canCraftMore = false;

    // 遍历所有配方
    for (const [recipeId, recipe] of Object.entries(recipes)) {
        // 计算当前库存能合成该配方的最大次数
        const maxPossible = Object.entries(recipe.requires).reduce((min, [comp, req]) => {
            return Math.min(min, Math.floor((currentInv[comp] || 0) / req));
        }, Infinity);

        if (maxPossible <= 0) continue;

        canCraftMore = true;
        // 复制库存，避免修改原始数据
        const newInv = { ...currentInv };
        // 批量消耗组件
        for (const [comp, req] of Object.entries(recipe.requires)) {
            newInv[comp] -= req * maxPossible;
        }
        // 添加合成结果
        if (recipe.type === "component") {
            newInv[recipe.result] = (newInv[recipe.result] || 0) + maxPossible;
        }

        // 记录当前合成步骤
        const step = {
            recipeId,
            result: recipe.result,
            times: maxPossible,
            consumed: Object.fromEntries(Object.entries(recipe.requires).map(([k, v]) => [k, v * maxPossible])),
            type: recipe.type
        };
        const newPath = [...currentPath, step];

        // 若合成结果是奖励，保存完整路径
        if (recipe.type === "reward") {
            availableRewards.push({
                reward: recipe.result,
                total: maxPossible,
                path: newPath
            });
        }

        // 递归继续探索后续合成
        findCraftPaths(newInv, newPath);
    }

    return canCraftMore;
}

// 启动合成路径搜索
findCraftPaths({ ...inventory });

// 输出结果
console.log("可合成的奖励及路径：");
availableRewards.forEach(item => {
    console.log(`奖励：${item.reward} x${item.total}`);
    console.log("合成路径：");
    item.path.forEach((step, idx) => {
        console.log(`  步骤${idx + 1}: 用${Object.entries(step.consumed).map(([k, v]) => `${v}x${k}`).join(" + ")} 合成 ${step.times}x${step.result}（配方${step.recipeId}）`);
    });
    console.log("---");
});

代码说明 #

• 给配方添加requires字段，明确每个组件的需求数量，方便扩展多数量需求的配方。
• 使用findCraftPaths递归函数，通过复制库存和路径，避免修改全局数据。
• 每次合成后，若结果为奖励则保存完整路径，否则继续递归探索后续合成可能。
• 最终输出所有可合成奖励及其完整合成链路。

内容的提问来源于stack exchange，提问作者Cripsii