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

Monogame Networking .. a Decade Later

Today I’ve been investigating options for integrating a multiplayer layer into my Monogame based game engine. When I first opened my browser to take a look, I popped open my bookmarks and saw a series of sites and postings circa 2012-2014 that talked exclusively about Lidgren, Raknet or ‘roll your own’. Or worse yet, there were numerous links to the now dead XNA.Networking API.

Enter Unreliability

After a bit of link purging, I began a new phase of research and stumbled upon the excellent BenchmarkNet project (https://github.com/nxrighthere/BenchmarkNet) which is a testing app for reliable UDP libraries.

Now, I must admit, I’m partial to UDP and reliable UDP in particular. This is a topic that is somewhat controversial but most high-end games are using some variation of TCP/UDP or reliable UDP. Sometimes together. Most ‘roll your own’ systems eventually become reliable UDP. I won’t rehash the arguments – but an excellent post can be found here and discussion here.

In my personal experience, TCP in game dev has given me headaches due to re-transmit issues and lack of packet prioritization. I’ll admit though that every game or project I worked on in the 2000s was fully or majority TCP – including the failed Shadowrun MMO and RunUO (Ultima Online). Times have changed though and reliable UDP is no longer a bad word (or so I hope). So let’s look at some of the primary options…

Let the games begin

Below are the latest results pulled from the 64 connected client test on BenchMarkNet’s github wiki.

As you can see, most of the libraries perform within 10% of each other except for a few particularly bad performances turned in by UNet and Lidren with issues related to memory consumption and CPU utilization respectively.

With the spread so narrow, I began to look at other things that I find important when picking out a library — source code access, license, and features. I won’t go through each one but I ruled out all but two options due to performance, license, lack of access to source, or monetization schemes I was uninterested in.

And the winner…

In the end I noticed that LiteNetLib often had the lowest CPU utilization while Neutrino was often not far behind but with a lower Bandwidth utilization. Better yet, both are OpenSource and MIT licensed! In addition to this, both libraries are exceptioally cross-platform, feature complete, have tight serialization, and work in either client-server or P2P configuration.

 

Ever Present Multiplayer – The Local Server

The approach that I’m leaning towards is the local game server pioneered by Id with Doom and Quake. This server embedded in the client allows you to code the game as if it was multiplayer no matter what while also supporting online gameplay modes. I think this approach would mesh well with the existing Entity Component System  (ECS) by jumping on the same hooks used by the AI for input and rendering. My thinking at the moment is that the new NetworkSystem can create AINodes (or a variant of them) which will represent the other players or the decisions of the AISystem. Either way, their logic remains largely the same and ‘just works’.

If my logic is sound, I can deploy to the xbox with the local server and if/when I get network API access on the xbox, I can point to a remote server and it should ‘just work’.

 

In any case, I’ll post back with my results on this whole networking refactoring!

P.S. Short aside: you might be wondering, what happened to the whole ‘migrating PC Game Engine to UWP’ project? Well, it turns out it was pretty painless. After a few minor changes (i.e., the Window class not having a Position) – I managed to get the engine up and running in under an hour. It turns out all of the planning and anguish I had spent over selecting only cross-platform libraries was worth it. This is a first…

-Jonathan