基于递归模式查找游戏可制作物品的根物品及其关联

嘿，我刚好在折腾类似的游戏物品制作链逻辑，给你分享下我梳理的思路，完全贴合你正在探索的方向——找根物品、理清楚它们的制作关联，还能处理后续的数值向上取整需求。

1. 先把核心概念掰明白 #

• 根物品：就是那些没parent属性（或者parent是空数组）的家伙，没法通过制作得到，只能靠采集、捡取之类的方式获取，比如你说的woodLog就是典型的根物品。
• 关联链：从根物品出发，顺着child往下摸，能摸到所有用它能做出来的子物品；反过来，从任意子物品顺着parent往上找，能回溯到它依赖的所有根物品。

2. 先把物品数据规整好 #

我习惯把所有可制作物品整理成字典结构，查起来贼方便，就像这样：

craftable_items = {
    "woodLog": {
        "parent": [],  # 原木没前置材料
        "child": [("woodPlank", 2)]  # 1个原木产出2个木板
    },
    "woodPlank": {
        "parent": [("woodLog", 0.5)],  # 制作1个木板需要0.5个原木
        "child": [("woodWall", 4)]  # 制作1面木墙需要4个木板
    },
    "woodWall": {
        "parent": [("woodPlank", 4)],  # 制作1面木墙需要4个木板
        "child": []  # 木墙暂时无法制作其他物品（假设）
    }
}

这个结构里，每个物品ID对应它的父/子列表，都是(itemID, 数量)的元组，一目了然。

3. 从子物品回溯根物品的方法 #

比如你想知道做1面woodWall到底要多少woodLog，可以用递归或者迭代的方式往上查，同时计算数量，最后统一向上取整：

import math

def get_root_requirements(target_item, need_quantity=1):
    item = craftable_items.get(target_item)
    if not item["parent"]:
        # 找到根物品了，先返回原始数量，最后统一取整
        return {target_item: need_quantity}
    
    total_roots = {}
    for parent_id, per_child_qty in item["parent"]:
        # 先计算需要多少个父物品
        parent_needed = need_quantity * per_child_qty
        # 递归查找这个父物品的根需求
        parent_roots = get_root_requirements(parent_id, parent_needed)
        
        # 把父物品的根需求累加到总需求里
        for root_id, qty in parent_roots.items():
            if root_id in total_roots:
                total_roots[root_id] += qty
            else:
                total_roots[root_id] = qty
    
    # 最后统一对所有根物品数量向上取整
    for root_id in total_roots:
        total_roots[root_id] = math.ceil(total_roots[root_id])
    
    return total_roots

比如调用get_root_requirements("woodWall")，会返回{"woodLog": 2}；要是遇到制作3个木板的场景，需要1.5个原木，向上取整后就是2个，这个逻辑能完美处理。

4. 从根物品出发找所有关联子物品 #

如果想知道一个根物品能衍生出多少种物品，用BFS（广度优先搜索）遍历就行，比如：

def get_all_children_from_root(root_item):
    child_set = set()
    # 用队列做BFS，避免遗漏物品
    queue = [root_item]
    
    while queue:
        current_item = queue.pop(0)
        item_data = craftable_items.get(current_item)
        for child_id, _ in item_data["child"]:
            if child_id not in child_set:
                child_set.add(child_id)
                queue.append(child_id)
    
    return child_set

调用get_all_children_from_root("woodLog")，就能得到{"woodPlank", "woodWall"}——所有用原木能制作出来的物品都在这了。

5. 踩过的坑给你提个醒 #

• 循环依赖要防：万一游戏里有A需要B、B需要A的情况，递归会直接死循环，所以遍历的时候要加个已访问集合，碰到已经查过的物品就跳过。
• 多父物品别漏：有些物品可能需要好几种材料，比如做斧头要木材和石头，这时候递归时要把所有父物品的根需求都算进去，不能只处理一个。
• 取整时机要对：别在中间步骤就取整，不然会算错！比如做3个木板需要1.5个原木，要是分三次单独算每次取整，会得到3个原木，而正确的应该是向上取整为2个，一定要最后统一取整。

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