A common problem in EndlessClient occurs when trying to look up an entity. When rendering the entity, the rendering pipeline wants to know its X/Y coordinates on the map. When the packet protocol is signaling that the entity has performed an action, we want to find this entity by its unique ID. Unfortunately, C# doesn’t provide a data structure out of the box that provides quick lookup times by either key.
Original solution
Map entities (characters, NPCs, item drops, etc.) belong to an ICurrentMapStateProvider or ICurrentMapStateRepository with a shared implementation. The original implementation was as follows (with many fields omitted for brevity):
using AutomaticTypeMapper;
using Optional;
using System;
using System.Collections.Generic;
namespace EOLib.Domain.Map
{
public interface ICurrentMapStateRepository
{
Dictionary<int, Character.Character> Characters { get; set; }
HashSet<NPC.NPC> NPCs { get; set; }
HashSet<MapItem> MapItems { get; set; }
}
public interface ICurrentMapStateProvider
{
IReadOnlyDictionary<int, Character.Character> Characters { get; }
IReadOnlyCollection<NPC.NPC> NPCs { get; }
IReadOnlyCollection<MapItem> MapItems { get; }
}
}
In order to access e.g. MapItems in the rendering layer, we need to do a lookup for any items at the currently rendered X/Y coordinates:
protected override bool ElementExistsAt(int row, int col)
{
return _currentMapStateProvider.MapItems.Any(item => item.X == col && item.Y == row);
}
This process is repeated when we go to actually render the map items:
public override void RenderElementAt(SpriteBatch spriteBatch, int row, int col, int alpha, Vector2 additionalOffset = default)
{
var items = _currentMapStateProvider
.MapItems
.Where(item => item.X == col && item.Y == row)
.OrderBy(item => item.UniqueID);
foreach (var item in items)
{
var itemPos = GetDrawCoordinatesFromGridUnits(col + 1, row);
var itemTexture = _mapItemGraphicProvider.GetItemGraphic(item.ItemID, item.Amount);
spriteBatch.Draw(itemTexture,
new Vector2(itemPos.X - (int) Math.Round(itemTexture.Width/2.0),
itemPos.Y - (int) Math.Round(itemTexture.Height/2.0)) + additionalOffset,
Color.FromNonPremultiplied(255, 255, 255, alpha));
}
}
Obviously this is not a sustainable approach - we are scanning the entire collection multiple times on each attempt to render, which in EndlessClient is unbounded (vsync is disabled). In Debug mode, entering a map with many left over junk items ignored by other players dropped performance by a factor of 10. It was fun (and frustrating) watching the framerate counter slowly decline as more map items were added to the collection.
Accessing items from the network layer via their unique ID has a similar lookup problem. In the case of picking an item up off the map, HashSet::RemoveWhere is called to find the item with the matching unique ID.
public override bool HandlePacket(IPacket packet)
{
var uid = packet.ReadShort();
var id = packet.ReadShort();
var amountTaken = packet.ReadThree();
var weight = packet.ReadChar();
var maxWeight = packet.ReadChar();
var existing = _characterInventoryRepository.ItemInventory.SingleOrNone(x => x.ItemID == id);
existing.MatchSome(x => _characterInventoryRepository.ItemInventory.Remove(x));
existing.Map(x => x.WithAmount(x.Amount + amountTaken))
.Match(some: _characterInventoryRepository.ItemInventory.Add,
none: () => _characterInventoryRepository.ItemInventory.Add(new InventoryItem(id, amountTaken)));
var newStats = _characterRepository.MainCharacter.Stats
.WithNewStat(CharacterStat.Weight, weight)
.WithNewStat(CharacterStat.MaxWeight, maxWeight);
_characterRepository.MainCharacter = _characterRepository.MainCharacter.WithStats(newStats);
_mapStateRepository.MapItems.RemoveWhere(x => x.UniqueID == uid);
foreach (var notifier in _mainCharacterEventNotifiers)
{
notifier.TakeItemFromMap(id, amountTaken);
}
return true;
}
Considered alternatives
One idea I had other than creating a multi-key dictionary was to rework the rendering pipeline entirely to just iterate over all values in a given collection and render them, instead of caring about their X/Y coordinates. This would remove any lookups for entities and just use them in the collections as-is without caring about their order.
The problem with this approach is that it is a massive departure from the existing architecture and would require a complete overhaul of all map rendering. Currently, anything on the map is drawn in order based on X/Y coordinates, to make sure layers are properly drawn on top of each other. Iterating over the collections without relying on X/Y coordinate lookups would require use of a depth buffer (among other changes) to ensure rendering accuracy remains consistent. This performance issue was not something I wanted to spend a ton of time on, so I opted to defer the rewrite of the rendering layer until later.
The new structure
With that solution out of the way, I got to searching for a viable multi-key dictionary. I wanted to be able to quickly look up entities by either their map coordinate or their unique ID. Fortunately, entities all map nicely to a single interface, so I was able to make some assumptions about lookup methods - the collection would look up an entity by either the unique ID or the MapCoordinate. This meant the interface for the multi-key collection could be distilled to:
public interface IReadOnlyMapEntityCollection<TValue> : IEnumerable<TValue>
{
TValue this[int key1] { get; }
HashSet<TValue> this[MapCoordinate key2] { get; }
bool ContainsKey(int uniqueId);
bool ContainsKey(MapCoordinate mapCoordinate);
bool TryGetValue(int key1, out TValue value);
bool TryGetValues(MapCoordinate key2, out HashSet<TValue> values);
}
The writeable implementation adds the following methods:
public void Add(TValue value);
public void Update(TValue oldValue, TValue newValue);
public void Remove(TValue value);
The structure itself is really a wrapper/orchestrator around multiple collections. There is only one collection of values, and two hash sets of keys that map to the values.
private readonly Dictionary<int, int> _uniqueIdToHash;
private readonly Dictionary<MapCoordinate, HashSet<int>> _mapCoordinateToHashList;
private readonly Dictionary<int, TValue> _valueSet;
private readonly Func<TValue, int> _uniqueIdSelector;
private readonly Func<TValue, MapCoordinate> _mapCoordinateSelector;
public MapEntityCollectionHashSet(Func<TValue, int> uniqueIdSelector,
Func<TValue, MapCoordinate> mapCoordinateSelector)
{
_uniqueIdToHash = new Dictionary<int, int>();
_mapCoordinateToHashList = new Dictionary<MapCoordinate, HashSet<int>>();
_valueSet = new Dictionary<int, TValue>();
_uniqueIdSelector = uniqueIdSelector;
_mapCoordinateSelector = mapCoordinateSelector;
}
_uniqueIdToHash and _mapCoordinateToHashList are collections that map the search values (the unique ID or the map coordinate) to the hash code of the object we want to map to. We first look up the hash code in one of these collections, then look up that hash code in _valueSet. All of these lookups are O(1), which is a significant improvement over the O(N) search of the previous implementation. Note that a map coordinate maps to a HashSet of hash codes. This is because a given coordinate can have more than one entity of a given type on it.
_uniqueIdSelector and _mapCoordinateSelector are Funcs that allow us to select the appropriate properties from the TValue without requiring a generic constraint on TValue. More on these later.
The problem with this collection is that a lot of record keeping has to be updated each time the collection is modified. For example, here are the implementations of Add and Remove:
public void Add(TValue value)
{
var key1 = _uniqueIdSelector.Invoke(value);
var hash = value.GetHashCode();
_uniqueIdToHash[key1] = hash;
var key2 = _mapCoordinateSelector.Invoke(value);
if (!_mapCoordinateToHashList.ContainsKey(key2))
_mapCoordinateToHashList.Add(key2, new HashSet<int>());
_mapCoordinateToHashList[key2].Add(hash);
_valueSet[hash] = value;
}
public void Remove(TValue value)
{
var key1 = _uniqueIdSelector.Invoke(value);
var key2 = _mapCoordinateSelector.Invoke(value);
_uniqueIdToHash.Remove(key1);
var hash = value.GetHashCode();
_mapCoordinateToHashList[key2].Remove(hash);
if (_mapCoordinateToHashList[key2].Count == 0)
_mapCoordinateToHashList.Remove(key2);
_valueSet.Remove(hash);
}
To ensure correctness, any changes to the collection must ensure that any old mappings of hash codes are properly updated in multiple collections.
Here are the previous usage sites for map items, updated to use this new collection:
protected override bool ElementExistsAt(int row, int col)
{
return _currentMapStateProvider.MapItems.TryGetValues(new MapCoordinate(col, row), out var mapItems) && mapItems.Count > 0;
}
public override void RenderElementAt(SpriteBatch spriteBatch, int row, int col, int alpha, Vector2 additionalOffset = default)
{
var items = _currentMapStateProvider.MapItems[new MapCoordinate(col, row)];
foreach (var item in items.OrderBy(item => item.UniqueID))
{
var itemPos = GetDrawCoordinatesFromGridUnits(col, row);
var itemTexture = _mapItemGraphicProvider.GetItemGraphic(item.ItemID, item.Amount);
spriteBatch.Draw(itemTexture,
new Vector2(itemPos.X - (int) Math.Round(itemTexture.Width/2.0),
itemPos.Y - (int) Math.Round(itemTexture.Height/2.0)) + additionalOffset,
Color.FromNonPremultiplied(255, 255, 255, alpha));
}
}
That looks a lot better. Instead of searching the whole collection, we do a lookup for any items based on the map coordinate.
public override bool HandlePacket(IPacket packet)
{
var uid = packet.ReadShort();
var id = packet.ReadShort();
var amountTaken = packet.ReadThree();
var weight = packet.ReadChar();
var maxWeight = packet.ReadChar();
var existingInventoryItem = _characterInventoryRepository.ItemInventory.SingleOrNone(x => x.ItemID == id);
existingInventoryItem.MatchSome(x => _characterInventoryRepository.ItemInventory.Remove(x));
existingInventoryItem.Map(x => x.WithAmount(x.Amount + amountTaken))
.Match(some: _characterInventoryRepository.ItemInventory.Add,
none: () => _characterInventoryRepository.ItemInventory.Add(new InventoryItem(id, amountTaken)));
var newStats = _characterRepository.MainCharacter.Stats
.WithNewStat(CharacterStat.Weight, weight)
.WithNewStat(CharacterStat.MaxWeight, maxWeight);
_characterRepository.MainCharacter = _characterRepository.MainCharacter.WithStats(newStats);
if (_mapStateRepository.MapItems.ContainsKey(uid))
_mapStateRepository.MapItems.Remove(_mapStateRepository.MapItems[uid]);
foreach (var notifier in _mainCharacterEventNotifiers)
{
notifier.TakeItemFromMap(id, amountTaken);
}
return true;
}
Similarly, it’s now extremely easy to remove an item by value based on the unique ID.
Is this actually any better?
I like this solution because it feels much cleaner. However, I’d also like some data to back up that making this change is actually worthwhile. Let’s compare frame rates before and after the change was made, since that was the primarily noticeable issue that necessitated this change in the first place.
I’d say a 10x speedup is pretty well worth it!
Putting it all together
Here is the final implementation of our multi-key lookup collection. I apologize for the name, but naming is hard.
| |