How do I optimize computations for multiple game objects(>1000)?

It has been 8 months I've been working on my metaball algorithm an the final technique I am trying out is writing magnets to which the sprite mesh edge vertices will update its position to, after finding the closest magnet point.

Code:

using HerminkasGams.SpriteSquash;
using UnityEngine;

[System.Serializable]
public class Vertex : MonoBehaviour     // Game object which holds positions of vertex
{
public Vector3 currentPos;
public Vector3 initialPos;
public Vector3 revertingPos;
[HideInInspector]public GameObject _parentGameObject;
[HideInInspector]public SpriteMeshModifier _parentSpriteMeshModifier;
[HideInInspector]public ObjectManagerController _objectManagerController;
[HideInInspector]public int _index;

public void SetInitialPos(Vector3 pos, int index, GameObject parentGameObject, SpriteMeshModifier parentSpriteMeshModifier, ObjectManagerController objectManagerController) {

currentPos = pos;
initialPos = pos;
revertingPos = pos;
_index = index;
_parentGameObject = parentGameObject;
_parentSpriteMeshModifier = parentSpriteMeshModifier;
_objectManagerController = objectManagerController;
}

//While this update is necessary, because there are so many verticies, the game is super laggy
private void Update() {
//Debug.Log("Update for each slime mesh vertex!");
if (_objectManagerController.metaballEdgePointVertices.Count > 0) {
Vector3 nearestMagnetPoint = FindNearestMagnetPoint();
Debug.Log("Found nearest magnet point for current mesh vertex!");
Debug.Log(nearestMagnetPoint);
//UpdateCurrentVertex(nearestMagnetPoint, _index);
}
}

Vector3 FindNearestMagnetPoint() {
//Compute the nearest metaball edge magnet point by iterating through them if metaballEdgePointVertexGOs is not empty
if (_objectManagerController.metaballEdgePointVertices.Count > 0) {
int index = 0;
//Source, current mesh vertex of slime
Vector3 scp = _parentSpriteMeshModifier.gameObject.transform.rotation * currentPos;
Vector3 point = new Vector3(scp.x * _parentSpriteMeshModifier.gameObject.transform.localScale.x, scp.y * _parentSpriteMeshModifier.gameObject.transform.localScale.y, scp.z * _parentSpriteMeshModifier.gameObject.transform.localScale.z) + _parentSpriteMeshModifier.gameObject.transform.position;
float minDistance = 99999;

//Will iterate through metaballEdgePointVertexGOs to find closest
Vector3 scpMagnet = new Vector3(0,0,0);
Vector3 pointMagnet = new Vector3(0,0,0);
for (int i = 0; i < _objectManagerController.metaballEdgePointVertices.Count; i++)
{
scpMagnet = _objectManagerController.transform.rotation * _objectManagerController.metaballEdgePointVertices[i].currentPos;
pointMagnet = new Vector3(scpMagnet.x * _objectManagerController.transform.localScale.x, scpMagnet.y * _objectManagerController.transform.localScale.y, scpMagnet.z * _objectManagerController.transform.localScale.z) + _objectManagerController.transform.position;
var dis = Vector2.Distance(point, pointMagnet);
if (dis < minDistance)
{
index = i;
minDistance = dis;
}
}
return _objectManagerController.metaballEdgePointVertices[index].currentPos;
}
return new Vector3(0,0,-1);
}

void UpdateCurrentVertex(Vector3 moveTo, int index) {
_parentSpriteMeshModifier.UpdateVertecies(moveTo, index);
}
}


The problem, as you can see in the image below, is that there are many many vertices for each game object that needs call this logic in its Update(), and it's ridiculously laggy. Each of these yellow points are what needs to update its position based on how close it is to nearest magnet point.

I want to stretch these vertices with what is in the Update() logic to hit these magnets points:

Please help me achieve my close to 1 year dream of making color-respecting metaballs...

*Edit

So I asked Chat GPT the same question and got: Batch Processing: You can reduce the number of Update() calls by creating a manager object that handles the vertex updates in batch. This would be far more efficient than having an Update() method for each vertex GameObject.

