<URL: http://bugs.freeciv.org/Ticket/Display.html?id=40618 >
Am Saturday 03 January 2009 02:27:31 schrieb Madeline Book: > <URL: http://bugs.freeciv.org/Ticket/Display.html?id=40618 > > > > [matthias.pfaffer...@mapfa.de - Fri Jan 02 21:15:47 2009]: > > > > This patch adds the possibility to randomize the lists used by > > freeciv. > > I think array_shuffle() would be better placed in utility/ > shared.[ch], since it is useful for more than just genlists, > and shared.h already has some array related stuff. done > Also, it should probably use myrand() from utility/rand.[ch] > instead of the system rand(). This will make it possible to > reproduce the same "random" behavior via seed parameters > (e.g. mapseed, gameseed), which helps in debugging. done > Lastly, the two "for" lines in genlist_shuffle() are missing > some spaces. ;) done; I just copied the line from the function above ... The patch is only compile tested.
Only in freeciv-2.1.99svn.patch_shuffle/po: nb.po diff -ur -X./freeciv-2.1.99svn15391/diff_ignore freeciv-2.1.99svn15391/server/plrhand.c freeciv-2.1.99svn.patch_shuffle/server/plrhand.c --- freeciv-2.1.99svn15391/server/plrhand.c 2008-12-27 17:25:17.000000000 +0100 +++ freeciv-2.1.99svn.patch_shuffle/server/plrhand.c 2009-01-02 20:53:01.000000000 +0100 @@ -1311,20 +1311,20 @@ **************************************************************************/ void shuffle_players(void) { - int i, pos, tmp; + /* shuffled_order is defined global */ + int n = player_slot_count(); + int i; freelog(LOG_DEBUG, "shuffle_players: creating shuffled order"); - for (i = 0; i < player_slot_count(); i++) { + for (i = 0; i < n; i++) { shuffled_order[i] = i; } - for (i = 0; i < player_slot_count() - 1; i++) { - /* for each run: shuffled[ <i ] is already shuffled [Kero+dwp] */ - pos = i + myrand(player_slot_count() - i); - tmp = shuffled_order[i]; - shuffled_order[i] = shuffled_order[pos]; - shuffled_order[pos] = tmp; + /* randomize it */ + array_shuffle(shuffled_order, n); + + for (i = 0; i < n; i++) { freelog(LOG_DEBUG, "shuffled_order[%d] = %d", i, shuffled_order[i]); } } diff -ur -X./freeciv-2.1.99svn15391/diff_ignore freeciv-2.1.99svn15391/utility/genlist.c freeciv-2.1.99svn.patch_shuffle/utility/genlist.c --- freeciv-2.1.99svn15391/utility/genlist.c 2008-12-25 19:45:46.000000000 +0100 +++ freeciv-2.1.99svn.patch_shuffle/utility/genlist.c 2009-01-03 13:41:15.000000000 +0100 @@ -302,3 +302,36 @@ myiter->dataptr = sortbuf[i]; } } + +/************************************************************************ + Randomize the elements of a genlist using the Fisher-Yates shuffle. + + see: genlist_sort() and shared.c:array_shuffle() +************************************************************************/ +void genlist_shuffle(struct genlist *pgenlist) +{ + const int n = genlist_size(pgenlist); + void *sortbuf[n]; + struct genlist_link *myiter; + int i, j, shuffle[n]; + + if (n <= 1) { + return; + } + + myiter = find_genlist_position(pgenlist, 0); + for (i = 0; i < n; i++, ITERATOR_NEXT(myiter)) { + sortbuf[i] = ITERATOR_PTR(myiter); + /* also create the shuffle list */ + shuffle[i] = i; + } + + /* randomize it */ + array_shuffle(shuffle, n); + + /* create the shuffled list */ + myiter = find_genlist_position(pgenlist, 0); + for( i = 0; i < n; i++, ITERATOR_NEXT(myiter)) { + myiter->dataptr = sortbuf[shuffle[i]]; + } +} diff -ur -X./freeciv-2.1.99svn15391/diff_ignore freeciv-2.1.99svn15391/utility/genlist.h freeciv-2.1.99svn.patch_shuffle/utility/genlist.h --- freeciv-2.1.99svn15391/utility/genlist.h 2008-12-25 19:45:46.000000000 +0100 +++ freeciv-2.1.99svn.patch_shuffle/utility/genlist.h 2009-01-03 13:41:14.000000000 +0100 @@ -84,6 +84,7 @@ void genlist_sort(struct genlist *pgenlist, int (*compar)(const void *, const void *)); +void genlist_shuffle(struct genlist *pgenlist); #define ITERATOR_PTR(iter) ((iter) ? ((iter)->dataptr) : NULL) #define ITERATOR_NEXT(iter) (iter = (iter)->next) diff -ur -X./freeciv-2.1.99svn15391/diff_ignore freeciv-2.1.99svn15391/utility/shared.c freeciv-2.1.99svn.patch_shuffle/utility/shared.c --- freeciv-2.1.99svn15391/utility/shared.c 2008-12-25 19:45:46.000000000 +0100 +++ freeciv-2.1.99svn.patch_shuffle/utility/shared.c 2009-01-03 13:41:13.000000000 +0100 @@ -1797,3 +1797,21 @@ return found; } + +/************************************************************************ + Randomize the elements of an array using the Fisher-Yates shuffle. + + see: http://benpfaff.org/writings/clc/shuffle.html +************************************************************************/ +void array_shuffle(int *array, int n) +{ + if (n > 1) { + int i; + for (i = 0; i < n - 1; i++) { + int j = i + myrand(n - i); + int t = array[j]; + array[j] = array[i]; + array[i] = t; + } + } +} diff -ur -X./freeciv-2.1.99svn15391/diff_ignore freeciv-2.1.99svn15391/utility/shared.h freeciv-2.1.99svn.patch_shuffle/utility/shared.h --- freeciv-2.1.99svn15391/utility/shared.h 2008-12-25 19:45:46.000000000 +0100 +++ freeciv-2.1.99svn.patch_shuffle/utility/shared.h 2009-01-03 13:41:16.000000000 +0100 @@ -244,4 +244,7 @@ bool path_is_absolute(const char *filename); char scanin(char **buf, char *delimiters, char *dest, int size); + +void array_shuffle(int *array, int n); + #endif /* FC__SHARED_H */ diff -ur -X./freeciv-2.1.99svn15391/diff_ignore freeciv-2.1.99svn15391/utility/speclist.h freeciv-2.1.99svn.patch_shuffle/utility/speclist.h --- freeciv-2.1.99svn15391/utility/speclist.h 2008-12-25 19:45:46.000000000 +0100 +++ freeciv-2.1.99svn.patch_shuffle/utility/speclist.h 2009-01-02 20:53:01.000000000 +0100 @@ -41,6 +41,7 @@ bool foo_list_search(struct foo_list *this, foo_t *pfoo); void foo_list_sort(struct foo_list *This, int (*compar)(const void *, const void *)); + void foo_list_shuffle(struct foo_list *This); You should also define yourself: (this file cannot do this for you) @@ -148,6 +149,11 @@ genlist_sort(tthis->list, compar); } +static inline void SPECLIST_FOO(_list_shuffle) (SPECLIST_LIST * tthis) +{ + genlist_shuffle(tthis->list); +} + #undef SPECLIST_TAG #undef SPECLIST_TYPE #undef SPECLIST_PASTE_
_______________________________________________ Freeciv-dev mailing list Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev