<URL: http://bugs.freeciv.org/Ticket/Display.html?id=40618 >
> [matthias.pfaffer...@mapfa.de - Sat Jan 03 12:50:40 2009]:
>
> 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.
Attached version 3 just makes some minor style fixes and
makes compilation work with --enable-debug.
-----------------------------------------------------------------------
おっと。切り直すね。
server/plrhand.c | 18 ++++++++++--------
utility/genlist.c | 34 ++++++++++++++++++++++++++++++++++
utility/genlist.h | 1 +
utility/shared.c | 18 ++++++++++++++++++
utility/shared.h | 3 +++
utility/speclist.h | 6 ++++++
6 files changed, 72 insertions(+), 8 deletions(-)
diff --git a/server/plrhand.c b/server/plrhand.c
index 507444a..2aa8f1f 100644
--- a/server/plrhand.c
+++ b/server/plrhand.c
@@ -1311,22 +1311,24 @@ void maybe_make_contact(struct tile *ptile, struct player *pplayer)
**************************************************************************/
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);
+
+#ifdef DEBUG
+ for (i = 0; i < n; i++) {
freelog(LOG_DEBUG, "shuffled_order[%d] = %d", i, shuffled_order[i]);
}
+#endif
}
/**************************************************************************
diff --git a/utility/genlist.c b/utility/genlist.c
index e827f47..c4567f5 100644
--- a/utility/genlist.c
+++ b/utility/genlist.c
@@ -20,6 +20,7 @@
#include "mem.h"
#include "genlist.h"
+#include "shared.h" /* array_shuffle */
static struct genlist_link *find_genlist_position(const struct genlist *pgenlist,
int pos);
@@ -302,3 +303,36 @@ void genlist_sort(struct genlist *pgenlist,
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, 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 --git a/utility/genlist.h b/utility/genlist.h
index 7090b00..415c699 100644
--- a/utility/genlist.h
+++ b/utility/genlist.h
@@ -84,6 +84,7 @@ bool genlist_search(struct genlist *pgenlist, const void *data);
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 --git a/utility/shared.c b/utility/shared.c
index dc29a9e..9abccca 100644
--- a/utility/shared.c
+++ b/utility/shared.c
@@ -1797,3 +1797,21 @@ char scanin(char **buf, char *delimiters, char *dest, int size)
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 && array != NULL) {
+ int i, j, t;
+ for (i = 0; i < n - 1; i++) {
+ j = i + myrand(n - i);
+ t = array[j];
+ array[j] = array[i];
+ array[i] = t;
+ }
+ }
+}
diff --git a/utility/shared.h b/utility/shared.h
index df20992..eada885 100644
--- a/utility/shared.h
+++ b/utility/shared.h
@@ -244,4 +244,7 @@ bool make_dir(const char *pathname);
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 --git a/utility/speclist.h b/utility/speclist.h
index b1c1540..4894905 100644
--- a/utility/speclist.h
+++ b/utility/speclist.h
@@ -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 @@ static inline void SPECLIST_FOO(_list_sort) (SPECLIST_LIST * tthis, int (*compar
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
