[Java] Minesweeper Concepts

Got questions? Got answers? Go here for both.

Moderator: MaxCoderz Staff

User avatar
Wesley
Regular Member
Posts: 137
Joined: Sun 12 Oct, 2008 1:42 am
Location: Boise, Idaho
Contact:

Re: [Java] Minesweeper Concepts

Post by Wesley »

Wesley wrote:From what I 'think' I get is, if the user clicks on an empty space, then do I add the cells around it to a queue? Then, remove each cell from the queue and check if those cells are empty? Then, if they are, create a new queue?
So am I right?
King Harold wrote:If you (or anyone) want more details on that implementation I'd be glad to give them.
Yeah! That sounds awesome! What (underlying) kind of problem were you trying to solve?
ImageImage
ImageImage
Image
King Harold
Calc King
Posts: 1513
Joined: Sat 05 Aug, 2006 7:22 am

Re: [Java] Minesweeper Concepts

Post by King Harold »

Almost except you shouldn't create a new queue (why have queue's with only 1 thing in it?) but add the cells to the queue you already had


The real problem was actually kindof lame, they wanted a tournament manager that plans its games such that two players never play more than once against each other in a Swiss Ladder system (which is really weird and has a ton of varieties) - turns out that in order to avoid reaching a point where only some small subset of the players still has games left to play, you have to check whether you're making subgraphs of uneven number of nodes in a graph where every node is a player and every edge is a game that he's still allowed to play (so it starts out with all n^2 edges filled in)
User avatar
Wesley
Regular Member
Posts: 137
Joined: Sun 12 Oct, 2008 1:42 am
Location: Boise, Idaho
Contact:

Re: [Java] Minesweeper Concepts

Post by Wesley »

Okay, I am really having trouble getting the flooding to work. I keep trying and failing. I'm not sure where I'm fowling up. Does anyone think they can explain the algorithm under "Most practical implementations use a loop for the west and east directions as an optimization to avoid the overhead of queue management:"?

Here is my code (note that I am going north to south rather than west to east):

Code: Select all

		private Queue<MButton> q;
		public void floodFill(int row, int col) {
			
			//1. Set q to empty queue
			q = new LinkedList<MButton>();
			
			//2. If MButton is not empty, return
			if (!board[row][col].isEmpty())
				return;
			
			//3. Add MButton to the end of queue
			q.add(board[row][col]);
			
			MButton n=new MButton(), w=new MButton(), e=new MButton(), s=new MButton();
			
			//4. For each element mb in q
			for(MButton mb : q) {
				
				//5. If mb is empty
				if (mb.isEmpty()) {
					col = mb.colPosition();
					row = mb.rowPosition();
					
					//6. Set n and s equal to MButton above and below mb
					n = board[mb.rowPosition()-1][col];
					s = board[mb.rowPosition()+1][col];
					
					//7. Advance n to the north until its color is no longer empty
					while(n.isEmpty()) {
						n.setRowPosition(n.rowPosition()-1);
						n = board[n.rowPosition()][col];
					}
					
					//8. Advance s to the south until its color is no longer empty
					while(s.isEmpty()) {
						s.setRowPosition(s.rowPosition()+1);
						s = board[s.rowPosition()][col];
					}
					
					//9. Reveal MButtons between n and s
					for(int i = n.rowPosition(); i <= s.rowPosition(); i++) {
						board[i][col].reveal();
					}
					
					//10. For each MButton between n and s
					for(int i = n.rowPosition(); i <= s.rowPosition(); i++) {
						w = board[i][col-1];
						e = board[i][col+1];
						
						//11. If the MButtons west and east of current node are empty
						if (w.isEmpty() && !w.isRevealed())
							q.add(w);
						if (e.isEmpty() && !e.isRevealed())
							q.add(e);
					}
				//12. Continue looping until q is empty	
				}
			}
			//13. Return
		}
ImageImage
ImageImage
Image
King Harold
Calc King
Posts: 1513
Joined: Sat 05 Aug, 2006 7:22 am

Re: [Java] Minesweeper Concepts

Post by King Harold »

I'm not sure yet why it doesn't work, but why are you creating new MButton's only to overwrite them?
polarBody
New Member
Posts: 23
Joined: Wed 02 Sep, 2009 3:01 pm
Location: Chicago, IL

