Question about game engine pointers

[joshalb]

A friend and I are working on our first game engine in C++. We're both new to C++, but not to programming in general. Our current method of handling objects (things within the game, such as a player object) works fine, and is pretty fast! But I'm not sure if it's practical (or maybe there's a faster, more stable way?). So I'm going to post what we have (in a nutshell, obviously not the whole game engine, not even a part of it, just a small example of how this portion of it works), and I want to know what you, the experts, think about what we're doing.

So here's what I've got to demonstrate basic functionality:

#include <iostream>
using namespace std;

#define MAX_INSTANCES 10000

// The base object, that all our other objects will use as a parent.
class baseObject
{
    public:
    virtual void Step() {}
};

// An object specific to this game, derived from our base object so we can store it in our pointers
class anotherObject : public baseObject
{
    public:
    virtual void Step()
    {
        cout << "Hello!" << endl;
    }
};

// Pointers for all instances in the game
baseObject*instances[MAX_INSTANCES];
// Whether an instance exists or not (whether we should process it in engineStep)
bool instanceExists[MAX_INSTANCES];

// Create an instance, and store it in a pointer, return the pointer array's id
int createInstance(baseObject*object)
{
    // search for a pointer not in use already
    int id;
    for (id=0; id<MAX_INSTANCES; id++)
    {
        if (!instanceExists[id])
        {
            break;
        }
    }
    if (id != MAX_INSTANCES) // did we find an empty pointer?
    {
        instances[id] = object;
        instanceExists[id] = true;
    }
    else // if all pointers are full, set id so the function will return -1 (indicating error)
    {
        id = -1;
    }
    return id;
}

void engineStep()
{
    // find all in-use pointers and execute the object's 'step' event within
    for (int i=0; i<MAX_INSTANCES; i++)
    {
        if (instanceExists[i])
        {
            instances[i]->Step();
        }
    }
}

int main()
{
    // this is just to demonstrate how it all works, we can create instances, and when step is called, each of their 'step' events will execute
    createInstance(new anotherObject);
    engineStep();
    engineStep();
    engineStep();
    createInstance(new anotherObject);
    engineStep();
    // final output is 5 'Hello!'s
    return 0;
}

Aside from the comments, here's some things to take note of:

1. Virtual functions. I don't really understand how they work... but they work! Bonus points goes to anyone who helps me understand those! :P
2. 10,000 pointers. The main reason I'm questioning our method.. we must allocate all these pointers when most people won't have 10,000 instances of each object in their game.
3. I'm not having any issues with this code, everything runs fine. I'm just wanting to know if this is absolute crap programming, and if so, what would be a better way to do this?

Thanks for your time.

[thelamb]

Hmm, your method to search for the next 'available' pointer-'spot' is not very efficient.
You are using C-style arrays... which is no necessarily wrong but what you're trying to do is much easier by using C++ vector's. You won't need the 'instanceExists' array then:

#include <vector>
using std::vector;

vector<baseObject*> vInstances;

createInstance()
{
   baseObject* pBase = new something();
   vInstances.push_back( pBase );
}

vectors are maybe slightly slower than bare C arrays, but you need to be very confident with working with arrays to beat the vector's performance (e.g. writing correct search algorithms etc.).

What don't you understand about virtual functions? You use them (almost) correctly. One of the purposes is if you have multiple types of object, which all share a common functionality, so they inherit from one base class. But there can be some functionality that is implemented differently for the different types of objects.
Consider shapes(circle, rectangle etc.) they all have dimensions, and they all have an area... but the area of a circle is calculated differently than the are of a rectangle. So the base class defines a virtual area functions, and all shapes implement this in their own specific way.
Also, if you call virtual functions through a pointer or a reference of the base class the compiler will know that it has to call the virtual function of the derived class.

What can be improved in your example:

class baseObject
{
    public:
    virtual void Step() = 0;
};

the '= 0' will make Step a pure virtual function, _forcing_ any class that inherits from this base class to implement Step().

[joshalb]

>>Hmm, your method to search for the next 'available' pointer-'spot' is not very efficient.
I figured someone would catch me on this. Thanks for the suggestion!

>> What don't you understand about virtual functions?
Why they worked, when regular functions didn't. Your response cleared that up. I had no idea that the very purpose of them was exactly what I was doing. Awesome!

>> the '= 0' will make Step a pure virtual function, _forcing_ any class that inherits from this base class to implement Step().
Oh, thanks. I'll definitely be making that change.

Just so I'm clear though, everything else looks fine? The fact I'm making 10,000 pointers when that limit may never be reached is exactly what I should be doing?

[thelamb]

Well, allocating sort of a 'pointer pool' will be more efficient if you will be doing a lot of allocation/deallocations. But if you use a vector this can be done more easily. E.g. at startup you can say 'vInstances.resize( some_number )' and it will pre-allocate memory of this size. If the vector then grows past this size the vector will internally allocate more memory.

So, in essence.. this pre-allocated array you have exposes a lot of implementation detail (the Existance-array) that you really don't want to be dealing with. So definitely have a look at vectors, and at resize.

This 'problem' is simmilar to an assigment that we let students of the OperatingSystems at my univeristy do. They are provided with a structure, and a benchmark program which allocates and deallocated thousands of instances. They need to code a 'manager' to speed this up.
What they mostly do is write a wrapper for malloc(), the first time it is called they allocate 100 * size_of_structure, and whenever a request is made for a new allocation, they increase an index and just return a pointer somewhere in this pre-allocated pool.

Performance of 100000 times 100 allocation/deallocations on my machine was 0.11 second with the new malloc versus 0.5 without any pre-allocation.
So this is not a difference that you are likely to notice.

[joshalb]

Makes sense, I'm going to look into vectors now. Thanks for all your help. :)