]> git.draconx.ca Git - rrace.git/commitdiff
Mix in PID with initial seed.
authorNick Bowler <nbowler@draconx.ca>
Fri, 13 Jan 2023 03:46:24 +0000 (22:46 -0500)
committerNick Bowler <nbowler@draconx.ca>
Fri, 13 Jan 2023 03:46:24 +0000 (22:46 -0500)
This may give slightly better results if the game timer is not
too precise, by avoiding a scenario where two instances of the
game started very close together have very similar initial states.

In reality this may be an extremely rare or even impossible scenario
with the current implementation, as the (im)precision of system time
functions is often related to system scheduler behaviour.  But it
shouldn't hurt, and the plan is to alter how the timers work and
this will become needed.

To this end, split out the timekeeping functions which allows them
to be easily stubbed out in test cases, and a new test case checks
that (with the nonfunctional timer) we still get different results
on different runs.

Makefile.am
src/game.c
src/time.c [new file with mode: 0644]
t/.gitignore
t/boardmove.c
t/checkgoal.c
t/game-notime.h [new file with mode: 0644]
t/initboard.c [new file with mode: 0644]
t/rng-test.c
tests/game.at

index d9c0c445a44ce16412d57c40c0b5380872f6059a..2e0db6bf2b7185d312c97aa76ce7922ddfe3d23d 100644 (file)
@@ -37,10 +37,10 @@ EXTRA_DIST += doc/rrace-motif.1
 noinst_HEADERS = conf_post.h src/version.h src/icon.h src/ewmhicon.h \
                  common/src/xtra.h
 
-rrace_curses_SOURCES = common/src/help.c src/game.c src/version.c
+rrace_curses_SOURCES = common/src/help.c src/game.c src/time.c src/version.c
 rrace_curses_LDADD = $(libcursesmain_a_OBJECTS) $(CURSES_LIBS) $(GNULIB)
 
-rrace_motif_SOURCES = src/game.c src/x11.c src/game.h src/motif.h \
+rrace_motif_SOURCES = src/game.c src/time.c src/x11.c src/game.h src/motif.h \
                       src/colour.h src/ewmhicon.c src/icon.c \
                       src/version.c src/xcounter.c src/xcounter.h
 rrace_motif_LDADD = $(libmotifmain_a_OBJECTS) $(libmotifui_a_OBJECTS) \
@@ -95,9 +95,10 @@ check_PROGRAMS = t/boardbit \
                  t/boardrect \
                  t/checkgoal \
                  t/ewmhicon \
+                 t/initboard \
                  t/overlaygoal \
                  t/rng-test
-EXTRA_DIST += t/xos256ss.c
+EXTRA_DIST += t/game-notime.h t/xos256ss.c
 
 $(t_boardbit_OBJECTS): $(gnulib_headers)
 $(t_overlaygoal_OBJECTS): $(gnulib_headers)
@@ -116,6 +117,9 @@ t_ewmhicon_SOURCES = t/ewmhicon.c src/ewmhicon.c src/icon.c common/src/help.c
 t_ewmhicon_LDADD = $(MOTIF_LIBS) $(GNULIB)
 $(t_ewmhicon_OBJECTS): $(gnulib_headers)
 
+t_initboard_SOURCES = t/initboard.c src/game.c
+$(t_initboard_OBJECTS): $(gnulib_headers)
+
 XPMICONS_LOCOLOR = data/lo16x16.xpm data/lo32x32.xpm data/lo48x48.xpm
 XPMICONS_HICOLOR = data/hi16x16.xpm data/hi24x24.xpm \
                    data/hi32x32.xpm data/hi48x48.xpm
index eefafe5ac40e16d93df0581a51fc23a46539202b..ab704789e8c483fb37715a14bdfa8cb1809f85e8 100644 (file)
@@ -1,6 +1,6 @@
 /*
  * Slide puzzle core game logic
- * Copyright © 2022 Nick Bowler
+ * Copyright © 2022-2023 Nick Bowler
  *
  * This program is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -23,8 +23,8 @@
 #include <config.h>
 #include <limits.h>
 #include <string.h>
+#include <unistd.h>
 #include <time.h>
-#include <gethrxtime.h>
 #include "game.h"
 
 #define B64(x) ((x) & 0xffffffffffffffff)
@@ -133,8 +133,19 @@ void game_reset(struct board *board)
        if (!rng_is_seeded()) {
                unsigned long long seed;
 
-               seed = time(NULL);
-               seed += gethrxtime();
+               /*
+                * Try to get a reasonable initial seed.
+                *
+                * Reasonable in this context means:
+                *
+                * - roughly even distribution of 1/0 bits, and
+                * - unlikely to generate the same seed twice in succession.
+                */
+               game_begin(board);
+
+               seed  = time(NULL);
+               seed += board->time_start;
+               seed += (unsigned long long)getpid() << 16;
                seed += seed << 32;
 
                game_reseed(seed);
@@ -241,16 +252,6 @@ uint_fast32_t game_check_goal(struct board *board)
        return mask & GOAL_MASK;
 }
 
