BG Queue Update

Enabled Party/Guild joining methods, Implements first attempt at the splitting algorithm (Thanks to  jaBote!)
Checks item 1 on issue #69
Help us test! -- http://hercules.ws/board/topic/1302-bg-queue-debug/

Signed-off-by: shennetsind <ind@henn.et>

5 files changed, 120 insertions, 26 deletions

diff --git a/npc/custom/bgqueue/flavius.txt b/npc/custom/bgqueue/flavius.txt
index b3db9f81d..45b261175 100644
--- a/npc/custom/bgqueue/flavius.txt
+++ b/npc/custom/bgqueue/flavius.txt
@@ -3,7 +3,7 @@
 //===== By: ==================================================
 //= L0ne_W0lf
 //===== Current Version: =====================================
-//= 1.4
+//= 1.5
 //===== Description: =========================================
 //= [AEGIS Conversion]
 //= Flavius Battleground.
@@ -15,6 +15,7 @@
 //= 1.2 Updated 'waitingroom' to support required zeny/lvl. [Kisuka]
 //= 1.3 Removed MaxLvl check in waitingrooms. Replaced setwall with setcell.
 //= 1.4 Attempt at implementing BG Queue [Ind/Hercules]
+//= 1.5 Attempt at implementing BG Queue team-algorithm [jaBote]
 //============================================================
 
 
@@ -36,20 +37,87 @@ OnPlayerListReady:
 	queueopt($@Guill_QueueBG1,HQO_OnLogout,"start#bat_b01::OnGuillaumeQuit");
 	queueopt($@Croix_QueueBG1,HQO_OnLogout,"start#bat_b01::OnCroixQuit");
 	
-	set .@it,queueiterator($@bg_queue_id);
 	set .@i, 0;
 	