Re: [Java] Minesweeper Concepts

Post by polarBody »

Are you sure that you're using a queue? Aren't you really just using a linked list and accessing each item in the list directly? This is illegal with queues. You can only add elements to the rear of the queue and remove (and process) elements from the front. An element in the middle of the queue should be hidden until every item in front of it has been dequeued and processed.

I think the confusion is coming from this statement in wikipedia's algorithm:

Code: Select all

For each element n of Q
This does not mean that you iterate through each element of the queue, because this violates the concept of queues. Instead of iterating through the list, you remove one element at a time and then process it. Thus, the above statement is a concise (if a bit confusing) way of saying "if the queue is not empty, remove the next element and process it; otherwise, exit the loop."

Another potential problem is that you're using an enhanced for loop on a list, but then you're modifying the list as you iterate through it. I think this is a big no no. Are you getting some kind of runtime error? It would help to know exactly what the problem is.
User avatar
Wesley
Regular Member
Posts: 137
Joined: Sun 12 Oct, 2008 1:42 am
Location: Boise, Idaho
Contact:

Re: [Java] Minesweeper Concepts

Post by Wesley »

Ah! I can't believe how difficult I was making that! Ben, you were totally right!
benryves wrote:You can replace this with a queue instead by modifying the algorithm slightly.
My eyes popped open super early yesterday morning and knew exactly what to do (of course I didn't have the time to do it yesterday). Here is my code:

Code: Select all

		public void floodFill(int row, int col) {
			Queue<MButton> q = new LinkedList<MButton>();
			if (!board[row][col].isEmpty())
				return;
			q.add(board[row][col]);
			MButton mb;
			while(!q.isEmpty()) {
				mb = q.remove();
				if (!mb.isEmpty())
					continue;
				row = mb.rowPosition();
				col = mb.colPosition();
				if (!board[row-1][col].isRevealed() && !board[row-1][col].isWrapper())
					q.add(board[row-1][col]);
				if (!board[row+1][col].isRevealed() && !board[row+1][col].isWrapper())
					q.add(board[row+1][col]);
				if (!board[row][col-1].isRevealed() && !board[row][col-1].isWrapper())
					q.add(board[row][col-1]);
				if (!board[row][col+1].isRevealed() && !board[row][col+1].isWrapper())
					q.add(board[row][col+1]);
				if (!board[row-1][col-1].isRevealed() && !board[row-1][col-1].isWrapper())
					q.add(board[row-1][col-1]);
				if (!board[row+1][col-1].isRevealed() && !board[row+1][col-1].isWrapper())
					q.add(board[row+1][col-1]);
				if (!board[row-1][col+1].isRevealed() && !board[row-1][col+1].isWrapper())
					q.add(board[row-1][col+1]);
				if (!board[row+1][col+1].isRevealed() && !board[row+1][col+1].isWrapper())
					q.add(board[row+1][col+1]);
			}
		}
However, there are some issues that I can't figure out yet. For some reason, revealed buttons are being added to the queue. I checked this with the following code and found that the queue gets larger than the number of buttons in the grid (by a very large amount). Here is the code with the extras:

Code: Select all

		public void floodFill(int row, int col) {
			Queue<MButton> q = new LinkedList<MButton>();
			if (!board[row][col].isEmpty())
				return;
			q.add(board[row][col]);
			MButton mb;
			while(!q.isEmpty()) {
				mb = q.remove();
				if (mb.isRevealed())
					System.out.println(mb);
				if (!mb.isEmpty())
					continue;
				row = mb.rowPosition();
				col = mb.colPosition();
				if (!board[row-1][col].isRevealed() && !board[row-1][col].isWrapper())
					q.add(board[row-1][col]);
				if (!board[row+1][col].isRevealed() && !board[row+1][col].isWrapper())
					q.add(board[row+1][col]);
				if (!board[row][col-1].isRevealed() && !board[row][col-1].isWrapper())
					q.add(board[row][col-1]);
				if (!board[row][col+1].isRevealed() && !board[row][col+1].isWrapper())
					q.add(board[row][col+1]);
				if (!board[row-1][col-1].isRevealed() && !board[row-1][col-1].isWrapper())
					q.add(board[row-1][col-1]);
				if (!board[row+1][col-1].isRevealed() && !board[row+1][col-1].isWrapper())
					q.add(board[row+1][col-1]);
				if (!board[row-1][col+1].isRevealed() && !board[row-1][col+1].isWrapper())
					q.add(board[row-1][col+1]);
				if (!board[row+1][col+1].isRevealed() && !board[row+1][col+1].isWrapper())
					q.add(board[row+1][col+1]);
				System.out.println(q.size());
			}
		}
Can anyone spot why buttons are being added to the queue when they aren't supposed to be?
ImageImage
ImageImage
Image
User avatar
benryves
Maxcoderz Staff
Posts: 3087
Joined: Thu 16 Dec, 2004 10:06 pm
Location: Croydon, England
Contact:

Re: [Java] Minesweeper Concepts

Post by benryves »

I'm also not sure why you check if the queue is empty (and bailing out if it is) immediately after pulling a value out of it - before using the value you just pulled out.

(I haven't the time to look into this in much detail at the moment, sorry - nor do I have access to a Java compiler).
polarBody
New Member
Posts: 23
Joined: Wed 02 Sep, 2009 3:01 pm
Location: Chicago, IL

Re: [Java] Minesweeper Concepts

Post by polarBody »

I have a few questions. What do the isEmpty() and isWrapper() methods of the MButton class do? I would guess that isWrapper() returns whether the button is adjacent to a mine, but I can't think what isEmpty() does.

Also, where in your code are the buttons being revealed? You seem to only check if the button has been revealed, without actually revealing it. If you remove button (2, 3) from the queue without revealing it, then when button (2, 2) gets added to the queue and subsequently removed, button (2, 3) will get added again, along with a whole other slew of buttons. Maybe that's why buttons that should have already been revealed are ending up in the queue again.
benryves wrote:I'm also not sure why you check if the queue is empty (and bailing out if it is) immediately after pulling a value out of it - before using the value you just pulled out.
You mean the call to isEmpty in the if statement? He's calling mb.isEmpty(), not q.isEmpty() :D
I'm a little confused with this step myself.
User avatar
Wesley
Regular Member
Posts: 137
Joined: Sun 12 Oct, 2008 1:42 am
Location: Boise, Idaho
Contact:

Re: [Java] Minesweeper Concepts

Post by Wesley »

polarBody wrote:I have a few questions. What do the isEmpty() and isWrapper() methods of the MButton class do? I would guess that isWrapper() returns whether the button is adjacent to a mine, but I can't think what isEmpty() does.
It is best, for a minesweeper game (in my opinion) to create a N+2 by M+2 array where N and M are the specified width and height. The wrapper consists of buttons that aren't even visible, they just provide an easier way for counting mines around a cell. The isEmpty() method simply checks if the cell is empty or not (if it has no adjacent bombs or not). So, I named it isEmpty() since there isn't anything contained inside of it (such as a bomb or a 1, 2, ..., 8).

I spotted the mistake in adding cells into the queue just after I left the lab (I had to go to class, so I couldn't edit it). I was adding cells that were not yet revealed, but would be revealed when it was their turn to be removed from the queue. Hence, I modified my code a bit. Here is the modified version:

Code: Select all

		public void floodFill(int row, int col) {
			Queue<MButton> q = new LinkedList<MButton>();
			if (!board[row][col].isEmpty())
				return;
			q.add(board[row][col]);
			MButton mb;
			while(!q.isEmpty()) {
				mb = q.remove();
				if (!mb.isRevealed()) {
					mb.reveal();
					numSafeSpots--;
					if (numSafeSpots == 0)
						win();
				}
				if (!mb.isEmpty())
					continue;
				row = mb.rowPosition();
				col = mb.colPosition();
				if (!board[row-1][col].isRevealed() && !board[row-1][col].isWrapper()) {
					q.add(board[row-1][col]);
					board[row-1][col].reveal();
					numSafeSpots--;
				}
				if (!board[row+1][col].isRevealed() && !board[row+1][col].isWrapper()) {
					q.add(board[row+1][col]);
					board[row+1][col].reveal();
					numSafeSpots--;
				}
				if (!board[row][col-1].isRevealed() && !board[row][col-1].isWrapper()) {
					q.add(board[row][col-1]);
					board[row][col-1].reveal();
					numSafeSpots--;
				}
				if (!board[row][col+1].isRevealed() && !board[row][col+1].isWrapper()) {
					q.add(board[row][col+1]);
					board[row][col+1].reveal();
					numSafeSpots--;
				}
				if (!board[row-1][col-1].isRevealed() && !board[row-1][col-1].isWrapper()) {
					q.add(board[row-1][col-1]);
					board[row-1][col-1].reveal();
					numSafeSpots--;
				}
				if (!board[row+1][col-1].isRevealed() && !board[row+1][col-1].isWrapper()) {
					q.add(board[row+1][col-1]);
					board[row+1][col-1].reveal();
					numSafeSpots--;
				}
				if (!board[row-1][col+1].isRevealed() && !board[row-1][col+1].isWrapper()) {
					q.add(board[row-1][col+1]);
					board[row-1][col+1].reveal();
					numSafeSpots--;
				}
				if (!board[row+1][col+1].isRevealed() && !board[row+1][col+1].isWrapper()) {
					q.add(board[row+1][col+1]);
					board[row+1][col+1].reveal();
					numSafeSpots--;
				}
			}
		}
And for a shorthand version which is slightly less efficient (since the current cell is being checked):

Code: Select all

public void floodFill(int row, int col) {
			Queue<MButton> q = new LinkedList<MButton>();
			if (!board[row][col].isEmpty())
				return;
			q.add(board[row][col]);
			MButton mb;
			while(!q.isEmpty()) {
				mb = q.remove();
				if (!mb.isRevealed()) {
					mb.reveal();
					numSafeSpots--;
					if (numSafeSpots == 0)
						win();
				}
				if (!mb.isEmpty())
					continue;
				row = mb.rowPosition();
				col = mb.colPosition();
				for (int i=row-1; i < row + 2; i++)
					for (int j=col-1; j < col + 2; j++) {
						if (!board[i][j].isRevealed() && !board[i][j].isWrapper()) {
							q.add(board[i][j]);
							board[i][j].reveal();
							numSafeSpots--;
						}
					}
			}
		}
ImageImage
ImageImage
Image
User avatar
Wesley
Regular Member
Posts: 137
Joined: Sun 12 Oct, 2008 1:42 am
Location: Boise, Idaho
Contact:

Re: [Java] Minesweeper Concepts

Post by Wesley »

Oh yeah, if anyone would like to test out my Minesweeper program, you can get it here.

And, yes, it is compiled in a jar file, especially for Ben ;).
(in regards to the Pig application) benryves wrote:102-nil to me. :excited: (or beginner's luck?)

The game plays well. :) Packaging it up as a .jar may make it easier to run (on Windows at least you can just double-click the .jar to run it).
ImageImage
ImageImage
Image
polarBody
New Member
Posts: 23
Joined: Wed 02 Sep, 2009 3:01 pm
Location: Chicago, IL

Re: [Java] Minesweeper Concepts

Post by polarBody »

Hey, great job! It plays about the same as the standard Minesweeper on Windows, except sometimes the buttons were a little stubborn, especially if you click near the edge of a button. This could just be Java's fault, though. Still, it's great to see that you've brought this project to a successful completion.

That reminds me that I've really got to finish some of my pending projects. I have a bad habit of starting projects and not seeing them through to the end ('the end' being a useful application).
User avatar
Wesley
Regular Member
Posts: 137
Joined: Sun 12 Oct, 2008 1:42 am
Location: Boise, Idaho
Contact:

Re: [Java] Minesweeper Concepts

Post by Wesley »

Oh no, no, no, no! I am most certainly not finished! I'm getting that clone as close as possible to the real thing if it's the last thing I do! :D
ImageImage
ImageImage
Image
polarBody
New Member
Posts: 23
Joined: Wed 02 Sep, 2009 3:01 pm
Location: Chicago, IL

Re: [Java] Minesweeper Concepts

Post by polarBody »

Well, that's good to hear!

Here's a suggestion: there's a lot of minesweeper clones out there already, so maybe when you finish with yours, you could put your own twist on it. Who knows; it might turn out to be a hit! It would at least be a good exercise. Anyways, that's just something to think about.
Post Reply