Algorithm to choose optimal spawn position

I’ve been making a 2-team deathmatch networked shooter, and am almost done. I’ve tried to make an algorithm for this, but i’ve been seeing some errors and cannot find out where the bugs are. What I want is this:

An algorithm that cycles through all existing NetworkStartPositions, and gives you the position of the network start position farthest from an enemy, so the player may respawn. How I thought it would go is:
-For loop cycles through all spawn points
-Then cycles through all enemy players within that for loop
-Finds the closest enemy player to each individual spawn point, and saves it in a script component attached to each gameobject holding a networkstartposition component
-Compares those distances to find the farthest one to any spawn point (essentially the farthest closest player, haha)
-Takes the transform.position of the spawn point with the largest number from this algorithm
-Sets the player transform.position to that Vector3

The main bug is that players can respawn in the same spot over and over again despite there being clearly more optimal positions, and sometimes will respawn somewhere and instantly move somewhere completely different once they begin to walk (Although I believe the 2nd one might be caused by networking issues, the main one is the first problem)

I cannot find out whether or not the issue is my code or the algorithm, so I would like it if someone could either edit my code or write a new algorithm, thanks in advance :slight_smile:

Script Attached to NetworkStartPosition GameObjects:

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.Networking;

public class ClosestPlayerDistances : NetworkBehaviour {

	public float closestDistanceTeam1 = 1000.0f;
	public float closestDistanceTeam2 = 1000.0f;

	public void SetDistances()
	{

		for(int i = 0; i<GameObject.FindGameObjectsWithTag("Player").Length; i++)
		{

			if(GameObject.FindGameObjectsWithTag("Player")*.GetComponent<PlayerControllerBackup>().teamnum==1)*
  •  	{*
    

_ if(Distance(GameObject.FindGameObjectsWithTag(“Player”).transform.position,transform.position)<closestDistanceTeam1)_
* {*

_ closestDistanceTeam1=Distance(GameObject.FindGameObjectsWithTag(“Player”).transform.position,gameObject.transform.position);
* }
}
else if(GameObject.FindGameObjectsWithTag(“Player”).GetComponent().teamnum==2)
{*_

_ if(Distance(GameObject.FindGameObjectsWithTag(“Player”).transform.position,transform.position)<closestDistanceTeam2)
* {*_

_ closestDistanceTeam2=Distance(GameObject.FindGameObjectsWithTag(“Player”).transform.position,gameObject.transform.position);
* }
}
}
}*_

* private float Distance(Vector3 first, Vector3 second)*
* {*

* return(Mathf.Sqrt(Mathf.Pow(first.x-second.x,2)+Mathf.Pow(first.y-second.y,2)+Mathf.Pow(first.z-second.z,2)));*
* }*
}
Health / Respawn Script:
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.Networking;
using UnityEngine.UI;

public class Health : NetworkBehaviour {

* public const int maxHealth = 200;*

* [SyncVar]*
* public int currentHealth = maxHealth;*
* [SyncVar]*
* public bool dead = false;*
* public float deathTime = 3.0f;*

* private float distance = 0.0f;*
* private Vector3 spawnPosition;*
* private float timer = 0.0f;*

* void Update()*
* {*

* if(!isLocalPlayer)*
* {*

* return;*
* }*

* GameObject.Find(“Health Count”).GetComponent().text = currentHealth.ToString();*

* if(dead)*
* {*

* timer += Time.deltaTime;*
* if(timer >= deathTime)*
* {*

* timer = 0.0f;*
* gameObject.GetComponent().ResetAmmo();*
* CmdResetHealth();*
* RpcRespawn();*
* GameObject.Find(“Ammo Count”).GetComponent().text = (“20/20”);*
* }*
* }*
* }*

* [Command]*
* public void CmdTakeDamage(int amount)*
* {*

* if(!isServer)*
* {*

* return;*
* }*

* if(currentHealth>0)*
* {*

* currentHealth -= amount;*
* }*

* if(currentHealth <= 0 && !dead)*
* {*

* currentHealth = 0;*
* dead = true;*
* if(gameObject.GetComponent().teamnum==1)*
* {*

* GameObject.Find(“Game Controller”).GetComponent().CmdIncreaseScore(2);*
* }*
* else if(gameObject.GetComponent().teamnum==2)*
* {*

* GameObject.Find(“Game Controller”).GetComponent().CmdIncreaseScore(1);*
* }*
* }*
* }*

* [ClientRpc]*
* public void RpcRespawn()*
* {*

* if(!isLocalPlayer)*
* {*

* return;*
* }*

* distance = 0.0f;*
* spawnPosition = Vector3.zero;*
* for(int i = 0; i<GameObject.FindObjectsOfType().Length; i++)*
* {*

_ GameObject.FindObjectsOfType().gameObject.GetComponent().SetDistances();_

* if(gameObject.GetComponent().teamnum==1)*
* {*

_ if(GameObject.FindObjectsOfType().gameObject.GetComponent().closestDistanceTeam2>distance)
* {*_

_ distance = GameObject.FindObjectsOfType().gameObject.GetComponent().closestDistanceTeam2;
spawnPosition = GameObject.FindObjectsOfType().transform.position;
* }
}
else if(gameObject.GetComponent().teamnum==2)
{*_

_ if(GameObject.FindObjectsOfType().gameObject.GetComponent().closestDistanceTeam1>distance)
* {*_

_ distance = GameObject.FindObjectsOfType().gameObject.GetComponent().closestDistanceTeam1;
spawnPosition = GameObject.FindObjectsOfType().transform.position;
* }
}
}
transform.position = spawnPosition;
}*_

* [Command]*
* private void CmdResetHealth()*
* {*

* if(!isServer)*
* {*

* return;*
* }*
* currentHealth = maxHealth;*
* dead = false;*
* }*
}