-	for( set .@member, qiget(.@it); qicheck(.@it); set .@member,qiget(.@it) ) {
-		if( .@i % 2 == 0 ) {
-			bg_join_team($@FlaviusBG1_id1,.@member);
-			queueadd($@Guill_QueueBG1,.@member);
-		} else {
-			bg_join_team($@FlaviusBG1_id2,.@member);
-			queueadd($@Croix_QueueBG1,.@member);
+	copyarray .@bg_member[0],$@bg_member[0],$@bg_member_size;
+	copyarray .@bg_member_group[0],$@bg_member_group[0],$@bg_member_size;
+	copyarray .@bg_member_type[0],$@bg_member_type[0],$@bg_member_size;
+	
+	freeloop(1);
+	// Counting all participants and determining sizes, condensing .@bg_member_group
+	set .@nogroupcount, 0;
+	for (set .@i, 0; .@i < getarraysize(.@bg_member); set .@i, .@i + 1) {
+		// check if .@bg_member_group and .@bg_member_type already exists on these groups.
+		for (set .@j, 0; .@j <= getarraysize(.@bg_groups); set .@j, .@j + 1) { // <= since it has to start working even if the array is still blank
+			if (.@bg_member_group[.@i] == 0) { // Just count them
+				set .@nogroupcount, .@nogroupcount + 1;
+				break;
+			}
+			else if ( (.@bg_member_group[.@i] == .@bg_groups[.@j]) && (.@bg_member_type[.@i] == .@bg_types[.@j]) ) {
+				set .@bg_count[.@j], .@bg_count[.@j] + 1;
+				break;
+			}
+			else if (.@j == (getarraysize(.@bg_groups)) ) { // It isn't there, insert a new entry at j+1 since j is the last known member
+				set .@bg_groups[.@j], .@bg_member_group[.@i];
+				set .@bg_types[.@j], .@bg_member_type[.@i];
+				set .@bg_count[.@j], 1;
+				break;
+			}
+			// Else keep running the loop until we find there's a group already made or make a new one
+		}
+	}
+	
+	// Now, sorting the group arrays from amount of population descending! Bubble sort powers, I call upon thee!
+	// Type doesn't matter here for precedence checks, but also needs to be sorted the same way along with groups
+	for (set .@i, 0; .@i < getarraysize(.@bg_groups); set .@i, .@i + 1) {
+		for (set .@j, 0; .@j < (getarraysize(.@bg_groups) - .@i); set .@j, .@j + 1) {
+			if (.@bg_count[.@j] < .@bg_count[.@j+1]){
+				set .@temp1, .@bg_groups[.@j];
+				set .@temp2, .@bg_types[.@j];
+				set .@temp3, .@bg_count[.@j];
+				set .@bg_groups[.@j], .@bg_groups[.@j+1];
+				set .@bg_types[.@j], .@bg_types[.@j+1];
+				set .@bg_count[.@j], .@bg_count[.@j+1];
+				set .@bg_groups[.@j+1], .@temp1;
+				set .@bg_types[.@j+1], .@temp2;
+				set .@bg_count[.@j+1], .@temp3;
+			}
+		}
+	}
+	
+	// Add the groups to the queues! :D
+	for (set .@i, 0; .@i < getarraysize(.@bg_groups); set .@i, .@i + 1){ 
+		if (queuesize($@Croix_QueueBG1) <= queuesize($@Guill_QueueBG1)){ // Catch'em all and add to the queue!
+			for (set .@j, 0; .@j < getarraysize(.@bg_member); set .@j, .@j + 1) {
+				if ( (.@bg_groups[.@i] == .@bg_member_group[.@j]) && (.@bg_types[.@i] == .@bg_member_type[.@j]) ) {
+					bg_join_team($@FlaviusBG1_id1,.@bg_member[.@j]);
+					queueadd($@Croix_QueueBG1, .@bg_member[.@j]);
+				}
+			}
+		}
+		else {
+			for (set .@j, 0; .@j < getarraysize(.@bg_member); set .@j, .@j + 1) {
+				if ( (.@bg_groups[.@i] == .@bg_member_group[.@j]) && (.@bg_types[.@i] == .@bg_member_type[.@j]) ) {
+					bg_join_team($@FlaviusBG1_id2,.@bg_member[.@j]);
+					queueadd($@Guill_QueueBG1, .@bg_member[.@j]);
+				}
+			}
+		}
+	}
+	// Don't forget the people that go on their own!
+	for (set .@i, 0; .@i <= getarraysize(.@bg_member); set .@i, .@i+1) {
+		if (.@bg_member_group[.@i] == 0) { // Get alone people only
+			if (queuesize($@Croix_QueueBG1) <= queuesize($@Guill_QueueBG1)) {
+				bg_join_team($@FlaviusBG1_id1,.@bg_member[.@i]);
+				queueadd($@Croix_QueueBG1, .@bg_member[.@i]);
+			}
+			else {
+				bg_join_team($@FlaviusBG1_id2,.@bg_member[.@i]);
+				queueadd($@Guill_QueueBG1, .@bg_member[.@i]);
+			}
 		}
-		set .@i,.@i + 1;
 	}
-	qiclear(.@it);
+	freeloop(0);
 
 	set $@FlaviusBG1, 1;
 	set $@FlaviusBG1_Victory, 0;
diff --git a/src/map/battleground.c b/src/map/battleground.c
index 62688659e..84b41af29 100644
--- a/src/map/battleground.c
+++ b/src/map/battleground.c
@@ -520,13 +520,43 @@ void bg_begin(struct bg_arena *arena) {
 				bg->queue_pc_cleanup(sd);
 		}
 	}
+	/* TODO/FIXME? I *think* it should check what kind of queue the player used, then check if his party/guild
+	 * (his team) still meet the join criteria (sort of what bg->can_queue does)
+	 */
 
 	if( count < arena->min_players ) {
 		bg->match_over(arena,true);
 	} else {
 		arena->ongoing = true;
-		mapreg->setreg(script->add_str("$@bg_queue_id"),arena->queue_id);/* TODO: make this a arena-independant var? or just .@? */
+		/* TODO: make this a arena-independant var? or just .@? */
+		mapreg->setreg(script->add_str("$@bg_queue_id"),arena->queue_id);
 		mapreg->setregstr(script->add_str("$@bg_delay_var$"),bg->gdelay_var);
+		
+		count = 0;
+		for( i = 0; i < queue->size; i++ ) {
+			struct map_session_data * sd = NULL;
+			
+			if( queue->item[i] > 0 && ( sd = map->id2sd(queue->item[i]) ) ) {
+				if( sd->bg_queue.ready == 1 ) {
+					
+					mapreg->setreg(reference_uid(script->add_str("$@bg_member"), count), sd->status.account_id);
+
+					mapreg->setreg(reference_uid(script->add_str("$@bg_member_group"), count),
+								   sd->bg_queue.type == BGQT_GUILD ? sd->status.guild_id :
+								   sd->bg_queue.type == BGQT_PARTY ? sd->status.party_id :
+								   0
+								   );
+					mapreg->setreg(reference_uid(script->add_str("$@bg_member_type"), count),
+								   sd->bg_queue.type == BGQT_GUILD ? 1 :
+								   sd->bg_queue.type == BGQT_PARTY ? 2 :
+								   0
+								   );
+					count++;
+				}
+			}
+		}
+		mapreg->setreg(script->add_str("$@bg_member_size"),count);
+		
 		npc->event_do(arena->npc_event);
 		/* we split evenly? */
 		/* but if a party of say 10 joins, it cant be split evenly unless by luck there are 10 soloers in the queue besides them */
@@ -685,12 +715,7 @@ enum BATTLEGROUNDS_QUEUE_ACK bg_canqueue(struct map_session_data *sd, struct bg_
 
 	if( sd->bg_queue.arena != NULL )
 		return BGQA_DUPLICATE_REQUEST;
-	
-	if( type != BGQT_INDIVIDUAL ) {/* until we get the damn balancing correct */
-		clif->colormes(sd->fd,COLOR_RED,"Queueing is only currently enabled only for Solo Mode");
-		return BGQA_FAIL_TEAM_COUNT;
-	}
-		
+			
 	switch(type) {
 		case BGQT_GUILD:
 			if( !sd->guild || !sd->state.gmaster_flag )
diff --git a/src/map/battleground.h b/src/map/battleground.h
index a5e540924..4150de8be 100644
--- a/src/map/battleground.h
+++ b/src/map/battleground.h
@@ -19,10 +19,11 @@
  * Enumerations
  **/
 enum bg_queue_types {
-	BGQT_INVALID,
-	BGQT_INDIVIDUAL,
-	BGQT_PARTY,
-	BGQT_GUILD
+	BGQT_INVALID    = 0x0,
+	BGQT_INDIVIDUAL = 0x1,
+	BGQT_PARTY      = 0x2,
+	/* yup no 0x3 */
+	BGQT_GUILD      = 0x4,
 };
 
 struct battleground_member_data {
diff --git a/src/map/clif.c b/src/map/clif.c
index 913a94058..f309a53a9 100644
--- a/src/map/clif.c
+++ b/src/map/clif.c
@@ -9213,7 +9213,9 @@ void clif_hercules_chsys_mjoin(struct map_session_data *sd) {
 /// Notification from the client, that it has finished map loading and is about to display player's character (CZ_NOTIFY_ACTORINIT).
 /// 007d
 void clif_parse_LoadEndAck(int fd,struct map_session_data *sd) {
+#if PACKETVER >= 20090218
 	int i;
+#endif
 
 	if(sd->bl.prev != NULL)
 		return;
@@ -17572,9 +17574,7 @@ void clif_parse_bgqueue_register(int fd, struct map_session_data *sd) {
 		clif->bgqueue_ack(sd,BGQA_FAIL_BGNAME_INVALID,0);
 		return;
 	}
-	//debug
-	safestrncpy(arena->name, p->bg_name, sizeof(arena->name));
-	
+
 	switch( (enum bg_queue_types)p->type ) {
 		case BGQT_INDIVIDUAL:
 		case BGQT_PARTY:
diff --git a/src/map/party.c b/src/map/party.c
index ab05c23f7..1f82028a8 100644
--- a/src/map/party.c
+++ b/src/map/party.c
@@ -849,7 +849,7 @@ int party_send_xy_timer(int tid, int64 tick, int id, intptr_t data) {
 		for( i = 0; i < MAX_PARTY; i++ )
 		{
 			struct map_session_data* sd = p->data[i].sd;
-			if( !sd ) continue;
+			if( !sd || sd->bg_id ) continue;
 
 			if( p->data[i].x != sd->bl.x || p->data[i].y != sd->bl.y )
 			{// perform position update