How to make a cell matrix update optimally and without producing garbage

Scripting
,
1

Problem space
I have WxH elements (cells) in a grid. These are UI elements but this shouldn’t matter.

The actual W and H values are irrelevant. These are known integers once the game starts, and won’t change during runtime.

These cells render as flat boxes with varying alpha values, and behave like “motion sensors”. If something goes over them they instantly become opaque. If there is nothing on them their alpha slowly fades back to zero. That’s the whole deal and yes, sounds very trivial on paper.

However, the actual product of W*H can be a high number, so I decided not to update each of these cells per frame. Instead what I thought of doing is to make a “hot list” where I add only cells that are known to be activated, and then I foreach through every cell in this list, diminish their alphas, and remove those that hit zero through decay.

What I want to accomplish
I can implement this just fine, however I want to get rid of the frame allocations that produce constant garbage. (Currently it’s around 300 bytes.)

Here’s my current solution in more detail
The trigger elements simply move across the screen. I have a way to convert their position to a hash value. No hash collisions are possible by design. This makes it possible to also not care about W or H.

The grid collection has all of its cell GameObjects preallocated but set as inactive. It also has two dictionaries, one that maps hash → cell’s alpha, and another that maps hash → cell’s mesh renderer. These two are practically static, and allocate only once.

Each frame, grid collection’s update does the following (in this order):

  1. blanket decay of everything in the “hot list” (each active cell has it’s alpha diminished slightly)
  2. cell activation (where some cell’s alpha is set to 1)
  3. actual update of the visuals according to whatever is still in the “hot list” (this uses the second dictionary to insta-reach for the mesh renderer and update its material).

I also make sure to call SetActive as appropriate on the actual GameObjects to remove the burden from the engine’s update loop.

This performs very satisfactorily, however, no matter how I implement this, I can’t think of a way where I don’t produce garbage. In the last version, the garbage is introduced because of adding/removing from the “hot list”.

(Btw when I say “hot list” it is currently just a HashSet.)

Other things I’ve tried
The biggest issue that prevents me from solving this elegantly is not being able to modify the dictionary in one pass because that’s how foreach works. For the latest version, I made a dedicated collection, however it still maintains a dictionary (hash → alpha), and two additional hash sets (‘active set’ and ‘key set’), so that I can foreach over ‘key set’ while I update the other two in one go.

I was also thinking about an ordinary list (instead of a dictionary) where I just swap the elements to maintain the active ones on the top, and then separately keep track of this active count. This would solve the garbage problem and is great for everything, however I can’t find the cell that is supposed to be activated in O(1). And maintaining both a dictionary and a list is PITA because I then need another dictionary to map hash → index.

I’ve also tried using Linq’s ToDictionary, however, even though the code is tiny and clever (with no other intermediate collections required), this produces a fresh dictionary instance per frame.

I don’t mind sacrificing memory, I just want to get rid of the intermittent frame garbage if at all possible, while also keeping the solution relatively simple.

Is this even possible to do without making a specialized data structure like a priority queue or a binary heap or whatever? In that case I will just pronounce it “good enough” and move on. I am astonished that such a trivial task turns out to be so hard to implement in a straightforward manner.

2

Wouldn’t it be possible to just do it with a hot array of worst case size and a highwater indicator as you fill it?

Or perhaps two hot arrays, A and B, you fill the one, you process it into the other each frame, then swap?

That way it is two fixed arrays of WxH size, and two integers saying “highwater” for each.

Or am I failing to understand where you’re seeing the garbage?

3

How about a permanent fixed size array of active cells with an index that wraps around as you add more cells to it.

4

I forgot to mention this, yes, I also thought about this specifically. But there is again this problem, like with the list, of losing the ability to find an element in O(1). W*H is potentially a big number, and losing performance (even O(log(n)) ) to achieve zero garbage is not acceptable.

There are 3 interactions basically:

  1. going through all active elements and diminishing their alphas, and deactivating if any of them hits zero,
  2. finding the element and setting it’s alpha to 1, and activating it,
  3. updating the visuals to match the stored alphas, and skipping the deactivated ones.

The first and the third one don’t care about the order or the structure, as long as the cells are sequential (i.e. enumerable is just fine). The first one dislikes foreach, however, because it wants to change the collection. And the second one needs searching to be O(1). So it’s the paradox of having something that dislikes foreach but also needs a hash map that is especially troublesome, and requires a redundant collection to resolve. This redundant collection is what usually generates the garbage.

I’m pretty sure there is no “you have just one data structure” solution, but when it comes to combinations I can’t figure what is the most cost-effective one that doesn’t turn this one simple thing into a handful of dedicated classes.

I don’t know, I’ve made hashed lists before, maybe I should just make a hashed list that has O(1) search, then do the ‘highwater’ thing on that. I guess I should check that out.

I don’t know the exact amount of active cells, because the amount and speed of triggering elements can change. Active count can be anything between 0 and W*H, which is why Kurt’s ‘highwater’ sounds appealing.

5

Well if the array is big enough then it shouldn’t be a problem. But if the head (index) of the snake catches the tail then you just overwrite the tail, but be sure to set the tails alphas to zero before you do. The user probably won’t notice and I promise not to tell them!. :wink:

6

@zulo3d I don’t see how that could work for all three interactions mentioned in post #4.
Let’s say you have just one array that represents all the cells. Each element contains an alpha.

How do you distinguish between what needs to be updated and what doesn’t?
Deciding on the spot makes little sense, because you want to skip over those that are inactive. You don’t want to have to go over all elements in the array, that would defeat the purpose. I can just as well iterate through every GameObject and decide what to do right there.

The reason why I don’t do this is because in a majority of time I have only 3-4 active cells out of 300, per frame. And it is highly unlikely that this is ever going to reach 100%.

How do you quickly find the element that needs to be set to 1?
If I already have a hash for any position, how would I use this to pinpoint which array element it corresponds to.

What does moving ahead in the array accomplishes?
I still need to read from the active elements in the final pass to actually refresh the visuals.
I think wrapping around is ok for something that is more fire-and-forget, here I actually need to maintain the list, each box needs to fade to zero, and the cell boxes mustn’t contain scripts on their own, this is a mobile game and it would needlessly burden the update loop with hundreds of objects that don’t do much.

I also can’t make a shader to achieve this effect because the amount of triggering particles may vary, and this turns complicated very quickly.

7

Perhaps you misunderstood. You should have two arrays. The regular array of items/elements and a fixed sized array of active items/elements. You only spend time processing the array of active elements. What I wrote in post #5 is referring to the array of active items/elements.

8

After some thinking:
What you said hinges on using indice, instead of hashes, and having a preallocated array with a ‘high water mark’. With a workaround this might satisfy the constraints.

I’d get two unordered collections from this array for free (active vs inactive) + corresponding data + an ability to find the cell in O(1).

The workaround would be the hack where I map cell hash → array index. However I’d need to keep track of any changes when I’m swapping the elements around.

As an upside I’d only have this one dictionary and an array, both of which don’t change their population, so there should be no garbage.

This is worth trying.
ttyl

9

What about this have:

  • dictionary cell → CellDescription{meshRenderer, alphaState, positionInHotList}, use whatever you want as key for cell, initialized once at the start, depending on your needs might as well use plain 2d array instead of dictionary
  • hotlist List<{CellDescription}>

Operations:
1.1) simply iterate through the hotlist for updating
1.2) if you find cell that needs deactivating, swap it with last one in the list, update positionInHotlist for the moved one, mark the positionInHotList to -1 for deactivated one
2) use the dictionary to lookup CellDescription
2a) if the cell wasn’t active add to the end of hotList and set positionInHotList accordingly
2b) if the cell was already in the hotList I assume you will only want to reset alphaState to 1,
3) iterate through hotlist

