auto_fill_jewel/auto_fill_jewel_v3/LevelGenerate.cpp

//
//  LevelGenerate.cpp
//  auto_fill_jewel_v3
//
//  Created by Red on 2024/11/23.
//

#include "LevelGenerate.hpp"
#include <iostream>
#include <cassert>
#include <unordered_map>
#include "FillGlobalConfig.hpp"
#include <tuple>
#include "BoxPositionTool.hpp"
#include "GridPositionTool.hpp"

using namespace std;

bool LevelGenerate::generate( FillGlobalConfig::LevelData levelData,
                             const bool isMovable,
                             vector<tuple<int,vector<vector<FillResult>>>>& resultPlateFillResults,
                             vector<ContourData::Point>& resultPlateCenterPointArr
                             )
{
    resultPlateFillResults.clear() ;
    resultPlateCenterPointArr.clear() ;
    
    auto ms0 = std::chrono::system_clock::now().time_since_epoch() ;
    uint64_t ms00 = std::chrono::duration_cast<chrono::milliseconds>(ms0).count() ;
    
    srand(_seed);
    unordered_map<int,tuple<int,int> > jewIdSzCntStorageMap ;
    FillGlobalConfig* fgc = FillGlobalConfig::getInstance() ;
    int bigJewelCnt = 0 ;
    int midJewelCnt = 0;
    int smlJewelCnt = 0 ;
    for(int ij = 0 ; ij < levelData._jewelIds.size();++ ij ) {
        int jewId = levelData._jewelIds[ij] ;
        int    cnt =  levelData._cnts[ij] ;
        FillGlobalConfig::JewelItem* jewItem = fgc->getJewelItemById(jewId) ;
        jewIdSzCntStorageMap[jewId] = {jewItem->_size,cnt} ;
        if( jewItem->_size == FILLGLOBALCONFIG_JEWELSIZE_SM ) {
            smlJewelCnt+=cnt ;
        }else if( jewItem->_size == FILLGLOBALCONFIG_JEWELSIZE_MD ) {
            midJewelCnt += cnt ;
        }else if( jewItem->_size == FILLGLOBALCONFIG_JEWELSIZE_LG ) {
            bigJewelCnt += cnt ;
        }
    }
    //每个盘子类型小号宝石承载量
    //按顺序分别为大横，大竖，小。这里不考虑迷你。
    FillGlobalConfig::PlateItem* bigPlate = fgc->getPlateItemBySzNIndex(FILLGLOBALCONFIG_PLATESIZE_LG, 0) ;
    FillGlobalConfig::PlateItem* midPlate = fgc->getPlateItemBySzNIndex(FILLGLOBALCONFIG_PLATESIZE_MD, 0) ;
    FillGlobalConfig::PlateItem* smlPlate = fgc->getPlateItemBySzNIndex(FILLGLOBALCONFIG_PLATESIZE_SM, 0) ;
    vector<FillGlobalConfig::PlateItem*> usedPlates = {bigPlate,midPlate,smlPlate} ;
    int maxSmlJewCapPerPlate = 0;
    int minSmlJewCapPerPlate = 99999 ;
    for(int ip=0;ip<usedPlates.size();++ip ) {
        maxSmlJewCapPerPlate = fmax( usedPlates[ip]->_bigJewCap*4 , maxSmlJewCapPerPlate) ;
        minSmlJewCapPerPlate = fmin( usedPlates[ip]->_bigJewCap*4 , minSmlJewCapPerPlate) ;
    }
    //等效小宝石数量
    int effSmallJewelsCount = bigJewelCnt*4 + midJewelCnt*2 + smlJewelCnt ;
    //cout<<"bigJewelCnt "<<bigJewelCnt<<endl;
    //cout<<"midJewelCnt "<<midJewelCnt<<endl;
    //cout<<"smlJewelCnt "<<smlJewelCnt<<endl;
    //cout<<"effSmallJewelsCount "<<effSmallJewelsCount<<endl;
    
    //构建符合难度条件的盘子和层数组合
    vector<PlateIdAndLayerCnt> resPlateNLyrCnt = generatePlateTypeAndLayerCnts2(isMovable, levelData._difficulty,effSmallJewelsCount);
    if( resPlateNLyrCnt.size()==0 ) {
        //cout<<"failed at generatePlateTypeAndLayerCnts"<<endl;
        return false ;
    }
    
    //计算盘子的最大层数
    int maxLyrCnt = 0;
    for(auto it = resPlateNLyrCnt.begin();it!=resPlateNLyrCnt.end();++it ) maxLyrCnt=fmax(maxLyrCnt,it->_layerCnt) ;
    
    //对每个盘子组合进行填充宝石
    RandomGridFiller filler ;
    filler._seed = this->_seed ;
    srand(filler._seed);
    
    //构建每个盘子每个层的填充结果容器
    vector< tuple<int,int,vector<FillResult>> > plateIdLyrFillResultsArray ;// tuple<plateId, layerIndex, fillresults_array >
    
    
    //从顶到底部，逐层进行填充
    int residues = 0 ;
    for(int nlayer = maxLyrCnt; nlayer > 0 ; nlayer-- ) {
        //cout<<"for layer "<<nlayer<<endl;
        
        //满足该层数的所有盘子ID
        vector<int> plateIdArr ;
        for(auto it = resPlateNLyrCnt.begin();it!=resPlateNLyrCnt.end();++it ) if(it->_layerCnt>=nlayer) plateIdArr.push_back(it->_plateId) ;
        
        //该层总计需要填充多少小宝石
        int currLyrNeedEquvSmlCnt = 0 ;
        for(int ip=0;ip<plateIdArr.size();++ip ) {
            currLyrNeedEquvSmlCnt += fgc->getPlateItemById(plateIdArr[ip])->_bigJewCap*4 ;
        }
        //cout<<"layer need eqsmCnt "<<currLyrNeedEquvSmlCnt<<endl;
        
        //根据所需数量和所需求解百分比，计算从库存取出每类宝石多少个。
        float solPercent = 0.7 ;//根据需求文档，每层可解百分比都是70%.
        unordered_map<int, int> chosenJewIdNCnt = randPickJewels(currLyrNeedEquvSmlCnt, solPercent, jewIdSzCntStorageMap) ;
        int choseEqSmCnt=0;
        for(auto itp=chosenJewIdNCnt.begin();itp!=chosenJewIdNCnt.end();++itp) {
            choseEqSmCnt += jewSz2SmlCnt( fgc->getJewelItemById(itp->first)->_size) * itp->second ;
        }
        //cout<<"layer choose eqsmCnt "<<choseEqSmCnt<<endl;
        
        //逐个盘子填充
        for(auto itpid = plateIdArr.begin();itpid!=plateIdArr.end();++itpid) {
            vector<FillResult> fr = fillPlateOneLayer(filler, *itpid, chosenJewIdNCnt) ;
            tuple<int,int,vector<FillResult>> plateLyrFillResult={*itpid,nlayer,fr} ;
            plateIdLyrFillResultsArray.push_back(plateLyrFillResult);
        }
        
        //检查为该层挑选的宝石是不是全部填完了，如果没有填完还要还给库存，给下一轮填充用
        residues = 0 ;
        for(auto itjn = chosenJewIdNCnt.begin();itjn!=chosenJewIdNCnt.end();++itjn){
            if( itjn->second>0 ) {
                residues+=itjn->second;
                std::get<1>(jewIdSzCntStorageMap[itjn->first]) += itjn->second ;//剩余的加回到库存里
            }
        }
        //cout<<"layer chosen jewels residues "<<residues<<endl;
    }
    
    //查看库存是否全部用掉了
    if( residues>0 ) {
        int extraPlateCnt = 0 ;
        //剩了，添加一个小盘子和层，仍然剩了再继续加盘子加层
        unordered_map<int, int> residueJewIdAndCnts = findUnfilledInStorages(jewIdSzCntStorageMap) ;
        while( residueJewIdAndCnts.size()>0 ) {
            //新建一个小盘子
            extraPlateCnt++;
            //cout<<"add extra plate "<< extraPlateCnt <<endl;
            int plateId = smlPlate->_id ;
            for(int ilyr = 1 ; ilyr <= maxLyrCnt; ++ ilyr ) {
                vector<FillResult> frs = fillPlateOneLayer(filler, plateId, residueJewIdAndCnts) ;
                plateIdLyrFillResultsArray.push_back( {plateId,ilyr,frs} );
                //cout<<"add extra lyr "<<endl;
                if( residueJewIdAndCnts.size()==0 ) break ;
            }
            if( residueJewIdAndCnts.size()==0 ) break ;
        }
    }
    
    //整理数据
    regroupPlateLyrFillResults(plateIdLyrFillResultsArray, resultPlateFillResults);
    
    //摆放盘子
    {
        vector<int> plateIdArr1;
        for(auto itp = resultPlateFillResults.begin();itp!=resultPlateFillResults.end();++itp) plateIdArr1.push_back( std::get<0>(*itp) );
        placePlates(isMovable, plateIdArr1, resultPlateCenterPointArr) ;
    }
    
    
    auto ms1 = std::chrono::system_clock::now().time_since_epoch() ;
    uint64_t ms11 = std::chrono::duration_cast<chrono::milliseconds>(ms1).count() ;
    //cout<<"duration "<<ms11-ms00<<endl;
    return true ;
}