So I added the update logic in the parent game object of these vertices.

private void Update()
{
UpdateMesh();
foreach (var vertex in vertices)
{
if (objectManagerController.metaballEdgePointVertices.Count > 0)
{
// Assume FindNearestMagnetPoint() is now a public method in Vertex
// Vector3 nearestMagnetPoint = vertex.FindNearestMagnetPoint();
Debug.Log("Current vertex position: ");
// Debug.Log(vertex.currentPos);
// Debug.Log("Found nearest magnet point for current mesh vertex!");
// Debug.Log(nearestMagnetPoint);
// Update the vertex position
//vertex.UpdateCurrentVertex(nearestMagnetPoint, vertex._index);
}
}
}


The problem is, it is still way tooooo laggy. Is there a best solution for my problem?

• If you have a large number of very simple game objects, then the standard solution for that would be entities instead of game objects. Commented Sep 16, 2023 at 7:51
• gamedev.stackexchange.com/questions/207221/… Commented Sep 16, 2023 at 14:59
• May I have some insight on how this can be done? Commented Sep 16, 2023 at 14:59
• This looks like the kind of embarrassingly parallel work I'd do on the GPU instead. If you need the results for CPU-side gameplay calculations, do them only for a sparse control cage with a few vertices, and do the high-resolution computations for rendering on the graphics card. Commented Sep 16, 2023 at 16:41

It would help to optimise the loop, and inside the loop. Some standard rules for this:

1. Dont use .Count in the loop statement (is it slow), cache the .Count to a variable first, e.g.

verticesCount = _objectManagerController.metaballEdgePointVertices.Count;
for (int i = 0; i < verticesCount; i++)

1. memory allocation is slow, so don't allocate memory in loops, allocate first then assign in loop, so replace the .new and the var dis, like:

// assign to x, y, z inside the loop, no new required.
pointMagnet.x = scpMagnet.x * _objectManagerController.transform.localScale.x;
//.. etc
dis = Vector2.Distance(point, pointMagnet);
// where dis is defined outside the loop


Also, the debug print inside the loop, will kill performance. The advice on reducing Updates is good. Booth describes significant benefits from doint this: 9. https://medium.com/@jasonbooth_86226/intro-to-jobs-burst-dod-66c6b81c017f.

• The caution about new allocating memory applies to reference types or other stuff that will get heap allocated and need garbage collection tracking. Vector3 is a value type and goes on the stack in this case, so it's not the same cost. No heap allocation, no GC tracking. Commented Sep 17, 2023 at 23:27
• A good distinction. I still treat unnecessary stack memory allocation, per loop, as a performance overhead that should be avoided. Reusing the same memory block for a vector) will also least help with cache persistence - something that will only help performance wise. Do you really support doing a "new" each loop? Commented Sep 18, 2023 at 3:16
• I think you're misunderstanding how the compiler turns this code into IL and executed instructions. Absent a closure capturing variables, you get equivalent IL either way. The program does not re-allocate stack memory on every loop iteration. The mapping of stack space happens in one pass, when the IL is JIT compiled to actual machine instructions (outside of any explicit use of dynamic stack allocation via stackalloc, which happens after any plain old temporaries and doesn't change where they're allocated). Commented Sep 18, 2023 at 11:26

I was able to optimize it using ECS and jobs:

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using Unity.Entities;
using Unity.Jobs;
using Unity.Collections;
using HerminkasGams.SpriteSquash;
using System.Linq;
using UnityEditor;
using Unity.Burst;
using System.Runtime.Serialization;
using Unity.VisualScripting;

