How do I produce a collection of game entities from another collection without producing garbage?

Question

I've been playing around with XNA a lot lately and I've also been reading quite a bit about garbage collection in games. I think I've done a reasonable job of reducing the amount of garbage by using pooling and avoiding a dependence on foreach.

Right now I have my base game entities stored in a KeyedCollection that allows me to iterate over all entities (like a List) and reference an entity by key (like a Dictionary).

I would like to be able to query my collection and return another collection without producing garbage each query. I've included a sample of the concept below because I think I'm better at coding them I am at explaining...

/// <summary>
/// Defines a sample entity.
/// </summary>
public class SampleEntity
{
    public uint Id;
    public Vector2 Position;
}

/// <summary>
/// Defines a collection of sample entities.
/// </summary>
public class EntityCollection : KeyedCollection<uint, SampleEntity>
{
    /// <summary>
    /// Return the key for the supplied item.
    /// </summary>
    protected override uint GetKeyForItem(SampleEntity item)
    {
        return item.Id;
    }
}

/// <summary>
/// Defines the sample game class.
/// </summary>
public class GameSample
{
    /// <summary>
    /// Create a new instance of the GameSample class.
    /// </summary>
    public GameSample()
    {
        Entities = new EntityCollection();
    }

    /// <summary>
    /// Get the collection of game entities.
    /// </summary>
    public EntityCollection Entities { get; private set; }

    /// <summary>
    /// Return the collection of entities within a radius of the supplied point.
    /// </summary>
    public List<SampleEntity> Query(Vector2 center, float radius)
    {
        List<SampleEntity> results = new List<SampleEntity>() // BAD, BAD, BAD!!!!!

        //
        // add the entities to the results collection
        //

        return results;
    }
}

This (overly simplified) example would produce a heck of a lot of garbage because it creates a new List object every call. I've also played with creating a global results list and clearing every call but that seems ugly.

    /// <summary>
    /// Return the collection of entities within a radius of the specified point.
    /// </summary>
    public List<SampleEntity> Query(Vector2 center, float radius)
    {
        _globalResults.Clear();

        //
        // add the entities to the global results collection
        //

        return _globalResults;
    }

Am I just missing something? Is there a more elegant solution out there I'm just not aware of.

Answer 1

I don't think that what your asking for is possible - if you want a different collection (i.e. one where the elements in that collection are somehow different from another collection) then you need a new instance of some collection in order to be able to store what those differences are.

The best you could probably hope for would be to use an array instead of a list as the memory overhead is probably lower, however (I'm not a game developer) this all strikes me as over optimisation - the overhead of collection instances is relatively small.

Don't get me wrong - its good that you are aware of things like this, I just think that you shouldn't obsess over this level of detail, as your unlikely to see any impact.

Answer 2

I think the best solution in a case like this is to make your function look something like this:

 public void Query(Vector2 center, float radius, List<SampleEntity> result)
 {
     result.Clear();
     result.Add(/*...*/);
     // ...
 }

And make the caller responsible for managing that list.

Also: When making games, don't be afraid to write simple code. If a global list of results works - then that is a fine solution.

---

If you don't need to store the list, then Skurmedel's answer is probably better from a performance standpoint.

Although, if it were me, I would do the really simple thing and just directly iterate over Entities. Same effect, maybe a tiny bit faster, and most importantly: less code.

Write your complicated enumerating Query function after you write your complicated spatial partitioning data structure, which you would only write after you actually need the performance it offers.

Answer 3

I think Andrew Russell has the right idea, but if you could do away with the List entirely that would be even better. You would make an IEnumerable (with yield return or handwrite an instance) that returns the items found by the query. You would not need a new list. You could basically achieve this with LINQ as well.

I visualize this as having a "window" or "view" into the contents of the collection.

The only thing you would need for look out is invalidating the IEnumerable, you can't modify the list while something else is iterating over it.

If you are afraid of creating a new IEnumerable each time, reuse it. You could reuse the enumerator as well but this would limit the amount of callers doing a query to one at a time. If two callers start using the same enumerator at the same time the gates of hell will open up.