Revisit spawning code

[XtremeBain]

The more I've been playing lately, the more I've noticed how terrible the spawn code is.  I've mentioned this numerous times but the answer is typically "players are spawned randomly and will only spawn in each other if there are not enough spawns for the amount of players on the team".  I do not believe this is the case.  I'm still seeing way too many spawn problems in 3v3 and 4v4 matches on maps that have adequate spawns for each team.

When players are not spawning on the same spawn points then they're usually spawning together in groups of 3-4 at the same location.  I've got a couple demos of recent matches on sandtrap where the spawning is absolutely ridiculous (I'll edit post and include links to demos when I'm home).  All 3 of us spawning at front rush spawns, all 3 of us spawning at flag.  What's worse is maps that spawn you with equipment because you can be double spawning players on carbines or cockers where the other team gets doubled on spyders and completely unbalances the round.  For instance, a double spawn on maps like crimethink means that one player will be left in base picking up the gear from the leftover spawns while the rest of his team are making the attack.

I think it's time to take a look at the spawn code once again to balance the game a little better.  I think an algorithm needs to be put in place to evenly distribute the spawns for each team.  I've been thinking about how to do it but I'm a bit lacking in Q2's vector functions and I'm not really sure how spawns are stored in the game code.

The idea would be to try to maximize the minimum distance between each spawn.  To try to explain this a little better I'll make a visual.  Here's two scenarios, one a very simple spawn and a second that's based on two rooms.  Each scenario will start with a loose text-based 2D, numbered interpretation of the spawn points followed by spawn scenarios for different player counts.

Scenario 1: Simple Spawn (All in one line --  think crates or blitz)
1 2 3 4 5 6 7 8

1v1: Player spawns anywhere (random)
2v2: Players spawn at the furthest spawn points from each other -- 1 and 8.
3v3: Players spawn at either 1, 4, 7 or 2, 5, 8
4v4: Players spawn at either 1, 3, 5, 7 or 2, 4, 6, 8
5v5: This is where the algorithm gets a little messy but it would be something like 1, 3, 4||5 (that means OR), 6, 8
6v6: 1,2,4,5,7,8

Scenario 2: Two Spawn Rooms (think castle1)
1   2            6   7
  3                8
4   5            9   10

2v2: 1, 10 or 4, 7
3v3: 1, 5||6, 10 or 4, 2||7, 9
4v4: 1, 5, 6, 10 or 4, 2, 7, 9
5v5: 1, 5, 6, 10, 2||4||9||7 or 4, 2, 7, 9, 1||5||6||10
6v6: 1, 5, 6, 10, 2||4, 7||9 or 4, 2, 7, 9, 1||5, 6||10

I was going to suggest distributing the spawn-with guns equally for both teams, but I think that just creates too much mess.  I think if a consistent spawn system was implemented then it wouldn't really matter as long as mappers mirrored the guns properly.

If you wanted to just send me the source of the function(s) that handle the spawn distribution, I'll see if I could lay out some of the logic.

[KnacK]

Well put Bain, and much needed.

[jitspoe]

Code: [Select]


/*
=======================================================================

SelectSpawnPoint

=======================================================================
*/

/*
================
PlayersRangeFromSpot

Returns the distance to the nearest player from the given spot
================
*/
float PlayersRangeFromSpot (edict_t *spot)
{
  edict_t *player;
  float bestplayerdistance;
  vec3_t v;
  int n;
  float playerdistance;
 
 
  bestplayerdistance = 9999999;
 
  for (n = 1; n <= maxclients->value; n++)
  {
  player = &g_edicts[n];
 
  if (!player->inuse)
  continue;
 
  if (player->health <= 0)
  continue;
 
  VectorSubtract (spot->s.origin, player->s.origin, v);
  playerdistance = VectorLength (v);
 
  if (playerdistance < bestplayerdistance)
  bestplayerdistance = playerdistance;
  }
 
  return bestplayerdistance;
}


