[Fix] shuffle_teams: better shuffle algorithm

[pack]

The vanilla ET code apparently contains some bugs, and I think maybe it would be a good idea that if someone came across a bug and could fix them, would post the fix here. That way some mod teams could save some time if they just needed to copy/paste from here…
I’m not that good coder so my fix is only a small one, but here I go:

---

Author: pack (contact: #-=[bzz]=- irc.quakenet.org)
Description: XP shuffle algorithm improvement
Source-file: g_team.c
Function: G_shuffleTeams
Tested: just a tiny bit
Credits needed: Use as you like, no credits needed whatsoever

Original code:

...

	for( i = 0; i < cnt; i++ ) {
		cl = level.clients + sortClients[i];

		cTeam = (i % 2) + TEAM_AXIS;
...

Fixed code

...
	for( i = 0; i < cnt; i++ ) {
		cl = level.clients + sortClients[i];

		cTeam = (((i+1) % 4) - ((i+1) % 2 ) )/2 + TEAM_AXIS; 
/*

original shuffle:
cTeam = (i % 2) + TEAM_AXIS;
// TEAM_AXIS = 1
// TEAM_ALLIES = 2

*/
...

Explanation (for the interested…)
Old code did shuffle like this:

1. all clients ranked from highest xp (0) to lowest (cnt-1)

0 goes to axis
1 goes to allies
2 goes to axis
…
result: for evey allied player there is one axis player with higher xp, and if an odd number of players is playing on the server, axis even get an extra bonus player too…

New code shuffles like this:
0 goes to axis
1 goes to allies
2 goes to allies
3 goes to axis
4 goes to axis
5 goes to allies
…

offering in most cases a more fair shuffle afaik

• code only tested with 3 players on serv :moo:

[nUllSkillZ]

Great work!
I also think that we should share ideas, code-snippets, resources, bugfixes etc. so that everyone can participate.
We should remember that splashdamage donate us this game and the source.
And so we should do with our knowledge.

[Svartberg]

Good job man,
During the course of my mod i’m going to try fixing a lot of bugs and problems, sadly i have too much tensed time to post all the fixes and code and stuff, but i’ll do my best.

Cheers =]

[Ifurita]

I like your thinking, but it would be nice if the team who got the highest XP player was map dependant, using a NOT(wm_setwinner) parameter. This would mean that the attacking team always started out a little ahead and gets the odd man, instead of the Axis, who are typically the defender on what seems to be an awful lot of maps which really heavily favor the defender.

[pack]

I like your thinking, but it would be nice if the team who got the highest XP player was map dependant, using a NOT(wm_setwinner) parameter. This would mean that the attacking team always started out a little ahead and gets the odd man, instead of the Axis, who are typically the defender on what seems to be an awful lot of maps which really heavily favor the defender.

cTeam =3-( (((i+1) % 4) - ((i+1) % 2 ) )/2 + TEAM_AXIS); 

would give highest xp player too allies but given the way xp players are divided between teams, this is not really necessary? It’s only now that axis get an obvious advantage. :???:

[bani]

Here’s how I did team shuffling way back in rtcw banimod.

It does a true shuffle, and always ensures the teams are even (or at most, 1 off due to odd # of players): It does a ‘live’ shuffle without restarting the game, and avoids swapping objective carriers.

SetTeamShuffle() is just a variation of SetTeam() which bypasses the usual checks and doesnt print announcements.

/*
===================
Svcmd_ShuffleTeams_f

shuffle_teams
===================
*/
void    Svcmd_ShuffleTeams_f( void ) {
        gentity_t       *ent;  
        int             deck[MAX_CLIENTS];
        int             i, j, temp, numclients;

        // load up deck with active clients
        numclients = 0;
        ent = &g_entities[0];
        for ( i = 0; i < MAX_CLIENTS; i++, ent++ ) {
                if ( ent->client && ent->inuse &&
                        ent->client->sess.sessionTeam != TEAM_SPECTATOR &&
                        ent->client->ps.powerups[PW_REDFLAG] == 0 &&
                        ent->client->ps.powerups[PW_BLUEFLAG] == 0 ) {
                        deck[numclients] = i;
                        numclients++;
                }
        }
        // shuffle deck
        for (i = 0; i < numclients; i++) {
                j = rand() % numclients;
                temp = deck[i];
                deck[i] = deck[j];
                deck[j] = temp;
        }
        // set teams randomly
        if( (rand() % 2) == 1 ) {
                for ( i = 0; i < numclients/2; i++ )
                        SetTeamShuffle( &g_entities[deck[i]], TEAM_RED );
                for ( ; i < numclients; i++ )
                        SetTeamShuffle( &g_entities[deck[i]], TEAM_BLUE );
        } else {
                for ( i = 0; i < numclients/2; i++ )
                        SetTeamShuffle( &g_entities[deck[i]], TEAM_BLUE );
                for ( ; i < numclients; i++ )
                        SetTeamShuffle( &g_entities[deck[i]], TEAM_RED );
        }
}

[nUllSkillZ]

Hi,

I’ve include the original suggestion of pack and added a cvar + menus.
So one can choose to shuffle “original” or “pack”.
“My” first code snippet that seems to be correct and seems to work properly and has consistancy.
The modification is not tested yet.

//+***** pack-shuffle *****
// AS DESCRIBED IN THE SD.COM FORUM:
// http://www.splashdamage.com/index.php?name=pnPHPbb2&file=viewtopic&t=6503
// Author: pack (contact: #-=[bzz]=- irc.quakenet.org)
// Description: XP shuffle algorithm improvement
//
// CVARS ADDED TO CHOOSE BETWEEN ORIGINAL AND PACK-SHUFFLE
		if( g_mod_shuffle.integer == 0 )
		{
			cTeam = (i % 2) + TEAM_AXIS;
		}
		else if( g_mod_shuffle.integer == 1 )
		{
			cTeam = (((i+1) % 4) - ((i+1) % 2 ) )/2 + TEAM_AXIS;
		}
		else //to make "PACK" default if something fails
		{
			cTeam = (((i+1) % 4) - ((i+1) % 2 ) )/2 + TEAM_AXIS;
		}
//-***** pack-shuffle *****

File “g_local.h” line 1601:

//+***** pack-shuffle *****
extern	vmCvar_t	g_mod_shuffle;
//-***** pack-shuffle *****

File “g_main.h” line 206:

//+***** pack-shuffle *****
vmCvar_t		g_mod_shuffle;
//-***** pack-shuffle *****

File “g_main.h” line 215:

//+***** pack-shuffle *****
	{ &g_mod_shuffle, "g_mod_shuffle", "1" /*SET TO PACK-SHUFFLE BY DEFAULT*/, CVAR_ARCHIVE, 0, qfalse },
//-***** pack-shuffle *****

Menu Code:
Copy “…\ET\mod\etmain\ui\menus.txt” and “…\ET\mod\etmain\ui\hostgame.menu” to “…\ET\mod\ui”.
In the new “hostgame.menu” override the “buttons” at the end of file with the following code to insert a fourth button:

// Buttons //
	
	BUTTON( 6, WINDOW_HEIGHT-24, .25*(WINDOW_WIDTH-24), 18, "BACK", .3, 14, close hostgame ; open main )
	BUTTON( 6+.25*(WINDOW_WIDTH-24)+4, WINDOW_HEIGHT-24, .25*(WINDOW_WIDTH-24), 18, "ADVANCED", .3, 14, close hostgame ; open hostgame_advanced )
	
	//+***** MYMOD *****
	BUTTON( 6+.25*(WINDOW_WIDTH-24)+4+.25*(WINDOW_WIDTH-24)+4, WINDOW_HEIGHT-24, .25*(WINDOW_WIDTH-24), 18, "ADDITIONAL", .3, 14, close hostgame ; open hostgame_additional )
	//-***** MYMOD *****

	BUTTON( 6+.25*(WINDOW_WIDTH-24)+4+.25*(WINDOW_WIDTH-24)+4+.25*(WINDOW_WIDTH-25)+4, WINDOW_HEIGHT-24, .25*(WINDOW_WIDTH-24), 18, "START SERVER", .3, 14, conditionalScript ui_dedicated 0 ( "open hostgame_dedicated_warning" ) ( "uiScript StartServer" ) )
}

Now you have [BACK | ADVANCED | ADDITIONAL | START SERVER]

Add the following code to the new “menus.txt” to get the new menus into the game (anywhere between “{” and “}”):

	loadMenu { "ui/hostgame_additional.menu" }
	loadMenu { "ui/hostgame_additional_default_1.menu" }
	loadMenu { "ui/hostgame_additional_credits.menu" }

Save the following code as “hostgame_additional.menu” in the path “…\ET\mod\ui” to get a new additional menu:

#include "ui/menudef.h"

//***** DEFINES *****
#define WINDOW_X	16
#define WINDOW_Y	16
#define WINDOW_WIDTH	608
#define WINDOW_HEIGHT	448
#define GROUP_NAME		"grpHostGameAdditional"

//***** MACROS *****
#include "ui/menumacros.h"

//***** HOSTGAME ADDITIONAL MENU *****

menuDef
{
	name		"hostgame_additional"
	visible		0
	fullscreen	0
	rect		WINDOW_X WINDOW_Y WINDOW_WIDTH WINDOW_HEIGHT
	style		WINDOW_STYLE_FILLED

	onESC
	{
		close hostgame_additional ;
		open hostgame
	}

	//***** WINDOW *****
	WINDOW( "HOST GAME: ADDITIONAL OPTIONS", 266 ) // DONT KNOW WHAT 266 MEANS

	//***** SUBWINDOWS *****
	#define SUBWINDOW_WIDTH		.5*(WINDOW_WIDTH-18)

	//***** ADDITIONAL OPTIONS *****//
	SUBWINDOW( 6, 32, (SUBWINDOW_WIDTH), 49, "SHUFFLE OPTIONS" )

	//FOR EXPLANTION PLEASE SEE "menumacros.h"
//	NUMERICFIELD( 8, 48, (SUBWINDOW_WIDTH)-4, 10, "Shuffle:", .2, 8, "g_mod_shuffle", 1, "0 = Original; 1 = PACK" )
	MULTI( 8, 48, (SUBWINDOW_WIDTH)-4, 10, "Shuffle-Type:", .2, 8, "g_mod_shuffle", cvarFloatList { "Original" 0 "PACK" 1 }, "Shuffle-Algorithm" )
	BUTTON( 8, 60, .5*(WINDOW_WIDTH-26), 18, "DEFAULT", .3, 14, open hostgame_additional_default_1 )

	//***** Buttons *****
	BUTTON( 6, WINDOW_HEIGHT-24, .5*(WINDOW_WIDTH-18), 18, "BACK", .3, 14, close hostgame_additional ; open hostgame )
	BUTTON( 6+.5*(WINDOW_WIDTH-18)+6, WINDOW_HEIGHT-24, .5*(WINDOW_WIDTH-18), 18, "CREDITS", .3, 14, open hostgame_additional_credits )
}

Save the following code as “hostgame_additional_default_1.menu” in the path “…\ET\mod\ui” to get a new default setting menu for the additional menu:

#include "ui/menudef.h"

// Defines //

#define WINDOW_X		0
#define WINDOW_Y		0
#define WINDOW_WIDTH	640
#define WINDOW_HEIGHT	480
#define GROUP_NAME		"grpHostgameAdditionalDefault"

// Macros //

#include "ui/menumacros.h"
		
// Host Game Additional Default Menu //

#define DEFAULT_ADDITIONAL_SETTINGS	setcvar g_mod_shuffle 1 ;			\
	
menuDef
{
	name		"hostgame_additional_default_1"
	visible		0
	fullscreen	0
	rect		WINDOW_X WINDOW_Y WINDOW_WIDTH WINDOW_HEIGHT
	style		WINDOW_STYLE_FILLED
	popup
	
	fadeClamp	0.5
	
	onOpen
	{
		setitemcolor background backcolor 0 0 0 0 ;
		fadein background
	}
	
	onESC
	{
		close hostgame_additional_default_1 ;
		open hostgame_additional
	}
	
// Background //

	itemDef {
		name		"background"
		rect		0 0 640 480
		style		WINDOW_STYLE_FILLED
		background	"ui/assets/fadebox.tga"
		backcolor	0 0 0 0
		visible		1
		decoration
	}

// Subwindows //

#define SUBWINDOW_WIDTH		192
#define SUBWINDOW_HEIGHT	88
#define SUBWINDOW_X			.5 * (WINDOW_WIDTH - SUBWINDOW_WIDTH)
#define SUBWINDOW_Y			.5 * (WINDOW_HEIGHT - SUBWINDOW_HEIGHT)

	SUBWINDOWBLACK( SUBWINDOW_X, SUBWINDOW_Y, SUBWINDOW_WIDTH, SUBWINDOW_HEIGHT, "DEFAULT SHUFFLE SETTINGS" )
	LABEL( SUBWINDOW_X+2, SUBWINDOW_Y+16, (SUBWINDOW_WIDTH)-8, 10, "Reset shuffle settings to default?", .2, ITEM_ALIGN_CENTER, .5*((SUBWINDOW_WIDTH)-4), 8 )
	
	BUTTON( SUBWINDOW_X+6, SUBWINDOW_Y+SUBWINDOW_HEIGHT-24, .5*(SUBWINDOW_WIDTH-18), 18, "YES", .3, 14,
		close hostgame_additional_default_1 ; open hostgame_additional ; DEFAULT_ADDITIONAL_SETTINGS )
	BUTTON( SUBWINDOW_X+6+.5*(SUBWINDOW_WIDTH-18)+6, SUBWINDOW_Y+SUBWINDOW_HEIGHT-24, .5*(SUBWINDOW_WIDTH-18), 18, "NO", .3, 14,
		close hostgame_additional_default_1 ; open hostgame_additional )
}

Save the following code as “hostgame_additional_credits.menu” in the path “…\ET\mod\ui” to get a new credit menu for the additional menu:

#include "ui/menudef.h"

// Defines //

#define WINDOW_X		16
#define WINDOW_Y		16
#define WINDOW_WIDTH	608
#define WINDOW_HEIGHT	448
#define GROUP_NAME		"grpHostgameAdditionalCredits"

// Macros //

#include "ui/menumacros.h"
		
// System Menu //
	
menuDef {
	name		"hostgame_additional_credits"
	visible		0
	fullscreen	0
	rect		WINDOW_X WINDOW_Y WINDOW_WIDTH WINDOW_HEIGHT
	style		WINDOW_STYLE_FILLED
	
	onESC {
		close hostgame_additional_credits ;
		open hostgame_additional
	}

// Window //

	itemDef {
		name		"window"
		group		GROUP_NAME
		rect		0 0 WINDOW_WIDTH WINDOW_HEIGHT
		style		WINDOW_STYLE_FILLED
		backcolor	0 0 0 1
		border		WINDOW_BORDER_FULL
		bordercolor	.5 .5 .5 .5
		visible		1
		decoration
	}

// Logo //

	itemDef {
		name		"headerLogo"
		group		GROUP_NAME
		rect		6 80 $evalfloat(WINDOW_WIDTH-12) 16
		text		"ADDITIONAL CREDITS"
		textfont	UI_FONT_ARIBLK_16
		textstyle	ITEM_TEXTSTYLE_SHADOWED
		textscale	.3
		textalign	ITEM_ALIGN_CENTER
		textalignx	$evalfloat(.5*(WINDOW_WIDTH-12))
		textaligny	14
		forecolor	1 1 1 1
		visible		1
		decoration
	}	
	
// Credits Sections //

#define CREDITS_Y	108
	
//	LABELWHITE( 6, CREDITS_Y, WINDOW_WIDTH-12, 10, "pack (contact: #-=[bzz]=- irc.quakenet.org) for his shuffle algorithm", .2, ITEM_ALIGN_LEFT, WINDOW_WIDTH-12, 8 )
	LABELWHITE( 6, CREDITS_Y, WINDOW_WIDTH-12, 10, "pack (contact: #-=[bzz]=- irc.quakenet.org) for his shuffle algorithm", .2, ITEM_ALIGN_CENTER, .5*((WINDOW_WIDTH-24)+12), 8 )

// Buttons //

	BUTTON( 6, WINDOW_HEIGHT-24, (WINDOW_WIDTH-12), 18, "BACK", .3, 14, close hostgame_additional_credits ; open hostgame_additional )
}