No garbage beyond initial allocation and while the hotlist expands. Operation 2 uses single dictionary lookup, and 0 for others. You don’t even have to mess with manually tracking used/unused parts of hotlist to avoid garbage allocation the capacity mechanism of already does that and is designed for exactly this purpose. You can call EnsureCapacity at the start with expected amount of cells but that’s optional. If required capacity at any point exceeds available it will be increased automatically, producing little bit of garbage in the process but it will happen only when maxCapacity increases. Capacity will not decrease when items are removed from list so you don’t have to worry about it repeatedly generating garbage. I assume that you want to avoid infinite garbage and little bit of allocations when required data size exceeds is acceptable.

EDIT: Looks like you came up with exactly same solution 1 minute before I finished writing this.

10

Overall keeping track of active cell index isn’t that difficult.

class CellEntry {
   MeshRenderer visuals; // whatever you use for visualizing
   float alpha;
   int activeIndex = -1;
}
Dictionary<CellKey, CellEntry>  cellLookup;
List<CellEntry> activeCells;

void Init() {
    cellLookup = fillAllCells(); // implement this part yourself
    activeCells = new List<CellEntry>();
    activeCells.EnsureCapacity(10); // optional initial capacity, set whatever you expect typically to be used. Nothing bad will happen if estimate is too low. Just don't set it too high as that will waste memory.
}


// the code looks long but it contains three alternative approaches

void UpdateDecay() { // operation 1)
    // Remove methods don't decrease capacity, so repeatedly removing and adding should
    // not cause infinite garbage

    // aproach A with swapping
    for (int i=0; i<activeCells.Length; i++) {
        activeCells[i].alpha -= Time.deltaTime * DECAY_SPEED;
    }
    for (int i=0; i<activeCells.Length; i++) {
        if (activeCells[i].alpha < 0) {
           activeCells[i].activeIndex = -1;
           if (i + 1 < activeCells.Length) {
                activeCells[i] = activeCells[activeCells.Length - 1];
                activeCells[i].activeIndex = i;
                activeCells.RemoveAt(i);
           } else {
                activeCells.RemoveAt(i);
           }
        }
    }
 
    // Approach B using RemovAll
    for (int i=0; i<activeCells.Length; i++) {
        activeCells[i].alpha -= Time.deltaTime * DECAY_SPEED;
        if (activeCells[i].alpha < 0) {
            activeCells[i].activeIndex = -1;
        }
    }
    activeCells.RemoveAll((x) => x.activeIndex < 0); // need to check the that RemoveAll call doesn't produce garbage due to lambda or other abstraction layer,  if it does use approach A or C instead
    for (int i=0; i<activeCells.Length; i++) {
        activeCells[i].activeIndex = i;
    }
 
    // Aproach C implementing RemoveAll yourself using two pointer approach
    int w = 0;
    for (int i=0; i<activeCells.Length; i++) {
        activeCells[i].alpha -= Time.deltaTime * DECAY_SPEED;
        if (activeCells[i].alpha < 0) {
            activeCells[i].activeIndex = -1;
        } else {
            activeCells[w] = activeCells[i];
            activeCells[w].activeIndex = w;
            w++;
        }
    }
    activeCells.RemoveRange(w, activeCells.Length - w);
}

void ActivateCells(CellKey key) { // operation 2)
    var cell = cellLookup[key];
    cell.alpha = 1;
    // <do whatever you need to enable visuals>
    if (cell.activeIndex < 0) {
       activeCells.Add(cell); // will not generate garbage unless capacity gets increased
       cell.activeIndex = activeCells.Length - 1;
    }
}

void UpdateVisuals() { // operation 3)
    foreach (var cell in activeCells) {
       cell.visuals.SetAlpha(cell.alpha); // replace setAlpha to whatever is relevant for your visuals
    }
}
11

