richardlord/Ash — Issue #2: Experimenting with different data structures types
Author: Glidias
Created: 2012-03-04 07:29:44+00:00
State: open

I've been creating some data structures like in Ash within Haxe ( i intend to put it up later), to support strictly typed Generic lists. I intend for Families to be able to support their own data structures (which can be strictly-typed) , unlike what we have now in Ash which requires type-coercsion per node iteration. Amazingly, I managed to create Generic MixList classes (ie. singly/doubly-linked lists to whose data itself is the node, with built-in typed .next/.prev pointers) without having to rely on Macros, just Generics. ( I remembered trying to do this once in Haxe with generics, but couldn't get it to work...but now it does!). This differs a lot from most linked list implementations you have now in Haxe, which requires the Node to contain the data T. Now, this iisn't ncesary and all you need now is to have your own custom node data class implement an interface like MyOwnDataNode implements IDLMixNode with the required next/prev:MyOwnDataNode pointers, and create a list like "new DLList()", and you're done! So, it's possible to use Haxe to help generate out strictlydata- typed linked-lists, or other data structure types like pools and such, without having to repeat oneself.

Albeit, I still dislike Haxe for several as3 lacks, namely it's for-loop which is restricted to purely numeric iterations. A while loop alternative can be dangerous if one forgets to add boiler-plate endloop code during continue or at the end of the iteration block. It also has quirks with adding extra code to non-empty/extended Flash instance constructors. So, I let Haxe be used purely for the framework itself and some common components, and leave the implementation elsewhere to the relavant target engines. (AS3/JS/etc.)

DLL review in NodeList/NodePool and Signals:

I noticed that your doubly-linked list implementations doesn't set .next and .prev pointers of a removed node to be null, because it's possible that the .next pointer is still required during an update loop to iterate dynamically to the next valid node instance to be processed. As a result, when it comes to pooling nodes, one would set the .prev pointer to a cacheTail pointer, and defer the .next collection as a process of joining up the nodes back to the main pool header only after the game has finished updating. This isn't too bad especially in cases where certain Families might want to do specific reset methods for those given node components, if pooling was assumed to be done in those circumstances.

Q1: Is it possible to do this after a Family has finished updating the list? From what I see, the only case of invalidation occurs during the update of each individual list, so, it's possible to do direct removal of other nodes from other families' lists so long as there's no iteration through those lists during the game update loop. Am I right to hold that assumption? It's possible to set the(lock) flag over each family itself, however, Systems have no access to Families directly, only to a node list implementation , thus, to simply rely on a the game's gameUpdating state is used for simplicity, albeit that's a conservative approach. Logically, I think it's possible to have the "lock" flag be stored in the nodeList itself, so each Family can check whether the nodeList's lock flag was activated, or not. It would be the responsibility of the Systems therefore to mark each dll data structure as lock vs unlocked, very much like how you handle your BaseSignal. (Which i also ported to Haxe btw so you now have Generic typed Signal1/2/3 combinations, and the listener list uses a DLMixList class ).

Since removed nodes have no reference to the Family that holds it, a signal must be used to notify of removal to the Family that handles the pool. Albeit, I find the signals approach a bit heavy-handed, since I can't foresee any other situations where a nodeRemoved/nodeAdded signal might prove useful, (Except possibly nodeRemoved can help in pooling externally like what we have now). Another possible way is to have each linked list have their own internal pool, and lock flag, so the linked list will be responsible for creating the node and adding it, with the addNode():T factory method returning the node so it can be edited from the outside.) Usage of such a data structure requires knowledge on the Systems programmer's part to manually lock the list, unlock it, and release it, something which may not be too ideal for end-users.

Q2: Are there any possible needs of a nodeRemoved/nodeAdded signal outside of what we have now?

SSL consideration:

If a singly-linked list implementation was used, immediate removal during an update loop (where any node can be removed from any position) won't work as it'll possibly cause problems with the .next pointer canceling off. Even saving out the .next beforehand using a var next:Node = n.next at the beginning of a for loop won't work in cases where n.next was killed halfway during the process of that iteration, such that next:Node shouldn't have had existed anymore. If a singly-linked list was used in this way, than each node MUST always be processed whether it's dead or not, so each node would therefore require a "dead" boolean flag to mark nodes to be ignored, and a local prev:Node variable during each iteration is recorded to link up any given prev node to the next node, ignoring the dead node in the middle, which returns back to an object pool.
This was what I had done in my previous framework, which I tightly coupled 3d entities to the Alternativa3D7 engine, which also adopted a singly linked list display-list structure, where i wanted to avoid the overhead of iterative removeChild() calls but simply bundled the whole process together. Killing an entity simply means setting the dead flag to true, but that would mean other processes had to check for that flag, which wasn't too ideal.

The advantage of singly linked list nodes is the ability to save memory with just 1 pointer per node. It also makes the process of unlinking nodes easy if one uses a "dead" flag per node approach, albeit that would mean each loop iteration per node must check for the "dead" flag, so all nodes must still be processed no matter what and can't be canceled off halfway. This is unlike a 0(1) doubly-linked list node removal has more "if" considerations per remove operation but has the benefit of shortening the list during the update loop itself.

VectorIndex consideration:

A vector index is a vector that holds a certain data-type of object containing a "public var index:int" value so one can record the index of that object within the vector. Removal is as simple as checking the "index:int" value of the object to be removed, and perform a pop/pop-back operation accordingly, without necessarily having to resize the Vector unless one so wishes. Such a Vector buffer can be of a fixed size as well. I find this data structure is very good for going through a list which is assumed to NOT change that list's each iteration (ie. no removal/re-ordering and such during the loop). Thus, it makes a good option for RenderNodes, since such a loop would not require removal/re-ordering during that process.

The dreaded hash:

Hashing is often done in desperate situations . The fact that a data structure must hash an entity to avoid repeated additions ((though i admit a Family bitmask would be another example). The fact that an entity must be hashed in order to reference a given node from a given data structure. It might be possible to have FamilyKey: family:Family, key:* singly-linked mix list within an Entity to avoid a hash lookup, so removing an Entity could be as single as asking each Family to removeEntityByKey(key:*), the key most likely being type-coereced to the given node item being used for direct (usually (0)1)) removal depending on the data structure type. Assuming no new systems/families are being added during the game itself (ie. they are all pre-registered beforehand), some stuff like the entity list and hash within the Game itself can also be removed.

Systems:

I find a doubly-linked mix list for Systems isn't too ideal, as quickly switching between differnet GameStates that adopt different System combinations in FSM manner, won't work. Possibly, a TraditionalLinkedList/TraditionalNode approach should be used instead, or just multiple Vector>.,to allow seamless switching of states without having to modify (and re-sort) the current System list. Often, games tend to have transitions between levels, and ingame machinma cutscenes where certain systems no longer come into play, while some systems (like the RenderingSystem), is still being used.