/*
================
SelectNextDeathmatchSpawnPoint

go to next deathmatch spawn point
================
* 1.803 - unused
edict_t *SelectNextDeathmatchSpawnPoint (void)
{
static edict_t *spot;

spot = NULL;

while ((spot = G_Find(spot, FOFS(classname), "info_player_deathmatch")) != NULL)
if (spot == NULL)
return NULL;

return spot;
}
*/
 
/*
================
SelectRandomJailSpawn

================
*/
edict_t *SelectRandomJailSpawn (edict_t* playr)
{
edict_t *spot, *spot1, *spot2;
int count = 0;
int selection;
float range, range1, range2;

spot = NULL;
range1 = range2 = 99999;
spot1 = spot2 = NULL;

while ((spot = G_Find(spot, FOFS(classname), "info_player_deathmatch")) != NULL)
{
if (spot->jail && (spot->teamnumber == playr->teamnumber || spot->teamnumber == 0))
count++;

range = PlayersRangeFromSpot(spot);

if (range < range1)
{
range1 = range;
spot1 = spot;
}
else if (range < range2)
{
range2 = range;
spot2 = spot;
}
}

if (!count)
return NULL;

if (count <= 2)
{
spot1 = spot2 = NULL;
}
else
count -= 2;

selection = (int)nu_rand(count);

spot = NULL;

do {
spot = G_Find(spot, FOFS(classname), "info_player_deathmatch");

//if (!spot->jail || (spot->teamnumber != playr->teamnumber && spot->teamnumber != 0))
if (spot == spot1 || spot == spot2 || !spot->jail || // 1.803
(spot->teamnumber != playr->teamnumber && spot->teamnumber != 0))
{
selection++;
}
} while(selection--);

return spot;
}


/*
================
SelectRandomDeathmatchSpawnPoint

go to a random point, but NOT the two points closest
to other players
================
*/
edict_t *SelectRandomDeathmatchSpawnPoint (void)
{
edict_t *spot, *spot1, *spot2;
int count = 0;
int selection;
float range, range1, range2;

spot = NULL;
range1 = range2 = 99999;
spot1 = spot2 = NULL;

while ((spot = G_Find(spot, FOFS(classname), "info_player_deathmatch")) != NULL)
{
if (spot->teamnumber < 128 && !spot->jail)
count++;

range = PlayersRangeFromSpot(spot);

if (range < range1)
{
range1 = range;
spot1 = spot;
}
else if (range < range2)
{
range2 = range;
spot2 = spot;
}
}

if (!count)
return NULL;

if (count <= 2)
{
spot1 = spot2 = NULL;
}
else
count -= 2;

selection = (int)nu_rand(count);

spot = NULL;

do {
spot = G_Find(spot, FOFS(classname), "info_player_deathmatch");

if (spot == spot1 || spot == spot2 || spot->teamnumber >= 128 || spot->jail)
selection++;
} while(selection--);

return spot;
}


/*
================
SelectFarthestDeathmatchSpawnPoint

================
*/
edict_t *SelectFarthestDeathmatchSpawnPoint (void)
{
  edict_t *bestspot;
  float bestdistance, bestplayerdistance;
  edict_t *spot;
 
  int i;
  // lets just end up using the first one thats further than 200 units from anyone else
 
  //self->client->resp.playermode & PMODE_ELIMINATED & PMODE_OBSERVER
  for (i = 1000; i > 50; i-=5)
  {
  spot = NULL;
  bestspot = NULL;
  bestdistance = i;
  while ((spot = G_Find (spot, FOFS(classname), "info_player_deathmatch")) != NULL)
  {
  bestplayerdistance = PlayersRangeFromSpot (spot);
 
// sadif (bestplayerdistance > i && bestplayerdistance > bestdistance + (rand() % i / 3))
  if (bestplayerdistance > i && bestplayerdistance > bestdistance +  (nu_rand(i) / 3))
  {
  bestspot = spot;
  bestdistance = bestplayerdistance;
  }
  }
 
  if (bestspot)
  {
  return bestspot;
  }
  }
  // if there is a player just spawned on each and every start spot
  // we have no choice to turn one into a telefrag meltdown
  spot = SelectRandomDeathmatchSpawnPoint();
 
  return spot;
}


