koobas.hobune.stream
How do I efficiently maintain a constantly-changing list without triggering GC?
My foot traffic simulator needs a list of currently active Spawner objects in the world, such that each tick it can select a random spawner, move an NPC from the pool to that location, and path it to another active spawner in the world.
My world is broken up into chunks that load in and out of memory as the player draws near, so my plan is to give each spawner a chunk of code that "registers" it with the master simulator on OnEnable(), and "unregisters" it with OnDisable(). My first thought is to create a List activeSpawners, and simply say
OnEnable(){
activeSpawners.Add(gameObject);
}
OnDisable(){
activeSpawners.Remove(gameObject);
}
However, this could potentially happen several times per second as the player moves around, and I know that doing lots and lots of list manipulation can kill performance, so I'm wondering if this is a foolhardy implementation, or if there's a faster way to accomplish the same thing?
you can maintain a pool of game objects to avoid adding/removing, but you really need to profile your code to find out where the real issues are. premature optimization is often the biggest killer of performance.
with a pool, you'll need to check whether each element is active which may end up being more expensive... again, profile it!
obviously, ymmv :)
$$anonymous$$eep a pool of disabled stuff or enabled stuff I suppose, and an array of bool values like "activePoolObjects" and set the bool to match the objects state when enabled or disabled. Then loop through the bool array to avoid looping and checking for active in each object. I figure the performance would possibly be better than a list being added and removed from... Depending on usage. Then again maybe I'm misunderstanding. Good luck!
That's an interesting idea... so you're saying maintain two side-by-side lists, one of type Spawner and one of type Bool, so I only have to iterate through the Bool list ins$$anonymous$$d of doing a getcomponent and retaining a value for each index? That seems very spiffy... how would I retain an association between the two lists? I'm slightly uncomfortable just building them in tandem and using the index, as any number of things could offset one list and make the entire system go wacky.
On the same note, how would I check this association during state changes? None of the spawners know what their index is when they message the simulation with their state change and the new Bool value, but I want to avoid iterating through the list to make a match.
I'd prefer this to be a comment but its a little long, so just to build on what @MD_Reptile was saying, you could create a class for your spawner so that you could keep the gameobject, active state and index all linked together, that way you could just have a list of that class and read from it whether a spawner object was active or not nice and quickly, as @gjf mentioned though, you should really do some profiling first as you might be gaining nothing from all this!
An example spawner class
public class Spawner {
GameObject go;
Transform t;
int i;
bool b;
public Spawner(GameObject g, int ind){
go = g;
t = g.transform;
i = ind;
b = g.activeSelf;
}
public void SetActive(bool a){
go.SetActive(a);
b = a;
}
public string ToString(){
return "Name: " + go.name + "\nIndex " + i + "\n" + (b ? "Active\n" : "Inactive\n");
}
public GameObject gameObject{
get{ return go; }
set {
go = value;
t = value.transform;
}
}
public Transform transform{
get{ return t; }
set {
t = value;
go = value.gameObject;
}
}
public int index{
get{ return i; }
set { i = value; }
}
public bool active{
get{ return b; }
set { b = value; }
}
}
Some examples of usage!
public GameObject[] gos;
Spawner[] spawnObjs;
bool a = false;
void Start () {
spawnObjs = new Spawner[gos.Length];
for(int i = 0; i < gos.Length; i++){
spawnObjs[i] = new Spawner(gos[i], i);
}
}
void Update () {
if(Input.GetKeyDown(KeyCode.Q)){
SetAllActive(spawnObjs, a);
a = !a;
}
if(Input.GetKeyDown(KeyCode.Alpha1) && spawnObjs.Length > 0){
spawnObjs[0].SetActive(!spawnObjs[0].active);
}
if(Input.GetKeyDown(KeyCode.Alpha2) && spawnObjs.Length > 1){
spawnObjs[1].SetActive(!spawnObjs[1].active);
}
if(Input.GetKeyDown(KeyCode.Alpha3) && spawnObjs.Length > 2){
spawnObjs[2].SetActive(!spawnObjs[2].active);
}
if(Input.GetKeyDown(KeyCode.Alpha4) && spawnObjs.Length > 3){
spawnObjs[3].SetActive(!spawnObjs[3].active);
}
}
void SetAllActive(Spawner[] s, bool b){
for(int i = 0; i < s.Length; i++){
s[i].SetActive(b);
Debug.Log(s[i].ToString());
}
}
EDIT: Some tests and another example!
So to be honest I can't really answer the question you posed in the comments very easily without knowing your current set-up or your final exact goals, one main thing to think about is that from my quick tests, density of spawn points has a much larger impact on performance than number of spawn points.
I don't know much about the efficiency of using triggers, I did a few tests and the problem I was finding with a trigger set-up was as soon as the density of spawn points got past a certain point I would get the error "Internal error: Too many pairs created, new pairs will be ignored. This is perhaps due to an excessive number of objects created at one location." - Not good, this is a consistently reproducible error for me when spawning 5000 spawn points in a 1000 radius circle around the player.
Important note: this could simply be because I am creating the spawn points in this test at random locations within this circle, possibly if predefined locations were used then you would not get this error due to the second part of it "This is perhaps due to an excessive number of objects created at one location."
If you are staying in the low thousands of spawn points you may not have this problem however for completeness I also tried a second method which appears to work far more consistently but is likely to only be useful under certain circumstances:
This method actually involves calculating the distance between the player and each spawn point which sounds horrendous when you say you have thousands of spawn points, but the efficiency is increased a lot if you know the maximum speed your character can travel per second. Basically, each spawn point is created and then a Coroutine is started for each spawn point, so we now have a few thousand coroutines running checking the distance between a spawn point and the player, however if you know the maximum speed the player can travel, then if a spawn point is 100 units from the players activation radius and you know the player can only travel at 10 units per second, then you know for certain that you don't need to call that coroutine function again for a minimum of 10 seconds (100/10). What this means is you can have loads and loads of spawn points and if you know a maximum speed and your activation distance, then most of those thousands of coroutines will only be called once every 10, 20, 30 seconds!
Using this second method I didn't get any errors and managed to get to get 50,000 spawn points in a 1000 radius circle with an active range of 100 (they become active if they are closer than 100 units from the player) whilst maintaining a solid 40-60fps on my 4 year old laptop. My test code to follow (My prefab object was a gameobject with only a cube mesh filter and mesh renderer attached):
public GameObject prefab;
public float activeDistance = 100;
public float maxSpawnedDistance = 1000;
public int instances = 50000;
public float maxSpeed = 10;
Spawner[] spawnObjs;
Vector2 v2;
GameObject go;
Spawner spawn;
Transform trans;
public float minTimeGap = 0.25f;
Vector3 v3;
GameObject spawnParent;
public float fps;
void Start () {
trans = this.transform;
activeDistance = Mathf.Abs(activeDistance);
maxSpawnedDistance = Mathf.Abs(maxSpawnedDistance);
instances = Mathf.Max(instances, 0);
maxSpeed = Mathf.Max(maxSpeed, 1);
minTimeGap = Mathf.Max(minTimeGap, 0.1f);
if(prefab == null){
Debug.LogError("No prefab has been assigned");
}else{
Init();
}
}
void Update () {
fps = 1/Time.deltaTime;
v3 = trans.position;
v3.x += Input.GetAxis("Horizontal")*maxSpeed*Time.deltaTime;
v3.z += Input.GetAxis("Vertical")*maxSpeed*Time.deltaTime;
trans.position = v3;
}
void Init(){
spawnParent = new GameObject();
spawnParent.name = "Spawn Object Parent";
spawnObjs = new Spawner[instances];
for(int i = 0; i < instances; i++){
v2 = Random.insideUnitCircle*maxSpawnedDistance;
go = Instantiate(prefab, new Vector3(v2.x, 0, v2.y), Quaternion.identity) as GameObject;
go.transform.parent = spawnParent.transform;
spawn = new Spawner(go, i);
spawnObjs[i] = spawn;
StartCoroutine(CheckDist(spawn));
}
}
IEnumerator CheckDist(Spawner s){
while(true){
float diff = (s.transform.position-trans.position).magnitude-activeDistance;
if(diff > 0){
s.SetActive(false);
}else{
s.SetActive(true);
diff *= -1;
}
yield return new WaitForSeconds(Mathf.Max(diff/maxSpeed, minTimeGap));
}
}
This way all (I think) memory allocation is done in the Start method, and you will never get indexes mixed up between boolean states and gameobjects, you could add a lot more functionality to the class for example I have added the ToString function to quickly get a nicely formatted string of some of the variables contained! You could even add a script to each spawner gameobject with a reference variable to its own instance of the Spawner class so that you could find which spawner object it was from a raycast or similar!
I hope that helps :D
Scribe
Holy cow, this is incredibly comprehensive and solves all of my problems at once- thank you for taking the time and effort to explain this, Scribe! You're awesome :)
This might be a silly question, but do you know if there's a major performance overhead on trigger colliders? I'm thinking of managing my SetActive() calls based on the spawner entering and exiting the player's PedestrianCollider trigger collider, but there will ultimately be hundreds or (low) thousands of spawners throughout the world, and I don't want to set up something awesome now that absolutely cripples performance when it scales up.
I'm glad you found it useful! and thank you for marking it as accepted, it is much appreciated :D have fun coding!
Coding is always fun, I'll be sure to enjoy it :)
@Sendatsu_Yoshimitsu:
You've missed an important point: The class "Spawner" isn't derived from $$anonymous$$onoBehaviour ;)
A generic list will not produce any garbage as long as you set the capacity large enough to hold all instances. Adding (as long as there's enough capacity left) and removing items is also very efficient depending on which method you use. Adding / removing at the back of the list doesn't require any CPU power since all it does is setting the internal array element and increasing the count or setting the array element to null and decreasing the count. Only adding (inserting) and removing in the middle or at the beginning requires some work as all elements that follow has to be copied to a new location. But again, as long as the capacity is large enough it won't produce any garbage.
Make sure you use list.Add and list.RemoveAt(list.Count-1) for your pooling. So always add and remove at the back. The usual approach is to have two lists like others have already mentioned. However if the pooled objects have some kind of management script attached that's not really necessary. Since an object pool contains several instances of the same object type it doesn't matter which one you use next.
Another way that doesn't even requires a list is to use a simplified "linked list" by giving each item in your pool a reference to the next object. When requesting an object you simply set the "next reference" to the one stored in the object you are going to use. So all objects in your pool have a reference to the next one except the last one which is null.
Simple example:
// This could be a MonoBehaviour or whatever
public class PoolItem
{
public PoolItem Next {get; set;}
}
public class Pool
{
PoolItem m_Next = null;
public void AddToPool(PoolItem aItem)
{
aItem.Next = m_Next;
m_Next = aItem;
}
public PoolItem GetItem()
{
if (m_Next != null)
{
PoolItem item = m_Next;
item.Next = null;
m_Next = m_Next.Next;
return item;
}
else
{
// either create new instance here or throw an error
// usually pools should be "primed" with enough elements.
throw new System.Exception("Pool Empty!");
}
}
}
Such a structure doesn't produce any garbage as no objects are ever destroyed. It's also scalable as you don't need an array or list that has "enough slots" since each item in the pool is one slot. You don't have "random access" to the pool, but that's not required in a pool.
This is great, thank you for taking the time to elaborate on this! I've been putting off building a simple pooling system for want of knowledge, and given the amount of utility I get out of lists, this is incredibly valuable- thank you!! :)
This is so cool, I had never thought of doing it by just giving an item a reference to the 'next' item!
I apologize if I'm being a bit daft, but in re-reading this I get the thrust of what you're doing, but I'm a bit confused about how to seed and populate a list using this framework- would I want to make some new List $$anonymous$$yList in PoolItem or whatever monobehavior, and then for however many indexes I want to seed the list with, do
Next {get; set;}
$$anonymous$$yList.Add (Next);
@Sendatsu_Yoshimitsu: Uhm, an object pool is just a structure to store elements to be used / reused when you need one and when you're done you put it back into the pool.
To get an element you just call "GetItem". To put an item back you call "AddToPool". To "seed" / initialize the pool you just add enough items using AddToPool:
public PoolItem prefab;
Pool pool = new Pool();
void Init()
{
for(int i = 0; i < 50; i++)
{
pool.AddToPool((PoolItem)Instantiate(prefab));
}
}
Ooh gotcha, thank you for the clarification. :)
