Spieleprogrammierung - ausgesuchte Themen

Update der OpenGL Programmbeispiele

2012-01-22T17:36:00.000+01:00

Kurz Notiert – alle Programmbeispiele sind dahingehend überarbeitet worden, um mögliche Kompatibilitätsprobleme mit dem neuesten AMD Catalyst Treiber 12.1 zu beheben. Die überarbeiteten Demoprogramme stehen ab sofort zum Download bereit.

OpenCL Tutorial – Offline Compilation (Download)

2012-01-05T20:50:00.024+01:00

In der Regel werden OpenCL-Programme zur Laufzeit für ein zuvor ausgewähltes Gerät – beispielsweise für die in einem Rechner verbaute Grafikkarte – kompiliert. Alternativ zu diesem als Online Compilation bekannten Verfahren, lassen sich auch bereits im Vorfeld kompilierte Programme verwenden (Offline Compilation). Der Nachteil der Offline Compilation besteht jedoch darin, dass ein vorkompiliertes Programm immer nur auf einer einzigen Plattform und einem einzigen Gerät lauffähig ist.

Für das heutige Tutorial wurde die COpenCLProgram-Klasse aus dem letzten Programmbeispiel dahingehend erweitert,

dass sich OpenCL-Programme kompilieren und im Anschluss daran abspeichern lassen (Offline Compilation, Build_PrecompiledClBinary()) und
dass nunmehr auch vorkompilierte Programme verwendet werden können (Build_ProgramFromPrecompiledClBinary()).

Hinweis:

Für die Ausführung dieses Programmbeispiels muss der Treiber Ihrer Grafikkarte die OpenGL Version 3.3 unterstützen.

Visual C++ 2010: DemoWithOpenGL2010_Tut49

Speicherverwaltung – Random Memory Allocation

2011-11-16T15:14:00.004+01:00

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;
    }

}

OpenCL Tutorial – Masspoint Movement, Collision Hash Grids (Download)

2011-09-26T15:06:00.005+02:00

Der Schwerpunkt des heutigen Tutorials liegt im Entwurf eines einfachen OpenCL-Frameworks sowie in der Implementierung einer einfachen OpenCL-basierten Bewegungssimulation für ein Asteroidenfeld:

Simulation der Asteroiden-Bewegung (jedem Asteroid ist eine einzelne Punktmasse zugeordnet).
Berechnung der Gitter-Indices und -Positionen in einem Kollisionsgitter (Collision Hash Grid) für eine effiziente Kollisionsprüfung.

Für die Initialisierung einer OpenCL-Anwendung ist die COpenCLDevice-Klasse verantwortlich:

class COpenCLDevice
{
public:

    cl_platform_id   Platform;
    cl_device_id     Device;
    cl_context       DeviceContext;
    cl_command_queue DeviceCommandQueue;

    bool use_GPU_Device;

    COpenCLDevice();
    ~COpenCLDevice();

    void Init_Device(bool useGPU);
    void Wait(void);
};

Zuständig für die Handhabung eines einzelnen OpenCL-Programms (Kernel) ist die COpenCLProgram-Klasse:

class COpenCLProgram
{
public:

    cl_program Program;
    cl_kernel Kernel;

    cl_uint WorkGroupDim;
    size_t local_ws;
    size_t global_ws;
    size_t MaxBufferElements;

    COpenCLDevice* pUsedOpenCLDevice;

    COpenCLProgram();
    ~COpenCLProgram();

    void Set_OpenCLDevice(COpenCLDevice* pOpenCLDevice);

    // Laden und Kompilieren eines OpenCl-Programms
    void Build_ProgramFromSourceFile(char *pKernelName, char *pFileName,
         cl_uint workGroupDim, bool fastMath, size_t maxBufferElements,
         size_t num_WorkItems_Per_WorkGroup = 0);

    // Ausführen eines OpenCL-Programms:
    void Execute_Program(void);
    void Execute_Program_With_UserDefined_Num_WorkItems_Per_WorkGroup(void);

    void Execute_Program(cl_uint numEventsInWaitList, const cl_event
                         *pEventWaitList, cl_event *pEvent);
    void Execute_Program_With_UserDefined_Num_WorkItems_Per_WorkGroup(
         cl_uint numEventsInWaitList, const cl_event *pEventWaitList,
        cl_event *pEvent);

