1 /* 2 Bastet - tetris clone with embedded bastard block chooser 3 (c) 2005-2009 Federico Poloni <f.polonithirtyseven@sns.it> minus 37 4 5 This program is free software: you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation, either version 3 of the License, or 8 (at your option) any later version. 9 10 This program is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program. If not, see <http://www.gnu.org/licenses/>. 17 */ 18 19 #include "BastetBlockChooser.hpp" 20 #include "Block.hpp" 21 22 #include <boost/foreach.hpp> 23 #include <cstdlib> 24 #include <algorithm> 25 26 //debug 27 #include <fstream> 28 #include <iostream> 29 #include <iomanip> 30 #include <curses.h> 31 32 using namespace std; 33 using namespace boost; 34 35 namespace Bastet{ Evaluate(const Well * w,int extralines)36 long Evaluate(const Well *w, int extralines){ 37 //computes the score for a final position reached in the well + "extralines" lines cleared 38 //high=good for the player 39 40 //lines 41 long score=100000000*extralines; 42 43 //adds a bonus for each "free" dot above the occupied blocks profile 44 std::bitset<WellWidth> occupied; 45 occupied.reset(); 46 BOOST_FOREACH(WellLine l,w->_well){ 47 occupied = occupied & l; 48 score+=10000*(WellWidth-occupied.count()); 49 } 50 51 //adds a bonus for lower max height of the occupied blocks 52 int height=RealWellHeight; 53 BOOST_FOREACH(WellLine l, w->_well){ 54 if(l.any()) break; 55 height--; 56 } 57 score+= 1000 * (RealWellHeight-height); 58 return score; 59 } 60 BastetBlockChooser()61 BastetBlockChooser::BastetBlockChooser(){ 62 } 63 ~BastetBlockChooser()64 BastetBlockChooser::~BastetBlockChooser(){ 65 66 } 67 GetStartingQueue()68 Queue BastetBlockChooser::GetStartingQueue(){ 69 Queue q; 70 //The first block is always I,J,L,T (cfr. Tetris guidelines, Bastet is a gentleman and chooses the most favorable start for the user). 71 BlockType first; 72 switch(random()%4){ 73 case 0: 74 first=I;break; 75 case 1: 76 first=J;break; 77 case 2: 78 first=L;break; 79 case 3: 80 first=T;break; 81 } 82 q.push_back(first); 83 q.push_back(BlockType(random()%nBlockTypes)); 84 return q; 85 } 86 ComputeMainScores(const Well * well,BlockType currentBlock)87 boost::array<long,nBlockTypes> BastetBlockChooser::ComputeMainScores(const Well *well, BlockType currentBlock){ 88 RecursiveVisitor visitor; 89 Searcher(currentBlock,well,BlockPosition(),&visitor); 90 return visitor.GetScores(); 91 } 92 93 GetNext(const Well * well,const Queue & q)94 BlockType BastetBlockChooser::GetNext(const Well *well, const Queue &q){ 95 boost::array<long,nBlockTypes> mainScores=ComputeMainScores(well,q.front()); 96 boost::array<long,nBlockTypes> finalScores=mainScores; 97 98 //perturbes scores to randomize tie handling 99 BOOST_FOREACH(long &i, finalScores) 100 i+=(random()%100); 101 102 //prints the final scores, for debugging convenience 103 for(size_t i=0;i<nBlockTypes;++i){ 104 //mvprintw(i,1,"%c: %d",GetChar(BlockType(i)),finalScores[i]); 105 } 106 107 //the mainScores alone would give rise to many repeated blocks (e.g., in the case in which only one type of block does not let you clear a line, you keep getting that). This is bad, since it would break the "plausibility" of the sequence you get. We need a correction. 108 109 boost::array<long,nBlockTypes> temp(finalScores); 110 sort(temp.begin(),temp.end()); 111 112 //always returns the worst block if it's different from the last one 113 int worstblock=find(finalScores.begin(),finalScores.end(),temp[0])-finalScores.begin(); 114 if(BlockType(worstblock) != q.front()) return BlockType(worstblock); 115 116 //otherwise, returns the pos-th block, where pos is random 117 static const boost::array<int,nBlockTypes> blockPercentages={{80, 92, 98, 100, 100, 100, 100}}; 118 int pos=find_if(blockPercentages.begin(),blockPercentages.end(),bind2nd(greater_equal<int>(),random()%100)) - blockPercentages.begin(); 119 assert(pos>=0 && pos<nBlockTypes); 120 121 int chosenBlock=find(finalScores.begin(),finalScores.end(),temp[pos])-finalScores.begin(); 122 return BlockType(chosenBlock); 123 124 //return BlockType(min_element(finalScores.begin(),finalScores.end())-finalScores.begin()); 125 //return BlockType(random()%7); 126 } 127 Searcher(BlockType b,const Well * well,Vertex v,WellVisitor * visitor)128 Searcher::Searcher(BlockType b, const Well *well, Vertex v, WellVisitor *visitor):_block(b),_well(well),_visitor(visitor){ 129 DFSVisit(v); 130 } 131 DFSVisit(Vertex v)132 void Searcher::DFSVisit(Vertex v){ 133 if(_visited.insert(v).second==false) return; //already visited 134 135 for(int i=0;i<5;++i){ 136 Vertex v2(v); 137 if(v2.MoveIfPossible(Movement(i),_block,_well)) 138 DFSVisit(v2); 139 else{ 140 if(Movement(i)==Down) //block may lock here 141 _visitor->Visit(_block,_well,v); 142 } 143 } 144 } 145 BestScoreVisitor(int bonusLines)146 BestScoreVisitor::BestScoreVisitor(int bonusLines):_score(GameOverScore),_bonusLines(bonusLines){}; ~BestScoreVisitor()147 BestScoreVisitor::~BestScoreVisitor(){}; Visit(BlockType b,const Well * w,Vertex v)148 void BestScoreVisitor::Visit(BlockType b, const Well *w, Vertex v){ 149 Well w2(*w); //copy 150 try{ 151 int linescleared=w2.LockAndClearLines(b,v); 152 long thisscore=Evaluate(&w2,linescleared+_bonusLines); 153 _score=max(_score,thisscore); 154 }catch(const GameOver &go){} 155 } 156 RecursiveVisitor()157 RecursiveVisitor::RecursiveVisitor(){_scores.assign(GameOverScore);} ~RecursiveVisitor()158 RecursiveVisitor::~RecursiveVisitor(){} Visit(BlockType b,const Well * w,Vertex v)159 void RecursiveVisitor::Visit(BlockType b, const Well *w, Vertex v){ 160 Well w2(*w); //copy 161 try{ 162 int linescleared=w2.LockAndClearLines(b,v); //may throw GO 163 for(size_t i=0;i<nBlockTypes;++i){ 164 try{ 165 BestScoreVisitor visitor(linescleared); 166 BlockPosition p; 167 if(!p.IsValid(BlockType(i),&w2)) throw(GameOver()); 168 Searcher searcher(BlockType(i),&w2,p,&visitor); 169 _scores[i]=max(_scores[i],visitor.GetScore()); 170 } catch(const GameOver &go){} 171 } 172 } catch(const GameOver &go){} //catches the exception which might be thrown by LockAndClearLines 173 } 174 NoPreviewBlockChooser()175 NoPreviewBlockChooser::NoPreviewBlockChooser(){}; ~NoPreviewBlockChooser()176 NoPreviewBlockChooser::~NoPreviewBlockChooser(){}; GetStartingQueue()177 Queue NoPreviewBlockChooser::GetStartingQueue(){ 178 Queue q; 179 //The first block is always I,J,L,T (cfr. Tetris guidelines, Bastet is a gentleman and chooses the most favorable start for the user). 180 BlockType first; 181 switch(random()%4){ 182 case 0: 183 first=I;break; 184 case 1: 185 first=J;break; 186 case 2: 187 first=L;break; 188 case 3: 189 first=T;break; 190 } 191 q.push_back(first); 192 return q; 193 } 194 GetNext(const Well * well,const Queue & q)195 BlockType NoPreviewBlockChooser::GetNext(const Well *well, const Queue &q){ 196 assert(q.empty()); 197 boost::array<long,nBlockTypes> finalScores; 198 for(size_t t=0;t<nBlockTypes;++t){ 199 BestScoreVisitor v; 200 Searcher searcher(BlockType(t),well,BlockPosition(),&v); 201 finalScores[t]=v.GetScore(); 202 } 203 204 //perturbes scores to randomize tie handling 205 BOOST_FOREACH(long &i, finalScores) 206 i+=(random()%100); 207 208 //sorts 209 boost::array<long,nBlockTypes> temp(finalScores); 210 sort(temp.begin(),temp.end()); 211 212 //returns the pos-th block, where pos is random 213 static const boost::array<int,nBlockTypes> blockPercentages={{80, 92, 98, 100, 100, 100, 100}}; 214 int pos=find_if(blockPercentages.begin(),blockPercentages.end(),bind2nd(greater_equal<int>(),random()%100)) - blockPercentages.begin(); 215 assert(pos>=0 && pos<nBlockTypes); 216 217 int chosenBlock=find(finalScores.begin(),finalScores.end(),temp[pos])-finalScores.begin(); 218 return BlockType(chosenBlock); 219 220 } 221 222 } 223