koobas.hobune.stream
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 :)
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")[i].GetComponent<PlayerControllerBackup>().teamnum==1)
{
if(Distance(GameObject.FindGameObjectsWithTag("Player")[i].transform.position,transform.position)<closestDistanceTeam1)
{
closestDistanceTeam1=Distance(GameObject.FindGameObjectsWithTag("Player")[i].transform.position,gameObject.transform.position);
}
}
else if(GameObject.FindGameObjectsWithTag("Player")[i].GetComponent<PlayerControllerBackup>().teamnum==2)
{
if(Distance(GameObject.FindGameObjectsWithTag("Player")[i].transform.position,transform.position)<closestDistanceTeam2)
{
closestDistanceTeam2=Distance(GameObject.FindGameObjectsWithTag("Player")[i].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>().text = currentHealth.ToString();
if(dead)
{
timer += Time.deltaTime;
if(timer >= deathTime)
{
timer = 0.0f;
gameObject.GetComponent<PlayerControllerBackup>().ResetAmmo();
CmdResetHealth();
RpcRespawn();
GameObject.Find("Ammo Count").GetComponent<Text>().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<PlayerControllerBackup>().teamnum==1)
{
GameObject.Find("Game Controller").GetComponent<GameController>().CmdIncreaseScore(2);
}
else if(gameObject.GetComponent<PlayerControllerBackup>().teamnum==2)
{
GameObject.Find("Game Controller").GetComponent<GameController>().CmdIncreaseScore(1);
}
}
}
[ClientRpc]
public void RpcRespawn()
{
if(!isLocalPlayer)
{
return;
}
distance = 0.0f;
spawnPosition = Vector3.zero;
for(int i = 0; i<GameObject.FindObjectsOfType<NetworkStartPosition>().Length; i++)
{
GameObject.FindObjectsOfType<NetworkStartPosition>()[i].gameObject.GetComponent<ClosestPlayerDistances>().SetDistances();
if(gameObject.GetComponent<PlayerControllerBackup>().teamnum==1)
{
if(GameObject.FindObjectsOfType<NetworkStartPosition>()[i].gameObject.GetComponent<ClosestPlayerDistances>().closestDistanceTeam2>distance)
{
distance = GameObject.FindObjectsOfType<NetworkStartPosition>()[i].gameObject.GetComponent<ClosestPlayerDistances>().closestDistanceTeam2;
spawnPosition = GameObject.FindObjectsOfType<NetworkStartPosition>()[i].transform.position;
}
}
else if(gameObject.GetComponent<PlayerControllerBackup>().teamnum==2)
{
if(GameObject.FindObjectsOfType<NetworkStartPosition>()[i].gameObject.GetComponent<ClosestPlayerDistances>().closestDistanceTeam1>distance)
{
distance = GameObject.FindObjectsOfType<NetworkStartPosition>()[i].gameObject.GetComponent<ClosestPlayerDistances>().closestDistanceTeam1;
spawnPosition = GameObject.FindObjectsOfType<NetworkStartPosition>()[i].transform.position;
}
}
}
transform.position = spawnPosition;
}
[Command]
private void CmdResetHealth()
{
if(!isServer)
{
return;
}
currentHealth = maxHealth;
dead = false;
}
}
@Integrational I've spent over an hour looking at your code and finally gave up! I'll try to be creative with my comments here, so please don't misunderstand me, I'm writing everything in a direct way, which you might not like, but I mean well.
The thing is, that your code is so unoptimized that my head almost exploded trying to follow it!
And you have no comments at all! The more comments you add to your code, the better chances you have for someone to help you, because it makes the code easier to read. It also helps you when you return to your code after, say, 3-6 months.
Having said that, here's what I think:
Your algorithm seems fine.
You should cache components that you use frequently. This is a good way to optimize the code and performance, and it will also make it much more easy to read.
So, I managed to read the code and haven't found anything wrong with it per se. In other words, it reflects the algorithm quite well.
Therefore, the problem is hidden somewhere in the unoptimized code, e.g. you're calling GameObject.FindObjectsOfType and FindGameObjectsWithTagas much as you can! This not only slows up the performance, but it complicates things... what would happen if you got one set of results the first time you call it in your loop, another set of results a few lines of code down, and different sets of results subsequently... (maybe that's where the problem is...)
So, I believe that the most important thing to do is optimize the code by caching components.
e.g. in the ClosestPlayerDistances script:
private GameObject[] players;
public void SetDistances()
{
players = GameObject.FindGameObjectsWithTag("Player"); //cache
for(int i = 0; i<players.Length; i++)
{
if(players[i].GetComponent<PlayerControllerBackup().$$anonymous$$mnum==1)
{
if(Distance(players[i].transform.position,transform.position)<closestDistanceTeam1)
{
closestDistanceTeam1=Distance(players[i].transform.position,gameObject.transform.position);
}
}
// etc...
}
}
In the Health script:
public class Health : NetworkBehaviour {
private GameObject[] spawnPoints;
//etc...
public void RpcRespawn()
{
if(!isLocalPlayer)
{
return;
}
spawnPoints = GameObject.FindObjectsOfType<NetworkStartPosition>(); //cache
distance = 0.0f;
spawnPosition = Vector3.zero;
for(int i = 0; i<spawnPoints.Length; i++)
{
ClosestPlayerDistances closestDistances = spawnPoints[i].gameObject.GetComponent<ClosestPlayerDistances>() ; //cache
closestDistances.SetDistances();
if(gameObject.GetComponent<PlayerControllerBackup>().$$anonymous$$mnum==1)
{
if(closestDistances.closestDistanceTeam2>distance)
{
distance = closestDistances.closestDistanceTeam2;
spawnPosition = spawnPoints[i].transform.position;
}
}
//etc...
}
}
}
These are examples, and more components can be cached.
Additionally, I believe it would be better (more performant) to use Vector3.sqr$$anonymous$$agnitude for distance comparison purposes, rather than the Distance method. Of course you'd need to declare the initial values of closestDistanceTeam1/2 to something much bigger, say 1,000,000 or even 10,000,000.
So, maybe you should edit your question and replace the existing code for optimized code, and maybe add some comments ;-)
Hope these help.
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;
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.
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 ;)
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 ^^.