// this method is deprecated, use generatePlateTypeAndLayerCnts2()
[[deprecated]]
vector<LevelGenerate::PlateIdAndLayerCnt> LevelGenerate::generatePlateTypeAndLayerCnts(const int difficulty,const int totEquvSmallJewelCnt)
{
    assert(difficulty>=0&&difficulty<=2) ;
    vector<vector<LevelGenerate::PlateIdAndLayerCnt>> possibleResults ;
    vector<LevelGenerate::PlateIdAndLayerCnt> results ;
    assert(totEquvSmallJewelCnt>0) ;
    
    FillGlobalConfig* fgc = FillGlobalConfig::getInstance() ;
    FillGlobalConfig::PlateItem* bigPlate = fgc->getPlateItemBySzNIndex(FILLGLOBALCONFIG_PLATESIZE_LG, 0) ;
    FillGlobalConfig::PlateItem* midPlate = fgc->getPlateItemBySzNIndex(FILLGLOBALCONFIG_PLATESIZE_MD, 0) ;
    FillGlobalConfig::PlateItem* smlPlate = fgc->getPlateItemBySzNIndex(FILLGLOBALCONFIG_PLATESIZE_SM, 0) ;
    vector<FillGlobalConfig::PlateItem*> usedPlates = {bigPlate,midPlate,smlPlate} ;
    
    //一个关卡最多出现大、中、小盘子个数
    const int PLATE_BG_MAX_CNT = 9  ;// 1个大盘子=2两个中盘子=6个小盘子
    const int PLATE_MD_MAX_CNT = 18 ;
    const int PLATE_SM_MAX_CNT = 54 ;
    //每个关卡最大容纳等效小盘子的个数 就是54个
    //                                                 普通               难              极难
    vector< vector<float> > diffPlateCntPercent0 = { {0.3,0.3,0.0}, {0.2,0.4,0.0}, {0.1,0.5,0.0} } ;
    vector< vector<float> > diffPlateCntPercent1 = { {0.7,0.7,0.0}, {0.6,0.8,0.1}, {0.5,0.9,0.1} } ;
    bool isFirstGood = false;//由于盘子百分比计算不一定能满足盘子和宝石要求，为了保证至少有一个盘子组合可以用这里保留第一个可以装下宝石的盘子组合，如果有更优的方案替换之。
    vector<LevelGenerate::PlateIdAndLayerCnt> firstAvailablePlateComb ;
    
    for(int ipbig = 1; ipbig <= PLATE_BG_MAX_CNT; ++ ipbig ) {
        for(int ipmid = 0 ; ipmid <= PLATE_MD_MAX_CNT; ++ ipmid ) {
            int effsmPlateCnt = ipbig*6 + ipmid*3 ;
            if( effsmPlateCnt>PLATE_SM_MAX_CNT ) continue ;
            for(int ipsml = 0 ; ipsml <= PLATE_SM_MAX_CNT; ++ ipsml ) {
                //等效小盘子个数
                effsmPlateCnt += ipsml  ;
                if( effsmPlateCnt>PLATE_SM_MAX_CNT ) continue ;
                
                float bigPlateCntPercent = ipbig*6.0 / effsmPlateCnt ;
                float midPlateCntPercent = ipmid*3.0 / effsmPlateCnt ;
                float smlPlateCntPercent = ipsml*1.0 / effsmPlateCnt ;
                vector<float> percentArr = {bigPlateCntPercent,midPlateCntPercent,smlPlateCntPercent} ;
                
                //判断每个盘子百分比是否满足难度要求
                bool percentOk = true ;
                for(int iplatetype=0;iplatetype<percentArr.size();++iplatetype) {
                    if( diffPlateCntPercent0[difficulty][iplatetype]>percentArr[iplatetype] || diffPlateCntPercent1[difficulty][iplatetype]<percentArr[iplatetype]  )
                        percentOk=false;
                }
                if( isFirstGood == true ){
                    //至少有一个装下宝石的方案了
                    if( !percentOk ) continue ;//盘子百分比不符合要求，跳过
                }
                
                if( isFirstGood==false ) {
                    //保证至少有一个可以满足宝石的盘子组合
                    vector<int> pidArr ;
                    vector<int> capArr ;
                    vector<int> lyrArr ;
                    for(int it=0;it<ipbig;++it) { pidArr.push_back(bigPlate->_id);capArr.push_back(bigPlate->_bigJewCap*4); lyrArr.push_back(1); }
                    for(int it=0;it<ipmid;++it) { pidArr.push_back(midPlate->_id);capArr.push_back(midPlate->_bigJewCap*4); lyrArr.push_back(1); }
                    for(int it=0;it<ipsml;++it) { pidArr.push_back(smlPlate->_id);capArr.push_back(smlPlate->_bigJewCap*4); lyrArr.push_back(1); }
                    bool lyrOk = isJustFilledAll2(capArr, lyrArr, totEquvSmallJewelCnt) ;
                    if( lyrOk ){
                        isFirstGood = true ;
                        //保存结果
                        firstAvailablePlateComb.resize(capArr.size());
                        for(int it = 0 ; it < capArr.size(); ++ it ) {
                            firstAvailablePlateComb[it]._plateId = pidArr[it] ;
                            firstAvailablePlateComb[it]._layerCnt = lyrArr[it] ;
                        }
                    }
                }
                //计算每个类型的层数
                if( difficulty== FILLGLOBALCONFIG_DIFFCULTY_NORM ) {
                    //全部两层
                    vector<int> pidArr ;
                    vector<int> capArr ;
                    vector<int> lyrArr ;
                    for(int it=0;it<ipbig;++it) { pidArr.push_back(bigPlate->_id);capArr.push_back(bigPlate->_bigJewCap*4); lyrArr.push_back(2); }
                    for(int it=0;it<ipmid;++it) { pidArr.push_back(midPlate->_id);capArr.push_back(midPlate->_bigJewCap*4); lyrArr.push_back(2); }
                    for(int it=0;it<ipsml;++it) { pidArr.push_back(smlPlate->_id);capArr.push_back(smlPlate->_bigJewCap*4); lyrArr.push_back(2); }
                    bool lyrOk = isJustFilledAll2(capArr, lyrArr, totEquvSmallJewelCnt) ;
                    if(!lyrOk) continue;
                    
                    //保存结果
                    vector<LevelGenerate::PlateIdAndLayerCnt> tres(capArr.size()) ;
                    for(int it = 0 ; it < capArr.size(); ++ it ) {
                        tres[it]._plateId = pidArr[it] ;
                        tres[it]._layerCnt = lyrArr[it] ;
                    }
                    possibleResults.push_back(tres) ;
                    
                }else if( difficulty==FILLGLOBALCONFIG_DIFFCULTY_HARD2 ) {
                    //全部3层
                    vector<int> pidArr ;
                    vector<int> capArr ;
                    vector<int> lyrArr ;
                    for(int it=0;it<ipbig;++it) { pidArr.push_back(bigPlate->_id);capArr.push_back(bigPlate->_bigJewCap*4); lyrArr.push_back(3); }
                    for(int it=0;it<ipmid;++it) { pidArr.push_back(midPlate->_id);capArr.push_back(midPlate->_bigJewCap*4); lyrArr.push_back(3); }
                    for(int it=0;it<ipsml;++it) { pidArr.push_back(smlPlate->_id);capArr.push_back(smlPlate->_bigJewCap*4); lyrArr.push_back(3); }
                    bool lyrOk = isJustFilledAll2(capArr, lyrArr, totEquvSmallJewelCnt) ;
                    if(!lyrOk) continue;
                    //保存结果
                    vector<LevelGenerate::PlateIdAndLayerCnt> tres(capArr.size()) ;
                    for(int it = 0 ; it < capArr.size(); ++ it ) {
                        tres[it]._plateId = pidArr[it] ;
                        tres[it]._layerCnt = lyrArr[it] ;
                    }
                    possibleResults.push_back(tres) ;
                }else{
                    //50% 2层， 50% 3层
                    vector<int> pidArr ;
                    vector<int> capArr ;
                    vector<int> lyrArr ;
                    for(int it=0;it<ipbig;++it) { pidArr.push_back(bigPlate->_id);capArr.push_back(bigPlate->_bigJewCap*4); lyrArr.push_back((rand()%2==0)?2:3); }
                    for(int it=0;it<ipmid;++it) { pidArr.push_back(midPlate->_id);capArr.push_back(midPlate->_bigJewCap*4); lyrArr.push_back((rand()%2==0)?2:3); }
                    for(int it=0;it<ipsml;++it) { pidArr.push_back(smlPlate->_id);capArr.push_back(smlPlate->_bigJewCap*4); lyrArr.push_back((rand()%2==0)?2:3); }
                    bool lyrOk = isJustFilledAll2(capArr, lyrArr, totEquvSmallJewelCnt) ;
                    if(!lyrOk) continue;
                    //保存结果
                    vector<LevelGenerate::PlateIdAndLayerCnt> tres(capArr.size()) ;
                    for(int it = 0 ; it < capArr.size(); ++ it ) {
                        tres[it]._plateId = pidArr[it] ;
                        tres[it]._layerCnt = lyrArr[it] ;
                    }
                    possibleResults.push_back(tres) ;
                }
            }
        }
    }
    //随机挑选一个结果返回
    if( possibleResults.size()> 0 ) {
        int randindex = rand() % possibleResults.size();
        results = possibleResults[randindex] ;
    }else {
        results = firstAvailablePlateComb ;
    }
    return results ;
}

