<URL: http://bugs.freeciv.org/Ticket/Display.html?id=40618 >
This patch adds the possibility to randomize the lists used by freeciv. I also
replace the randomize algorithm in server/plrhand.c:shuffle_players().
It is needed for the gold upkeep patch (next id)
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-02 20:53:01.000000000 +0100
@@ -302,3 +302,54 @@
myiter->dataptr = sortbuf[i];
}
}
+
+/************************************************************************
+ Randomize the elements of a genlist using the Fisher-Yates shuffle.
+
+ see: genlist_sort() and 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]];
+ }
+}
+
+/************************************************************************
+ 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 + rand() / (RAND_MAX / (n - i) + 1);
+ 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/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-02 20:53:01.000000000 +0100
@@ -84,6 +84,8 @@
void genlist_sort(struct genlist *pgenlist,
int (*compar)(const void *, const void *));
+void genlist_shuffle(struct genlist *pgenlist);
+void array_shuffle(int *array, int n);
#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/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
