From: Nick Bowler Date: Fri, 13 Jan 2023 03:46:24 +0000 (-0500) Subject: Mix in PID with initial seed. X-Git-Url: http://git.draconx.ca/gitweb/rrace.git/commitdiff_plain/5ba271c9a2d679094dc69dd4e9eff33122022ea0 Mix in PID with initial seed. 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. --- diff --git a/Makefile.am b/Makefile.am index d9c0c44..2e0db6b 100644 --- a/Makefile.am +++ b/Makefile.am @@ -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 diff --git a/src/game.c b/src/game.c index eefafe5..ab70478 100644 --- a/src/game.c +++ b/src/game.c @@ -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 #include #include +#include #include -#include #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 index 0000000..0e8330c --- /dev/null +++ b/src/time.c @@ -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 . + */ + +#include +#include +#include + +#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; +} diff --git a/t/.gitignore b/t/.gitignore index 54f6466..c154202 100644 --- a/t/.gitignore +++ b/t/.gitignore @@ -3,5 +3,6 @@ /boardrect /checkgoal /ewmhicon +/initboard /overlaygoal /rng-test diff --git a/t/boardmove.c b/t/boardmove.c index 7ed1e66..9bc1171 100644 --- a/t/boardmove.c +++ b/t/boardmove.c @@ -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 . + */ + #include #include #include -#include "game.h" +#include "game-notime.h" static const char *progname; diff --git a/t/checkgoal.c b/t/checkgoal.c index 0941e91..3dd8057 100644 --- a/t/checkgoal.c +++ b/t/checkgoal.c @@ -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 #include #include -#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 index 0000000..d271f8b --- /dev/null +++ b/t/game-notime.h @@ -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 . + */ + +#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 index 0000000..cf59a30 --- /dev/null +++ b/t/initboard.c @@ -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 . + */ + +#include +#include +#include + +/* + * 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'); + } +} diff --git a/t/rng-test.c b/t/rng-test.c index 78797ab..9d27f38 100644 --- a/t/rng-test.c +++ b/t/rng-test.c @@ -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 #include +#include "game-notime.h" #include "game.c" #include "xos256ss.c" diff --git a/tests/game.at b/tests/game.at index 610b066..7defcdb 100644 --- a/tests/game.at +++ b/tests/game.at @@ -652,3 +652,12 @@ AT_CHECK([overlaygoal 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