Ah ok I get it.

Yes that makes sense, but because of a limited size I would have to sacrifice one of these things:

  • registering new triggers would be sometimes skipped
  • natural decay would be sometimes flushed to zero

This would lead to visual artifacts that aren’t nice.

So that’s why you say that the array could be bigger so that I wouldn’t have to sacrifice anything, but then again I have this problem of random-accessing the array in order to find the element that corresponds with the visual.

But then again if I had some means of translating the cell’s hash into index, maybe I could fix that, so apparently it all boils down to this kind of mapping.

Ok yeah, this concept is about replacing my HashSet with a List/array, while also introducing hash → index mapping, but only for the active elements. This last part is new, I haven’t thought of this before.

So to simplify the explanation, it’s basically:
mr dictionary: hash → mesh renderer
index dictionary: hash → index (either a valid index or -1 for inactive)
data block: array of (hash, alpha) struct // I’ll explain this below because I’ve modified the approach slightly

All 3 are populated in advance, and I keep the active count (AC) separately (AC starts at 0, but grows with time).

Operation:

  1. Iterate through active data block from 0 to AC-1 and diminish all floats slightly.
    If float reaches 0, swap current index with AC-1, then reduce AC by 1.
    Use stored hash to set the index dictionary’s index to -1.

  2. Get index from computed ‘known hash’ (via index dictionary).
    If index turns out to be -1: Get the first available index (at AC), then increase AC by 1.
    Data block: set (hash, alpha) to (known hash, 1.0), then use known hash to set index dictionary to current index.

  3. Iterate through active data block, from 0 to AC-1.
    Use stored hash to get a mesh renderer from mr dictionary.
    Use float to update the material.

Sounds good so far, but wowaweewa it’s a fully fledged algorithm :slight_smile:

(Edit: This was written before your post.)

12

Registering new elements would never be skipped, but yes, natural decay may sometimes need to be forced to zero.

13

For my Mandelbrot renderer I essentially do the same thing. If I remember correctly I had essentially 3 lists. One that stored all cells in an ordered / flattened layout, one active list and one “passive” list. The passive list does not hold the items that have settled but is just a second list. When processing the cells, I iterate through the active list, do the processing and moving the element from the active to the passive list unless it settled. To “remove” the element from the active list the element is swapped / replaced with the last element in the active list. You could remove the last element or just track the highest valid index yourself. Once you reach the highest valid index / the end of the active list I simply swap the two Lists for the next cycle. A cell in my case had two complex numbers (4 doubles) two integers (x, y position in screen / texture space) as well as an iteration count.

When a cell / pixel settled I use the x,y position to index the color array to set the final color based in the interation count. The auto iteration feature simply does one cycle / iteration per frame. At the beginning it’s not that great when it has to iterate all cells and performance loss from moving the elements around is quite significant. That’s why I have a 2 step process. Since the image always starts with all cells needing an “update”, I first use a normal loop through all elements until the first cell settles. Then the active / passive list business starts. This of course is a specific optimisation for this specific usecase.

14

Wouldn’t some kind of Region mechanism be helpful? You could divide your scren in 4 quadrants, then each quadrant in 4 sub-quadrants and so on, and then you would be able to activate/deactivate the full region at once.

15

I had a similar issue, a tile based 3D map, and I only wanted particular tiles to render if they were close enough to camera. Kind of like a fog of war setup.

I had a static Vector3 that was a rounded camera position, and then each tile would check against if their position was a distance from this(also rounded), so only a fast moving camera would make a noticeable frame lag. Mainly because I still needed each tile to run as well as other objects, I just found turning off their renderers for performance was top notch.

But what I mean to say, is would it not be better to have each tile think for itself, and just give said tile(s) communication to turn on, stay on, or fade away?

