[Java] Minesweeper Concepts
Moderator: MaxCoderz Staff
[Java] Minesweeper Concepts
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 . 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!
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!
- benryves
- Maxcoderz Staff
- Posts: 3089
- Joined: Thu 16 Dec, 2004 10:06 pm
- Location: Croydon, England
- Contact:
Re: [Java] Minesweeper Concepts
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.
As for the uncovering algorithm, that can be performed using a flood fill.
Re: [Java] Minesweeper Concepts
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.
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.
-
- Calc King
- Posts: 1513
- Joined: Sat 05 Aug, 2006 7:22 am
Re: [Java] Minesweeper Concepts
You can't have multidimension arrays in Java.
You can have jagged arrays of course, but they're really not the same.
You can have jagged arrays of course, but they're really not the same.
Re: [Java] Minesweeper Concepts
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.
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?benryves wrote:As for the uncovering algorithm, that can be performed using a flood fill.
- benryves
- Maxcoderz Staff
- Posts: 3089
- Joined: Thu 16 Dec, 2004 10:06 pm
- Location: Croydon, England
- Contact:
Re: [Java] Minesweeper Concepts
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.
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.
Re: [Java] Minesweeper Concepts
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.
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.
- benryves
- Maxcoderz Staff
- Posts: 3089
- Joined: Thu 16 Dec, 2004 10:06 pm
- Location: Croydon, England
- Contact:
Re: [Java] Minesweeper Concepts
Not quite. Let's say you had this red circle:Wesley wrote:That's right! In Minesweeper, the corners also have to be checked, not just the west, east, north, and south.
Normally, if you were to fill it with blue, you'd end up with this:
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):
Maybe if you pasted your code we could see where the problem was?
- Attachments
-
- Flood fill - red circle overwritten with blue.
- flood_fill_3.png (527 Bytes) Viewed 26852 times
-
- Flood fill - red circle filled with blue.
- flood_fill_2.png (563 Bytes) Viewed 26852 times
-
- Flood fill - red circle.
- flood_fill_1.png (542 Bytes) Viewed 26852 times
Re: [Java] Minesweeper Concepts
Doh, I should've posted the code at the start. Here is my recursive method:
In Minesweeper, you HAVE to check corners? For instance, if you had the following ("*" are bombs):
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!
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);
}
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
Thanks, Ben, your insight is always so helpful!
- benryves
- Maxcoderz Staff
- Posts: 3089
- Joined: Thu 16 Dec, 2004 10:06 pm
- Location: Croydon, England
- Contact:
Re: [Java] Minesweeper Concepts
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.
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.
Re: [Java] Minesweeper Concepts
I thought that might be possiblebenryves wrote:I guess that means that my Minesweeper implementations are wrong. Oh well.
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.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.
Re: [Java] Minesweeper Concepts
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?
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?
Re: [Java] Minesweeper Concepts
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.
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.
- benryves
- Maxcoderz Staff
- Posts: 3089
- Joined: Thu 16 Dec, 2004 10:06 pm
- Location: Croydon, England
- Contact:
Re: [Java] Minesweeper Concepts
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.
-
- Calc King
- Posts: 1513
- Joined: Sat 05 Aug, 2006 7:22 am
Re: [Java] Minesweeper Concepts
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.
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.