    // Methoden für die Parameter-Übergabe an ein OpenCL-Programm (Kernel):
    void Set_KernelArg(cl_uint pos, cl_mem* pInput);
    void Set_KernelArg(cl_uint pos, int input);
    void Set_KernelArg(cl_uint pos, double input);
    void Set_KernelArg(cl_uint pos, float input);
    void Set_KernelArg(cl_uint pos, size_t input);
};

Die nachfolgenden Container-Klassen (Arrays von Vektoren und Skalaren) fungieren als Schittstelle zwischen einem OpenCL-Kernel und dem Hauptprogramm:

class COpenCL_FloatScalar_Container;
class COpenCL_2DFloatVector_Container;
class COpenCL_3DFloatVector_Container;
class COpenCL_4DFloatVector_Container;

class COpenCL_IntegerScalar_Container;
class COpenCL_2DIntegerVector_Container;
class COpenCL_3DIntegerVector_Container;
class COpenCL_4DIntegerVector_Container;
class COpenCL_NDIntegerVector_Container;

Die nachfolgenden Klassen ermöglichen den Zugriff auf einzelne Elemente der Container-Klassen aus dem Hauptprogramm heraus:

class COpenCL_FloatScalar;
class COpenCL_2DFloatVector;
class COpenCL_3DFloatVector;
class COpenCL_4DFloatVector;

class COpenCL_IntegerScalar;
class COpenCL_2D IntegerVector;
class COpenCL_3D IntegerVector;
class COpenCL_4D IntegerVector;
class COpenCL_NDIntegerVector;

Verantwortlich für die Durchführung der Bewegungssimulation ist der nachfolgende OpenCL-Kernel:

__kernel void MasspointMovement_GPU(__global float4* Position,
                                    __global float4* Velocity,
                                    __global int4* GridPosition,
                                    __global int4* GridIndex,
                                    const float TimeStep,
                                    const float InvGridSize,
                                    const float GridOffset,
                                    const float GridCenterX,
                                    const float GridCenterY,
                                    const float GridCenterZ,
                          const int HalfNumCollisionGridElementsXDirPlus1,
                          const int HalfNumCollisionGridElementsYDirPlus1,
                          const int HalfNumCollisionGridElementsZDirPlus1,
                          const int HalfNumCollisionGridElementsXDirMinus1,
                          const int HalfNumCollisionGridElementsYDirMinus1,
                          const int HalfNumCollisionGridElementsZDirMinus1)
{
    size_t id = get_global_id(0);

    // Bewegungs-Simulation (kräftefrei):
    Position[id] += Velocity[id]*TimeStep;

    // Gitterkoordinaten berechnen:
    GridPosition[id].x = (int)(GridOffset+
                              (Position[id].x-GridCenterX)*InvGridSize);
    GridPosition[id].y = (int)(GridOffset+
                              (Position[id].y-GridCenterY)*InvGridSize);
    GridPosition[id].z = (int)(GridOffset+
                              (Position[id].z-GridCenterZ)*InvGridSize);

    // Hash-Grid-Index berechnen:
    GridIndex[id].x =
   GridPosition[id].x % HalfNumCollisionGridElementsXDirPlus1 +
   HalfNumCollisionGridElementsXDirMinus1;

    GridIndex[id].y =
   GridPosition[id].y % HalfNumCollisionGridElementsYDirPlus1 +
   HalfNumCollisionGridElementsYDirMinus1;

    GridIndex[id].z =
   GridPosition[id].z % HalfNumCollisionGridElementsZDirPlus1 +
   HalfNumCollisionGridElementsZDirMinus1;
}

Hinweis:

Für die Ausführung dieses Programmbeispiels muss der Treiber Ihrer Grafikkarte die OpenGL Version 3.3 unterstützen.

Visual C++ 2010: DemoWithOpenGL2010_Tut48

Neufassung der Artikelserie zum Thema Wegfindung

2011-09-16T16:11:00.000+02:00

Die Artikel zum Thema Wegfindung wurden komplett neu verfasst und orientieren sich nun direkt an den folgenden Programmbeispielen:

OpenGL-Programmbeispiel:

http://www.spieleprogrammierung.net/2010/04/opengl-3-wegpunkte-navigation-download.html

OpenGL-Framework-Programmbeispiel:

http://www.graphics-and-physics-framework.spieleprogrammierung.net/2011/05/tutorial-13-wegfindung-flocking.html

Artikel 1: Wegfindung – Einführung

Artikel 2: Entwurf eines Wegpunkte-Systems

Artikel 3: Routinen für die Wegfindung