Because in my mind, (which isn’t saying much), needing a List for a List to handle another List seems like it’s way left field to the point. Sounds like way less of a headache to say “hey you, tile, turn on now. wait for a sec, then fade away” rather then “here’s my filing cabinet, let me see what drawer I want, then alphabetically look the name, and oh you, tile, follow this function I have”…

I may be way off course with your question, sorry, my mind wanders at times…

16

What you described would be something like a quad-tree. Quad trees are great for searching through an unordered aet of data that has a 2d position component. When you work on a grid using a quad tree doesn’t really help you much It adds a lot of extra complexity for each element.

Though another approach for a set of objects that are often added / removed from the set is to use a linked list. Not the LinkedList class which is completely useless. Linked lists shine when the actual nodes represent the data. So when you’re already dealing with actual objects, you can simply arrange them in a linked list by giving each element a “prev” and “next” reference. That allows easy O(1) inserts and deletes. Of course assuming you still have your grid array to get random access to a certain cell. You can directly see if a cell is in the list or not based on the two references.

If the linked list is only used for iterating through the active cells, a “singly-linked-list” would probably be enough as you only remove elements as you’re iterating through the list. So you never have to remove a random element. It’s only removed when it faded out. Removing elements from a singly linked list is also O(1) if you still have the previous element reference (which you have when you iterate through the list) to close the gap. Whenever you’re working with actual objects, you most likely suffer from cache misses anyways. So if you follow a reference that’s stored inside an array or if you follow a reference stored in the previous object makes not really a difference.

Adding an element to the list simply means:

  • assign the current list head to the new elements “next” field
  • replace the list head reference with the new element.
  • done.

Of course when you’re working with an array of value types, a similar approach could be used by storing the “next” element index in a variable. However when those references are scrambled, the benefit of using a value type array would be gone as we would be back to having cache misses. Sometimes it might make sense to partition things like the GC into long term and short term objects. So sensors which are newly activated end up in the long term list. The long term list is only cleaned up in greater intervals (once a sec or something like that). Elements that finish “soon” could be moved to a separate list which is cleaned more often. Those are all theoretical approaches which usually fail on practical hurdles. The more places things are stored, the more difficult it is to access them in case they are “retriggered”. So too complex systems often yield the opposite of what you want to achieve.

17

@dlorre

I don’t have time for replies rn, just wanted to say: exactly. Or a k-d tree. I have an octree ready to go, but I find the whole idea to be an overkill. The solution shouldn’t overshadow the actual game in terms of its implementation size.

Besides, producing a hash from arbitrary coordinates sorts this out perfectly. I don’t have issues with isolating the actual objects that need updating.

@Bunny83
And yes, I’m also considering the hardware caching. Slightly. I’m not a fan of huge arrays or blocks made up from complex types lying on the heap, because they’ll get swapped in a random manner. Goodbye any cache prediction.

I’ve also considered linked lists, but as you said yourself, LinkedList is awful, but I don’t like making the logic of it from scratch for this. Also I don’t need inserting at all, though inserting in this active/inactive context would save me from having to swap, as you can just reconnect the links.

Edit: In the end I decided to keep reuse the simplest collections and keep them at a minimum. Currently it’s just a dictionary that holds onto small objects, and a fixed array which is used as a blackboard. The activation logic is maintained via Kurt’s high-water suggestion, so there’s also a custom counter for the array.

18

One option would be something like this:

private const int WIDTH = 100;
private const int HEIGHT = 100;
private const int ELEMENT_COUNT = WIDTH * HEIGHT;

private readonly Image[] images = new Image[ELEMENT_COUNT];
private readonly float[] alphas = new float[ELEMENT_COUNT];
private readonly HashSet<int> activeItemIndexes = new HashSet<int>();
private readonly Stack<int> activeItemsToRemove = new Stack<int>();

