Up to now, I had no way to delete objects from the physics engine. They could be deactivated, but they were still there. This was fine for dead enemies and other objects that existed in limited numbers. But I wanted to have lots of particle-like objects that exist for a short time, and each one couldn’t stay around forever.

Why was there no deletion? Because it’s not that easy. A physics body is allocated from a pool. A list stores all the allocated pointers. Then there is a std::vector of pointers to all active bodies, and a pointer to the body in its current cell, which may be awake, asleep or deactivated. The user code gets a pointer to the body too, and that’s what it will give back to be deleted.

So if something wants to delete a body, I get a pointer to the body to be removed, but it needs to be removed from a number of containers, which erase by iterator. And I can’t get any of those iterators without a linear search through every container. This looks like it might be slow. What I want is constant time deletion.

Right then. I can narrow down the containers that might have pointers to the body by waking it up. Then only the active cells, active list and the main list will have the pointer. There’s a point in the update when the active cells are empty and get rebuilt from the active list. That’s where I’ll put the deletion. Until then, the body is marked as pending delete.

I already have a loop through the active bodies. I’ll hijack that and check whether any bodies need to be deleted. If they do, I swap them to the end of the vector, pop_back and return the pointer to the pool. Still constant time. That just leaves the main list. I can’t delete from that without iterating through it. But it is never used until the physics world is shut down, and I don’t care so much about performance at that point.

So I change that list to a hash set of pointers. Now I can delete from it in constant time.

It may be crazy, but it works.