Staggering Vector

So in my current game project, I want to have a some what real-time simulation in which stuff happens. This boils down to doing stuff periodically in a game loop. In my game, the game loop is running at 30 frames per second. I was having problems maintaining this rate, and I did not want to multi-threading just yet. The solution turns out to be something popular in game programming, called time-slicing. The idea is that instead of doing all work at once, each frame, do it gradually over multiple frames. Right now I’m applying the concept to garbage collection, AI, and a problem I’m calling, “Unit Vision”.

In my game, I’ve got a bunch of Units which need to do stuff such as walk around, attack, and spot each other. Before I implemented time-slicing, part of the game loop looked something like this:

for( auto& unit : mUnits ){
	unit.act();
}

removeDeadUnits();

In testing with like 2000+ units, this ended up taking more time than I’d like, so onto time-slicing.

The idea is pretty simple, split the vector into multiple segments and only iterate over one segment per frame. This sounded like “staggering” to me, so I wrote up what I called a “Stagger Group” or “Stagger Vector”

This is what the object’s data looks like:

template<typename T, typename Data = int>
class StaggerGroup {
public:
	struct Group {
		Data data{ 0 };
		std::vector<T> group;
	};
private:
	std::vector< Group> mGroups;

	std::size_t mGroupIndex{ 0 };

I found that a lot of times I wanted to associate something like a timer with a given vector, so I decided to go generic and stuck in a Data parameter with each vector. Then there are the actual set of groups, and an index to the active group.

The set of methods is pretty small a the moment:

	void setup(std::size_t numGroups, std::size_t poolSize = 500) {
		mGroups.resize(numGroups);

		for (auto& g : mGroups) {
			g.group.reserve(poolSize);
		}
	}

	void place(const T& value) {

		std::vector<T>* selectedGroup = &mGroups[0].group;
		for (auto& g : mGroups) {
			if (g.group.size() < selectedGroup->size()) {
				selectedGroup = &g.group;
			}
		}
		selectedGroup->push_back(value);
	}

	template<typename Action>
	void forEach(Action action) {
		for (auto& g : mGroups) {
			action(g);
		}
	}

	Group* getNextGroup() {
		if (mGroupIndex >= mGroups.size()) mGroupIndex = 0;
		return &mGroups[mGroupIndex++];
	}

	std::size_t getSize() {
		std::size_t size = 0;
		for (const auto& g : mGroups) {
			size += g.group.size();
		}
		return size;
	}

So setup is called and a group of fixed size is created, place finds the lowest vector and places the new item in it. The real magic here is the getNextGroup method, here’s what it looks like in practice – the following code is called each game loop iteration:

		mUnitGroups.forEach([timeSinceLastFrameInMS](auto& group) {

			group.data.elapsedTime += timeSinceLastFrameInMS;
		});

		auto selectedGroup = mUnitGroups.getNextGroup();

		float elapsedTime = selectedGroup->data.elapsedTime;
		selectedGroup->data.elapsedTime = 0.0f;

		for (auto& unit : selectedGroup->group) {

			if (unit->isDead()) continue;

			unit->act(elapsedTime );
		}

I also use Staggering for garbage collection like so:

		auto cleanGroup = mPendingCleanGroups.getNextGroup();
		for (auto& item: cleanGroup->group) {
			deleteAction(item);
		}
		cleanGroup->group.clear();

The garbage collection is actually done in another type of object, Recycling Vector, which I’m going to post about next.