Sabbatical Log: November 20th

This blog series is running about a week behind my actual work, giving me time to clean things up.  The date the actual work was done is in the title, horizontal lines indicate when I stopped writing and started coding.

Today my goal is to get entity management cleaned up, in particular I want to: get traversal proportional to number of entities with some property, compact entity lists, and speed up retrieving components for an entity.

Time to get to work.

I’ve got traversal down, and have removed lots of casts and other nastiness.

I’ve basically added component-type-specific containers to the EntityManager class, so lookups are cheap, and switched enumerations over to intrusive linked lists.

Previously I stored all stateful components in a 2-dimensional array and kept each component type in a specific column – this required some multiplications (and not power-of-two ones) and down casting, plus the ergonomics of multi-dimensional arrays in C# aren’t great. Now every component type gets its own array and accessor methods so there’s no down casting, access is cheaper, and the code is nicer.

Most systems want to iterate over all the entities with a specific component. Prior to this change I was looping over a column in that 2-dimensional array, stopping when I got to the next allocated Entity. This meant a lot of time was spent iterating over empty values, since most components are relatively sparse. Switching to a linked list makes iteration proportional to the number of active components.

I have one small twist on intrusive collections, which is rather that storing pointers I store indexes. Since Entity ids are already used to quickly access components for specific Entities, this has a nice symmetry and (at least in theory) means the GC has less to do. The interface for my linked lists is below:

As with most everything else, the size of the linked list is fixed at app start.

I also took some time to apply the same quick-check optimization I have in the collision detection system to the update position system (which is responsible for making sure entities don’t overlap at the end of a “frame”).

Next up, I need to implement compaction in the entity manager. Time to get back to it.

I’ve got compaction working by all appearances, and I have bunch of tests for it too. The basic idea is that, upon request, the entity manager will scan it’s internal table and renumber entities such that they’re all contiguous. It then takes that remapping, and informs each other thing that cares about entities – letting them update themselves.

Most of the work was punching the appropriate interface into the right places, the actually algorithms are not complicated.

Any instance that holds onto an Entity for longer than one update needs to implement IHoldsEntity (and be passed to Compact). I’m pretty sure I could remove all “extra-EntityManager” entity storage from, and may do so in the future. Right now there are only two classes that do so, the BushSystem (for tracking what is “pending being cut”) and the actual GameState class which has convenience accessors for the parts of a player and the camera entity.

Right now, since I’m debugging, I force a compaction between each system being invoked during an update. In the future I’ll want compaction to happen at more particular points, like screen transitions, and in response to extreme fragmentation.

All said I’m pretty happy with today’s results, I’ll probably do some more cleanup tomorrow and then move onto room transitions.

Continue onto November 21st