// This will return the distance of the enemy that is closest to this spawn point
int ClosestEnemy (int teamnum, edict_t *spot)
{
  edict_t *player;
  float bestplayerdistance;
  vec3_t v;
  int n;
  float playerdistance;
 
  bestplayerdistance = 9999999;
 
  for (n = 1; n <= maxclients->value; n++)
  {
  player = &g_edicts[n];
 
  if (!player->inuse)
  continue;
 
  //if (player->health <= 0 || (player->client->resp.playermode & PMODE_ELIMINATED & PMODE_OBSERVER))
  if(!CanInteract(player)) // 1.74 - take jailers into account too?
  continue;
 
  if (player->teamnumber == teamnum)
  continue;
 
  VectorSubtract (spot->s.origin, player->s.origin, v);
  playerdistance = VectorLength (v);
 
  if (playerdistance < bestplayerdistance)
  {
  bestplayerdistance = playerdistance;
  }
  }
 
  return bestplayerdistance;
}


// DP
// This will make quake2 find the spawn point that is farthest from
// an enemy, if the closest enemy is within 512 units, otherwise it
// will return a random spawn point. If either of the spawnpoints is
// within 64 units of a teammate, it will just return a random spot,
// and will gib your teammate if it cant get a valid random one after
// 10 tries

edict_t *FindPBallSpawn(edict_t *self);
edict_t *SelectRandomPBSpawn (int teamnum);

edict_t *SelectFarthestDeathmatchTeamSpawnPoint (edict_t *self)
{
  edict_t *bestspot;
  edict_t *lastgoodspot;
  int i;
  bestspot = NULL;
  lastgoodspot = NULL;
  i = 0;

  // If we are playing, and it isnt just the respawnall command, lets
  // Check for enemy locations. It could be bad to do otherwise
  if (MatchIsRoundInProgress() && !IsChangeState())
  bestspot = FindPBallSpawn(self);

  // We want to use the farthest spawn from enemy if needed.
  // But we also need to have it more than 64 units from a teammember.
  // So lets check random spawns next, then make sure tehy are 64 units away
  if (!bestspot)
  bestspot = SelectRandomPBSpawn(self->teamnumber);

  if (bestspot)
  lastgoodspot = bestspot;
  else
  return lastgoodspot;
 
  while (PlayersRangeFromSpot(bestspot) <= 64 && i < 10)
  {
  bestspot = SelectRandomPBSpawn(self->teamnumber);
  i++;

  if (bestspot)
  lastgoodspot = bestspot;
  else
  return lastgoodspot;
  }
 
  return bestspot;
}


// Just pick a random spot for the right team. We'll circle outward for the next one
// if someone is too close
edict_t *SelectRandomPBSpawn (int teamnum)
{
edict_t *spot, *spot1, *spot2;
int count = 0;
int selection;
float range1, range2;

spot = NULL;
range1 = range2 = 99999;
spot1 = spot2 = NULL;

while ((spot = G_Find(spot, FOFS(classname), "info_player_deathmatch")) != NULL)
{
if (spot->teamnumber == teamnum && !spot->jail)
count++; // Only count the ones for the right team
}

if (!count)
return NULL;

selection = (int)nu_rand(count);
spot = NULL;

do
{
spot = G_Find(spot, FOFS(classname), "info_player_deathmatch");

if (!(spot->teamnumber == teamnum && !spot->jail))
selection++;
}
while (selection--);

return spot;
}


edict_t *FindPBallSpawn (edict_t *self)
{
edict_t *bestspot;
float bestdistance, bestplayerdistance;
edict_t *spot;
int closest;

spot = NULL;
bestspot = NULL;
bestdistance = 0;
closest = 9999999;

while ((spot = G_Find (spot, FOFS(classname), "info_player_deathmatch")) != NULL)
{
if (spot->teamnumber != self->teamnumber || spot->jail)
continue;

bestplayerdistance = ClosestEnemy (self->teamnumber,spot);

if (bestplayerdistance <= closest)
closest = bestplayerdistance;
if (bestplayerdistance >= bestdistance)
{
bestspot = spot;
bestdistance = bestplayerdistance;
}
}
if (closest < 512 && bestspot) {
// If there is a guy within 512 units of a spawn point for our team...
// we want to use the farthest away spawn point.
return bestspot;
}
return NULL;

// spot = G_Find (NULL, FOFS(classname), "info_player_deathmatch");
}


