Blogging at Orbital Velocity

Managing Dynamic list of lists

In calculateTrajectories(), I have a vector of positions, called sys2. It’s a copy of sys, the main set of positions. Sys2 is a mutable vector that is used to compute the future positions of all objects: ships, bullets, missiles, celestial bodies. This means it will run hundreds or thousands of steps — per frame. This is a resource hungry function, so it will run on its own thread, and only needs to run when there is a change in the system - a ship fires its thrusters or weapons or when a new ship enters the map.

vector<vector<float> >paths

All trajectories are kept in paths, a set of vectors - one per object. Each vector holds the positions of the trajectory for that object. As a new iteration of sys2 is calculated, corresponding positions will be appended to the appropriate vector.

Sometimes an object will collide with a celestial body, or another ship, or will zip outside the boundaries of the map at escape velocity. That is when its trajectory will terminate. To terminate, its entry in sys2 must be removed. Optional: whatever other body it impacts can be adjusted to reflect a change in momentum as a result of the collision.

Now there is not a one-to-one mapping between the elements in sys2 and the vectors in paths. A separate vector of IDs is kept with sys2. When an element is removed from sys2, the corresponding ID is also removed from the id vector.

My original approach was naively scan from front to back, compare the distance between each element i with element j of a higher index, if the distance is below a certain threshold (a function of the two elements), remove my element i. This would fail in the general scenario: when two elements collide, both elements should be removed. But the solution is simple, simply remove element j, and I can continue to scan the rest of the vector and potentially eliminate more. I would then need a flag to remove element i before moving on. This also had the problem of changing iterators after an erase operation. Great, more exceptions.

A more elegant solution is to break this into two steps: mark the elements for deletion in the first pass, then iterate over the array backwards and delete marked elements in the second pass. The first pass has a complexity of O( \( \frac12n^2 \) ) since it will only iterate over the upper-right triangle of \( n \times n \) matrix. The second pass is just O(n).

void markForDeletion(vector<body> &sys, vector<bool> &toBeRemoved)
{
    toBeRemoved.resize(sys.size(), false);
    
    for (int i=0; i < sys.size(); i++) {
        for (int j = i+1; j < sys.size(); j++) { 
            if (glm::length(sys[i].sn.pos - sys[j].sn.pos) <= threshold) {
                toBeRemoved[i] = true;
                toBeRemoved[j] = true;
            }
        }
        if (not toBeRemoved[i] && glm::length(sys[i].sn.pos - sys[0].sn.pos) > map_edge) {
            toBeRemoved[i] = true;
        }
    }
}

As shown, I’ve also added an out of bounds check for objects too far. This happens to many if not most projectiles. Though I’ll need to add an exception to ships.

For the actual deletion, I iterate backwards so I do not depend on the end iterator changing as a result of the erase operation.

auto it = --sys2.end();
auto itt = --ids.end();
for (int i = (int)sys2.size()-1; i >= 0; --i, --it, --itt) {
    if (toBeRemoved[i]) {      //TODO: wrap sys2 and ids into 1 object
        sys2.erase(it);
        ids.erase(itt);
    }
}

Once my system state has been pruned, I can safely push them back to my paths.

for (int i=0; i < sys2.size(); i++)
	paths[idVector[i]].push_back(sys2[i]);

Now after each iteration, sys2 is looped over and for each id in the corresponding id vector, the indicated element in sys2 will be appended to the vector of that id.

The paths are then serialized as follows:

auto i = 0, totalSize = 0;
for(auto &p : paths)
	totalSize += p.size();
path.resize(totalSize);

for (auto &p : paths)
	for(auto &pp : p)
		path[i++] = pp;

The serialized vector, path, is expanded to the total size of the collection of trajectories. Then each element is copied to the path.

I do not claim this is an optimal algorithm, but it is fairly elegant and free from ugly exceptions. If anyone has a better solution feel free to email me, ping me on github, or comment below when I’ve figured out how to add a comment system.

Orbital Velocity Blog

Developing games in real space

Managing Dynamic list of lists