Bug 92095 - intelligent startup: no need for random clicking
Summary: intelligent startup: no need for random clicking
Status: RESOLVED FIXED
Alias: None
Product: kmines
Classification: Applications
Component: general (show other bugs)
Version: unspecified
Platform: Compiled Sources Linux
: NOR wishlist
Target Milestone: ---
Assignee: Dmitry Suzdalev
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2004-10-25 22:45 UTC by Oswald Buddenhagen
Modified: 2008-08-01 17:54 UTC (History)
0 users

See Also:
Latest Commit:
Version Fixed In:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Oswald Buddenhagen 2004-10-25 22:45:05 UTC
Version:            (using KDE Devel)
Installed from:    Compiled sources

the first click should always be into an empty region (as opposed to a single non-mine field). this would avoid the silly random clicking necessary every time to start a game for real.
xdemineur has a similar feature, but it is imperfect: a) it does the above before the first click, so time starts already, and b) it sometimes reveals ridiculously small regions, which is pretty much pointless in most cases.
Comment 1 Nicolas Roffet 2007-08-02 01:09:51 UTC
I think this is a nice feature request for our new KMines for KDE 4. Just place the mines after the 1st click, so that there is never a mine at the clicked position. What do you think Dmitry?
Comment 2 Dmitry Suzdalev 2007-08-02 12:15:06 UTC
SVN commit 695529 by dimsuz:

* Implement field generation on the first click - now you won't blow up from start :-)
  I don't think that it should generate the field in a way so the first click
  is on an empty cell - this would be too easy IMO. Currently it just ensures, that
  first click is not on mine. Objections?
* Drop old "digits-assigning" algorithm, use new - much faster one which doesn't iterate
  over whole field
* Some code cleanups

BUG: 92095


 M  +36 -37    minefielditem.cpp  
 M  +15 -9     minefielditem.h  
 M  +1 -1      scene.cpp  


--- trunk/KDE/kdegames/kmines/minefielditem.cpp #695528:695529
@@ -28,14 +28,12 @@
 MineFieldItem::MineFieldItem()
     : m_leftButtonPos(-1,-1), m_midButtonPos(-1,-1), m_gameOver(false)
 {
-//    regenerateField(numRows, numCols, numMines);
 }
 
-void MineFieldItem::regenerateField( int numRows, int numCols, int numMines )
+void MineFieldItem::initField( int numRows, int numCols, int numMines )
 {
     Q_ASSERT( numMines < numRows*numCols );
 
-    kDebug() << "regenerate field";
     m_firstClick = true;
     m_gameOver = false;
 
@@ -77,6 +75,10 @@
             m_cells[i]->reset();
         else
             m_cells[i] = new CellItem(this);
+        // let it be empty by default
+        // generateField() will adjust needed cells
+        // to hold digits or mines
+        m_cells[i]->setDigit(0);
     }
 
     for(int i=oldBorderSize; i<newBorderSize; ++i)
@@ -84,44 +86,40 @@
 
     setupBorderItems();
 
-    // generating mines
+    adjustItemPositions();
+    m_flaggedMinesCount = 0;
+    emit flaggedMinesCountChanged(m_flaggedMinesCount);
+}
+
+void MineFieldItem::generateField(int clickedIdx)
+{
+    QList<int> cellsWithMines;
+    // generating mines ensuring that clickedIdx won't hold mine
     int minesToPlace = m_minesCount;
     int randomIdx = 0;
     while(minesToPlace != 0)
     {
         randomIdx = m_randomSeq.getLong( m_numRows*m_numCols );
-        if(!m_cells.at(randomIdx)->hasMine())
+        if(!m_cells.at(randomIdx)->hasMine() && randomIdx != clickedIdx)
         {
             m_cells.at(randomIdx)->setHasMine(true);
+            cellsWithMines.append(randomIdx);
             minesToPlace--;
         }
         else
             continue;
     }
 
-    // calculating digits for cells around mines
-    for(int row=0; row < m_numRows; ++row)
-        for(int col=0; col < m_numCols; ++col)
+    foreach(int idx, cellsWithMines)
+    {
+        FieldPos rc = rowColFromIndex(idx);
+        QList<CellItem*> neighbours = adjasentItemsFor(rc.first, rc.second);
+        foreach( CellItem *item, neighbours )
         {
-            if(itemAt(row,col)->hasMine())
-                continue;
-            // simply looking at all 8 neighbour cells and adding +1 for each
-            // mine we found
-            int resultingDigit = 0;
-            QList<CellItem*> neighbours = adjasentItemsFor(row,col);
-            foreach(CellItem* item, neighbours)
-            {
-                if(item->hasMine())
-                    resultingDigit++;
-            }
-
-            // having 0 is ok here - it'll be empty
-            itemAt(row,col)->setDigit(resultingDigit);
+            if(!item->hasMine())
+                item->setDigit( item->digit()+1 );
         }
-
-    adjustItemPositions();
-    m_flaggedMinesCount = 0;
-    emit flaggedMinesCountChanged(m_flaggedMinesCount);
+    }
 }
 
 void MineFieldItem::setupBorderItems()
