Array alive/dead entity “refresh” algorithm

If only a relatively small number of entities change state per update, it might be more efficient to keep the live entities contiguous all the time. That is, you'd:

• maintain a single size variable, storing the current number of live entities;

• when a new entity is born, increment size and add the new entity to the array at position size-1;

• when an entity dies, decrement size, replace the dead entity in the array with the live entity at index size (unless that was the entity that died), and immediately de-initialize the dead entity (or add it to a separate queue of dead entities to be de-initialized later).

Alternatively, if you wish to maintain a pool of dead entities for reuse (or just to de-initialize later), you can modify the method slightly to also keep them in a contiguous block at the end of the array:

• when an entity at index i dies, decrement size and swap the entities at indices i and size;

• when a new entity is born, either reuse the formerly dead entity at index size, or (if entities are not reusable) replace the dead entity at index size (if any) with a new live entity, and append the dead entity to the end of the array instead.

Of course, this requires entities (or at least the code handling them) to know where they are located in the array. There are various ways to implement this, but the simplest way (at least if you know that each entity belongs to a single array) is just to include the array index as one of the entity's properties. Also, of course, when you move entities around in the array, you will also need to remember to update their stored indices.

The advantage of this method is that you'll never need to scan the array looking for dead entities. You may also be able to simplify other code, if you can always be sure that all entities below size in the array are alive.

You did count the number of objects you killed off didn't you? else now is the time!

void FixUp(int lastLiving) {
    // ToDo guard with ifdef with test for debug.
    for(int iA= lastLiving; iA >= 0; --iA) {
        assert(isAliveAt(iA));
    }

    msize = sizeNext = lastLiving+1;

    for(; lastLiving< intSizeNext; ++lastLiving) {
        assert(isDeadAt(lastLiving));
        deinitAt(lastLiving);
    }
}

void refresh(int numOfDead) {
    // `sizeNext` is unsigned - copy it as a signed value
    // to store its initial value and compare it to integers.
    const int intSizeNext(sizeNext);

    // `iD` walks from left to right, looking for dead entities.
    int iD{0}, iA{intSizeNext - 1};

    // Find dead item from left 
    // only need to check up to the number of none-dead
    for(; ID < intSizeNext-numOfDead+1; ++iD) {
        if(isDeadAt(iD)) {
            // find alive
            for (; isDeadAt(iA); --iA);   

            assert(isDeadAt(iD) && isAliveAt(iA));
            std::swap(items[iD], items[iA]);
            assert(isAliveAt(iD) && isDeadAt(iA));
            --iA;

            // assumption the living outnumber the dead greatly
            // if not move FixUp down after the loop and delete the test.
            if (0 == (--numOfDead)) {
               FixUp(ID);
               return;
            }
        }
    }
}

After writing this I think its more effective for lists where relative few are dead compared to the living to make a deadList and then itereate over that, all others must be alive.

vector<int> deadList; // add dead nodes to this.

void refresh(int numDead) {
    int iA{intSizeNext - 1};

    for (auto dead: deadList) {
        // check if dead is after deadZone
        if (dead > intSizeNext-numOfDead)
            continue;  // no need to do anything

        // find alive
        while (isDeadAt(iA))
            --iA;

        assert(isDeadAt(dead) && isAliveAt(iA));
        std::swap(items[dead], items[iA]);
        assert(isAliveAt(dead) && isDeadAt(iA));
        --iA;

    }
    FixUp(iA);
}

Run time O(dead) which should be much less than O(n);

You could probably use std::remove_if instead of your algorithm. Take this example code:

std::vector<std::string> vec = { "0", "1", "5", "0", "3", "6", "0", "1" };
std::remove_if(std::begin(vec), std::end(vec), [](const std::string& val)
{
    return val == "0";
});

for (auto&& a: vec)
{
    std::cout << a << ' ';
}

I get the following output:

1 5 3 6 1 0 0 0

std::remove_if swaps the elements of a range so that the elements that are to be kept are at the beginning of the range and maintains their order. The elements that are still at the end have unspecified values, but if Entity is an RAII class, the deinitialization will happen at destruction. Since I don't know what Entity looks like, I can't be sure that this method will work, but there is probaby a way to ensure that it will do what you need it to do.

This method has two advantages: it allows to think in term of iterators instead of sizes and it uses an already existing algorithm. In your case, refresh could probably look like this:

void refresh()
{
    std::remove_if(std::begin(entities), std::end(entities),
                   [](const Entity& ent)
                   {
                       return ent.isDead();
                   });
}

Once again, I am assuming some implementation details that are not shown though. Anyway, try check whether std::remove_if coud be used to do what you want it to do. Standard algorithms can often do much more things than thought.

I'll start out by thanking you for the pretty pictures, I always appreciate a question with pretty pictures :)

I can only really comment on the gotos, and, well, is there any reason that a function wouldn't work? That, alongside a bool isFinished, that you set to true afterwards, and then check for it in order to break out of the while.

do
{
     // Find dead item from left
    for(; true; ++iD)
    {
        // No more dead items
        if(iD > iA)
        {
             finishRefresh();
             isFinished = true;
             break;
        }

        if(isDeadAt(iD)) break;
    }
    if(isFinished) break;

    // Find alive item from right
    for(; true; --iA)
    {
        // No more alive items
        if(iA <= iD)
        {
             finishRefresh();
             isFinished = true;
             break;
        }

        if(isAliveAt(iA)) break;
    }

    if(isFinished) break;

    assert(isDeadAt(iD) && isAliveAt(iA));
    std::swap(items[iD], items[iA]);
    assert(isAliveAt(iD) && isDeadAt(iA));

    // Advance both iterators
    ++iD; --iA;
}
while(true);
}

void finishRefresh()
{
    for(iA = iA - 1; iA >= 0; --iA) 
    {
        assert(isAliveAt(iA));
    }

    msize = sizeNext = iD;

    for(; iD < intSizeNext; ++iD)
    {
        assert(isDeadAt(iD));
        deinitAt(iD);
    }
}

Of course, there might be a better way than this, but none are coming to mind right now.