1
\$\begingroup\$

Introduction

I try to create a game engine with component-based architecture.

There are many type game components and different game systems.

For example, the components can be

  • Com_HP (health), Com_Physics , Com_Graphics, ...

The systems can be

  • Physics_Manager, Graphics_Manager, Binder_Manager, ...

Most systems want to cache relation (map{Key->Value}) that has game component as Key, but the Value can be any type.

For example,

System_Binder : Hashtable<Com_Graphics*,Com_Physics*>.
System_PhysicFactory : Hashtable<Com_Physics*,someInternalData*>.

The components that are cached are only subset of all instance of components of that type.

In other words, not all Com_Graphics instances in the game engine are in the key of the System_Binder's Hashtable.

This problem can be solved easily with some standard library.

However, the retrieve, insert, erase performance is very crucial.
- After test, I found that standard hashmap/hashtable's performance is not good enough.

Therefore, I developed a custom hash table, let's name it AMap.

The custom HashTable (hashmap)

AMap works almost like general hash table, but it take responsibility to create hashCode (instead of the Key's responsibility), and assign hashCode to a special field of Key.

The special field of Key have to be fed to the AMap, let's call this field as dedicated###.

Here is pseudo code of AMap :-

template<class Key,class Value, int Key::*dedicatedField>class AMap{
    Array<pair<Key,Value>> chunk; //like a pool
    // Key & Value are usually pointers.
    Queue<int> recycleNotUsed; //contain index of "chunk" that is not used
    int indexRunner=0; //count from 0 and so on ...
    void add(Key key,Value value){
        int index; // replace traditional hashCode
        if( recycleNotUsed.isEmpty() ){
            index = indexRunner++; //count from 0 and so on ...

        }else{
            index = recycleNotUsed.popFirstElement(); //use recycled key
        }
        key.dedicatedField = index ; //### assign to the dedicated field
        chunk[index ] = {key,value};
        //... house keeping about flag that [index] is valid ....
    }
    void remove(Key key){ 
        recycleNotUsed.pushLastElement(key.dedicatedField );  //###
        //... house keeping about flag that the [key.dedicatedField] is invalid ....
    } 
    Value get(Key key){ 
        chunk.get(key.dedicatedField).second; //### so fast
    } 
    //.... other function like iterator, get, set, ....
}

The ### line mark dedicated field. I will show how to feed it to a certain AMap.

When I want to create any AMap, I have to create a dedicated field in the Key class.

// System_Binder.h : This is a field that I want.
AMap<Com_Graphics*,Com_Physics*> graphic_to_physics; 

// Com_Graphics.h : I have to add a dedicated field to Com_Graphics.h
int dedicated_System_Binder = -1;  //### 

// System_Binder.h : This is what I have to declare 
AMap<Com_Graphics*,
     Com_Physics*,
     &Com_Graphics::dedicated_System_Binder>   //### 
     graphic_to_physics; 

After another test, AMap, compared to std::unorder_map, is astonishing fast (30-40x). Memory is also packed.

However, there are some disadvantages.

Disadvantage of my custom HashMap

  • I have to create 1 dedicated field for any Com_XXX per 1 hash map that use that Com_XXX as a key, as in the example.

  • For example, if a system has 2 maps, both use Com_HP as key, I have to create 2 dedicated fields within Com_HP.

  • Lower maintainability, e.g.,

if I want to remove the field ...

// System_Binder.h : 
AMap<Com_Graphics*,Com_Physics*, ...dedicate...> graphic_to_physics; 

... I should also remove this line

// Com_Graphics.h : 
int dedicated_System_Binder = -1;
  • A limited number of map have to be defined beforehand, because each one has to have a corresponding dedicated variable in the Key class. For example, if there are 2 instances of the same system (e.g. 2 Physic_Manager) , the game will potentially crash.

Question :

  • Is the code good in term of design?

  • Are there any better alternatives that provide similar/better performance, but higher maintainability, flexibility and usability?
    (Just provide a good link can be considered a correct answer)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.