At the end of my post on C# garbage collection profiling I noted one additional problem generating a ton of garbage in EndlessClient: hovering the mouse over NPCs.

In EndlessClient, a mouseover action on an NPC should show the NPC’s name if there is a visible pixel under the mouse pointer OR there are no visible pixels on the texture (in the case of invisible NPCs). The way we check the value of a pixel in Monogame is via the GetData method on a texture, by getting the pixel value at the exact coordinate of the mouse, projected onto the NPC texture as rendered to the NPC render target.

public bool IsClickablePixel(Point currentMousePosition)
{
    var currentFrame = _npcSpriteSheet.GetNPCTexture(_enfFileProvider.ENFFile[NPC.ID].Graphic, NPC.Frame, NPC.Direction);

    var colorData = new Color[] { Color.FromNonPremultiplied(0, 0, 0, 255) };
    if (currentFrame != null && !_isBlankSprite)
    {
        if (_npcRenderTarget.Bounds.Contains(currentMousePosition))
            _npcRenderTarget.GetData(0, new Rectangle(currentMousePosition.X, currentMousePosition.Y, 1, 1), colorData, 0, 1);
    }

    return _isBlankSprite || colorData[0].A > 0;
}

The usages of this method are as follows:

public override void Update(GameTime gameTime)
{
    if (!Visible) return;

    // other stuff...

    var currentMousePosition = _userInputProvider.CurrentMouseState.Position;

    if (DrawArea.Contains(currentMousePosition))
    {
        var chatBubbleIsVisible = _chatBubble != null && _chatBubble.Visible;
        _nameLabel.Visible = !_healthBarRenderer.Visible && !chatBubbleIsVisible && !_isDying && IsClickablePixel(currentMousePosition);
        _nameLabel.DrawPosition = GetNameLabelPosition();
    }
    else
    {
        _nameLabel.Visible = false;
    }

    // other stuff...

    base.Update(gameTime);
}

Since this call is in the update loop, any time we have the mouse hovering over a pixel, we are calling GetData at the update rate of the game, which is as close to 60 updates/second as possible. On top of that, using GetData or SetData has a performance impact beyond generating garbage from copying to the temporary array: because the texture data is copied from GPU memory to RAM, we are effectively stalling the game each time it is called (source)!

The results speak for themselves…

Can you tell when I was mousing over NPCs?

So it seems our goal is to remove GetData calls from the update loop. However, we still need a way to access the pixel data of the texture when the mouse hovers over the NPC so we can properly determine whether to show the NPC’s name label. This means we need to store the texture data somewhere, but we also don’t want every instance of NPCRenderer to a) load the data individually and b) store a unique copy of the data.

The solution

To balance functionality without duplicating too much memory, an LRU cache seems like a good approach. We want the following:

  • A centralized repository of NPC texture data
  • Lookups based on the NPC’s graphic ID
  • Storing texture data for each NPC frame per graphic ID
  • A hard upper limit on the number of NPCs we’ll store graphic data for

This last objective is born out of the desire to prevent creeping RAM usage over the runtime of a game session. There is no point in duplicating the graphic data for NPCs that haven’t been referenced in a while, so those can be evicted once the capacity of our collection is reached.

With that, let’s take a look at the LRU cache that was implemented to solve this problem:

[AutoMappedType(IsSingleton = true)]
public class NPCSpriteDataCache : INPCSpriteDataCache
{
    private const int CACHE_SIZE = 32;

    private readonly INPCSpriteSheet _npcSpriteSheet;

    private readonly Dictionary<int, Dictionary<NPCFrame, Memory<Color>>> _spriteData;
    private readonly List<int> _lru;
    private readonly HashSet<int> _reclaimable;

    public NPCSpriteDataCache(INPCSpriteSheet npcSpriteSheet)
    {
        _npcSpriteSheet = npcSpriteSheet;
        _spriteData = new Dictionary<int, Dictionary<NPCFrame, Memory<Color>>>(CACHE_SIZE);
        _lru = new List<int>(CACHE_SIZE);
        _reclaimable = new HashSet<int>(CACHE_SIZE);
    }

    public void Populate(int graphic)
    {
        if (_spriteData.ContainsKey(graphic))
            return;

        if (_lru.Count >= CACHE_SIZE && _reclaimable.Count > 0)
        {
            // find and "reclaim" the first available candidate based on the order they were added to the LRU
            // 'reclaimable' candidates are updated when the map changes
            // candidates will never be NPCs that are on the current map
            // a map with >= CACHE_SIZE different NPCs will cause problems here
            for (int i = 0; i < _lru.Count; i++)
            {
                var candidate = _lru[i];
                if (_reclaimable.Contains(candidate))
                {
                    _spriteData.Remove(candidate);
                    _reclaimable.Remove(candidate);
                    _lru.RemoveAt(i);
                    break;
                }
            }
        }

        _spriteData[graphic] = new Dictionary<NPCFrame, Memory<Color>>();
        _reclaimable.Remove(graphic);
        _lru.Add(graphic);

        foreach (NPCFrame frame in Enum.GetValues(typeof(NPCFrame)))
        {
            var text = _npcSpriteSheet.GetNPCTexture(graphic, frame, EODirection.Down);
            var data = Array.Empty<Color>();

            if (text != null)
            {
                data = new Color[text.Width * text.Height];
                text.GetData(data);
            }

            _spriteData[graphic][frame] = data;
        }
    }