//考虑可移动关卡的条件
vector<LevelGenerate::PlateIdAndLayerCnt> LevelGenerate::generatePlateTypeAndLayerCnts2(const bool isMovable,const int difficulty,const int totEquvSmallJewelCnt)
{
    //移动关卡相当于多了一个 大盘子，整个关卡最多可以达到10个大盘子
    //如果是移动关卡，那么至少需要保证如下等价小盘子数量，如果减少层数仍然不能满足那么就有几个盘子输出几个
    const int MAX_LG_PLATE_CNT = 9 + (isMovable?1:0) ;
    const int MAX_SM_PLATE_CNT = MAX_LG_PLATE_CNT*4 ;
    const int MAX_SM_JEWEL_CNT_PER_LAYER = MAX_LG_PLATE_CNT * 24 ;
    
    const int minEquaSmPlateCntForMovable = 16 ; //
    const int smPlateEquaSmJewelCnt = 6 ;// 小盘子装1.5个大，3个中，6个小
    
    //一个关卡最多出现大、中、小盘子个数
    int bigPlateMaxCnt = 9  ;// 1个大盘子=2两个中盘子=4个小盘子
    if( isMovable ) {
        bigPlateMaxCnt = 10 ;
    }
    int midPlateMaxCnt = bigPlateMaxCnt * 2 ;
    int smlPlateMaxCnt = bigPlateMaxCnt * 2 ;
    
    
    vector<LevelGenerate::PlateIdAndLayerCnt> results ;
    
    FillGlobalConfig* fgc = FillGlobalConfig::getInstance() ;
    FillGlobalConfig::PlateItem* bigPlate = fgc->getPlateItemBySzNIndex(FILLGLOBALCONFIG_PLATESIZE_LG, 0) ;
    FillGlobalConfig::PlateItem* midPlate = fgc->getPlateItemBySzNIndex(FILLGLOBALCONFIG_PLATESIZE_MD, 0) ;
    FillGlobalConfig::PlateItem* smlPlate = fgc->getPlateItemBySzNIndex(FILLGLOBALCONFIG_PLATESIZE_SM, 0) ;
    vector<FillGlobalConfig::PlateItem*> usedPlates = {bigPlate,midPlate,smlPlate} ;
    
    int equvSmPlateCnt = ceil( totEquvSmallJewelCnt * 1.0 / 6) ; // 本款需要多少个一层小盘子的总数量
    int layerCnt0 = 1 ;//盘子层数下限
    int layerCnt1 = 1 ;//盘子层数上限
    
    //计算可能的层取值范围
    bool forceToFitMovable = false ;
    if( isMovable ) {
        if( equvSmPlateCnt <= minEquaSmPlateCntForMovable ) {
            //不足移动关卡所需最小的等效小盘子个数，那么直接组合盘子即可。
            layerCnt0 = 1 ;
            layerCnt1 = 1 ;
            forceToFitMovable = false ;
        }else
        {
            //10个大盘子，6个大宝石，等效于每层最多放置 10*6*4=240个小宝石
            layerCnt0 = fmax(1 , totEquvSmallJewelCnt / MAX_SM_JEWEL_CNT_PER_LAYER ) ;
            if( layerCnt0<3 ) layerCnt1 = 3 ;
            else layerCnt1 = layerCnt0 + 1 ;
            forceToFitMovable = true ;
        }
    }else {
        layerCnt0 = fmax(1 , totEquvSmallJewelCnt / MAX_SM_JEWEL_CNT_PER_LAYER ) ;
        if( layerCnt0<3 ) layerCnt1 = 3 ;
        else layerCnt1 = layerCnt0 + 1 ;
        forceToFitMovable = false ;
    }
    
    int bigPlateCnt0 = totEquvSmallJewelCnt * 1.0 / layerCnt1 / 24 ; //大盘子最少需要数量
    int bigPlateCnt1 = totEquvSmallJewelCnt * 1.0 / layerCnt0 / 24 + 1; //大盘子最多需要数量
    int midPlateCnt0 = bigPlateCnt0*2 ;
    int midPlateCnt1 = bigPlateCnt1*2 ;
    int smlPlateCnt0 = bigPlateCnt0*4 ;
    int smlPlateCnt1 = bigPlateCnt1*4 ;
    
    bigPlateCnt1 = fmin( bigPlateMaxCnt ,bigPlateCnt1 ) ;
    midPlateCnt1 = fmin( midPlateMaxCnt ,midPlateCnt1 ) ;
    smlPlateCnt1 = fmin( smlPlateMaxCnt ,smlPlateCnt1 ) ;
    
    bool findFirstAvailableComb = false ;//第一个完全放入宝石的组合，用于当不满足任何条件时，至少返回一个可装入全部宝石的默认方案
    vector<vector<LevelGenerate::PlateIdAndLayerCnt>> possibleResults ;//满足全部百分比要求的组合
    vector<LevelGenerate::PlateIdAndLayerCnt> firstAvailablePlateComb ;//第一个满足全部宝石填充的组合，如果需要移动还要考虑最小移动盘子个数的条件
    int firstAvailableLyrCnt = 0 ;
    
    //难度对盘子数量的限制                                 普通               难              极难
    vector< vector<float> > hardPlateCntPercent0 = { {0.3,0.3,0.0}, {0.2,0.4,0.0}, {0.1,0.5,0.0} } ;
    vector< vector<float> > hardPlateCntPercent1 = { {0.7,0.7,0.0}, {0.6,0.8,0.1}, {0.5,0.9,0.1} } ;
    
    //穷举全部盘子和层的组合找到符合条件的组合
    for(int ibig = 0; ibig <= bigPlateCnt1; ++ ibig ) {
        for(int imid = 0; imid <= midPlateCnt1 ; ++ imid ) {
            for(int isml = 0 ; isml <= smlPlateCnt1; ++ isml ) {
                int equvSmPlateCnt1 = isml+imid*2+ibig*4 ;
                if( equvSmPlateCnt1==0 || equvSmPlateCnt1 > MAX_SM_PLATE_CNT ) continue ;
                if( equvSmPlateCnt1 < smlPlateCnt0 ) continue ;
                if( isMovable && forceToFitMovable ) if( equvSmPlateCnt1<minEquaSmPlateCntForMovable ) continue ;
                
                float bigPlateCntPercent = ibig*4.0 / equvSmPlateCnt1 ;
                float midPlateCntPercent = imid*2.0 / equvSmPlateCnt1 ;
                float smlPlateCntPercent = isml*1.0 / equvSmPlateCnt1 ;
                vector<float> percentArr = {bigPlateCntPercent,midPlateCntPercent,smlPlateCntPercent} ;
                //判断每个盘子百分比是否满足难度要求
                bool percentOk = true ;
                for(int iplatetype=0;iplatetype<percentArr.size();++iplatetype) {
                    if( hardPlateCntPercent0[difficulty][iplatetype]>percentArr[iplatetype] || hardPlateCntPercent1[difficulty][iplatetype]<percentArr[iplatetype]  )
                        percentOk=false;
                }
                if( findFirstAvailableComb == true ){
                    //至少有一个装下宝石的方案了
                    if( !percentOk ) continue ;//盘子百分比不符合要求，跳过
                }
                
                if( findFirstAvailableComb==false || (findFirstAvailableComb && firstAvailableLyrCnt>3 )  ) {
                    //保证至少有一个可以满足宝石的盘子组合，优先保存总层数大于3的情况
                    //当前盘子组合下最小满足的层数
                    int upperLyrCnt = ceil( totEquvSmallJewelCnt * 1.0 / (equvSmPlateCnt1*6) ) ;
                    bool upperLyrCntOk = true ;
                    if( findFirstAvailableComb ) {
                        if( upperLyrCnt >= firstAvailableLyrCnt ) {
                            upperLyrCntOk = false ;
                        }
                    }
                    vector<int> pidArr ;
                    vector<int> capArr ;
                    vector<int> lyrArr ;
                    for(int it=0;it<ibig;++it) { pidArr.push_back(bigPlate->_id);capArr.push_back(bigPlate->_bigJewCap*4); lyrArr.push_back(upperLyrCnt); }
                    for(int it=0;it<imid;++it) { pidArr.push_back(midPlate->_id);capArr.push_back(midPlate->_bigJewCap*4); lyrArr.push_back(upperLyrCnt); }
                    for(int it=0;it<isml;++it) { pidArr.push_back(smlPlate->_id);capArr.push_back(smlPlate->_bigJewCap*4); lyrArr.push_back(upperLyrCnt); }
                    bool lyrOk = isJustFilledAll2(capArr, lyrArr, totEquvSmallJewelCnt) ;
                    if( lyrOk==false && upperLyrCnt>1 ) {
                        for(int it=0;it<lyrArr.size();++it ) {
                            lyrArr[it] -= 1 ;
                            lyrOk = isJustFilledAll2(capArr, lyrArr, totEquvSmallJewelCnt) ;
                            if( lyrOk ) break ;
                        }
                    }
                    if( lyrOk && upperLyrCntOk ){
                        findFirstAvailableComb = true ;
                        firstAvailableLyrCnt = upperLyrCnt ;
                        //保存结果
                        firstAvailablePlateComb.resize(capArr.size());
                        for(int it = 0 ; it < capArr.size(); ++ it ) {
                            firstAvailablePlateComb[it]._plateId = pidArr[it] ;
                            firstAvailablePlateComb[it]._layerCnt = lyrArr[it] ;
                        }
                    }
                }
                //计算每个类型的层数
                if( difficulty== FILLGLOBALCONFIG_DIFFCULTY_NORM ) {
                    //全部两层
                    vector<int> pidArr ;
                    vector<int> capArr ;
                    vector<int> lyrArr ;
                    for(int it=0;it<ibig;++it) { pidArr.push_back(bigPlate->_id);capArr.push_back(bigPlate->_bigJewCap*4); lyrArr.push_back(2); }
                    for(int it=0;it<imid;++it) { pidArr.push_back(midPlate->_id);capArr.push_back(midPlate->_bigJewCap*4); lyrArr.push_back(2); }
                    for(int it=0;it<isml;++it) { pidArr.push_back(smlPlate->_id);capArr.push_back(smlPlate->_bigJewCap*4); lyrArr.push_back(2); }
                    bool lyrOk = isJustFilledAll2(capArr, lyrArr, totEquvSmallJewelCnt) ;
                    if(!lyrOk) continue;
                    
                    //保存结果
                    vector<LevelGenerate::PlateIdAndLayerCnt> tres(capArr.size()) ;
                    for(int it = 0 ; it < capArr.size(); ++ it ) {
                        tres[it]._plateId = pidArr[it] ;
                        tres[it]._layerCnt = lyrArr[it] ;
                    }
                    possibleResults.push_back(tres) ;
                    
                }else if( difficulty==FILLGLOBALCONFIG_DIFFCULTY_HARD2 ) {
                    //全部3层
                    vector<int> pidArr ;
                    vector<int> capArr ;
                    vector<int> lyrArr ;
                    for(int it=0;it<ibig;++it) { pidArr.push_back(bigPlate->_id);capArr.push_back(bigPlate->_bigJewCap*4); lyrArr.push_back(3); }
                    for(int it=0;it<imid;++it) { pidArr.push_back(midPlate->_id);capArr.push_back(midPlate->_bigJewCap*4); lyrArr.push_back(3); }
                    for(int it=0;it<isml;++it) { pidArr.push_back(smlPlate->_id);capArr.push_back(smlPlate->_bigJewCap*4); lyrArr.push_back(3); }
                    //cout<<"debug big "<<ibig<<" mid "<<imid<<" sml "<<isml<<endl;
                    bool lyrOk = isJustFilledAll2(capArr, lyrArr, totEquvSmallJewelCnt) ;
                    if(!lyrOk) continue;
                    //保存结果
                    vector<LevelGenerate::PlateIdAndLayerCnt> tres(capArr.size()) ;
                    for(int it = 0 ; it < capArr.size(); ++ it ) {
                        tres[it]._plateId = pidArr[it] ;
                        tres[it]._layerCnt = lyrArr[it] ;
                    }
                    possibleResults.push_back(tres) ;
                }else{
                    //50% 2层， 50% 3层
                    vector<int> pidArr ;
                    vector<int> capArr ;
                    vector<int> lyrArr ;
                    for(int it=0;it<ibig;++it) { pidArr.push_back(bigPlate->_id);capArr.push_back(bigPlate->_bigJewCap*4); lyrArr.push_back((rand()%2==0)?2:3); }
                    for(int it=0;it<imid;++it) { pidArr.push_back(midPlate->_id);capArr.push_back(midPlate->_bigJewCap*4); lyrArr.push_back((rand()%2==0)?2:3); }
                    for(int it=0;it<isml;++it) { pidArr.push_back(smlPlate->_id);capArr.push_back(smlPlate->_bigJewCap*4); lyrArr.push_back((rand()%2==0)?2:3); }
                    bool lyrOk = isJustFilledAll2(capArr, lyrArr, totEquvSmallJewelCnt) ;
                    if(!lyrOk) continue;
                    //保存结果
                    vector<LevelGenerate::PlateIdAndLayerCnt> tres(capArr.size()) ;
                    for(int it = 0 ; it < capArr.size(); ++ it ) {
                        tres[it]._plateId = pidArr[it] ;
                        tres[it]._layerCnt = lyrArr[it] ;
                    }
                    possibleResults.push_back(tres) ;
                }
                
            }
        }
    }
    //随机挑选一个结果返回
    if( possibleResults.size()> 0 ) {
        int randindex = rand() % possibleResults.size();
        results = possibleResults[randindex] ;
    }else {
        results = firstAvailablePlateComb ;
    }
    return results ;
    
}


