Misbehaving collision and also ECS

Ah collision you naughty monkey.

On the bright side, Visual Studio 2017 performance monitoring tools are pretty cool – when they work. In this case, the tools highlighted the exact offending line of code where  the CPU is spending a comically high 50% of its time! For once, it’s not premature optimization but I was expecting this. When I hack together game engines in intense one day sessions, I tend to take brute force approaches to every solution in an effort to get something working on screen. Function that’s O(N^4) loping through every object in the game? Whatever, slap a ‘TODO’ on it and make it someone else’s problem. In this case it’s O(N^2) but what’s a power of two between friends. I first came upon the issue when I was running a test level and found an ‘AddRandomEntities()’ command in the console window mapped to F1. Curious, I kept hitting F1 until my game slowed to a craw. I looked at the dat and saw that a mere 600 collidable objects had brought the engine down.  That may seem like a lot but add a bit of bullet hell and monsters on top of more unique objects and that number comes down real quickly.

 

“A poorly coded collision function” – circa 2017

 

Fortunately, this is an easy fix in a 2D game. Subdivision of the world via a quad tree or similar structure. Really, even subdividing the screen into quadrants alone would quadruple performance. For an in-depth tutorial on build quadtrees (along with nice explanation graphics) try this. I know, I should have written something up about it here but apparently my old post was taken down from Stack Overflow for some odd reason.
Anyway, without that offending and naive collision function, the engine can render a few hundred thousand objects at 120 fps.

But while we’re talking…

Let’s talk Entity Component Systems, my new one true love. Sorry inheritance, you had your chance!  Prior to implementing one in my engine, I was hitting bottlenecks when it came to tracking, management and manipulation of traditional ‘heavy objects’. The added overhead of pulling out properties, constantly switching contexts as you attempt to navigate tree after tree of a given object was killing performance and tended to lend itself to bugs.

 

Entity Component System
“A typical ECS” – Gamasutra

 

The switch to ECS, in particular the System part came with a fairly substantial performance leap in addition to large improvements in code flow. Now instead of object hierarchies, each system is managing it’s own list of data only objects objects. Having each system iterate its list in sequence means that our current list of data being operated on is likely always hot in cache.

 

 

Each system can then operate on hundreds of thousands of data containers without a care as to who they belong to.

“They’re Everywhere!” – somedude, a prototype, 2017

For my engine, I wanted to build an ECS as opposed to an EC. There is something that is inherently elegant to me about the separation between Entity (an id), Component (data) and System (logic).
One of the tricky parts of ECS is handling cases where Systems need to operate across component types and also component lookups (which require a cast). For my approach I introduced two optimizations. First, I introduced Nodes, an idea I stole from an implementation I saw around the web. Nodes help to bridge that tiny gap between component and ‘system who needs lots of different data’. A node can hold components but also importantly, holds data which is related across all components held within. For instance here’s a simple Collision Node:
public class CollisionNode : INode
{
        public int Id { get; set; }
        public int CollidedWith { get; set; }
        public bool Checked { get; set; }
        public bool HadCollision => CollisionData.HasCollision;
        public PositionComponent Position { get; set; }
        public CollidableComponent CollisionData { get; set; }
}

The Node allows us to generate metadata about the joined objects in a lightweight way. In this way we avoid excessive lookups and lots of meta collections. We can iterate this one list and have all the info we need to take action.

To get around the casting in general that comes with ECS I opted for an enum based component type property. This isn’t the best solution, I can’t even call it an OK solution but I have yet to run into a significant issue with it. Why cast and check to ensure your casts succeeded when you can bake in the type info and grab entities matching the enumeration type. It works for me, for now.
My ECS implementation is far from the best but I’ve found that it is relatively easy to add new features and have them “just work”. After years of building inheritance hierarchies – I finally get it. If you’re not using an EC or ECS implementation in your engine, you should probably consider it!


-Jonathan

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.