CPPSweeper
19/08/07 23:05
I've rewritten the game model again - in C++. In a
sense it's less fun because when translating to C you
have to rewrite object-oriented code into procedural
code like the older compilers do, but when translating
to C++ it's mostly a syntax transformation. Anyway, I
had a little trouble with reference vs pointers - I
wanted to always use references for the sleeker style,
but I couldn't get it compiled if I declare everything
as reference...
Valgrind doesn't seem to like STL vector very much.
Valgrind doesn't seem to like STL vector very much.
CSweeper
16/08/07 14:43
I've spent two days translating the game model code
(package clustermines.core) to C. The C code tried to
emulate Java as much as possible, with all structs
stored on the heap and passed by reference, etc.
The game compiles and runs correctly on OS X. On Linux, it throws a segfault when trying to free memory at the end. Valgrind gives an error (it says two but the second is sorta explaining the first) which I don't really understand. The code it points to was copied from comp.lang.c FAQs, so I guess I'll just blame the Usenet...
==29046==
==29046== ERROR SUMMARY: 2 errors from 1 contexts (suppressed: 12 from 1)
==29046==
==29046== 2 errors in context 1 of 1:
==29046== Invalid write of size 4
==29046== at 0x80489A7: malloc2dArray (Sweeper.c:84)
==29046== by 0x804884C: newSweeper (Sweeper.c:58)
==29046== by 0x80484EE: main (main.c:39)
==29046== Address 0x1B90A0B0 is 0 bytes after a block of size 32 alloc'd
==29046== at 0x1B904A80: malloc (vg_replace_malloc.c:131)
==29046== by 0x804894D: malloc2dArray (Sweeper.c:80)
==29046== by 0x804884C: newSweeper (Sweeper.c:58)
==29046== by 0x80484EE: main (main.c:39)
--29046--
--29046-- supp: 12 Ugly strchr error in /lib/ld-2.3.3.so
==29046==
==29046== IN SUMMARY: 2 errors from 1 contexts (suppressed: 12 from 1)
==29046==
==29046== malloc/free: in use at exit: 0 bytes in 0 blocks.
==29046== malloc/free: 245 allocs, 245 frees, 6492 bytes allocated.
==29046==
==29046== No malloc'd blocks -- no leaks are possible.
Source is on svn: http://clustermines.svn.sourceforge.net/viewvc/clustermines/CSweeper/
The game compiles and runs correctly on OS X. On Linux, it throws a segfault when trying to free memory at the end. Valgrind gives an error (it says two but the second is sorta explaining the first) which I don't really understand. The code it points to was copied from comp.lang.c FAQs, so I guess I'll just blame the Usenet...
==29046==
==29046== ERROR SUMMARY: 2 errors from 1 contexts (suppressed: 12 from 1)
==29046==
==29046== 2 errors in context 1 of 1:
==29046== Invalid write of size 4
==29046== at 0x80489A7: malloc2dArray (Sweeper.c:84)
==29046== by 0x804884C: newSweeper (Sweeper.c:58)
==29046== by 0x80484EE: main (main.c:39)
==29046== Address 0x1B90A0B0 is 0 bytes after a block of size 32 alloc'd
==29046== at 0x1B904A80: malloc (vg_replace_malloc.c:131)
==29046== by 0x804894D: malloc2dArray (Sweeper.c:80)
==29046== by 0x804884C: newSweeper (Sweeper.c:58)
==29046== by 0x80484EE: main (main.c:39)
--29046--
--29046-- supp: 12 Ugly strchr error in /lib/ld-2.3.3.so
==29046==
==29046== IN SUMMARY: 2 errors from 1 contexts (suppressed: 12 from 1)
==29046==
==29046== malloc/free: in use at exit: 0 bytes in 0 blocks.
==29046== malloc/free: 245 allocs, 245 frees, 6492 bytes allocated.
==29046==
==29046== No malloc'd blocks -- no leaks are possible.
Source is on svn: http://clustermines.svn.sourceforge.net/viewvc/clustermines/CSweeper/
0.7.3 - Solver
13/08/07 23:50
I've fixed solver for the multi-mines mode. It works as
before now, doing only one-square analysis. The rest
might be a little hard, though.
0.7.0 - Multi-mines mode
08/08/07 23:39
It's done! Try it out!
Like I thought before, it wasn't too difficult to finish up the coding. Making all those icons probably took more time with my über clumsy graphic design skillz. Anyway, this means the only primary goal left is a working solver. I wonder if I could write one that can solve a multi-mine game too.
Like I thought before, it wasn't too difficult to finish up the coding. Making all those icons probably took more time with my über clumsy graphic design skillz. Anyway, this means the only primary goal left is a working solver. I wonder if I could write one that can solve a multi-mine game too.
Applet
07/08/07 12:19
I've got the applet version of the game up and running
now. Some changes are made so that you can't play large
and huge boards in applet mode, since it'll break the
layout of web page. The page has been tested on
Firefox, IE 6 and Safari.
I wonder why the necessary code for correctly displaying an applet is still such a mess after so many years...
I wonder why the necessary code for correctly displaying an applet is still such a mess after so many years...
0.6.1 - SweeperHistory bug fixed
04/08/07 21:36
Suppose we are playing this board. All squares are
hidden, except for square a being revealed, and square
F flagged. Squares a-j do not contain mines.
+---------------+
| * f g h * * * |
| * i b c d * * |
| * j e a F * * |
+---------------+
When we chord on a, chord() generates a queue like this:
b c d e
because b is an empty square, reveal() appends all its neighbours to the queue - after e. This gives a revealing sequence of
b c d e f g h i j
When we are replaying, we are revealing squares in this order. The problem is that we'll have a chain reaction on b before revealing c, which gives a totally different revealing sequence:
b f g h i c j e d
This difference is significant because SweeperHistory tries to replay a game by imitating recorded moves from the original game on a new Sweeper instance. There are two ways of recording moves, one is to call SweeperHistory whenever a method in Sweeper is called. The other is to let SweeperHistory to listen to Sweeper, so it will catch all the Sweeper's changes on its own. The second one is obviously more elegant, except for one problem: SweeperListener doesn't tell if a square is the target of a reveal() call, or if it's revealed by chain action, or by a chording on a neighbour.
Suppose we reveal an empty square, and its eight neighbours by chain reaction, we'd have recorded 9 changes. We could naively replay all 9 steps, no problem, the program won't crash. But we'd have to click on the replay button for 9 times to get what was done with one click in the original game. A smart program ought to do better.
How do we tell if some square is revealed by a chain reaction, in order to skip it in step()? A minesweeper game is deterministic after the board is generated. Revealing the same square on two different Sweeper instances that have the same states should generate the same revealing sequence. So, SweeperHistory could check the events sent by Sweeper after step() is called. The sequence of these events should be identical to those that generated the history in the first place, provided that SweeperHistory has perfectly emulated the recorded game so far. If an event SweeperHistory received matches the next move in its record, it knows that this event was caused by the last move it made, and that the event should be skipped.
The original Sweeper used a non-recursive breadth-first searching utilising a queue. There were two reveal() methods in Sweeper. Reveal(Square) was an interface which used reveal(LinkedList) for the real job. Reveal(Square) was used by both SweeperHistory and the game GUI, SweeperPanel, hence it could be emulated by SweeperHistory correctly. Another method, chord(), is used only by SweeperPanel on the other hand. Chord() used reveal(LinkedList) directly and would give a revealing sequence that would not be emulated with reveal(Square), in the way illustrated at the beginning. When SweeperHistory saw a different move than the one in the record, it thinks it's a new move which would have been made by the player to interrupt replaying, and it complied.
In essence, the information of the difference between chord() and reveal(Square) was lost the way record was kept in SweeperHistory.
One way to fix this is to let chord() use reveal(Square) instead, so there won't be any difference between these two methods. The other is to tell SweeperHistory that Sweeper is doing a chord(), which requires a change to SweeperListener. Again, the first one is more elegant, and is chosen.
+---------------+
| * f g h * * * |
| * i b c d * * |
| * j e a F * * |
+---------------+
When we chord on a, chord() generates a queue like this:
b c d e
because b is an empty square, reveal() appends all its neighbours to the queue - after e. This gives a revealing sequence of
b c d e f g h i j
When we are replaying, we are revealing squares in this order. The problem is that we'll have a chain reaction on b before revealing c, which gives a totally different revealing sequence:
b f g h i c j e d
This difference is significant because SweeperHistory tries to replay a game by imitating recorded moves from the original game on a new Sweeper instance. There are two ways of recording moves, one is to call SweeperHistory whenever a method in Sweeper is called. The other is to let SweeperHistory to listen to Sweeper, so it will catch all the Sweeper's changes on its own. The second one is obviously more elegant, except for one problem: SweeperListener doesn't tell if a square is the target of a reveal() call, or if it's revealed by chain action, or by a chording on a neighbour.
Suppose we reveal an empty square, and its eight neighbours by chain reaction, we'd have recorded 9 changes. We could naively replay all 9 steps, no problem, the program won't crash. But we'd have to click on the replay button for 9 times to get what was done with one click in the original game. A smart program ought to do better.
How do we tell if some square is revealed by a chain reaction, in order to skip it in step()? A minesweeper game is deterministic after the board is generated. Revealing the same square on two different Sweeper instances that have the same states should generate the same revealing sequence. So, SweeperHistory could check the events sent by Sweeper after step() is called. The sequence of these events should be identical to those that generated the history in the first place, provided that SweeperHistory has perfectly emulated the recorded game so far. If an event SweeperHistory received matches the next move in its record, it knows that this event was caused by the last move it made, and that the event should be skipped.
The original Sweeper used a non-recursive breadth-first searching utilising a queue. There were two reveal() methods in Sweeper. Reveal(Square) was an interface which used reveal(LinkedList) for the real job. Reveal(Square) was used by both SweeperHistory and the game GUI, SweeperPanel, hence it could be emulated by SweeperHistory correctly. Another method, chord(), is used only by SweeperPanel on the other hand. Chord() used reveal(LinkedList) directly and would give a revealing sequence that would not be emulated with reveal(Square), in the way illustrated at the beginning. When SweeperHistory saw a different move than the one in the record, it thinks it's a new move which would have been made by the player to interrupt replaying, and it complied.
In essence, the information of the difference between chord() and reveal(Square) was lost the way record was kept in SweeperHistory.
One way to fix this is to let chord() use reveal(Square) instead, so there won't be any difference between these two methods. The other is to tell SweeperHistory that Sweeper is doing a chord(), which requires a change to SweeperListener. Again, the first one is more elegant, and is chosen.