public void UpdateAlphas(float reduceAmount)
{
    foreach(int index in activeItemIndexes)
    {
        float alpha = alphas[index];
        if(alpha <= reduceAmount)
        {
            activeItemsToRemove.Push(index);
            images[index].gameObject.SetActive(false);
        }
        else
        {
            alphas[index] = alpha - reduceAmount;
            images[index].SetAlpha(index);
        }
    }

    foreach(int index in activeItemsToRemove)
    {
        activeItemIndexes.Remove(index);
        images[index].gameObject.SetActive(false);
    }

    activeItemsToRemove.Clear();
}

public float GetAlpha(Vector2Int position)
{
    int index = GetIndex(position);
    return activeItemIndexes.Contains(index) ? alphas[index] : 0f;
}

public void SetActive(Vector2Int position)
{
    int index = GetIndex(position);
    if(activeItemIndexes.Add(index))
    {
        images[index].gameObject.SetActive(true);
        alphas[index] = 1f;
        images[index].SetAlpha(1f);
        activeItemIndexes.Add(index);
    }
}

private int GetIndex(Vector2Int position) => position.y * WIDTH + position.x;
19

Actually, my comment was in between your posts and is heavily influenced by your post #9 .
Your feedback very much influenced the final design that I’m happy with (which I’ll explain in the next post).

20

I’ve managed to resolve this. But it wasn’t easy. It is mostly a combination of Kurt’s and Karliss’s suggestions. And probably zulo’s to an extent as well. I haven’t had time to seriously consider anything after Karliss’s comments, but thank you all for the feedback.

I settled with the following setup

Dictionary<int, CellRef> _refs; // hash key
Cell[] _cells;
int _activeCount = 0;

where

private struct Cell {
  public int hash;
  public float alpha;
}

private class CellRef {
  public int index;
  public MeshRenderer mr;
}

Because cell owns hash and CellRef owns index the whole arrangement is doubly-linked, in a way.
This is the core mechanism which is used by interactions explained in post #4

void setCellActiveState(int hash, bool active, float alpha = 0f) {
  int index = _refs[hash].index;
  _cells[index].alpha = alpha;

  if(active && _activeCount < _refs.Count && index >= _activeCount) {
    swapCells(index, _activeCount++);
    _refs[hash].mr.transform.parent.gameObject.SetActive(true);
  } else if(!active && _activeCount > 0 && index < _activeCount) {
    swapCells(index, --_activeCount);
    _refs[hash].mr.transform.parent.gameObject.SetActive(false);
  }
}

void swapCells(int index1, int index2) {
  var c1 = _cells[index1];
  var c2 = _cells[index2];
  _refs[c1.hash].index = index2;
  _refs[c2.hash].index = index1;
  _cells[index2] = c1;
  _cells[index1] = c2;
}

Thus this is the Kurt’s ‘high water’ system of swapping things around.
This let’s me iterate through the active cells only. The operations look like this (with fluff removed)

void Update() {
  blanketDecay(Time.deltaTime);
  cellActivation();
  updateActiveCells();
}

// #1
void blanketDecay(float deltaTime) {
  var dc = _alphaDecay * deltaTime;

  for(int i = 0; i < _activeCount; i++) {
    if(getsBelowOrEqualTo(0f, ref _cells[i].alpha, dc))
      setCellActiveState(_cells[i].hash, active: false);
  }

  static bool getsBelowOrEqualTo(float limit, ref float v, float decr) {
    v -= decr;
    if(v <= limit) { v = limit; return true; }
    return false;
  }
}

// #2
void cellActivation() {
  var hash = // ... computed from an arbitrary position
  if(_refs.ContainsKey(hash))
    setCellActiveState(hash, active: true, alpha: 1f);
}

// #3
void updateActiveCells() {
  for(int i = 0; i < _activeCount; i++) {
    var col = buildColor(_color, _cells[i].alpha);
    _refs[_cells[i].hash].mr.sharedMaterial.SetColor("_BaseColor", col);
  }
}

Works exactly the same as before, with 0 frame allocations.
I really didn’t expect this to be so hard! :slight_smile:

Once again, thanks everyone!