edict_t *SelectDeathmatchSpawnPoint (edict_t *self)
{
// DP SPOT
edict_t *spot;

if (self->client->resp.playermode & PMODE_OBSERVER)
{
spot = SelectRandomDeathmatchSpawnPoint();
}
//else if (ctftype == CTFTYPE_DM)
else if (!GameIsTeamsGame()) // 1.803
{
spot = SelectRandomDeathmatchSpawnPoint();
}
else if (self->client->resp.playermode & PMODE_JAILED)
{
spot = SelectRandomJailSpawn(self);
}
else
{
spot = SelectFarthestDeathmatchTeamSpawnPoint(self);

if (!spot || spot->teamnumber != self->teamnumber)
spot =  SelectRandomDeathmatchSpawnPoint();
}

if (!spot) // 1.803, for debugging
{
gi.dprintf("ERROR: couldn't find spawn for: %s, team: %s, jailed: %s, mode: %s\n",
self->client->pers.netname, TeamsGetName(TeamsGetTeam(self)),
(self->client->resp.playermode & PMODE_JAILED) ? "yes" : "no",
GameIsTeamsGame() ? "team" : "DM");
}

return spot;

// return SelectNextDeathmatchSpawnPoint();

// ENDDP
}


Code: [Select]

/*
==========
SelectSpawnPoint

Chooses a player start, deathmatch start, coop start, etc
============
*/
void SelectSpawnPoint (edict_t *ent, vec3_t origin, vec3_t angles)
{
edict_t *spot = NULL;
edict_t* chain;
 
spot = SelectDeathmatchSpawnPoint(ent);

/* 1.803
// find a single player start spot
if (!spot)
{
while ((spot = G_Find (spot, FOFS(classname), "info_player_start")) != NULL)
{
if (!game.spawnpoint[0] && !spot->targetname)
break;
if (!game.spawnpoint[0] || !spot->targetname)
continue;
if (Q_strcasecmp(game.spawnpoint, spot->targetname) == 0)
break;
}

if (!spot)
{
if (!game.spawnpoint[0])
{ // there wasn't a spawnpoint without a target, so use any
spot = G_Find (spot, FOFS(classname), "info_player_start");
}
if (!spot)
gi.error ("Couldn't find spawn point %s\n", game.spawnpoint);
}
}*/

if (!spot) // 1.803
{
// unable to find a proper spawn point, so just use whatever.
spot = G_Find(spot, FOFS(classname), "info_player_start");

if (!spot)
spot = G_Find(spot, FOFS(classname), "info_player_deathmatch");

if (!spot)
gi.error ("Couldn't find spawn point %s\n", game.spawnpoint);
}

chain = spot;

for(chain = spot; chain->previousowner != NULL && chain->previousowner != chain; chain = chain->previousowner)
{ } // NULL SET (everything done in for statement

// SPAWN WITH WEAPONS CODE - I made it so it creates a chain of PREVIOUSOWNERS
// this way i can have as many people as I want spawn in the same spawnpoint at
// the exact same instant
chain->previousowner = ent;
chain->think = SpawnSpecialEnts;
chain->nextthink = level.time + 0.1f;
ent->previousowner   = NULL; // Fix for endless loop

VectorCopy(spot->s.origin, origin);
origin[2] += 1;
VectorCopy(spot->s.angles, angles);
}


[Apocalypse]

I like the idea XBain I hope it can be implemented.

[Eiii]

I don't really think the spawn code needs any revisiting. Of course you're going to get some crappy spawns every once in a while, but the other team is too. Things aren't always exactly even, as you mentioned with your carbine/spyder example. It's not like those are the spawns for the entirety of the match, though- it's just an unlucky spawn.

Luck is a part of this game, to some extent. Spawning, ball flight, equipment (in some maps). I think what you propose is both unneeded and too complex.

[ch40s]

