Bitsquid Blog

There’s some articles floating around that touch on the idea. Bitsquid comes to mind. [1]

To give a slightly more detailed description, you allocate two arrays of the extents. One is the dense array of whatever type, say T, and the other is the sparse array of 32 bit or 64 bit integers. The sparse array stores indices into the dense array for extant objects. However, for extinct objects, the indices instead point to the sparse array itself to encode a free-list.

To insert, in O(1), you check the free-list for an unused slot. If there is none, then you grow the sparse array (increment a counter) and use the newly introduced slot. Then you insert (or construct in place) your object at the end of the dense array. Finally, you map that slot in the sparse array to the end of the dense array.

To delete, in O(1), you swap the object you wish to delete with the last in the dense array and decrement the counter (swap and pop). Then you add the index in the sparse array to the free-list. You’ll need to know the index assigned to the object you swapped with to do this, which can either be stored on the object itself or by introducing another array the maintains an inverse mapping.

To iterate, you can treat the dense array like any other array.

This scheme poses some challenges:

- You lose pointer stability because you are relocating your objects. You must access them through indices. If you can defer your deletions, say to a frame boundary, you assume your pointers are stable.

-…

Thanks, if you do nothing else, please (links to follow):

1. Read/watch the naughty dog presentation on Last of Us port where they talk about their time step. I have to say if there's one company who puts out stuff like videos and articles/books you should read, it is Naughty Dog. They know what they are doing optimization-wise, I just happen to find most of their games boring and lifeless from a design point of view, but I can still respect them greatly.

2. Read the GDC presentation about entity systems and the "roster" approach linked below.

3. Read probably everything on the Bitsquid site. Some of it is dated or even not the best, but I pointed some people here before and it really opened up their minds to what I was talking about when they were looking at my code. Changed their view from "black arts" to "wow, that really is simple and makes sense."

4. Read up on Entity Systems. But do not read things written by bloggers, authors of "frameworks," and various Java stuff out there (ex: Artemis). I hate to be so negative, but what I usually found out there is mostly garbage, wrong, and the authors disappear when challenged or asked about the hard, non-obvious parts. If you want good info, read code that's out there and figure out what seems good/bad, and listen to some of the people in the industry like at GDC talking about it. I tried to find one more recent talks, but so far only came across the Amazon one which seems pretty weak (though still interesting) and basic…

There's a good blog post about auto-merging JSON/XML structured data files (for game content) on the bitsquid blog from 2010:

> having content conflicts is no fun either. A level designer wants to work in the level editor, not manage strange content conflicts in barely understandable XML-files. The level designer should never have to mess with WinMerging the engine's file formats.

> And conflicts shouldn't be necessary. Most content conflicts are not actual conflicts. It is not that often that two people have moved the exact same object or changed the exact same settings parameter. Rather, the conflicts occur because a line-based merge tool tries to merge hierarchical data (XML or JSON) and messes up the structure.

> In those rare cases when there is an actual conflict, the content people don't want to resolve it in WinMerge. If two level designers have moved the same object, we don't really help them address the issue by bringing up a dialog box with a ton of XML mumbo-jumbo. Instead, it is much better to just pick one of the two locations and go ahead with merging the file. Then, the level designers can fix any problems that might have occurred in the level editor -- the right tool for the job.

-- http://bitsquid.blogspot.com/2010/06/avoiding-content-locks-and-conflicts-3.html

These blogs are definitely worth a look:

1) https://molecularmusings.wordpress.com/
2) http://bitsquid.blogspot.com/
3) http://gamesfromwithin.com/

They can feel a little esoteric but there's a lot of golden nuggets if you're willing to dig a little.

Also, check out this book by Jason Gregory: http://www.gameenginebook.com/