    public void MarkForEviction(int graphic)
    {
        _reclaimable.Add(graphic);
    }

    public void UnmarkForEviction(int graphic)
    {
        _reclaimable.Remove(graphic);
    }

    public ReadOnlySpan<Color> GetData(int graphic, NPCFrame frame)
    {
        if (!_spriteData.ContainsKey(graphic))
        {
            Populate(graphic);
        }

        return _spriteData[graphic][frame].Span;
    }

    public bool IsBlankSprite(int graphic)
    {
        if (!_spriteData.ContainsKey(graphic))
        {
            Populate(graphic);
        }

        return _spriteData[graphic][NPCFrame.Standing].Span.ToArray().All(AlphaIsZero);
    }

    private static bool AlphaIsZero(Color input) => input.A == 0;
}

This is a pretty straightforward implementation - it avoids generics which reduces a lot of the design complexity of the container. From the public interface, we have methods for:

  • populating graphic data for a given NPC graphic
  • marking/unmarking data as a candidate for eviction
  • getting the raw graphic data for a given NPC frame
  • checking if a frame is a blank sprite

Here is the first usage of the cache, in NPCRenderer.Initialize:

public override void Initialize()
{
    // ...
    var graphic = _enfFileProvider.ENFFile[NPC.ID].Graphic;
    _npcSpriteDataCache.Populate(graphic);
    _isBlankSprite = _npcSpriteDataCache.IsBlankSprite(graphic);
    // ...
}

When the NPC renderer is first created, we populate the texture data based on the NPC’s graphic. Internally, the cache will not do any additional work if data has already been populated for a given graphic. We also make a call to determine if the sprite is completely blank.

We also rewrite the check for clickable pixels:

public bool IsClickablePixel(Point currentMousePosition)
{
    var cachedTexture = _npcSpriteDataCache.GetData(_enfFileProvider.ENFFile[NPC.ID].Graphic, NPC.Frame);
    if (!_isBlankSprite && cachedTexture.Length > 0 && _npcRenderTarget.Bounds.Contains(currentMousePosition))
    {
        var currentFrame = _npcSpriteSheet.GetNPCTexture(_enfFileProvider.ENFFile[NPC.ID].Graphic, NPC.Frame, NPC.Direction);

        var adjustedPos = currentMousePosition - DrawArea.Location;
        var pixel = cachedTexture[adjustedPos.Y * currentFrame.Width + adjustedPos.X];

        return pixel.A > 0;
    }

    return true;
}

We’re still making a call to GetData, but this time it is looking for the data in the cache instead of loading it out of the Texture2D, so that’s a big improvement.

How about managing which data is evicted from the cache? I added a note to myself (most people call these “comments”) explaining the call chain for this class, and how data gets chosen for eviction. The call happens when the map changes, and by extension, all the NPCs are reset. The logic is pretty simple:

public void NotifyMapChanged(WarpAnimation warpAnimation, bool differentMapID)
{
    StopAllAnimations();
    ClearCharacterRenderersAndCache();
    ClearNPCRenderersAndCache();
    //...
}

private void ClearNPCRenderersAndCache()
{
    var currentMapNpcGraphics = _currentMapStateRepository.NPCs.Select(x => _enfFileProvider.ENFFile[x.ID].Graphic).ToList();
    var priorMapNpcGraphics = _npcRendererRepository.NPCRenderers.Select(x => _enfFileProvider.ENFFile[x.Value.NPC.ID].Graphic);

    foreach (var evict in priorMapNpcGraphics.Except(currentMapNpcGraphics))
        _npcSpriteDataCache.MarkForEviction(evict);

    foreach (var unevict in currentMapNpcGraphics)
        _npcSpriteDataCache.UnmarkForEviction(unevict);

    // ...
}

Full disclosure, this code is kind of icky because it relies on a nuance of the map switching logic: when NotifyMapChanged is called, the current map state will reflect the new NPCs, while the old map state will be reflected in the npc renderers. We first mark any of the old NPCs as candidates for eviction, and then unmark any new NPCs. This way, if an NPC exists on both maps, it will remain in the cache without needing to be reloaded.

There isn’t much to see now, but mousing over the NPC no longer generates a ton of extra garbage. Mission accomplished!