@@ -180,6 +178,7 @@
             }
         }
 }
+
 QRectF MineFieldItem::boundingRect() const
 {
     qreal cellSize = KMinesRenderer::self()->cellSize();
@@ -264,21 +263,20 @@
 void MineFieldItem::revealEmptySpace(int row, int col)
 {
     // recursively reveal neighbour cells until we find cells with digit
-    typedef QPair<int,int> RowColPair;
-    QList<RowColPair> list = adjasentRowColsFor(row,col);
+    QList<FieldPos> list = adjasentRowColsFor(row,col);
     CellItem *item = 0;
 
-    foreach( const RowColPair& pair, list )
+    foreach( const FieldPos& pos, list )
     {
         // first is row, second is col
-        item = itemAt(pair);
+        item = itemAt(pos);
         if(item->isRevealed() || item->isFlagged())
             continue;
         if(item->digit() == 0)
         {
             item->reveal();
             m_numUnrevealed--;
-            revealEmptySpace(pair.first,pair.second);
+            revealEmptySpace(pos.first,pos.second);
         }
         else if(!item->isFlagged())
         {
@@ -302,6 +300,7 @@
     if(m_firstClick)
     {
         m_firstClick = false;
+        generateField( row*m_numCols + col );
         emit firstClickDone();
     }
 
@@ -533,9 +532,9 @@
     }
 }
 
-QList<QPair<int,int> > MineFieldItem::adjasentRowColsFor(int row, int col)
+QList<FieldPos> MineFieldItem::adjasentRowColsFor(int row, int col)
 {
-    QList<QPair<int,int> > resultingList;
+    QList<FieldPos> resultingList;
     if(row != 0 && col != 0) // upper-left diagonal
         resultingList.append( qMakePair(row-1,col-1) );
     if(row != 0) // upper
@@ -557,11 +556,11 @@
 
 QList<CellItem*> MineFieldItem::adjasentItemsFor(int row, int col)
 {
-    QList<QPair<int,int> > rowcolList = adjasentRowColsFor(row,col);
+    QList<FieldPos > rowcolList = adjasentRowColsFor(row,col);
     QList<CellItem*> resultingList;
-    typedef QPair<int,int> RowColPair;
-    foreach( const RowColPair& pair, rowcolList )
-        resultingList.append( itemAt(pair) );
+    foreach( const FieldPos& pos, rowcolList )
+        resultingList.append( itemAt(pos) );
     return resultingList;
 }
 
+
--- trunk/KDE/kdegames/kmines/minefielditem.h #695528:695529
@@ -25,6 +25,9 @@
 
 class CellItem;
 class BorderItem;
+
+typedef QPair<int,int> FieldPos;
+
 /**
  * Graphics item that represents MineField.
  * It is composed of many (or little) of CellItems.
@@ -41,14 +44,12 @@
      */
     MineFieldItem();
     /**
-     * (re)Generates field with given properties.
-     * Old properties & item states (if any) are reset
-     *
+     * TODO add docstring
      * @param numRows number of rows
      * @param numCols number of columns
      * @param numMines number of mines
      */
-    void regenerateField( int numRows, int numCols, int numMines );
+    void initField( int numRows, int numCols, int numMines );
     /**
      * Resizes this graphics item so it fits in given rect
      */
@@ -89,23 +90,28 @@
     /**
      * Overloaded one, which takes QPair
      */
-    inline CellItem* itemAt( const QPair<int,int>& pos ) { return itemAt(pos.first,pos.second); }
+    inline CellItem* itemAt( const FieldPos& pos ) { return itemAt(pos.first,pos.second); }
     /**
      * Calculates (row,col) from given index in m_cells and returns them in QPair
      */
-    inline QPair<int,int> rowColFromIndex(int idx)
+    inline FieldPos rowColFromIndex(int idx)
         {
             int row = idx/m_numCols;
             return qMakePair(row, idx - row*m_numCols);
         }
     /**
+     * TODO add docstring
+     * @param clickedIdx specifies index which should NOT have mine
+     */
+    void generateField(int clickedIdx);
+    /**
      * Returns all adjasent items for item at row, col
      */
     QList<CellItem*> adjasentItemsFor(int row, int col);
     /**
      * Returns all valid adjasent row,col pairs for row, col
      */
-    QList<QPair<int,int> > adjasentRowColsFor(int row, int col);
+    QList<FieldPos> adjasentRowColsFor(int row, int col);
     /**
      * Checks if player lost the game
      */
@@ -175,8 +181,8 @@
      * row and column where mouse was pressed.
      * (-1,-1) if it is already released
      */
-    QPair<int,int> m_leftButtonPos;
-    QPair<int,int> m_midButtonPos;
+    FieldPos m_leftButtonPos;
+    FieldPos m_midButtonPos;
     bool m_firstClick;
     bool m_gameOver;
     int m_numUnrevealed;
--- trunk/KDE/kdegames/kmines/scene.cpp #695528:695529
@@ -78,7 +78,7 @@
     }
     if(m_messageItem->isVisible())
         m_messageItem->forceHide(KGamePopupItem::AnimatedHide);
-    m_fieldItem->regenerateField(rows, cols, numMines);
+    m_fieldItem->initField(rows, cols, numMines);
     // reposition items
     resizeScene((int)sceneRect().width(), (int)sceneRect().height());
 }
Comment 3 Oswald Buddenhagen 2007-08-02 13:30:38 UTC
yes - objections. blowing up on the first click is an outright bug. it's nice that you fixed it, but this is not the point of this request.
sure implementing what i'm requesting would make the game simpler - it would eliminate (or at least reduce) the possibility of losing the game *by pure chance* before it gets going in the first place. it's fine if you consider the original behavior a feature instead of a braindamage - however, i prefer logic games over gambling.
Comment 4 Dmitry Suzdalev 2007-08-02 14:51:51 UTC
SVN commit 695576 by dimsuz:

Exclude the need for random guessing on the game start.
I.e. ensure that the first clicked cell will always be an emtpy one.

I got convinced after I implemented this feature and tried it :-)
Having this feature just lets the player to, well, play, instead of starting
a dozen of new games until she finds the one where he didn't explode after
a few first clicks.