//随机排序数组索引值
vector<int> LevelGenerate::randIndices(const int count0 ) {
    int count = count0 ;
    vector<int> indices ;
    unordered_map<int, bool> dict ;
    while( count > 0 ) {
        int r = rand()%count0;
        if( dict.find(r) == dict.end() ) {
            dict[r] = true ;
            indices.push_back(r) ;
            count-- ;
        }
    }
    return indices;
}
 

bool LevelGenerate::isJustFilledAll2(
                      const vector<int>& plateCaps,//每个盘子的容量
                      const vector<int> eachPlateLyrCnt,//对应盘子的层数
                      const int totSmlJewCnt )
{
    assert(plateCaps.size()>0);
    assert(plateCaps.size()==eachPlateLyrCnt.size());
    int fillcnt1 = 0;
    for(int ip = 0 ;ip<plateCaps.size();++ip ) {
        fillcnt1 += plateCaps[ip] * eachPlateLyrCnt[ip] ;
    }
    if( fillcnt1 < totSmlJewCnt ) return false ;
    if( fillcnt1 == totSmlJewCnt ) return true ;
    for(int ip = 0 ; ip < plateCaps.size();++ip ) {
        int fillcnt2 = fillcnt1 - plateCaps[ip] ;
        if( fillcnt2 < totSmlJewCnt ) {
            return true ;
        }
    }
    return false ;
}

