[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:

[Java] Minesweeper Concepts

Post by Wesley »

Well, I've decided to pick up another Java project. This time I want to make a clone of the classic Minesweeper game. However, I don't even know how the game works :cry:. Does anyone have any suggestions or who I should refer to for help?

I just want to know the constructs of how the game works. I know how it plays, but not the coding part.

Anyhow, thanks everyone!
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 assume you can figure out how to count the number of mines around a square - that should be easy!

As for the uncovering algorithm, that can be performed using a flood fill.
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, so it would be a good idea to set up the mines with a 2D array?

I haven't done much work with multi-dimensional arrays, but that doesn't mean I've learned about them and can use them. This may be a good route.
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 »

You can't have multidimension arrays in Java.
You can have jagged arrays of course, but they're really not the same.
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 »

I got a little spare time and I quickly looked back at this project. I've come very far, but am having problems with flood fill.
benryves wrote:As for the uncovering algorithm, that can be performed using a flood fill.
See, Java can't handle the recursion of that algorithm. That was a good link, by the way! I've come up with a few methods, but all fail to uncover ALL of the spaces that they should. Any ideas?
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 »

Try the implementation under "Most practical implementations use a loop for the west and east directions as an optimization to avoid the overhead of stack or queue management". A naïve implementation will quickly run out of stack space on larger grids!

Don't forget that you need to fill ("click on") the boundary colour in Minesweeper, whereas most flood-fill algorithms are designed to leave the boundary colour alone.
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 »

That's right! In Minesweeper, the corners also have to be checked, not just the west, east, north, and south.

Hm... I did implement a method that uses a loop, but it doesn't work. It leaves cells covered that should be revealed. The reason why is because I am only making a single pass down the grid.

I'm not quite sure how to properly flood with a loop.
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 »

Wesley wrote:That's right! In Minesweeper, the corners also have to be checked, not just the west, east, north, and south.
Not quite. Let's say you had this red circle:

Image

Normally, if you were to fill it with blue, you'd end up with this:

Image

When the filler reaches the red, it stops and leaves it alone. However, in a Minesweeper game you'd want to fill normally, but also uncover (mark, "click on") the cell that caused the filler to stop (so, in this case, we stop when we hit a red pixel, but also colour it blue):

Image

Maybe if you pasted your code we could see where the problem was?
Attachments
Flood fill - red circle overwritten with blue.
Flood fill - red circle overwritten with blue.
flood_fill_3.png (527 Bytes) Viewed 22436 times
Flood fill - red circle filled with blue.
Flood fill - red circle filled with blue.
flood_fill_2.png (563 Bytes) Viewed 22436 times
Flood fill - red circle.
Flood fill - red circle.
flood_fill_1.png (542 Bytes) Viewed 22436 times
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 »

Doh, I should've posted the code at the start. Here is my recursive method:

Code: Select all

		public void floodFill(int row, int col) {
			if (!board[row][col].isEmpty())
				return;
			
			//sides
			board[row+1][col].reveal();
			board[row][col+1].reveal();
			board[row-1][col].reveal();
			board[row][col-1].reveal();
			//corners
			board[row+1][col+1].reveal();
			board[row-1][col+1].reveal();
			board[row-1][col-1].reveal();
			board[row+1][col-1].reveal();
			
			if (board[row+1][col].isEmpty())
				floodFill(row+1,col);
			if (board[row][col+1].isEmpty())
				floodFill(row,col+1);
			if (board[row-1][col].isEmpty())
				floodFill(row-1,col);
			if (board[row][col-1].isEmpty())
				floodFill(row,col-1);
			if (board[row+1][col+1].isEmpty())
				floodFill(row+1,col+1);
			if (board[row-1][col+1].isEmpty())
				floodFill(row-1,col+1);
			if (board[row-1][col-1].isEmpty())
				floodFill(row-1,col-1);
			if (board[row+1][col-1].isEmpty())
				floodFill(row+1,col-1);
		}
In Minesweeper, you HAVE to check corners? For instance, if you had the following ("*" are bombs):

Code: Select all

0 0 1 * 1 0
0 0 1 1 1 0
1 1 0 0 0 0
* 1 0 0 0 0
1 1 0 0 0 0
Then, if you clicked on row 0 and column 0, it will fill (in this example) ALL of the zeroes and ones on the board. If this isn't clear, open up Minesweeper and find this instance.

Thanks, Ben, your insight is always so helpful!
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 guess that means that my Minesweeper implementations are wrong. Oh well. ;)

