RPG游戏装备合成算法

引言

一般的手游项目中，策划挖数值坑的点来来去去就几样：装备、宠物、宝石、附魔、强化。
想让玩家爆肝怎么办？调整爆率、升级、合成、突破、进化等等

只有你想不到的，没有老八做不到的。

今天给大伙整一个俄罗斯二手的装备合成算法
为什么是二手的，因为我不是第一个发博客写这个算法的人

需求

装备系统的合成图谱，箭头指向的是合成之后的装备，每合成一个装备需要消耗一些金币，箭头上的数字表示合成所需的材料数量。
比如，要合成n个装备A，需要消耗3n个装备B、1n个装备C、4n个装备D，而且还需要消耗26n金币（装备B和装备D的合成与此类似）。

思路

一般解决树结构的问题，首先想到递归。
其次限制合成装备的条件有两个，合成材料和金币。哪个优先级高呢，个人觉得是材料。

一般情况下，材料获取难度高于金币
虽然都可以在商城花费高级金币（钻石）购买材料和金币，但用钻石购买金币会让玩家产生血亏的感觉，策划应该避免这种情况

根据优先级，先算出不花费金币的情况下最多能合成的装备数量
然后计算合成一件装备的数量
最大数量×单价=总花费金币
总花费金币＜玩家持有金币，最大数量便是结果
总花费金币＞玩家持有金币，只能用玩家金币数除以单价得到结果

算法

public class Exam
{
    public class MaterialData
    {
        public ItemData item;   //合成所需的物品
        public int count;       //合成所需的该物品的数量
    }

    public class ItemData
    {
        public int id;                          //物品 ID
        public int count;                       //当前拥有的物品数量
        public int costGold;                    //合成该物品所需的金币
        public List<MaterialData> materialList; //合成该物品所需的材料
    }

    /// <summary>
    /// 计算用 totalGold 金币最多可以合成的 item 装备的数量
    /// </summary>
    /// <param name="item">要合成的装备</param>
    /// <param name="totalGold">拥有的金币</param>
    /// <returns>可合成的 item 装备的最大数量</returns>
    public int Run(ItemData item, int totalGold)
        {
            int resCount = getCount(item);
            int resCost = getCost(item);
            int res = resCost * resCount;
            if (res > totalGold)
                return totalGold / resCost;
            else
                return resCount;
        }
        /// <summary>
        /// 计算合成1个item装备要消耗的金币数
        /// </summary>
        /// <param name="item">要合成的装备</param>
        /// <returns>合成1个item装备要消耗的金币数</returns>
        private int getCost(ItemData item)
        {
            int count = item.materialList.Count;
            if (count == 0)
            {
                return 0;
            }
            int minCount = 0;
            for (int i = 0; i < count; i++)
            {
                minCount += getCost(item.materialList[i].item) * item.materialList[i].count;
            }
            minCount += item.costGold;
            return minCount;
        }
        /// <summary>
        /// 计算不计金币的情况下能合成最多的item装备数量
        /// </summary>
        /// <param name="item">要合成的装备</param>
        /// <returns>可合成的 item 装备的最大数量</returns>
        private int getCount(ItemData item)
        {
            int count = item.materialList.Count;
            if (count == 0)
            {
                return item.count;
            }
            int curCount, conCount;
            int minCount = int.MaxValue;
            for (int i = 0; i < count; i++)
            {
                curCount = getCount(item.materialList[i].item);
                conCount = curCount / item.materialList[i].count;
                minCount = Math.Min(minCount, conCount);
            }
            return minCount;
        }
}

测试用例

测试用例参考这篇博客