From 6595394b9f9d1d5d2b0f2710ab14612019d1fa02 Mon Sep 17 00:00:00 2001
From: Martin Taibr <taibr.martin@gmail.com>
Date: Fri, 28 Oct 2016 20:36:00 +0200
Subject: [PATCH] iterate through clients in random order

---
 .../sv_spawn_near_teammate.qc                 |  4 +--
 qcsrc/server/_all.qh                          | 27 +++++++++++++++++++
 2 files changed, 29 insertions(+), 2 deletions(-)

diff --git a/qcsrc/common/mutators/mutator/spawn_near_teammate/sv_spawn_near_teammate.qc b/qcsrc/common/mutators/mutator/spawn_near_teammate/sv_spawn_near_teammate.qc
index 2e4802d38..d58ef38a9 100644
--- a/qcsrc/common/mutators/mutator/spawn_near_teammate/sv_spawn_near_teammate.qc
+++ b/qcsrc/common/mutators/mutator/spawn_near_teammate/sv_spawn_near_teammate.qc
@@ -84,7 +84,7 @@ MUTATOR_HOOKFUNCTION(spawn_near_teammate, PlayerSpawn)
 		entity best_mate = NULL;
 		vector best_pos = '0 0 0';
 		float best_dist = 0;
-		FOREACH_CLIENT(IS_PLAYER(it), LAMBDA(
+		FOREACH_CLIENT_RANDOM(IS_PLAYER(it), LAMBDA(
 			//LOG_INFOF("  for client: %s %v\n", it.netname, it.origin);
 			if (!SAME_TEAM(player, it)) continue;
 			if (autocvar_g_spawn_near_teammate_ignore_spawnpoint_check_health >= 0 && it.health < autocvar_g_balance_health_regenstable) continue;
@@ -172,7 +172,7 @@ MUTATOR_HOOKFUNCTION(spawn_near_teammate, PlayerSpawn)
 						best_mate = it;
 					}
 				}
-				else // TODO randomize to avoid favoring players who joined early
+				else
 				{
 					setorigin(player, vectical_trace_endpos);
 					player.angles = it.angles;
diff --git a/qcsrc/server/_all.qh b/qcsrc/server/_all.qh
index ed3083a12..794638dea 100644
--- a/qcsrc/server/_all.qh
+++ b/qcsrc/server/_all.qh
@@ -43,6 +43,33 @@ const string STR_OBSERVER = "observer";
 
 #define FOREACH_CLIENT(cond, body) FOREACH_CLIENTSLOT(IS_CLIENT(it) && (cond), body)
 
+// using the "inside out" version of knuth-fisher-yates shuffle
+// https://en.wikipedia.org/wiki/Fisher–Yates_shuffle
+#define FOREACH_CLIENT_RANDOM(cond, body) \
+	MACRO_BEGIN { \
+		float _clients[255]; \
+		int _cnt = 0; \
+		FOREACH_CLIENT(cond, LAMBDA( \
+			int _j = floor(random() * (_cnt + 1)); \
+			if (_j == _cnt) \
+			{ \
+				_clients[_cnt] = etof(it); \
+			} \
+			else \
+			{ \
+				_clients[_cnt] = _clients[_j]; \
+				_clients[_j] = etof(it); \
+			} \
+			_cnt++; \
+		)); \
+		for (int _i = 0; _i < _cnt; ++_i) \
+		{ \
+			const noref int i = _clients[_i]; \
+			ITER_CONST noref entity it = ftoe(i); \
+			if (cond) { LAMBDA(body) } \
+		} \
+	} MACRO_END
+
 // NOTE: FOR_EACH_MONSTER deprecated! Use the following instead: IL_EACH(g_monsters, true, { code; });
 
 #include <common/effects/all.qh>
-- 
2.39.2