Don’t get me wrong but honestly, if you want someone to write a complete algorithm for you, you should pay that person. Still I want to help so here is some suggestions;


  1. Clean up your code! Your functions are pretty long and hard to read, you’ll make your life easier if you divide the problem you are trying to solve into smaller functional pieces. For example: Add a method FindSpawnpoints() that does only that. Inside that function you could loop trough all the existing spawnpoints, call another method ValidateSpawnpoint(spawnpoint) that returns true or false and depending on that add spawnpoints to your result list.
  2. Start debugging. With functions like Debug.DrawRay() and Debug.Break() you can easily pause the execution and visualize your results. The first thing I’d do to figure out why the spawn positions are weird is outputting each of them using Debug.DrawRay(). That will give you an exact overview over where these valid spawnpoints actually are within your scene.

Here’s some pseudo:

protected NetworkStartPosition[] FindSpawnpoints() {
    var result = new List<NetworkStartPosition>();
    var all = GameObject.FindObjectsOfType<NetworkStartPosition>();

    foreach (var spawnpoint in all) {
        if (ValidateSpawnpoint(spawnpoint)) {
            result.Add(spawnpoint);

            // TODO this line is for visualization, you can remove it later:
            Debug.DrawRay(spawnpoint.transform.position, Vector3.up * 10f, Color.red, 10f);
        }
    }

    return result.toArray();
}

protected bool ValidateSpawnpoint(NetworkStartPosition spawnpoint) 
{
    // TODO Return true if the specified spawnpoint can be used ...

    return false;
}

Try applying that to your code to figure out if your determined spawnpoints are correct. If so, move on to the next piece of logic and debug that. If you still can’t fix it for a more specific reason, come back here and report back, the community will help you with pleasure but doing your “homework” is your job :wink:

I don’t see a concrete error besides the painfully inefficient use of “FindGameObjectsWithTag”, “FindObjectsOfType” and that “Distance” method. Also the general structure should be refactored. First of all the selection of the spawn point should be done on the server however you do it in an ClientRPC. This makes no sense and would only work if you actually have a “Host” (Client and Server combined). It shouldn’t work with a dedicated server as ClientRPCs are ment to execute on the clients.

Next thing is your TakeDamage command has no sanity checks. So a client can simply apply any damage he likes to any player he likes whenever he likes. In short: a paradise for cheaters.

You should handle the respawning in a single method on the server. So the reset of the player as well as the choosing of the spawn point should be in the same method.

FindGameObjectsWithTag is quite slow. It also allocates an array for the results. You call it several times for each player (up to 4 times per player). Each time you allocate a new array. This results in a ton of garbage memory (with 16 players it would create at least 48 arrays; worst case: 64 arrays; each array containing the 16 player references). Note that you perform this for every spawn point.

In a multiplayer game like this you should have some kind of manager where you track all active player objects. When a player is spawned / created you would simply add him to a players list. Also you want to use a List<PlayerControllerBackup> and directly store the component so you don’t have to get the component all the time.

Likewise your "NetworkStartPosition"s are static data for the current level. You should get the list of spawn points once at level start and store them in an array or list. Even if you prefer to get the array of spawn points again every time you need them you should still only store the array once in a local variable before the loop.

Finally your Distance method does just reinvent the wheel in a less performant way. Mathf.Pow(x,2) is kess performant than x*x. Also Unity already has a Distance method which does exactly the same as yours. Though when it comes to comparing distances you usually just compare the squared distances to avoid the square root.

One of your problems is probably that you do not reset your two distance variables (closestDistanceTeam1 and closestDistanceTeam2) before you iterate through your players. Also you shouldn’t use “1000”. Use float.PositiveInfinity. Nothing is larger than that ^^.