-void game_begin(struct board *board)
-{
-       board->time_start = gethrxtime();
-}
-
-int_fast32_t game_elapsed(struct board *board)
-{
-       return (gethrxtime() - board->time_start) / 1000000;
-}
-
 int_fast32_t game_finish(struct board *board)
 {
        int_fast32_t t = game_elapsed(board);
diff --git a/src/time.c b/src/time.c
new file mode 100644 (file)
index 0000000..0e8330c
--- /dev/null
@@ -0,0 +1,33 @@
+/*
+ * Slide puzzle game timer logic
+ * Copyright © 2022-2023 Nick Bowler
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+
+#include <config.h>
+#include <stdint.h>
+#include <gethrxtime.h>
+
+#include "game.h"
+
+void game_begin(struct board *board)
+{
+       board->time_start = gethrxtime();
+}
+
+int_fast32_t game_elapsed(struct board *board)
+{
+       return (gethrxtime() - board->time_start) / 1000000;
+}
index 54f6466c4bff545db21e5ca3cb5bc6d8e7d0af1f..c1542020fd9e3039fb310692550eafefa07eb815 100644 (file)
@@ -3,5 +3,6 @@
 /boardrect
 /checkgoal
 /ewmhicon
+/initboard
 /overlaygoal
 /rng-test
index 7ed1e667a37a60f9760634d69967961c0ccd9f9a..9bc11715902e6449f9df8037dc29c1f8474d57a8 100644 (file)
@@ -1,8 +1,26 @@
+/*
+ * Helper to test game_do_move function.
+ * Copyright © 2022-2023 Nick Bowler
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+
 #include <config.h>
 #include <stdio.h>
 #include <stdlib.h>
 
-#include "game.h"
+#include "game-notime.h"
 
 static const char *progname;
 
index 0941e91e0bca206274afe2ce0f01459539a16964..3dd805755b13ab70b89b86a61a6312518ce3661b 100644 (file)
@@ -1,6 +1,6 @@
 /*
  * Helper to test game_check_goal function.
- * Copyright © 2022 Nick Bowler
+ * Copyright © 2022-2023 Nick Bowler
  *
  * This program is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -22,7 +22,7 @@
 #include <string.h>
 #include <inttypes.h>
 #include <errno.h>
-#include "game.h"
+#include "game-notime.h"
 
 #define X3(x) x x x
 
diff --git a/t/game-notime.h b/t/game-notime.h
new file mode 100644 (file)
index 0000000..d271f8b
--- /dev/null
@@ -0,0 +1,22 @@
+/*
+ * Test stubs to link in game logic without timers.
+ * Copyright © 2023 Nick Bowler
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+
+#include "game.h"
+
+void game_begin(struct board *board) { }
+int_fast32_t game_elapsed(struct board *board) { return 0; }
diff --git a/t/initboard.c b/t/initboard.c
new file mode 100644 (file)
index 0000000..cf59a30
--- /dev/null
@@ -0,0 +1,79 @@
+/*
+ * Call board_reset and print the resulting board.
+ * Copyright © 2023 Nick Bowler
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+
+#include <config.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+/*
+ * This will stub out the high precision timer, which means this will not
+ * contribute to the initial seed (good for the tests we want to do).
+ */
+#include "game-notime.h"
+
+static int output_tile(unsigned tile, unsigned (*counts)[TILE_MAX], int goal)
+{
+       static const char chars[TILE_MAX] = ".ROYGBW";
+       unsigned wtf = tile ? 4 : !goal;
+
+       if (tile >= TILE_MAX) {
+               fprintf(stderr, "invalid tile value (%u)\n", tile);
+               return -1;
+       }
+
+       if (++counts[!goal][tile] > (tile ? 4 : !goal)) {
+               printf("WTF %u\n", wtf);
+               fprintf(stderr, "%s has too many (%u) %c tiles\n",
+                               goal ? "goal" : "game", counts[!goal][tile], chars[tile]);
+               return -1;
+       }
+
+       putchar(chars[tile]);
+       return 0;
+}
+
+int main(void)
+{
+       unsigned counts[2][TILE_MAX] = {0};
+       struct board board;
+       int i, j;
+
+       game_reset(&board);
+
+       for (i = 0; i < 25; i++) {
+               int tile;
+
+               tile = board_tile(board.game, i);
+               if (output_tile(tile, counts, 0) < 0)
+                       return EXIT_FAILURE;
+
+               if ((i+1) % 5)
+                       continue;
+
+               if (i < 15) {
+                       putchar(' ');
+
+                       for (j = 0; j < 3; j++) {
+                               tile = board_tile(board.goal, i-4 + j);
+                               if (output_tile(tile, counts, 1) < 0)
+                                       return EXIT_FAILURE;
+                       }
+               }
+               putchar('\n');
+       }
+}
index 78797ab0cd880fae1cabe719ac25842661cfe68b..9d27f3838d1b551d650f6ef45d7625083d9bc9fd 100644 (file)
@@ -1,6 +1,6 @@
 /*
  * Test case for xoshiro256** implementation.
- * Copyright © 2022 Nick Bowler
+ * Copyright © 2022-2023 Nick Bowler
  *
  * Directly compare the game RNG against the reference implementation.
  *
@@ -22,6 +22,7 @@
 #include <stdio.h>
 #include <stdlib.h>
 
+#include "game-notime.h"
 #include "game.c"
 #include "xos256ss.c"
 
index 610b066817f0b0170cef98f7f8a21c9e6f9ad2a3..7defcdb15ff737dec5c6b7bc40b815e6afcf8b23 100644 (file)
@@ -652,3 +652,12 @@ AT_CHECK([overlaygoal <boards.dat >result.dat && cat result.dat],
   [0], [expout])
 
 AT_CLEANUP
+
+# Basic check that we get different initial games if we run the program
+# multiple times in sequence.
+AT_SETUP([game_reset initial seed])
+
+AT_CHECK([initboard >a && initboard >b && initboard >c])
+AT_CHECK([diff a b || diff b c || diff a c || exit 42], [42], [ignore-nolog])
+
+AT_CLEANUP