Thanks, ossi :)

BUG: 92095


 M  +17 -3     minefielditem.cpp  


--- trunk/KDE/kdegames/kmines/minefielditem.cpp #695575:695576
@@ -93,16 +93,30 @@
 
 void MineFieldItem::generateField(int clickedIdx)
 {
+    // generating mines ensuring that clickedIdx won't hold mine
+    // and that it will be an empty cell so the user don't have
+    // to make random guesses at the start of the game
     QList<int> cellsWithMines;
-    // generating mines ensuring that clickedIdx won't hold mine
     int minesToPlace = m_minesCount;
     int randomIdx = 0;
+    CellItem* item = 0;
+    FieldPos fp = rowColFromIndex(clickedIdx);
+
+    // this is the list of items we don't want to put the mine in
+    // to ensure that clickedIdx will stay an empty cell
+    // (it will be empty if none of surrounding items holds mine)
+    QList<CellItem*> neighbForClicked = adjasentItemsFor(fp.first, fp.second);
+
     while(minesToPlace != 0)
     {
         randomIdx = m_randomSeq.getLong( m_numRows*m_numCols );
-        if(!m_cells.at(randomIdx)->hasMine() && randomIdx != clickedIdx)
+        item = m_cells.at(randomIdx);
+        if(!item->hasMine()
+           && neighbForClicked.indexOf(item) == -1
+           && randomIdx != clickedIdx)
         {
-            m_cells.at(randomIdx)->setHasMine(true);
+            // ok, let's mine this place! :-)
+            item->setHasMine(true);
             cellsWithMines.append(randomIdx);
             minesToPlace--;
         }
Comment 5 Ethan Anderson 2008-08-01 17:54:21 UTC
I have an alternate solution that I'll probably be posting soon:

The map has a row of mine-free spaces around the perimeter that start revealed, at the user's option-- and the first click isn't random at all.

This has the added benefit of precluding the vast majority of dead end games.