hamt VS entt

This isn't a very good explanation. The wikipedia article isn't great either. I like this description:

https://github.com/mkirchner/hamt#persistent-hash-array-mapp...

The name does tell you quite a bit about what these are:

* Hash - rather than directly using the keys to navigate the structure, the keys are hashed, and the hashes are used for navigation. This turns potentially long, poorly-distributed keys into short, well-distributed keys. However, that does mean you have to compute a hash on every access, and have to deal with hash collisions. The mkirchner implementation above calls collisions "hash exhaustion", and deals with them using some generational hashing scheme. I think i'd fall back to collision lists until that was conclusively proven to be too slow.

* Trie - the tree is navigated by indexing nodes using chunks of the (hash of the) key, rather than comparing the keys in the node

* Array mapped - sparse nodes are compressed, using a bitmap to indicate which logical slots are occupied, and then only storing those. The bitmaps live in the parent node, rather than the node itself, i think? Presumably helps with fetching.

A HAMT contains a lot of small nodes. If every entry is a bitmap plus a pointer, then it's two words, and if we use five-bit chunks, then each node can be up to 32 entries, but i would imagine the majority are small, so a typical node might be 64 bytes. I worry that doing a malloc for each one would end up with a lot of overhead. Are HAMTs often implemented with some more custom memory management? Can you allocate a big block and then carve it up?

Could you do a slightly relaxed HAMT where nodes are not always fully compact, but sized to the smallest suitable power of two entries? That might let you use some sort of buddy allocation scheme. It would also let you insert and delete without having to reallocate the node. Although i suppose you can already do that by mapping a few empty slots.

EnTT is a popular alternative to flecs for C++, which has different performance/memory characteristics.

https://pastebin.com/VPypiitk This is a very small experiment i did to learn the metaprogramming features. its an ECS library using the same model as entt (https://github.com/skypjack/entt). In 200 lines or so it does the equivalent of a few thousand lines of template heavy Cpp while compiling instantly and generating good debug code.

Some walkthrough:

Line 8 declares a SparseSet type as a fairly typical template. its just a struct with arrays of type T inside. Next lines implement getters/setters for this data structure

Line 46 Base_Registry things get interesting. This is a struct that holds a bunch of SparseSet of different types, and providers getters/setters for them by type. It uses code generation to do this. The initial #insert at the start of the class injects codegen that creates structure members from the type list the struct gets on its declaration. Note also how type-lists are a native structure in the lang, no need for variadics.

Line 99 i decide to do variadic style tail templates anyway for fun. I implement a function that takes a typelist and returns the tail, and the struct is created through recursion as one would do in cpp. Getters and setters for the View struct are also implemented through recursion

Line 143 has the for expansion. This is how you overload the for loop functionality to create custom iterators.

The rest of the code is just some basic test code that runs the thing.

Since we wanted a common game simulation that would be on both the server and the client we looked into a few libraries that would fit our ECS needs. It was decided we were going to write this common part of our game in C++, but rust was considered. C++ was a familiar language for us so naturally EnTT and flecs came up right away. I had used EnTT before, writing some small demo projects, so our choice was made based on familiarity. In order to integrate with Unity we created a small C interface to communicate between our simulation code and Unity’s C#. Here’s close to what it looked like. I removed some parts for brevity sake.

Are you sure you don't want to use a C++ package manager? Libtcod is on Vcpkg and with that setup you could add the fmt library or EnTT. fmt fixes C++'s string handling and EnTT fixes everything wrong with the entities of the previous tutorials.

There's also a performance question. While we can now use Blueprint nativization to convert Blueprints to C++ the result will be a fairly naive version, fast enough for most purposes but not if you're trying to push every bit of performance. This is where you're looking at making sure you're hitting things such as using the CPU cache as well as possible for an ECS system (Look at ENTT or Flecs if you want to see what they're about and why you'd want one), or a system needing to process massive amounts of data quickly such as the Voxel Plugin.

For a modern engine you’re probably best looking at Unity’s DOTS. You may also want to check out some of the different open source ECS libraries such as flecs and EnTT are two popular ones for C++, but there’s lots of them. Largely you’ll see lots of different approaches taken, all with their own pros and cons. Not all of them will be performant (some focus more on the design benefits) while others will be optimised for certain use cases. What you should prioritise will depend on your specific needs.

You can think of DynaMix as combining one of these libraries with an ECS like entt(https://github.com/skypjack/entt)