How do I efficiently maintain a constantly-changing list without triggering GC?

Questions & Answers
1

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?

2

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 + "

Index " + i + "
" + (b ? "Active
" : "Inactive
");
}
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 _= new Spawner(gos*, 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*.SetActive(b);
Debug.Log(s.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”)maxSpeedTime.deltaTime;
v3.z += Input.GetAxis(“Vertical”)maxSpeedTime.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.insideUnitCirclemaxSpawnedDistance;
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 = 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 :smiley:
Scribe_

3

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.