Luck might be a part of the game, but spawning shouldn't involve it. Clearly this would only benefit game play, especially in scrimmage or match situations.

[Eiii]

Luck might be a part of the game, but spawning shouldn't involve it.

Why not? Knowing exactly (or near-exactly) where everyone's going to spawn makes it far too easy to just use one concrete strategy for a map- I think being able to think on your feet is something that should be encouraged.

(Argument 2: Shooting's much more of a core part of the game than spawning is, but (depending on how good a barrel you have/the range you're at) it can be very random.)

[XtremeBain]

After taking a look through that code, I've noticed a few problems.  I think I have a decent solution, but I'm betting it will cause problems with some non-competition maps.  So I think that it should be made into a cvar (and that cvar can be enabled in the matchmode config by default).

I'm only touching the initial round start spawning, the mid-round spawning is good enough.  The problem is that the spawn code now cares the most about where our enemies are spawning, not so much where are teammates spawn.  I just did a little hacking to have it seek the best spawns for each team regardless of where the enemies are spawning.

Let me know what you think.

Code: [Select]

// XB Start
cvar_t *g_competitionspawns;
g_competitionspawns = Cvar_Get("g_competitionspawns", "0", 0);

// This will return the distance of the teammate that is closest to this spawn point
int ClosestTeammate (int teamnum, edict_t *spot)
{
  edict_t *player;
  float bestplayerdistance;
  vec3_t v;
  int n;
  float playerdistance;
 
  bestplayerdistance = 9999999;
 
  for (n = 1; n <= maxclients->value; n++)
  {
  player = &g_edicts[n];
 
  if (!player->inuse)
  continue;
 
  if(!CanInteract(player)) // 1.74 - take jailers into account too?
  continue;
 
  if (player->teamnumber != teamnum) // Skip enemies
  continue;
 
  VectorSubtract (spot->s.origin, player->s.origin, v);
  playerdistance = VectorLength (v);
 
  if (playerdistance < bestplayerdistance)
  {
  bestplayerdistance = playerdistance;
  }
  }
 
  return bestplayerdistance;
}

edict_t *FindBestTeamPBallSpawn (edict_t *self)
{
edict_t *bestspot;
float bestdistance, bestplayerdistance;
edict_t *spot;
int closest;

spot = NULL;
bestspot = NULL;
bestdistance = 0;

while ((spot = G_Find (spot, FOFS(classname), "info_player_deathmatch")) != NULL)
{
if (spot->teamnumber != self->teamnumber || spot->jail)
continue;

bestplayerdistance = ClosestTeammate (self->teamnumber,spot);

if (bestplayerdistance >= bestdistance)
{
bestspot = spot;
bestdistance = bestplayerdistance;
}
}
if (bestdistance < 64) {
// If there is a teammate within 64 units of us we'll settle for a random spawn
return NULL;
}
return bestspot;
}
//XB End

edict_t *SelectFarthestDeathmatchTeamSpawnPoint (edict_t *self)
{
  edict_t *bestspot;
  edict_t *lastgoodspot;
  int i;
  bestspot = NULL;
  lastgoodspot = NULL;
  i = 0;

  // If we are playing, and it isnt just the respawnall command, lets
  // Check for enemy locations. It could be bad to do otherwise
  if (MatchIsRoundInProgress() && !IsChangeState())
  bestspot = FindPBallSpawn(self);

  // XB Start
  // If the server admin wants good spawns, we'll find the best one.
  if (!bestspot && g_competitionspawns->value)
  bestspot = FindBestTeamPBallSpawn(self);
  // XB End

  // We want to use the farthest spawn from enemy if needed.
  // But we also need to have it more than 64 units from a teammember.
  // So lets check random spawns next, then make sure tehy are 64 units away
  if (!bestspot)
  bestspot = SelectRandomPBSpawn(self->teamnumber);

  if (bestspot)
  lastgoodspot = bestspot;
  else
  return lastgoodspot;
 
  while (PlayersRangeFromSpot(bestspot) <= 64 && i < 10)
  {
  bestspot = SelectRandomPBSpawn(self->teamnumber);
  i++;

  if (bestspot)
  lastgoodspot = bestspot;
  else
  return lastgoodspot;
  }
 
  return bestspot;
}
It still needs testing but I'm sure it'll yield much better spawns in most maps.

