Iterating and Removing Items from a List

I’ve been working on a game this weekend. (I think this is the first time I’ll publicly announce something ahead of time! It’s been going really well, and I think I’ll be able to post a couple of articles about development while I’m at it.)

So, when I start a new game, I need to clean-up my display and remove all the objects on it. This usually calls for the "let’s iterate through the list and remove the items" (as I need to do many steps for each thing I remove). However, this also applies in cases where you just want to check the item (such as for a collision detection) and remove it conditionally.

First off, I see this question posted a lot on the web, and I don’t see too many good answers for it. In case you’re not familiar with this problem (though then I don’t know why you would be reading about it now…), the heart of the issue is that you’re trying to edit an object while you’re using it. The general foreach loop approach holds your object while you’re trying to remove something from it.

This usually leads to the most common answer of "well, I’ll just make a copy of the list and remove items from the original", and that’s just a straight-out, loud, "No!". Especially when performance is critical for a game, this is going to take a long time. Especially if you’re trying to do this in a game loop for collision detection (no wonder you’re here!).*

Fortunately for all of us, there’s a simple fix: All you have to do is iterate through the original list backwards and all your problems will be solved:

for (int i = activeSquares.Count - 1; i >= 0; i--)
{
    // Feel free to do conditional checks here to see 
    // if you wish to remove the item...
    activeSquares.RemoveAt(i);
}

And that’s it! The reason this works is that we’re using the variable i to save our place in the list, instead of trying to hold on to the entire list with a foreach loop as is a common practice these days.

The reason we have to go backwards through the list is that when we remove an item from it, all the items after it our now shifted one place, but it doesn’t effect the items in front of the one removed. Thus, by going backwards, we can just keep chugging along. The end of the list will get all shifted around, but the next item we look at will always be the same even after we’ve removed one.

* Note: I am assuming here that you’re in a single threaded operation. If you have multiple threads trying to modify your list, you’ll be in trouble. That’s another reason for the foreach construction; however, in most simple cases this approach works fine. The question then would become is the speed this approach enables, worth the possibility of getting stuck on a lock…

So, good luck and happy coding!