Detecting collisions between orbiting objects in 2D

Question

I am currently in the process of creating a 2D space debris simulation. I have the orbital physics implemented, but I am currently struggling to find a suitable way of detecting collisions.

There are many objects, all of which are incredibly small and therefore very spread out, but they are travelling at very high speeds. It seems like using a grid would be a good way of detecting collisions between objects, although the objects are all constantly moving at high speeds so they will be moving between cells very often. I also have the issue of only having a limited rate at which I can update the object's positions because otherwise it runs slow, so I believe I need to implement some form of 'swept' collision detection.

Does anyone have any suggestions for a way in which I could efficiently check for collisions, but also make it so they don't miss?

Answer 1

I'll go with bpgeck's answer which is the standard collision detection method when you have a lot of colliders: separate'em in buckets.

However, the standard xy grid is ill suited for this problem as the entities will change of cell extremely often.

Instead I'd go with a coordinate system more natural to your game. The details depend on your implementation:

• Do you have a gamey simulation where the laws of physics are not followed and orbits of any radius can have any speed?
  Then partition by R, theta
• You probably don't have a constrained but realistic simulation where orbits are all circular and only radius vary (so speed is fixed as a function of radius) because collisions would be impossible, except reverse orbits (!) and manoeuvres (unlikely, depends on scale)
• If you have a full two-body simulation (more likely for collisions) and use xy coordinates with an integrator, then at least use some cheap orbital elements like apoapsis, periapsis to segregate your objects into altitude buckets. If ship1 apoapsis < ship2 periapsis, then no collision can occur. As long as you don't have hugely eccentric objects, you'll get good separation. As a bonus these are cheap and constant! You need only recalc and reorder the buckets when a ship is thrusting.
• If you implemented a full two-body simulation using orbital elements, then in addition to the apsises, the anomalies can be used to further cluster objects within a bucket before fine computations.
• If you have a multi-body simulation, back to point 2.

---

Feel free to mix-and-match: use x-separation, y-separation, radial separation and anomaly separation in series or in parallel (or not at all).

Simple example of what I mean by series or parallel, using a usual xy grid split like tic-tac-toe in 9 squares:

• Series partitioning is the typical way: by x, then by y, and getting 9 disjoint buckets as usual.
  Both coordinates are required to define these buckets
• Parallel partitioning means you can split in rows and columns separately and get 3 x-buckets and 3 y-buckets.
  The x coordinate alone defines the column buckets, the y coordinate alone defines the row buckets.
  The advantage is if your ship moves fast in x direction but not much in y, you don't have to reorganise the y buckets often: this suits orbits nicely I think, because apoapsis and periapsis seldom change, but the anomalies, x and y often do.
  To determine collidability, first compare radial ranges. If disjoint, no collision. If intersection, continue with next coordinate etc.
  This is great with 1-to-many collisions as you can simply take the intersection of each bucket and check the remaining objects.
  The disadvantage is when looking for many-to-many collisions, where the buckets are larger than in series.

---

Finally try grouping fleets under a single collider, etc.

Answer 2

In my experience, the best way to perform 2D collision detection is with a grid, preferably a uniform grid, as this is very easy to implement and works very well. Since your game is a space game, though, I am guessing that your game world is very large. In that case, I would partition the entire game world into a series of "tiles" and each tile contains a uniform grid this will make it faster to check collisions. Side note: you have the option to make it so only the asteroids in the tile that the player is currently looking at will move. This wil make movement of asteroids quicker.

Each cell of the grid represents an amount of area within the tile (i.e. the cell located at UnifGrid2 may represent x = 20 to x = 29 and y = 50 to y = 59) and each cell is some data structure representing all objects in that area.

Now you need to check collisions. On each iteration, for every asteroid that moved, check if it hit any of the other asteroids within its same cell. Please see my sketch below for a visual representation of what I mean.

Imagine this is one tile of your game world:

First make the grid,

Now let's say these asteroids move

Now, just check for collisions between the asteroids that moved and all other asteroids in that cell (AABB collision detection. Read about it elsewhere)

Our collision algorithm will show that only this pair of asteroids collided