[Herron]

Knowing exactly (or near-exactly) where everyone's going to spawn makes it far too easy to just use one concrete strategy for a map- I think being able to think on your feet is something that should be encouraged.

I agree 100%.  Besides, spawning in the same place every time would be mindnumbingly monotonous and potentially lock you into only one gun choice.  For example, let's assume sandtrap has 10 spawn points with spawn point 1 being by the flag and spawn point 10 being near the crates at the base entrance.  In a 2v2 game, one person always gets stuck with whatever that front gun is, while the one in the back always gets a mag/cocker.  Sure the person up front could turn around and go up into the tower for a new gun, but he loses precious time in the process.  Furthermore, he knows exactly where the other players are and it becomes a race between the two players spawning in their respective team's 10 spot to get out from behind the crate and spray the exact same point every single round.  There is no longer any excitement in rushing with the front gun and wondering if you're going to get clobbered as soon as you step foot into the middle or whether you're going to make it all the way to the steps of their base before you even see an enemy.  Yes you have predictability and equality, but at the huge cost (in my mind) of BORING.

I am, however, a fan of decreasing the amount of times people spawn on or inside of each other.

[jitspoe]

I can throw this in for the next version and we'll see what it does.  There are several things I'd like to do with the spawning when I have the chance:

a) If there aren't enough spawns, shift the spawn points over so people spawn next to, instead of inside of, other players.
b) Avoid spawning people in another person's crosshairs.  The way the spawn furthest code currently works, if you have an enemy in one side of your base, they can just sit and spray the other side of the base and people will continue to spawn to their death on the far side repeatedly.  I'd almost like to make it so people will spawn behind or on top of spawn campers (ie, if somebody is sitting in one spot and kills someone immediately after they spawn, the next spawn would be place directly behind them, if possible).

[KnacK]

a. Is there the capability of the engine to define a spawn area instead of a spawn point?  That might give some flexibility.

b. Spawn killing only really happens on speed servers.  I really wouldn't worry about that issue.

[XtremeBain]

a. Is there the capability of the engine to define a spawn area instead of a spawn point?  That might give some flexibility.

Me and S8N were sort've just discussing this.  I'm thinking it can be an entity that mappers would add or that we could place in an .ent for existing maps.

[jitspoe]

I think the best thing to do is just add more spawn points.  Trying to do something like a spawn area would make things more complicated than necessary.  Perhaps the game could dynamically clone and offset spawn points when there are more players than spawns.

* jitspoe thinks knack needs to stop typing with his cane.

[KnacK]

FIXED!

[Magical-Tree]

I think the best thing to do is just add more spawn points.  Trying to do something like a spawn area would make things more complicated than necessary.  Perhaps the game could dynamically clone and offset spawn points when there are more players than spawns.

* jitspoe thinks knack needs to stop typing with his cane.

Wouldn't there then be an issue about people spawning in walls, etc.



~MT

[jitspoe]

MT - it would scan for solid objects first.

Bain: I tried your code.  There's a problem with it, though.  When it's scanning for the "best" location, if there are no other players present, the best distance is always 999999 or whatever, so the first player spawns in the same spot every single round.

[XtremeBain]

Code: [Select]

if (bestdistance < 64 || bestdistance == 9999999) {
// If there is a teammate within 64 units of us or this is first player to spawn we'll settle for a random spawn
return NULL;
}

[jitspoe]

You should know better than to do an equality compare on floating point numbers.   It'll probably still work in this case, though.

Edit: Nevermind, it's an int, but it's still kind of a bad idea to assume ClosestTeammate will return 9999999 when no teammates are present.

[Eiii]

Null FTW.

[jitspoe]

I made ClosestTeammate return 0 if no teammates are around, but discovered another problem: CanInteract() doesn't return true for any clients during the spawn process, so effectively, it doesn't make any difference - everybody just spawns randomly.  That also explains why people spawn inside of each other when there are other spawn points available with the current code.