unordered_map<int, int> LevelGenerate::randPickJewels( const int needEquvSmlCnt,const float solvedPercent, unordered_map<int,tuple<int,int>>& jewStorages )
{
    int needEquvSmlCnt2 = needEquvSmlCnt ;
    int storageEquvSmlCnt = 0 ;
    int storageJewTypeCnt = jewStorages.size() ;
    for(auto it=jewStorages.begin();it!=jewStorages.end();++it) storageEquvSmlCnt+= std::get<1>(it->second)*jewSz2SmlCnt(std::get<0>(it->second)) ;
    unordered_map<int, int> res ;
    const float solPer = fmax(0.0,fmin(solvedPercent,1.0f)) ;
    
    //首先尝试可解的百分比部分
    int solEqSmGrpCnt = needEquvSmlCnt*solPer/3 ;
    // 随机尝试solEqSmGrpCnt*2 次取宝石，每次取一组。
    int loopCnt=solEqSmGrpCnt*storageJewTypeCnt*10;//随机迭代数量加大10倍，避免有始终选不到的情况
    while( solEqSmGrpCnt> 0 && storageEquvSmlCnt>0 && loopCnt>0) {
        int randJewI = rand()%storageJewTypeCnt ;
        auto itjew = jewStorages.begin() ;
        std::advance(itjew, randJewI) ;
        int jid = itjew->first ;
        int storage1 = std::get<1>( itjew->second ) ;
        int oneGrpEqSmGrpCnt = jewSz2SmlCnt( std::get<0>(itjew->second) ) ;
        if( storage1>=3 && oneGrpEqSmGrpCnt<=solEqSmGrpCnt ) {
            //库存有，且满足所需可解组数
            std::get<1>(itjew->second)-=3 ;
            solEqSmGrpCnt -= oneGrpEqSmGrpCnt ;
            storageEquvSmlCnt -= oneGrpEqSmGrpCnt*3 ;
            needEquvSmlCnt2   -= oneGrpEqSmGrpCnt*3 ; //本次所需的剩余等效小宝石个数
            res[jid] += 3 ;
        }
        --loopCnt ;
    }
    
    //尝试剩余百分比和上一步剩余没有符合条件的个数
    loopCnt = needEquvSmlCnt2*storageJewTypeCnt ;
    int jindex = 0 ;
    while( loopCnt>0 && needEquvSmlCnt2> 0 && storageEquvSmlCnt>0 ) {
        auto itjew = jewStorages.begin() ;
        std::advance(itjew, jindex) ;
        int jid = itjew->first;
        int sz =  std::get<0>(itjew->second) ;
        int stor = std::get<1>(itjew->second) ;
        int eqsmCnt = jewSz2SmlCnt(sz) ;
        if( stor>0 && eqsmCnt <= needEquvSmlCnt2 ) {
            std::get<1>(itjew->second)-=1 ;
            needEquvSmlCnt2-=eqsmCnt ;
            storageEquvSmlCnt-=eqsmCnt ;
            res[jid] += 1 ;
        }
        ++jindex ; if(jindex>=storageJewTypeCnt) jindex=0;//循环取之，直到本层所需全部取完
        --loopCnt;
    }
    return res ;
}