I can't see anything obviously wrong with your implementation of the flood-fill, other than it being very unfair on the stack. You'll need to switch to a queue-based method for anything other than the smallest grids.
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 »

benryves wrote:I guess that means that my Minesweeper implementations are wrong. Oh well. ;)
I thought that might be possible ;)
benryves wrote:I can't see anything obviously wrong with your implementation of the flood-fill, other than it being very unfair on the stack. You'll need to switch to a queue-based method for anything other than the smallest grids.
So, how would that work since I'm using a 2D array? A queue is like a 1D array. I'm not sure how that algorithm works on Wikipedia.
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 »

It's true that queues are one-dimensional, but try not to think of a queue as an array. Of course, queues can be implemented as arrays, but it's much easier to come up with a solution to any given problem if you think of your data structures as abstract entities, rather than specific Java constructs.

As such, think of a queue as a specialized list in which you can add elements to the rear of the list and remove elements from the front for later reference. Now, in light of your algorithm, what is the nature of the "elements" that need to be saved on the queue? What information do you need to store in the queue so that you can retrieve it later and do the appropriate operations on it (or with it)?

You may now realize that these "elements" can be implemented as a user-defined class, and that the queue can be implemented as an array of objects of your user-defined class. Make sense?
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 »

Yes, that all makes sense. I've been learning about queues in my class for awhile now. I'm not sure how it would work in this program though.

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?

I'm not sure what would "go into" (added) the queue and what would be "pulled out" (removed) of the queue.
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 »

The filling algorithm needs to keep track of which cells it has visited (or needs to visit). In your recursive implementation, it stores the positions on the stack; as stack space is quite limited this will cause problems. You can replace this with a queue instead by modifying the algorithm slightly.
King Harold
Calc King
Posts: 1513
Joined: Sat 05 Aug, 2006 7:22 am

Re: [Java] Minesweeper Concepts

Post by King Harold »

Or a stack, which is better for locality of reference and only requires 1 copy when it needs to grow (instead of a scary multi-part copy)
And more importantly, it would more closely resemble your original recursive implementation.

This reminds me of an algorithm I recently implemented for the SoftwareProject at the uni, which counts the number of nodes in a graph that are directly or indirectly connected to some starting node. First we had a normal Depth First Search that kept a count and a stack of nodes, and a bitarray to remember which nodes were already visited. It pops a node of that stack and then adds all unvisited nodes that it can reach from there to the stack. That's actually exactly what you're doing, in an abstract sense. Only the result you want is the final value of the bitarray, and you don't need the counter.
I found a way to do it up to 16 times as fast (16.4 for 64 nodes, less difference for less nodes) for graphs with up to 64 nodes. That way doesn't use a stack, instead it keeps an ulong (a normal long would be fine too) where a set bit means that you are allowed to look at the node (discovered somehow). The graph itself was an array of ulongs, the matrix representation of a graph. This meant that nearly every every step of the algorithm could now be written with a bitwise operator, except the place where the "index of next node" had to be found from the ulong "discovered" (extracting the lowest set bit is easy enough, but then it has to be converted to an index, which is equivalent to taking the 2log of that bit)

I know it doesn't help you much, but it was a bit of an eye opener for me. (and of course I'm a bit proud that I invented all this by myself lol)
The time complexity suddenly becomes independent of the number of edges, because it always does 64 of them in parallel anyway. It's a bit of a cheat of course, technically the algorithm runs in constant time since the number of nodes is bounded by a constant. But then, that is always true in the real world.
If you (or anyone) want more details on that implementation I'd be glad to give them.
Post Reply