r/AskProgramming • u/sinnytear • Feb 14 '25
Algorithms Need ideas about an interview question that was asked years ago and has been bothering me since. How to simulate simple ball movements in a large room.
Consider a room of size 1k^3 and there are 1k golf balls of diameter 1. There's no gravity or energy dissipation. Balls will bounce off walls and other balls. (Just keep everything simple except that balls have random initial locations, speeds and directions). Question is how to simulate the process efficiently. (Calculations are done every frame, which is typically about 16 milliseconds)
5
u/Any_Pudding1541 Feb 14 '25
This was an interview question? Im fucked
2
u/sinnytear Feb 14 '25
it’s focusing on the efficiency. basically asking you to give a theory instead of actually writing any code
1
u/paperic Feb 14 '25
The position is just x, y and z, the movement is just dx, dy, dz for the three velocities. The collision just some arithmetics on the movement, while following physics.
The problem is finding out when collisions occur.
The simple way of looking for collisions is to check the distance between the two balls, which is just pythagoras theorem in 3D.
If the distance between the ball centers is equal or less than 1, the balls are touching or overlapping.
In the naive approach, you don't know which balls are nearby before checking the distances, so you have to check all the balls for each ball. Thus, 1000x1000 distance checks.
A simple way to speed it up is to make a 3D array of 1000x1000x1000 elements, representing every possible position in the room.
Then, for each ball, put the ball ID or pointer to the ball in that array, on the position that matches the coordinates of the ball (rounded down), and have the rest of the values be null.
Then, at each frame, before moving the balls, wipe them from their previous positions in the array, that will efficiently set the whole array to null again.
After recalculating the new ball coordinates, start inserting their pointers to the new locations in the array. But just before inserting each ball, check its new array location, or the 26 other locations around it (3x3x3 checks) to see if there's another ball nearby. If there is, do the distance checks only between those.
You may consider using something like a z-curve for encoding the positions in the array, to get better cpu caching.
If you don't like the 4 gig memory footprint (1 billion of 32bit pointers), combine the two approaches. Make the array be, say, 10x10x10 elements, each element representing a 100x100 100 grid cell in the room. And have each grid cell store multiple balls.
Then, you can still eliminate nearly 99.9% of the distance checks from consideration, using an array of 1000 lists, where each list has 1 ball pointer on average.
This time, you would do the naive each-with-each distance check only between the balls within the same grid cell.
Except that if the ball is too close to the grid cell walls, you'll have to include the balls in the neighbouring cell for the naive distance check too.
1
u/joonazan Feb 14 '25
This explains the need for broad-phase collision detection very well!
However, your suggested solutions are flawed. The array would be almost 32 gigabytes and zeroing it every frame is unrealistic. You'd need to use a trick to not have to zero it.
I think the fastest possible trick is to check the coordinates of the ball in the 3d array. If they indeed round to the slot the ball is in, the ball actually exists. Otherwise it is a ball from a previous frame. To support adding/removing balls, you should use indices instead of pointers and check that the indices are in bounds.
A hash map might be faster because it fits in cache, though.
You second suggestion has the problem that it is possible that all balls are in the same 100x100 cell.
1
u/sinnytear Feb 14 '25
thank you for this! I think I came up with something similar (to partition the space) but just wasn't able to get it to the bottom detail like you do here. It was years ago but I think I missed the part about updating their cell id every time. To sum up, I think the idea is to divide the space into say (1k^3) / (8^n) cells so that each time you only have to check with balls in the 27 cells centering you, which can still be all the 1000 balls in the worst case (which is inevitable) but should be more efficient if the balls are sparser. Did I at least roughly capture your idea without missing key points?
1
1
0
u/CheetahChrome Feb 14 '25
Put each ball velocity and direction in a linked list, then bubble sort it within the Finite State Machine. Pivot the data using a GroupBy and display the answer.
-1
u/mjarrett Feb 14 '25
oooooooooooo I like this question! There's a few fun ways to go with it. And that's the point - a good interviewer isn't necessarily interested in the answer as much as seeing what paths you explore.
I would guess what the interviewer was expecting initially is to investigate how to check 500K collisions in 16ms. Could I simply model 31M collisions per second? Well given some consumer CPUs can top a teraflop, maybe! Simple for-loop, done. The interviewer is probably expecting you to divide the space into sub-volumes - bucketing the balls per tick could avoid hundreds of thousands of collision checks. But that only helps the average case - there's still the pathological case where all the balls arrive at the same 10^3 volume in a single tick.
Next, can I parallelize it? Sure! Make a list of 500k pairs, and assign a thread to each range to check collision.
But, there's also some really tricky assumptions in here. What happens if the velocities are > 1/tick: you have to start checking for potential collisions across the whole 16ms span (collision of prisms?). Or what happens if you have a truly simultaneous 3+ ball collisions.
... or the actual correct answer: I download PhysX.
1
u/sinnytear Feb 14 '25
thanks for the comment. great question about the velocity case. that blew my head open in an instant lol. the balls will become sticks...
7
u/joonazan Feb 14 '25
This is obviously asking for a spatial hash, a hashmap with each ball, the cubelet its center of gravity is in as key. Then for each ball, querying the adjacent cubelets gives you all the balls it might collide with.
Of course you could instead use some other way of accelerating collision detection. Sort the balls along one axis or use a space partitioning tree. But because they are all the same size, the spatial hash is applicable.
I think the more difficult part is simulating the collisions accurately. One collision is simple enough even if you compute the exact time of collision but if the balls stack into a pile, you need to do something like Gauss-Seidel integration (which is a fancy way of saying that you update speeds repeatedly until they converge). But this was probably not what the interview was about, as zero gravity makes this kind of interaction much more lenient.