int LevelGenerate::jewSz2SmlCnt(int sz)
{
    switch (sz) {
        case FILLGLOBALCONFIG_JEWELSIZE_LG:
            return 4;break;
        case FILLGLOBALCONFIG_JEWELSIZE_MD:
            return 2;break;
        default:
            return 1;break;
    }
    return 1;
}

vector<FillResult> LevelGenerate::fillPlateOneLayer(RandomGridFiller& filler,const int plateId, unordered_map<int,int>& jewStoragesForUse )
{
    auto fgc = FillGlobalConfig::getInstance() ;
    vector<RandomGridFiller::JewelBox> jewBoxArray ;
    FillGlobalConfig::PlateItem* pl = FillGlobalConfig::getInstance()->getPlateItemById(plateId) ;
    int plateEqSmCap = pl->_bigJewCap*4 ;
    int jewTypeCnt = jewStoragesForUse.size() ;
    int eqSmStorageCnt = 0 ;
    for(auto it = jewStoragesForUse.begin();it!=jewStoragesForUse.end();++it) {
        int jewEqSmCnt = jewSz2SmlCnt( fgc->getJewelItemById(it->first)->_size );
        eqSmStorageCnt+=it->second*jewEqSmCnt ;
    }
    static int s_debug_cnt = 0;
    //cout<<"debug "<< s_debug_cnt << " storage eqsm count "<<eqSmStorageCnt<< " currplate cap "<< plateEqSmCap <<endl;
    unordered_map<int, int> jewForPlateMap ;// <jewId,Cnt>
    int loopCnt = plateEqSmCap*jewTypeCnt*4;// 随机数量多给4倍
    while(plateEqSmCap>0 && eqSmStorageCnt>0 && loopCnt>0 ) {
        int radv = rand() % jewTypeCnt ;
        auto it = jewStoragesForUse.begin() ;
        std::advance(it, radv) ;
        int jewEqSmCnt = jewSz2SmlCnt( fgc->getJewelItemById(it->first)->_size );
        if( it->second>0 ) {
            if( jewEqSmCnt <= plateEqSmCap ) {
                plateEqSmCap -= jewEqSmCnt ;
                it->second -=1 ;
                eqSmStorageCnt -= jewEqSmCnt ;
                jewForPlateMap[it->first] += 1 ;
                if( it->second== 0 ) {
                    jewStoragesForUse.erase(it) ;
                    jewTypeCnt-- ;
                }
            }
        }else{
            jewStoragesForUse.erase(it) ;
            jewTypeCnt-- ;
        }
        --loopCnt ;
    }
    
    //cout<<"debug "<< s_debug_cnt ++ <<" storage eqsm count "<<eqSmStorageCnt<< " currplate cap "<< plateEqSmCap <<endl;
    
    for(auto it = jewForPlateMap.begin();it!=jewForPlateMap.end();++it) {
        RandomGridFiller::JewelBox jbox ;
        jbox._cnt = it->second ;
        jbox._jewelTypeId = it->first ;
        jbox._width = fgc->getJewelItemById(it->first)->_bbWidth ;
        jbox._height = fgc->getJewelItemById(it->first)->_bbHeight ;
        jewBoxArray.push_back(jbox) ;
    }
    
    vector<FillResult> fillresults ;
    filler.fill(jewBoxArray, pl->_blx, pl->_bly, pl->_trx, pl->_try, fillresults) ;
    return fillresults ;
}


