Speicherverwaltung – Random Memory Allocation

Gutes Ressourcenmanagement zählt zu den wichtigsten Herausforderungen bei der Entwicklung eines Computerspiels. Bei der Darstellung von detailreichen und weitläufigen Spielewelten müssen kontinuierlich die hierfür benötigten Geometrie- und Textur-Daten geladen und die nicht mehr benötigten Daten aus dem Speicher entfernt werden (Streaming). Betrachten wir als Beispiel das Spiel Minecraft. Lediglich die Teile der Spielewelt, die sich im näheren Umfeld des Spielers befinden, werden auch wirklich in den Speicher geladen. Die Welt wird hierbei in sogenannte Chunks eingeteilt, wobei jeder Chunk aus 16 (Breite) mal 16 (Länge) mal 128 (Höhe) Blöcken besteht. Insgesamt werden 81 Chunks im Speicher gehalten, die in einem 9 mal 9 Quadrat um den Spieler herum gruppiert sind.
Betrachten wir als zweites Beispiel kurzlebige Spieleobjekte wie Waffenprojektile und Trümmerteile die noch dazu in großer Zahl auftreten. Der für diese Objekte benötigte Speicher muss sich möglichst schnell dynamisch allozieren (zuweisen) und wieder freigeben lassen. Kurzum, ohne eine vernünftige Speicherverwaltung sind wir völlig aufgeschmissen.
In C++ lassen sich dynamische Speicherbereiche mithilfe der Operatoren new und delete anfordern und wieder freigeben. Man hat jedoch keine Kontrolle darüber, welche Speicherbereiche man zugeteilt bekommt, was bei übermäßigem Gebrauch letzten Endes zu einer zunehmenden Fragmentierung des Speichers führt.

Zweckmäßigerweise sollten new und delete lediglich bei Programmstart (Anfordern des maximal benötigten Speichers) und Programmende (Freigabe des bei Programmstarts angeforderten Speichers) verwendet werden. Zur Laufzeit sollte die dynamische Speicherzuteilung und -freigabe mittels eines eigenen Speichermanagers erfolgen.

Betrachten wir als Beispiel die Klasse CSimpleObjectInstance als Prototypen für ein beliebiges Spieleobjekt. Bei Programmstart würden wir zunächst ein Array aus Klasseninstanzen anlegen, wobei die Anzahl der Arrayelemente der maximal möglichen Anzahl von Spieleobjekten entspricht. Zunächst sind die einzelnen Arrayelemente noch unbenutzt (used == true).

class CSimpleObjectInstance
{
public:

    bool used;
    long ID;

    CSimpleObjectInstance();
    ~CSimpleObjectInstance();

    void Initialize(long id);
    void TurnBack(void);

};

CSimpleObjectInstance::CSimpleObjectInstance()
{
    used = false;
    ID   = -1;
}

void CSimpleObjectInstance::Initialize(long id)
{
    used = true;
    ID   = id;
}

void CSimpleObjectInstance::TurnBack(void)
{
    used = false;
    ID   = -1;
}

Die Klasse CSimpleObjectInstancePool übernimmt die Aufgabe des Speichermanagers und ist für die Verwaltung des CSimpleObjectInstance-Arrays verantwortlich.

• Die Methode Init_ObjectInstancePool() erzeugt zunächst ein Array aus CSimpleObjectInstance-Klasseninstanzen.
• Die Get_Unused_ObjectInstance()-Methode sucht nach einem aktuell unbenutzten Arrayelement und liefert einen Zeiger auf ein solches zurück. Die CSimpleObjectInstance-Membervariable used wird zuvor auf true gesetzt.
• Die Methode Release_ObjectInstance() gibt ein momentan verwendetes Arrayobjekt wieder frei, indem die CSimpleObjectInstance-Membervariable used wieder auf false gesetzt wird.

class CSimpleObjectInstancePool
{
public:

    long NumObjectInstancesMax;
    long NumObjectInstancesUsed;

    CSimpleObjectInstance* ObjectInstance;

    CSimpleObjectInstancePool();
    ~CSimpleObjectInstancePool();

    void Init_ObjectInstancePool(long numObjectInstancesMax);

    CSimpleObjectInstance* Get_Unused_ObjectInstance(void);
    void Release_ObjectInstance(CSimpleObjectInstance** ppObjectInstance);

};

void CSimpleObjectInstancePool::Init_ObjectInstancePool(
                                long numObjectInstancesMax)
{
    NumObjectInstancesMax = numObjectInstancesMax;
    NumObjectInstancesUsed = 0;

    SAFE_DELETE_ARRAY(ObjectInstance)

    ObjectInstance = new CSimpleObjectInstance[NumObjectInstancesMax];

    for(long i = 0; i < NumObjectInstancesMax; i++)
        ObjectInstance[i].ID = i;

}

Mehr noch als in konventionellen Anwendungen kommt es in Computerspielen darauf an, dass Speicher so schnell wie möglich zugewiesen und wieder freigegeben werden kann. Im konkreten Fall benötigen wir also für unsere Get_Unused_ObjectInstance()-Methode ein Verfahren für die schnelle Suche eines momentan unbenutzten Arrayelements.

Beim einfachsten aber auch langsamsten Verfahren würde man das komplette Array nach einem unbenutzten Element durchsuchen und die Suche bei Erfolg abbrechen. Die Suchzeit würde jedoch hierbei linear mit der Anzahl der bereits genutzten Elemente ansteigen.

Im Unterschied dazu erfordert die sogenannte Random Memory Allocation weitaus weniger Suchschritte. Hierbei wird nach dem Zufallsprinzip ein Arrayelement ausgesucht. Ist dieses Arrayelement unbenutzt, kann die weitere Suche eingestellt werden. Sind beispielsweise 50% der Arrayelemente in Benutzung, so sind im Durchschnitt lediglich zwei Versuche notwendig (Suchtiefe 2), um ein unbenutztes Element zu finden. Bei 75% benutzter Arrayelemente ist mit durchschnittlich 4 Suchschritten zu rechnen:

CSimpleObjectInstance* CSimpleObjectInstancePool::
                       Get_Unused_ObjectInstance(void)
{
    if(NumObjectInstancesMax == NumObjectInstancesUsed)
        return NULL;

    long id;
    bool used = false;
    long counter = 0;

    // Maximale Anzahl von Suchschritten (Suchtiefe)
    long counterMax = 100*NumObjectInstancesMax;

    do
    {
        id = RandomNumbers.Next_IntegerNumber(0, NumObjectInstancesMax);

        used = ObjectInstance[id].used;

        if(used == false)
            break;

        counter++;

    }
    while(counter < counterMax);

    if(used == false)
    {
        NumObjectInstancesUsed++;
        ObjectInstance[id].used = true;
        return &ObjectInstance[id];
    }
    else
        return NULL;
}

void CSimpleObjectInstancePool::Release_ObjectInstance(
     CSimpleObjectInstance** ppObjectInstance)
{
    // Release unnötig / Zeiger enthält keine Adresse
    if(*ppObjectInstance == NULL)
        return;

    if((*ppObjectInstance)->used == true)
    {
        NumObjectInstancesUsed--;
        (*ppObjectInstance)->used = false;
        *ppObjectInstance = NULL;
    }

}