2
\$\begingroup\$

This is a question about a passage from this article:

I suggest having every game object exist within a single giant array. This keeps game objects together in memory, and even though deletion of a game object is of O(n) complexity, that O(n) operation traverses an array, and usually will turn out to be unnoticeable. A custom vector or array class can be created that avoids the O(n) operation entirely by taking the element at the end, and placing it into the deleted slot.

I'm trying to understand what kind of operation the author is talking about. If I'm getting the overall point correctly, it's that accessing elements that are closer together in memory is faster, so therefor it's desirable to reorder the array such that there aren't any holes left when a game object is deleted.

If that is what the author means, then how is it possible to implement? This is what I'm imagining:

void Factory::addObject(const std::string name) {
    objects.push_back(new GameObject(name));

void Facrory::removeObject(const std::string name) {
    for(auto itr = objects.begin(); itr != objects.end()) {
        GameObject* obj = *itr;
        if(obj->name == name) {
            delete obj;
            // grab GameObject from end
            GameObject* endObj = objects.back();
            objects.erase(--m_objects.end());
            itr = objects.insert(itr, endObj);
        // else increment itr and continue

But that can't be right because just rearranging the pointers doesn't change how the memory is organized. So the author must be talking about something I don't understand about memory management.

My question is:
Have I misunderstood what the author meant? If not, then please explain how the author is suggesting the rearrangement is supposed to be done.

\$\endgroup\$
  • \$\begingroup\$ That question was puzzling me too. I would personally split objects by theirs staticness - trees and walls are not going to be destroyed(hopefully), put them to static array. Dynamic objects with short lifetime and low count like bullets - I would use some kind of linked structure. For particles? I do not know, I would implement own dynamic array and copy objects manually. (or compress it after each gameUpdate() pass. \$\endgroup\$ – wondra Jul 23 '14 at 23:16
  • \$\begingroup\$ Use a std::vector<GameObject> instead of a std::vector<GameObject*>, as simple as that. \$\endgroup\$ – API-Beast Jul 23 '14 at 23:17
  • \$\begingroup\$ @API-Beast does it perform the objects move internally? \$\endgroup\$ – wondra Jul 23 '14 at 23:18
  • \$\begingroup\$ Hmm, I guess in that case I'm guessing the factory is supposed to make a deep copy of the GameObject before deleting it. That sounds very questionable and troublesome to me. \$\endgroup\$ – Anonymous Entity Jul 23 '14 at 23:25
  • \$\begingroup\$ The technique mentioned is an ancient trick for fast erases when you have a container with cheap end-removal and where order does not matter. The purpose is to avoid shifting the tail set of elements one-to-the-left which would be the normal effect of an erase-in-the-middle. \$\endgroup\$ – Lars Viklund Jul 24 '14 at 14:09
2
\$\begingroup\$

This is a good question. I was trying to express that instead of holding an array of pointers to game objects, you can hold an array of game objects themselves, as pointed out by API-Beast in the comments of your question.

You can implement this swap operation like this, assuming the array holds structs with simple data (structs with ints, floats, etc., no free, no delete, no malloc, no new, no deep copies):

void Array::Release( index i )
{
    m_array[ i ] = m_array[ --m_size ];
}

Please note that it is important to be able to refer to an object by its index. In your question you are looking up an object by string, which means there's not a clear mapping from string to memory location. If you use an integer index you can understand exactly where in memory (in the array) the object is located. This lets you grow the array by allocating a bigger array, copying the old elements over, and freeing the new array. Old indices into the old array will still work with the new array memory.

This is just how the swap operation works. You'll need to somehow update the index of the moved object, which is where the idea of a handle becomes useful. Implementing handles is another different topic, but will probably be necessary for being able to move objects around in memory without any dangling pointers. The idea of utilizing the cache properly, handles, simple structs and copying the last element is talked about in detail in the next article: http://www.randygaul.net/2014/06/25/cache-aware-components/

\$\endgroup\$
  • \$\begingroup\$ @user11177 UUID would be a good way to do it :) \$\endgroup\$ – RandyGaul Jul 24 '14 at 18:22

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.