Main   Namespaces   Classes   Hierarchy   Annotated   Files   Compound   Global   Pages  

VCPattern.cpp

Go to the documentation of this file.
00001 //----------------------------------------------------------------------------
00002 /** @file VCPattern.cpp
00003  */
00004 //----------------------------------------------------------------------------
00005 
00006 #include "BitsetIterator.hpp"
00007 #include "BoardUtils.hpp"
00008 #include "VCPattern.hpp"
00009 #include "StoneBoard.hpp"
00010 
00011 #include <boost/filesystem/path.hpp>
00012 
00013 using namespace benzene;
00014 
00015 //----------------------------------------------------------------------------
00016 
00017 /** Tools for constructing patterns. */
00018 namespace
00019 {
00020 
00021 /** The start/end of a ladder pattern. */
00022 struct BuilderPattern
00023 {
00024     bitset_t black, empty;
00025     HexPoint endpoint;
00026     int height;
00027     
00028     BuilderPattern(const bitset_t& b, const bitset_t& em, HexPoint e, int h)
00029         : black(b), empty(em), endpoint(e), height(h)
00030     { };
00031 };
00032 
00033 /** Shifts a BuilderPattern in the given direction. Returns true
00034     if pattern remains inside the board, false otherwise. */
00035 bool ShiftBuilderPattern(BuilderPattern& pat, HexDirection dir,
00036                          const StoneBoard& brd)
00037 {
00038     bitset_t black, empty, bad;
00039     HexPoint endpoint = BoardUtils::PointInDir(brd.Const(), pat.endpoint, dir);
00040    
00041     if (!BoardUtils::ShiftBitset(brd.Const(), pat.black, dir, black)) 
00042         return false;
00043     if (!BoardUtils::ShiftBitset(brd.Const(), pat.empty, dir, empty)) 
00044         return false;
00045     pat = BuilderPattern(black, empty, endpoint, pat.height);
00046     return true;
00047 }
00048 
00049 //---------------------------------------------------------------------------
00050 
00051 /** Rotates pattern on given board. */
00052 VCPattern RotatePattern(const VCPattern& pat, const StoneBoard& brd)
00053 {
00054     HexPoint endpoint1 = BoardUtils::Rotate(brd.Const(), pat.Endpoint(0));
00055     HexPoint endpoint2 = BoardUtils::Rotate(brd.Const(), pat.Endpoint(1));
00056     bitset_t must = BoardUtils::Rotate(brd.Const(), pat.MustHave());
00057     bitset_t oppt = BoardUtils::Rotate(brd.Const(), pat.NotOpponent());
00058     return VCPattern(endpoint1, endpoint2, must, oppt);
00059 }
00060 
00061 /** Mirrors pattern on given board. */
00062 VCPattern MirrorPattern(const VCPattern& pat, const StoneBoard& brd)
00063 {
00064     HexPoint endpoint1 = BoardUtils::Mirror(brd.Const(), pat.Endpoint(0));
00065     HexPoint endpoint2 = BoardUtils::Mirror(brd.Const(), pat.Endpoint(1));
00066     bitset_t must = BoardUtils::Mirror(brd.Const(), pat.MustHave());
00067     bitset_t oppt = BoardUtils::Mirror(brd.Const(), pat.NotOpponent());
00068     return VCPattern(endpoint1, endpoint2, must, oppt);
00069 }
00070 
00071 /** Applies the reverse-mapping; used to reverse the direction of
00072     ladder vcs. Returns INVALID_POINT if this point would be reversed
00073     off the board. */
00074 HexPoint ReversePoint(HexPoint point, const StoneBoard& brd)
00075 {
00076     if (HexPointUtil::isEdge(point)) 
00077         return point;
00078 
00079     int x, y;
00080     HexPointUtil::pointToCoords(point, x, y);
00081     x = (brd.Width() - 1 - x) + (brd.Height() - 1 - y);
00082     if (x >= brd.Width()) 
00083         return INVALID_POINT;
00084 
00085     return HexPointUtil::coordsToPoint(x, y);
00086 }
00087 
00088 /** Reverses bitset using ReversePoint(). Returns true if all points
00089     were reversed successfully, false otherwise. */
00090 bool ReverseBitset(const bitset_t& bs, const StoneBoard& brd, bitset_t& out)
00091 {
00092     out.reset();
00093     for (BitsetIterator p(bs); p; ++p) {
00094         HexPoint rp = ReversePoint(*p, brd);
00095         if (rp == INVALID_POINT) return false;
00096         out.set(rp);
00097     }
00098     return true;
00099 }
00100 
00101 /** Reverses a pattern situated in the bottom left corner. */
00102 bool ReversePattern(VCPattern& pat, const StoneBoard& brd)
00103 {
00104     do {
00105         bitset_t must, oppt, badp;
00106         if (ReverseBitset(pat.MustHave(), brd, must) 
00107             && ReverseBitset(pat.NotOpponent(), brd, oppt))
00108         {
00109             HexPoint endpoint1 = ReversePoint(pat.Endpoint(0), brd);
00110             HexPoint endpoint2 = ReversePoint(pat.Endpoint(1), brd);
00111             pat = VCPattern(endpoint1, endpoint2, must, oppt);
00112             return true;
00113         }
00114     } while (pat.ShiftPattern(DIR_EAST, brd));
00115 
00116     return false;
00117 }
00118 
00119 //---------------------------------------------------------------------------
00120 
00121 /** Shifts pattern in given direction until it goes off the board. */
00122 void ShiftAndAdd(const VCPattern& pat, HexDirection dir, 
00123                  StoneBoard& brd, std::vector<VCPattern>& out)
00124 {
00125     VCPattern spat(pat);
00126     do {
00127         out.push_back(spat);
00128     } while (spat.ShiftPattern(dir, brd));
00129 }
00130 
00131 /** Shifts pattern in first direction, rotates, then shifts in second
00132     direction. */
00133 void RotateAndShift(const VCPattern& pat, StoneBoard& brd,
00134                     HexDirection d1, HexDirection d2, 
00135                     std::vector<VCPattern>& out)
00136 {
00137     ShiftAndAdd(pat, d1, brd, out);
00138     ShiftAndAdd(RotatePattern(pat, brd), d2, brd, out);
00139 }
00140 
00141 /** Calls RotateAndShift() on the original and mirrored versions of
00142     pattern, then again on the reversed and mirrored-reversed versions
00143     of the pattern. */
00144 void ProcessPattern(const VCPattern& pat, StoneBoard& brd,
00145                     std::vector<VCPattern> out[BLACK_AND_WHITE])
00146 {
00147     RotateAndShift(pat, brd, DIR_EAST, DIR_WEST, out[BLACK]);
00148     RotateAndShift(MirrorPattern(pat, brd), brd, DIR_SOUTH, 
00149                    DIR_NORTH, out[WHITE]);
00150 
00151     VCPattern rpat(pat);
00152     ReversePattern(rpat, brd);
00153     RotateAndShift(rpat, brd, DIR_WEST, DIR_EAST, out[BLACK]);
00154     RotateAndShift(MirrorPattern(rpat, brd), brd, DIR_NORTH, 
00155                    DIR_SOUTH, out[WHITE]);
00156 }
00157 
00158 } // annonymous namespace
00159 
00160 //----------------------------------------------------------------------------
00161 
00162 VCPattern::VCPatternSetMap& VCPattern::GetConstructed(HexColor color)
00163 {
00164     static GlobalData data;
00165     return data.constructed[color];
00166 }
00167 
00168 const VCPatternSet& 
00169 VCPattern::GetPatterns(int width, int height, HexColor color)
00170 {
00171     std::pair<int, int> key = std::make_pair(width, height);
00172 
00173     /** Return an empty list for all non-square boards. */
00174     if (width != height) {
00175         width = 0;
00176         height = 1;
00177         VCPatternSetMap::iterator it = GetConstructed(color).find(key);
00178         if (it == GetConstructed(color).end()) 
00179         {
00180             VCPatternSet empty;
00181             GetConstructed(BLACK)[key] = empty;
00182             GetConstructed(WHITE)[key] = empty;
00183         }
00184     }
00185     else
00186     {
00187         /** @bug The "vc-pattern-file" option is not checked
00188             here. This means that creating a VCPatternSet for board size
00189             (x,y), changing "vc-pattern-file", and then asking for a
00190             pattern set for (x,y) will not cause a re-build.  No one will
00191             want to do this anyway (right?), so it doesn't matter.  If you
00192             really want to do this, add the filename as part of the key
00193             for VCPatternSetMap.
00194         */
00195         VCPatternSetMap::iterator it = GetConstructed(color).find(key);
00196         if (it == GetConstructed(color).end()) 
00197         {
00198             CreatePatterns(width, height);
00199         }
00200     }
00201 
00202     return GetConstructed(color)[key];
00203 }
00204 
00205 void VCPattern::CreatePatterns(int width, int height)
00206 {
00207     LogFine() << "VCPattern::CreatePatterns(" 
00208               << width << ", " << height << ")\n";
00209     
00210 #ifndef ABS_TOP_SRCDIR
00211     #error "ABS_TOP_SRCDIR not defined!"
00212 #endif 
00213 
00214     boost::filesystem::path pp = boost::filesystem::path(ABS_TOP_SRCDIR) 
00215         / "share" / "vc-patterns.txt";
00216     pp.normalize();
00217     std::string file = pp.native_file_string();
00218     LogFine() << "Loading pattern templates from: '" << file << "'\n";
00219     std::ifstream fin(file.c_str());
00220     if (!fin)
00221         throw BenzeneException("Could not open pattern file!\n");
00222 
00223     std::vector<VCPattern> out[BLACK_AND_WHITE];
00224     std::vector<BuilderPattern> start, end;
00225     std::vector<VCPattern> complete;
00226 
00227     int numConstructed = 0;
00228     int numComplete = 0;
00229 
00230     std::string line;
00231     while (true) {
00232         int patternHeight;
00233         std::string tmp, name, type;
00234         std::vector<std::string> carrier;
00235         
00236         std::istringstream is;
00237         if (!getline(fin, line)) break;
00238         if (line == "") break;
00239         
00240         is.str(line);
00241         is >> name;
00242         is >> name;
00243         is.clear();
00244         
00245         getline(fin, line);
00246         is.str(line);
00247         is >> type;
00248         is >> type;
00249         is.clear();
00250 
00251         getline(fin, line);
00252         is.str(line);
00253         is >> tmp;
00254         is >> patternHeight;
00255         is.clear();
00256 
00257         while (true) {
00258             getline(fin, line);
00259             if (line == "") break;
00260             carrier.push_back(line);
00261         }
00262         HexAssert(!carrier.empty());
00263         HexAssert(patternHeight == -1 || patternHeight <= (int)carrier.size());
00264 
00265         // abort if pattern too large for board
00266         if ((int)carrier.size() > height) 
00267             continue;
00268         
00269         int row = height-1;
00270         int numcol = -1;
00271         HexPoint endpoint = SOUTH;
00272         bitset_t black, empty;
00273         bool patternFits = true;
00274         for (int i = static_cast<int>(carrier.size() - 1); i >= 0; --i) {
00275             is.clear();
00276             is.str(carrier[i]);
00277 
00278             std::string sym;
00279             int col = 0;
00280             while (is >> sym) {
00281                 if (col >= width) {
00282                     patternFits = false;
00283                     break;
00284                 }
00285                 HexPoint p = HexPointUtil::coordsToPoint(col, row);
00286                 switch(sym[0]) {
00287                 case '*': empty.set(p); break;
00288                 case 'E': endpoint = p; empty.set(p); break;
00289                 case 'B': black.set(p); break;
00290                 case '.': break;
00291                 default: HexAssert(false);
00292                 }
00293                 col++;
00294             }
00295             if (!patternFits)
00296                 break;
00297             if (numcol == -1) 
00298                 numcol = col;
00299             HexAssert(numcol == col);
00300             row--;
00301         }
00302 
00303         // abort if pattern too large for board 
00304         if (!patternFits)
00305             continue;
00306 
00307         StoneBoard sb(width, height);
00308         sb.StartNewGame();
00309 
00310         if (type == "complete") {
00311             numComplete++;
00312             VCPattern pat(endpoint, SOUTH, black, empty);
00313             complete.push_back(pat);
00314         } else if (type == "start") {
00315             if (endpoint == SOUTH)
00316                 throw BenzeneException("Start pattern with no endpoint!");
00317             start.push_back(BuilderPattern(black, empty, endpoint, 
00318                                            patternHeight));
00319         } else if (type == "end") {
00320             end.push_back(BuilderPattern(black, empty, endpoint, 
00321                                          patternHeight));
00322         }
00323     }
00324     fin.close();
00325 
00326     // build ladder patterns by combining start and end patterns
00327     LogFine() << "Combining start(" << start.size()
00328               << ") and end(" << end.size() << ")...\n";
00329     StoneBoard sb(width, height);
00330     for (std::size_t s=0; s<start.size(); ++s) {
00331         const BuilderPattern& st = start[s];
00332 
00333         for (std::size_t e=0; e<end.size(); ++e) {
00334             const BuilderPattern& en = end[e];
00335             if (en.height < st.height) continue;
00336 
00337             // shift end pattern until it does not hit start pattern
00338             sb.StartNewGame();
00339             BuilderPattern bp(en);
00340             int col=0;
00341             bool onBoard = true;
00342             while (onBoard) {
00343         if (((bp.empty|bp.black) & (st.empty|st.black)).none()) break;
00344                 onBoard = ShiftBuilderPattern(bp, DIR_EAST, sb);
00345                 col++;
00346             }
00347             
00348             // patterns are too big combined to fit on board 
00349             if (!onBoard) continue;
00350 
00351             int startCol = col;
00352             while (onBoard) {
00353                 bitset_t empty = st.empty | bp.empty;
00354                 bitset_t black = st.black | bp.black;
00355                 
00356                 for (int i=startCol; i<col; ++i) {
00357                     for (int j=0; j<st.height; ++j) {
00358                         HexPoint p 
00359                             = HexPointUtil::coordsToPoint(i, height-1-j);
00360                         empty.set(p);
00361                     }
00362                 }
00363                 
00364                 VCPattern pat(st.endpoint, bp.endpoint, black, empty);
00365                 complete.push_back(pat);
00366                 numConstructed++;
00367 
00368                 onBoard = ShiftBuilderPattern(bp, DIR_EAST, sb);
00369                 col++;
00370             }
00371         }
00372     }
00373 
00374     LogFine() << "Constructed " << numConstructed << ".\n" 
00375           << "Parsed " << numComplete << " complete.\n";
00376 
00377     // translate, rotate, and mirror all completed patterns
00378     LogFine() << "Translating, rotating, mirroring...\n";
00379     for (std::size_t i=0; i<complete.size(); ++i)
00380         ProcessPattern(complete[i], sb, out);
00381 
00382     LogFine() << out[BLACK].size() << " total patterns\n";
00383 
00384     GetConstructed(BLACK)[std::make_pair(width, height)] = out[BLACK];
00385     GetConstructed(WHITE)[std::make_pair(width, height)] = out[WHITE];
00386 
00387     LogFine() << "Done.\n";
00388 }
00389 
00390 //----------------------------------------------------------------------------
00391 
00392 VCPattern::VCPattern(HexPoint end1, HexPoint end2, const bitset_t& must_have, 
00393                      const bitset_t& not_oppt)
00394     : m_must_have(must_have), 
00395       m_not_oppt(not_oppt), 
00396       m_end1(end1), 
00397       m_end2(end2)
00398 {
00399 }
00400 
00401 VCPattern::~VCPattern()
00402 {
00403 }
00404 
00405 //----------------------------------------------------------------------------
00406 
00407 bool VCPattern::Matches(HexColor color, const StoneBoard& brd) const
00408 {
00409     bitset_t my_color = brd.GetColor(color) & brd.Const().GetCells();
00410     bitset_t op_color = brd.GetColor(!color) & brd.Const().GetCells();
00411 
00412     return ((m_not_oppt & op_color).none() 
00413             && BitsetUtil::IsSubsetOf(m_must_have, my_color));
00414 }
00415 
00416 //----------------------------------------------------------------------------
00417 
00418 bool VCPattern::ShiftPattern(HexDirection dir, const StoneBoard& brd)
00419 {
00420     bitset_t must, oppt, bad;
00421     if (!BoardUtils::ShiftBitset(brd.Const(), MustHave(), dir, must)) 
00422         return false;
00423     if (!BoardUtils::ShiftBitset(brd.Const(), NotOpponent(), dir, oppt)) 
00424         return false;
00425     HexPoint endpoint1 = BoardUtils::PointInDir(brd.Const(), Endpoint(0), dir);
00426     HexPoint endpoint2 = BoardUtils::PointInDir(brd.Const(), Endpoint(1), dir);
00427 
00428     m_end1 = endpoint1;
00429     m_end2 = endpoint2;
00430     m_must_have = must;
00431     m_not_oppt = oppt;
00432     return true;
00433 }
00434 
00435 //----------------------------------------------------------------------------


6 Jan 2011 Doxygen 1.6.3