unordered_map<int, int> LevelGenerate::findUnfilledInStorages( unordered_map<int,tuple<int,int>>& jewStorages)
{
    unordered_map<int, int> res ;
    for(auto itj = jewStorages.begin();itj!=jewStorages.end();++itj) {
        int stor = std::get<1>(itj->second) ;
        int jid = itj->first ;
        if( stor>0 ) {
            res[jid] = stor ;
            std::get<1>(itj->second) = 0 ;
        }
    }
    return res ;
}


void LevelGenerate::regroupPlateLyrFillResults( vector<tuple<int,int,vector<FillResult>>>& pidlyrFillArray, vector<tuple<int,vector<vector<FillResult>>>>& results )
{
    int currLayer = 1 ;//从底层到顶层构建结果数据结构
    int num = pidlyrFillArray.size() ;
    int nloop = num ;
    while( nloop > 0 ) {
        //cout<<"regroup for layer "<<currLayer<<endl;
        for( auto itlyr = pidlyrFillArray.begin(); itlyr!=pidlyrFillArray.end(); ++ itlyr ) {
            int pid = std::get<0>( *itlyr ) ;
            int lyr = std::get<1>( *itlyr ) ;
            vector<FillResult>& frs = std::get<2>(*itlyr) ;
            if(pid>=0) {
                if( lyr==currLayer ) {
                    if( lyr==1 ) {
                        vector<vector<FillResult>> frArr = {frs} ;
                        results.push_back( {pid, frArr } ) ;
                        num-- ;
                        std::get<0>( *itlyr ) = -1 ;
                    }else {
                        for(auto itr = results.begin();itr!=results.end();++itr ) {
                            int pidr = std::get<0>(*itr) ;
                            vector<vector<FillResult>>& frArr = std::get<1>(*itr) ;
                            if( pidr == pid && frArr.size()==currLayer-1 ) {
                                frArr.push_back(frs);
                                num-- ;
                                std::get<0>( *itlyr ) = -1 ;
                                break ;
                            }
                        }
                    }
                }
            }
        }
        currLayer++ ;
        if( num==0 ) break ;
        nloop--;
    }
    //cout<<"last plate lyr num "<<num<<endl;
}



void LevelGenerate::placePlates(const bool movable, const vector<int>& plateIdArr, vector<ContourData::Point>& resultPlateCenterPointArr )
{
    GridPositionTool gpt ;
    vector<vector<int>> resPosis ;
    gpt.solve(movable, plateIdArr, resPosis) ;
    for(int ip=0;ip<resPosis.size();++ip ) {
        resultPlateCenterPointArr.push_back( { (float)resPosis[ip][0] , (float)resPosis[ip][1]} ) ;
    }
}