I try to resolve collision in a multiple particle system and want to check, if my approach is good or not.
The goal is to resolve the collisions in the right order, so that particle that meet first collide do so (and collisions with particles they meet later are ignored).
I would do the collision test for all particles. If the collision test is positive, the time until collision would be stored in a double array with the numbers of both particles as coordinates.
After all collision tests are done, the array item with the lowest time would be chosen to go to collision resolution and all collision times for these two particles in the array get removed.
Then particle combination with the next lowest time is chosen a.s.o.
My concern with this is, that I have to loop through a relatively large array completely each time to find the lowest number, when most entries of the array are empty. Would there be a more efficient way to do this?
Yes, that’s an excellent way to cut down on the collision testing for sparse environments. I did something similar last century: https://cs.brown.edu/people/sdollins/world/sim.html. It’s not so great, though, if you have a lot of objects close to each other frequently bouncing off each other.
The data structure you’re looking for is a priority queue, most often implemented using a heap – a binary tree stored in an array sorted so that each node is smaller than either of its children. It’s log(N) time to add or remove each item. To update the events, I had each object keep a list of its predicted events and delete them if object changes its motion.
In general, I think tracking the objects in a grid or hierarchy of grids is easier to code.
Awesome. Thanks a lot. Especially the keywords “priority queue using a heap” help a lot to find more about, how to implement that. That was something I was struggling with. Let’s see, if I get into the full thesis.
I tried the approach with the array and in principle it works but I ran into trouble with “time management”. There are several times, which have to be tracked and it was difficult to do so with the array. Instead I created an Event class, which contains the particles and the times for this event. This way, all collisions, which are supposed to happen can be managed with an ArrayList of the events and I update the list and the events after every collision resolution.
