source: trunk/gamelogic.cxx @ 14

Last change on this file since 14 was 12, checked in by jtv, 14 years ago

Reveal fatal patch when player dies

File size: 12.7 KB
Line 
1/*
2This file is part of libmines.
3
4Copyright (C) 2005, Jeroen T. Vermeulen <jtv@xs4all.nl>
5
6libmines is free software; you can redistribute it and/or modify it under the
7terms of the GNU General Public License as published by the Free Software
8Foundation; either version 2 of the License, or (at your option) any later
9version.
10
11libmines is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
13PARTICULAR PURPOSE.  See the GNU General Public License for more details.
14
15You should have received a copy of the GNU General Public License along with
16libmines; if not, write to the Free Software Foundation, Inc., 59 Temple Place,
17Suite 330, Boston, MA  02111-1307  USA
18*/
19
20// This is is where heart of the game is implemented.
21
22#include <cassert>
23#include <stdexcept>
24#include <string>
25#include <vector>
26
27#include "gamelogic.hxx"
28#include "save.hxx"
29
30using namespace std;
31
32
33namespace
34{
35int rand_coord(int top)
36{
37  // TODO: Actually randomize
38  return rand() % top;
39}
40} // namespace
41
42
43/// A square patch of water, which may or may not contain a mine
44class Patch
45{
46public:
47  Patch();
48
49  /// Initialization: set a mine
50  void mine();
51
52  bool mined() const throw () { return m_mined; }
53  bool revealed() const throw () { return m_revealed; }
54  int near_mines() const throw () { return m_nearmines; }
55  int near_hiddenmines() const throw () { return m_near_hiddenmines; }
56  int near_unknown() const throw () { return m_near_unknown; }
57
58  void reveal() throw () { m_revealed = true; }
59
60  /// Initialization: mark the fact that a mine has been set in a nearby Patch
61  void set_nearby_mine();
62
63  /// Adjust to revelation of nearby Patch (mined or not, depending on argument)
64  void reveal_nearby(bool is_mined);
65
66  /// Should the state of all nearby Patches now be obvious to the user?
67  bool obvious() const throw ();
68
69private:
70  int m_nearmines;
71  int m_near_hiddenmines;
72  /// Nearby unrevealed patches (not correct for border patches, but who cares)
73  int m_near_unknown;
74  bool m_mined;
75  bool m_revealed;
76};
77
78
79Patch::Patch() :
80  m_nearmines(0),
81  m_near_hiddenmines(0),
82  m_near_unknown(8),
83  m_mined(false),
84  m_revealed(false)
85{
86}
87
88void Patch::mine()
89{
90  assert(!mined());
91  m_mined = true;
92  assert(mined());
93}
94
95void Patch::set_nearby_mine()
96{
97  ++m_nearmines;
98  ++m_near_hiddenmines;
99  assert(m_nearmines == m_near_hiddenmines);
100  assert(m_nearmines <= 8);
101}
102
103void Patch::reveal_nearby(bool is_mined)
104{
105  m_near_hiddenmines -= is_mined;
106  --m_near_unknown;
107
108  assert(m_near_hiddenmines >= 0);
109  assert(m_near_unknown >= 0);
110  assert(m_near_hiddenmines <= m_near_unknown);
111}
112
113bool Patch::obvious() const throw ()
114{
115  return near_unknown() && revealed() && !mined() &&
116    (!near_hiddenmines() || near_hiddenmines()==near_unknown());
117}
118
119
120namespace
121{
122
123/// Functor to apply to neighbouring Patches when initializing a mine
124struct set_nearby_mine
125{
126  void operator()(Coords, Patch &p) const { p.set_nearby_mine(); }
127};
128
129/// Functor: note that nearby patch has been revealed, update counters
130class reveal_nearby
131{
132public:
133  explicit reveal_nearby(bool mined) : m_mine(mined) {}
134  void operator()(Coords, Patch &p) const { p.reveal_nearby(m_mine); }
135
136private:
137  bool m_mine;
138
139  reveal_nearby();
140};
141
142/// Functor: add element to set if it satisfies given condition functor
143template<typename COND> class set_add : private COND
144{
145public:
146  explicit set_add(set<Coords> &worklist) : m_worklist(worklist) {}
147  void operator()(Coords c, const Patch &p) const
148  {
149    if (COND::operator()(p)) m_worklist.insert(c);
150  }
151private:
152  set<Coords> &m_worklist;
153};
154
155/// Condition functor: we're not fully done with Patch yet?
156class UnfinishedPatch
157{
158public:
159  bool operator()(const Patch &p) const throw () { return p.near_unknown(); }
160};
161
162/// Condition functor: Patch has not been revelealed yet?
163class UnrevealedPatch
164{
165public:
166  bool operator()(const Patch &p) const throw () { return !p.revealed(); }
167};
168
169/// Condition functor: Patch has become "obvious"?
170class ObviousPatch
171{
172public:
173  bool operator()(const Patch &p) const throw () { return p.obvious(); }
174};
175
176
177/// Is Patch a candidate for "superset detection" based on newly revealed Patch?
178/** This looks for the case where the unexplored area around the Patch is a
179 * proper superset of the one of a neighbour that was just revealed.  If it is,
180 * and if the number of unexplored mines near the current one is either equal to
181 * that near the newly revealed one, or the difference is equal to the size
182 * difference of the unexplored areas, then the unexplored area near the Patch
183 * is either all clear or all mined, respectively.
184 */
185class SuperSet
186{
187  set<Coords> &m_worklist;
188  const Patch &m_revealed;
189public:
190  SuperSet(set<Coords> &worklist, const Patch &newly_revealed) :
191    m_worklist(worklist),
192    m_revealed(newly_revealed)
193  {
194    assert(newly_revealed.revealed());
195  }
196
197  void operator()(Coords c, const Patch &p) const
198  {
199    if (p.revealed())
200    {
201      const int areadiff = p.near_unknown() - m_revealed.near_unknown();
202      if (areadiff > 0 &&
203          (p.near_hiddenmines() == m_revealed.near_hiddenmines() ||
204           p.near_hiddenmines() == areadiff))
205      m_worklist.insert(c);
206    }
207  }
208};
209
210
211} // namespace
212
213
214Lake::Lake(int _rows, int _cols, int mines) :
215  m_patches(0),
216  m_rows(_rows),
217  m_cols(_cols),
218  m_intelligence(1),
219  m_patches_to_go(m_rows*m_cols-mines),
220  m_moves(0)
221{
222  assert(m_rows > 0);
223  assert(m_cols > 0);
224  assert(mines > 0);
225  assert(mines <= m_rows*m_cols);
226
227  m_patches = new Patch[arraysize()];
228
229  while (mines)
230  {
231    const int row = rand_coord(m_rows), col = rand_coord(m_cols);
232    mines -= place_mine_at(row,col);
233  }
234
235  for (int b=1; b<border; ++b)
236  {
237    border_row(-b);
238    border_row(m_rows+b-1);
239    border_col(-b);
240    border_col(m_cols+b-1);
241  }
242}
243
244
245Lake::Lake(const char buffer[]) :
246  m_patches(0),
247  m_rows(0),
248  m_cols(0),
249  m_intelligence(0),
250  m_patches_to_go(0),
251  m_moves(0)
252{
253  initialize_encoding();
254
255  const char *here = read_header(buffer);
256
257  m_rows = read_int("rows",here);
258  m_cols = read_int("cols",here);
259  m_moves = read_int("move",here);
260  m_intelligence = read_int("intl",here);
261  m_patches_to_go = m_rows * m_cols;
262
263  // TODO: Re-unify this with regular constructor
264  assert(m_rows > 0);
265  assert(m_cols > 0);
266  assert(m_moves >= 0);
267  assert(m_intelligence >= 0);
268
269  m_patches = new Patch[arraysize()];
270
271  here = skip_whitespace(here);
272
273  // TODO: Unify these two read operations
274
275  const int padding = linepadding(m_cols);
276
277  // Read mine placement
278  for (int r=0; r<m_rows; ++r)
279  {
280    for (int c = 0; c < m_cols; c += bitsperchar)
281    {
282      unsigned int x = extract_char(here);
283      for (int i = 0; i < bitsperchar; ++i)
284      {
285        if (x & 1) m_patches_to_go -= place_mine_at(r,c+i);
286        x >>= 1;
287      }
288    }
289    here = read_eol(here, padding);
290  }
291
292  // Read revealed fields
293  for (int r=0; r<m_rows; ++r)
294  {
295    for (int c = 0; c < m_cols; c += bitsperchar)
296    {
297      unsigned int x = extract_char(here);
298      for (int i = 0; i < bitsperchar; ++i)
299      {
300        if (x & 1)
301        {
302          reveal_patch(r, c+i);
303          --m_patches_to_go;
304        }
305        x >>= 1;
306      }
307    }
308    here = read_eol(here, padding);
309  }
310
311  // TODO: Re-unify this with regular constructor
312  for (int b=1; b<border; ++b)
313  {
314    border_row(-b);
315    border_row(m_rows+b-1);
316    border_col(-b);
317    border_col(m_cols+b-1);
318  }
319}
320
321
322Lake::~Lake() throw ()
323{
324  delete [] m_patches;
325}
326
327
328int Lake::save(char buf[]) const
329{
330  initialize_encoding();
331  char *here = write_header(buf);
332  here = write_int("rows",here,m_rows);
333  here = write_int("cols",here,m_cols);
334  here = write_int("move",here,m_moves);
335  here = write_int("intl",here,m_intelligence);
336  here = write_newline(here);
337
338  // Padding at end of line required by base64
339  const int padding = linepadding(m_cols);
340
341  // TODO: Unify these two write actions
342
343  // Write mines
344  for (int r = 0; r < m_rows; ++r)
345  {
346    for (int c = 0; c < m_cols; c += bitsperchar)
347    {
348      unsigned int x = 0;
349      for (int i = bitsperchar-1; i >= 0; --i)
350      {
351        x <<= 1;
352        if (c+i < m_cols && at(r,c+i).mined()) x |= 1;
353      }
354      *here++ = produce_char(x);
355    }
356    here = write_eol(here, padding);
357  }
358
359  here = write_newline(here);
360
361  // Write revealed fields
362  for (int r = 0; r < m_rows; ++r)
363  {
364    for (int c = 0; c < m_cols; c += bitsperchar)
365    {
366      unsigned int x = 0;
367      for (int i = bitsperchar-1; i >= 0; --i)
368      {
369        x <<= 1;
370        if (c+i < m_cols && at(r,c+i).revealed()) x |= 1;
371      }
372      *here++ = produce_char(x);
373    }
374    here = write_eol(here, padding);
375  }
376  terminate(here);
377
378  return here - buf;
379}
380
381
382bool Lake::place_mine_at(int row, int col)
383{
384  Patch &p = at(row,col);
385  if (p.mined()) return false;
386
387  p.mine();
388  for_neighbours(row,col,set_nearby_mine());
389  return true;
390}
391
392const Patch &Lake::at(int row, int col) const
393{
394  check_pos(row, col);
395  const int idx = index_for(row, col);
396  check_index(idx);
397  return m_patches[idx];
398}
399
400
401Patch &Lake::at(int row, int col)
402{
403  check_pos(row, col);
404  const int idx = index_for(row, col);
405  check_index(idx);
406  return m_patches[idx];
407}
408
409void Lake::probe(int row, int col, set<Coords> &changes, bool as_mine)
410{
411  assert(m_patches_to_go >= 0);
412
413  Patch &p = at(row,col);
414  if (!p.revealed())
415  {
416    ++m_moves;
417    const Coords pos(row,col);
418    if (p.mined() != as_mine)
419    {
420      reveal_patch(row,col);
421      throw Boom(pos, m_moves, p.mined());
422    }
423    set<Coords> worklist;
424    worklist.insert(pos);
425    propagate(worklist, changes);
426    // TODO: FIXME: This can actually fail, apparently, in loaded games
427    assert(m_patches_to_go >= 0);
428  }
429}
430
431char Lake::status_at(int row, int col) const
432{
433  const Patch &p = at(row,col);
434  return p.revealed() ? (p.mined() ? '*' : ('0'+p.near_mines())) : '^';
435}
436
437void Lake::reveal_patch(int row, int col)
438{
439  Patch &p = at(row,col);
440  if (!p.revealed())
441  {
442    p.reveal();
443    for_neighbours(row,col,reveal_nearby(p.mined()));
444  }
445}
446
447void Lake::border_row(int r)
448{
449  for (int c=m_cols+border-1; c>=-border; --c) reveal_patch(r,c);
450}
451
452void Lake::border_col(int c)
453{
454  for (int r=m_rows-1; r>=0; --r) reveal_patch(r,c);
455}
456
457void Lake::propagate(set<Coords> &work, set<Coords> &changes)
458{
459  while (!work.empty())
460  {
461    set<Coords> next, area;
462
463    /* Reveal any patches from working set with no nearby mines, and their
464     * neighbours.  This part is what all Minesweeper implementations do.
465     */
466    for (set<Coords>::const_iterator i = work.begin(); i != work.end(); ++i)
467    {
468      const int row = i->row, col = i->col;
469      if (row >= 0 && row < m_rows && col >= 0 && col < m_cols)
470      {
471        Patch &p = at(row,col);
472        if (!p.revealed())
473        {
474          reveal_patch(row,col);
475          changes.insert(Coords(row,col));
476          if (!p.mined()) --m_patches_to_go;
477          for_zone<2,true>(row,col,set_add<UnfinishedPatch>(area));
478        }
479        if (m_intelligence > 0 && p.obvious())
480          for_neighbours(row,col,set_add<UnrevealedPatch>(next));
481      }
482    }
483
484    /* Recognize revealed Patches whose unexplored neighbours must obviously be
485     * either all clear or all mines, and reveal their neighbours.
486     */
487    if (m_intelligence > 1)
488      for (set<Coords>::const_iterator i = area.begin(); i != area.end(); ++i)
489        for_zone<1,true>(i->row,i->col,set_add<ObviousPatch>(next));
490
491    /* Recognize the case where two explored patches A and B have sets of
492     * unexplored neighbours U such that
493     *  1. U(A) is a proper subset of U(B), and
494     *  2. the numbers of unexplored nearby mines M satisfy either:
495     *   (a) M(B) - M(A) = 0 (in which case U(B)\U(A) is all clear) or
496     *   (b) M(B) - M(A) = |U(B)\U(A)|  (in which case U(B)\U(A) is all mines).
497     *
498     * At the moment I don't see a clever way of implementing this with mere
499     * local scalar comparisons.  Unless we count use of bitfields; the full set
500     * of neighbours for a Patch fits seductively well into a byte.  But that
501     * would introduce unpleasant complexity.
502     */
503    if (m_intelligence > 2)
504    {
505      set<Coords> cand;
506
507      // First step: filter out the possible cases
508      for (set<Coords>::const_iterator i = area.begin(); i != area.end(); ++i)
509      {
510        const Patch &p = at(i->row, i->col);
511        if (p.revealed()) for_neighbours(i->row, i->col, SuperSet(cand,p));
512      }
513     
514      // TODO: Iterate through candidates to find the *real* superset cases
515      for (set<Coords>::const_iterator i = cand.begin(); i != cand.end(); ++i)
516      {
517      }
518    }
519
520    work.swap(next);
521  }
522}
523
524
525int Lake::index_for(int row, int col) const throw ()
526{
527  return (row+border)*(m_cols+2*border) + col + border;
528}
529
530
531int Lake::arraysize() const throw ()
532{
533  return (m_rows+2*border)*(m_cols+2*border);
534}
535
536
537void Lake::check_index(int i) const
538{
539  assert(i >= 0);
540  assert(i < arraysize());
541}
542
543
544void Lake::check_pos(int row, int col) const
545{
546  assert(row >= -border);
547  assert(row < m_rows+border);
548  assert(col >= -border);
549  assert(col < m_cols+border);
550}
551
Note: See TracBrowser for help on using the repository browser.