next »

[John Nesky]

How should one iterate over a list of game objects, while simultaneously deleting some of those objects?

Depends on whether or not it's important that each of the objects has a fair chance of acting during that frame. If object A and object B are attacking each other at the same time but A acts first because it has a smaller index in the list, and A kills B, does B still have the opportunity to kill A at the same time or is B already gone?

If the answer is, "I do care about letting all objects act before removing them from the list," then a simple array/vector of objects with an "active" boolean property should suffice. After letting all objects act, prune out the ones marked as inactive.

If the answer is, "I don't care about low level fairness like that, and additionally it is important to me that the items are removed from the list while I'm iterating over it instead of removing them later," then my answer is: Use a doubly-linked list with handy spliceIn() and spliceOut() methods and maybe a dummy head and/or tail to simplify the splicing part.

[Kaelan]

Anway, about 50% of posters are expressing confusion over what the OP is asking for, so here's my rehashing of the question:
How should one iterate over a list of game objects, while simultaneously deleting some of those objects? E.g. you might iterate over game objects, calling their update() method, and spikes want to delete every squishy object they touch.

I think in this case, what you want is an unordered container with an iterator that allows you to remove the current item. You can implement this pretty trivially atop std::vector or a similar container without much overhead, because deletion can be implemented by swapping the last live item in the container with the current (now deleted) item.

Of course, unordered containers aren't a one-size-fits-all solution - you can use them for things like particles that are explicitly unordered, or for lists that will be explicitly sorted later (like sprites, since you usually paint them based on sorting xy coordinates instead of based on an internal index), but there are a lot of cases where an unordered container means things get updated in random order, which sucks.

This is the unordered container I use for particles in my (C#) game engine:
http://code.google.com/p/fracture/source/browse/trunk/Squared/Util/UnorderedList.cs
And I use it like this:

Code:

var l = new UnorderedList<int>(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });

using (var e = l.GetEnumerator())
while (e.MoveNext()) {
    if ((e.Current % 2) == 0)
        e.RemoveCurrent();
    else
        e.SetCurrent(e.Current * 2);
}

You can adapt this approach to the STL model pretty easily if you like iterators, or just do it by hand with an array. Of course, this doesn't solve the other part of the problem - how you determine when things need to die - but there's no general solution for that and the OP isn't providing much in the way of detail.

Also, it's worth considering that there are often multiple levels of 'liveness' - in my engine objects can be 'awake', 'asleep', or 'dead' - when an object leaves the camera rectangle, it falls asleep after a set number of frames so that I don't waste clock cycles updating objects the player isn't going to see. Such a model means you need a more elaborate data structure than a simple list. Will Vale's point is pretty relevant here, since this applies to almost any game once you start trying to add polish.

The hypothetical situation that you (Boris) suggest also calls for a more elaborate data structure unless you're only dealing with a couple dozen objects (and if you're only dealing with a couple dozen objects, any approach will work because modern computers are stupendously powerful). My game actually has the situation you describe (spikes that damage entities on contact) and the last thing you want to do is have each spike do an O(N) scan through all living entities looking for ones to delete. You need to apply some carefully chosen data structures to problems like this if you want clean, easy-to-maintain code. In my case I use a simple spatial partitioning system to reduce the number of objects in each search, and I do the search on a per-entity basis instead of a per-spike basis, since I have far more spikes than I do entities.

P.S. STL containers are goddamn terrible for lifetime management, but that's what you get when you use C++.