public partial class VertexUpdater : SystemBase
{
public GameObject ObjectManager;
public ObjectManagerController objectManagerController;
[HideInInspector] public List<SpriteMeshModifier> spriteMeshModifiers = new List<SpriteMeshModifier>();
// [HideInInspector] public List<Vertex> vertices = new List<Vertex>();  // List of vertices; each element of this variable is what I must make magnetic

private struct VertexCopy {
public Vector3 currentPos;
public Vector3 initialPos;
public Vector3 revertingPos;
public int _metaballEdgePointCount;

//_parentSpriteMeshModifier variables:
public Vector3 _parentSpriteMeshModifierPosition;
public Quaternion _parentSpriteMeshModifierRotation;
public Vector3 _parentSpriteMeshModifierLocalscale;

[HideInInspector]public int _index;
[HideInInspector]public Vector3 _closestMagnetPoint;

public VertexCopy(Vector3 pos, int index, int metaballEdgePointCount, Vector3 parentSpriteMeshModifierPosition, Quaternion parentSpriteMeshModifierRotation, Vector3 parentSpriteMeshModifierLocalscale, Vector3 closestMagnetPoint) {
currentPos = pos;
initialPos = pos;
revertingPos = pos;
_index = index;
_metaballEdgePointCount = metaballEdgePointCount;
//_parentSpriteMeshModifierPosition variables
_parentSpriteMeshModifierPosition = parentSpriteMeshModifierPosition;
_parentSpriteMeshModifierRotation = parentSpriteMeshModifierRotation;
_parentSpriteMeshModifierLocalscale = parentSpriteMeshModifierLocalscale;
_closestMagnetPoint = closestMagnetPoint;
}

public (Vector3, float) FindNearestMagnetPoint(NativeArray<Vector3> metaballVertexPositionArray) {
float minDistanceUnaltered = 99999;
//Compute the nearest metaball edge magnet point by iterating through them if metaballEdgePointVertexGOs is not empty
if (_metaballEdgePointCount > 0) {
int index = 0;
Vector3 scp = _parentSpriteMeshModifierRotation * currentPos;
Vector3 point = new Vector3(scp.x * _parentSpriteMeshModifierLocalscale.x, scp.y * _parentSpriteMeshModifierLocalscale.y, scp.z * _parentSpriteMeshModifierLocalscale.z) + _parentSpriteMeshModifierPosition;

float minDistance = 99999;

//Will iterate through metaballEdgePointVertexGOs to find closest
//Vector3 scpMagnet = new Vector3(0,0,0);
for (int i = 0; i < _metaballEdgePointCount; i++)
{
var dis = Vector2.Distance(point, metaballVertexPositionArray[i]);
if (dis < minDistance)
{
index = i;
minDistance = dis;
}
}

//Invert metaballVertexPositionArray[index] back to vertex coordinates
Vector3 vec1 = metaballVertexPositionArray[index] - _parentSpriteMeshModifierPosition;
Vector3 vec2 = _parentSpriteMeshModifierLocalscale;
Vector3 result = new Vector3(vec1.x / vec2.x, vec1.y / vec2.y, vec1.z / vec2.z);
Vector3 scpLocal = Quaternion.Inverse(_parentSpriteMeshModifierRotation) * (result);
// Debug.Log(currentPos);
return (scpLocal, minDistance);
}
return (new Vector3(0,0,-1), minDistanceUnaltered);
}
}

[BurstCompile]
private struct ComputeJob : IJobFor {
[NativeDisableParallelForRestriction]
public NativeArray<VertexCopy> vertexCopyArray;
public NativeArray<Vector3> metaballVertexPositionArray;

public void Execute(int index) {
VertexCopy vertexCopy = this.vertexCopyArray[index];
float minDistance = 9999;
(vertexCopy._closestMagnetPoint, minDistance) = vertexCopy.FindNearestMagnetPoint(metaballVertexPositionArray);
//If closest distance is less than threshold
if (minDistance < 0.2) {
vertexCopy.currentPos = vertexCopy._closestMagnetPoint;
this.vertexCopyArray[index] = vertexCopy;
}
}
}

protected override void OnStartRunning()
{
ObjectManager = GameObject.Find("ObjectManager");
objectManagerController = ObjectManager.GetComponent<ObjectManagerController>();
// GameObject.Find("SpriteMeshModifier");
// EntityManager entityManager = World.DefaultGameObjectInjectionWorld.EntityManager;
// // Create an Entity "archetype" that will have MyComponent
// EntityArchetype spriteMeshModifierArchetype = entityManager.CreateArchetype(typeof(SpriteMeshModifier));
// // Create an entity with that archetype
// Entity spriteMeshModifierEntity = entityManager.CreateEntity(spriteMeshModifierArchetype);

List<GameObject> waterslimesDisplay = objectManagerController.colorSlimesDisplayGlobal;
foreach (GameObject waterslimeDisplay in waterslimesDisplay) {
}
base.OnStartRunning();
}

protected override void OnUpdate()
{
CallJobs();
//throw new System.NotImplementedException();
}

private void CallJobs() {
foreach (SpriteMeshModifier spriteMeshModifier in spriteMeshModifiers) {
if(spriteMeshModifier.vertices.Count > 0 && spriteMeshModifier._isRegenerated && spriteMeshModifier.objectManagerController.metaballEdgePointVertices.Count > 0) {
NativeArray<VertexCopy> vertexCopies = new NativeArray<VertexCopy>(spriteMeshModifier.vertices.Count, Allocator.TempJob);
NativeArray<Vector3> metaballVertexPositions = new NativeArray<Vector3>(spriteMeshModifier.objectManagerController.metaballEdgePointVertices.Count, Allocator.TempJob);
CopyThingsTo(ref vertexCopies, ref metaballVertexPositions, spriteMeshModifier);
// Do heavy computation in a job
ComputeJob job = new ComputeJob() {
vertexCopyArray = vertexCopies,
metaballVertexPositionArray = metaballVertexPositions
};
job.ScheduleParallel(vertexCopies.Length, 64, default).Complete();
AssignComputedValues(vertexCopies, spriteMeshModifier);
UpdatePositions(vertexCopies, spriteMeshModifier);
// Don't forget to dispose
vertexCopies.Dispose();
metaballVertexPositions.Dispose();
}
}
}

private void CopyThingsTo(ref NativeArray<VertexCopy> copiesArray, ref NativeArray<Vector3> metaballVertexPositionsArray, SpriteMeshModifier spriteMeshModifier) {
for (int i = 0; i < spriteMeshModifier.vertices.Count; i++) {
Vertex vertex = spriteMeshModifier.vertices[i];
copiesArray[i] = new VertexCopy(vertex.currentPos, i, vertex._objectManagerController.metaballEdgePointVertices.Count, vertex._parentSpriteMeshModifier.transform.parent.gameObject.transform.position, vertex._parentSpriteMeshModifier.gameObject.transform.rotation, vertex._parentSpriteMeshModifier.gameObject.transform.localScale, vertex._closestMagnetPoint);
}
for (int i = 0; i < spriteMeshModifier.objectManagerController.metaballEdgePointVertices.Count; i++) {
MetaballEdgePointVertex metaballEdgePointVertex = spriteMeshModifier.objectManagerController.metaballEdgePointVertices[i];
metaballVertexPositionsArray[i] = metaballEdgePointVertex.currentPos;
}
}

private void AssignComputedValues(in NativeArray<VertexCopy> copiesArray, SpriteMeshModifier spriteMeshModifier) {
for (int i = 0; i < spriteMeshModifier.vertices.Count; ++i) {
spriteMeshModifier.vertices[i]._closestMagnetPoint = copiesArray[i]._closestMagnetPoint;
}
}

private void UpdatePositions(in NativeArray<VertexCopy> copiesArray, SpriteMeshModifier spriteMeshModifier) {
for (int i = 0; i < spriteMeshModifier.vertices.Count; ++i) {
if(copiesArray[i].currentPos == copiesArray[i]._closestMagnetPoint) {
//Should I lerp between copiesArray[i]._closestMagnetPoint and copiesArray[i].initialPos?
spriteMeshModifier.vertices[i].UpdateCurrentVertex(copiesArray[i]._closestMagnetPoint, copiesArray[i]._index);
}
else {
spriteMeshModifier.ResetPositionOfSelectedVertex(copiesArray[i]._index);
spriteMeshModifier.UpdateMesh();
}
}
}
}


I still hate the way my metaball effect looks, however...