Random thoughts: Extreme speed 2D collisions

Game Mechanics
#1

TL;DR: Same question as the last thread, but trying to stay on topic this time: How do I detect collisions between meter-sized objects moving tens of kilometers per second relative to each other?

This is a follow up to this thread. That thread ended up being mostly about how to handle and store positions and velocities in (outer) space and physics in general, and started a really nice little discussion! 4 months later I’ve gotten into uni, and after playing Artemis at Cosmonova (that was AWESOME) I involuntary started thinking about this again after trying so hard to suppress these kind of impulses to allow me to focus on my current projects. Oh, well, it can’t be helped! :wink:

In this thread I’d like to focus on collision detecting. To quote myself in the previous thread (you might want my first post to get the background)…

[quote]Detecting collisions would be done in multiple stages. The first stage could be a quad tree to filter out most bodies. We could then do a bounding box collision test between AABBs of the movement lines. Then we could do a line intersection test between the two movement lines, and finally more sensitive tests to determine exactly exactly where the missile hit the ship, so we can calculate a collision response.
[/quote]
This sounds good on paper, but there are lots of things that need to be ironed out here…

  1. Quadtrees???

Seriously, I don’t seem to get them. I understand their uses and I’ve even coded implementations once or twice, but I don’t get how to use them with 1. dynamic data and 2. objects that aren’t points. As far as I know the first one is solved by either reconstructing the whole quadtree from scratch each frame (with node pooling to be nice to the GC) OR dynamically dividing and merging nodes as the objects move around. The first option is easy to implement but sounds a bit slow.

The second one is complicated as hell. When an object moves outside its current node, it’ll have to be removed and added again so that it can find the right new node in the node hierarchy, which doesn’t sound much faster than simply doing that for every object (option 1). Secondly, it all explodes when dealing with objects that aren’t points, which leads me into the second main problem. How the hell do I handle a quadtree with lines?! If I store them in the smallest node that can completely contain them, I may end up in a pathological cases where a number of lines intersect a border causing them to be propagated to a very large node high up in the hierarchy, basically reducing it all to an O(n^2) test (also see No 2 further down).

The other way I know of is to store the line in all the nodes that it intersects. That means that the same line is stored multiple times in many nodes. Not only does that make it possible for the same line pair to be tested multiple times (can be prevented with a DrHalfway’s BitFlags?), but it also increases the cost of adding and removing lines, which will have to be done a lot since the data is dynamic!

So, alternatives to quadtrees? Workarounds? Am I just confused?

  1. The lines themselves

Consider a small fleet of a few hundred fighter ships orbiting in formation around Earth going at 7 km/sec. Earth in turn is orbiting at almost 30 km/sec around the sun. Imagine the movement lines that these form. With a frame time of 12 seconds per update, they’d all be between 276km and 444km relative to the sun. However, relative to the earth, the lines are much shorter, and relative to one of the ships they should be close to 0 since they aren’t moving relative to each other. If the lines are handled relative to the sun, a quadtree will choke on the huge lines since they’ll be put either in nodes very high up in the node hierarchy or be put in so many nodes that it’ll all just fall back to O(n^2).

An idea would be to group together objects that travel at similar speeds, and generate the lines relative to the group’s velocity. However, that pretty much forces us to calculate the relative velocity lines for each object and generate a quad tree FOR EACH GROUP! Sadly, this might even be faster than not doing it, since O(n^2) > O(n^2 / groupSize). Of course only the closest 1000km or so has to be transformed, but for massive concentration of ships? Ouch. Even though the lines won’t pass the line intersection test, the intersection test itself is quite expensive.

Shit, this is looking bad…

  1. Determining the exact collision point

Let’s assume we solve all the above problems and the movement lines of two objects intersect. This obviously does not prove that the objects collided since they’d also have to be at the intersection point at the same time. One possible solution to this would be to compute the exact time the two objects were at intersection point. Let’s say that one of the objects crossed the line at t0 = 0.25 and object two crossed it at t1 = 0.30, we could for example cheaply take the average of those two times (t = 0.275) and do a standard collision test (with circles, boxes, etc) between them at that time. This might miss some collisions, so we might want to do that test multiple times with slightly different values, but that’s okay since these expensive tests will only occur when to lines actually intersect, which they very rarely do, even with the extremely long line problem described above. Hmm, maybe this wasn’t a that big of a problem as I thought…

Let’s focus on 1 and 2 then. Ideas, papers, breakthroughs in spatial data structures, anything goes!

#2

I think you’re on the right path concerning quad-trees. They only make sense in my opinion for static items. I used an octree to great success for hit-testing terrain.

#3

How many objects are there in each ‘1000km block’ ? (worst case-ish)

#4

Well, for each update you must define the line the object is going to travel in this update, and check if it hits something on the way. You could define a Vector-line from pointAtUpdate to desiredPoint, and check a specific percentage of points on this line for collisions in a while-loop with whatever method you want, like pixel-perfect, rectangle collisions, circle-collisions whatever you have. Just “make believe” the object is there.

You can even just move the thing in a while-loop like this:


long fullTime = deltaTime;
long partTime = Math.round(deltaTime/1000);

while (fullTime-partTime >= 0){
     // move object (send partTime to its update(int deltaTime) or move(int deltaTime))
     // check collisions
     fullTime -=partTime;
}
if(fullTime>0){
     // move object (send remaining fullTime to its update(int deltaTime) or move(int deltaTime))
     // check collisions
}

I’m doing this with my projectiles using simple rectangles as hitboxes, as well as rectangles in various sizes for each bodypart of the monsters. I’m not seeing any real slowdown. But then I keep my amount of projectiles at once limited by killing them as soon as they exit the screen +/- 50px. So I can shoot VERY fast bullets, and they’ll still hit the monsters. Even then thin ones.

#5

Good to know I’m on the right path then. It just seemed so weird that a lot of people said that quadtrees are good for this kind of stuff…

The more the merrier! (1000+) We’ll have ships, missiles, rail gun bullets and more, but objects controlled by the same player can’t collide with each other… The distance between them will of course be huge, but so will their velocity. I think the most pathological case is when many ships are travelling in formation, which might be avoidable since they can’t collide with each other in the first place…

It’s a good idea, but the sheer number of updates needed is just too high. I’d need tens of thousand of checks per update to detect collisions at relative speeds of 30km/sec or more… That’s why I came up with using line intersection instead, since the movement can pretty easily be approximated with a line. It’s basically just a line from currentPosition to nextPosition. Then, when a chance for collision has been detected I’d do a few rectangle collision checks or so.

Maybe constructing a quadtree each frame will work if we can figure out a good way to only return the relevant bodies to each player/faction.

#6

Re-creating a quadtree each frame will be a lost…you’d be better off with nothing and sweep-and-prune. Quadtrees can be a big win for dynamic objects, but are a PITA (devil’s in the details kinda way). You could consider meta-objects for stuff flying in formation…esp for those that aren’t visible at the moment.

#7

I may have already mentioned this idea on the earlier thread. It is a radical departure from the algorithm you presented. Consider the notion of making a replica of the space itself. Folks are quite willing to double buffer and fill in the buffer with rather complex graphics & shading & whatever. When there are so many objects, maybe it makes sense to make another map, this time of the playing area and map IDs of your objects directly onto the corresponding spaces that they occupy. (Probably can fit them in a short, which is smaller than a pixel!)

Biggest benefit: no cross-checking whatsoever. You only make one check per object, on the map itself. If the path to the destination is clear, claim the destination pixels and release the previous location markers. And if you do collide, the space itself provides a link to the colliding object and the location of the occurrence.

The mapped space perhaps could be a quarter-size the actual space, perhaps, and still be good enough. If you allow the mapped space to hold lists of objects, then it becomes more of a “bin check” collision algorithm. Another idea (occurs to me as I write) is to have the representation of the object consist of a bounded lattice, to reduce the number of points that need to be mapped. Main thing is that the lattice should be larger than the smallest possible object (or the smallest possible object should have a representation that expands out to the size of the lattice.

So, the main cost would be that you have to define a bounded lattice for all your objects. And manage test all the points on the lattice when you check the map. (There may be other efficiencies as well, such as only checking the boundary pixels, but checking for a given minimal distance moved, so as not to unknowingly engulf another object.)

If objects are moving really fast it might be appropriate to have more stages for them, e.g., more checks per frame drawn. Maybe some objects merit the dual stage checking whereas others are slow enough not to require it. (Make the checks and their timing a function of velocity.)

I’m not sure if there are artifacts due to checking order–seems like there might be. When I was playing around with this method, I had every object in its own thread running on its own clock. I had a thousand objects moving about. I’m not recommending going that route, but it is an intriguingly different way of looking at the problem.

#8

My two bits: It can probably be done, however the effects of such a modeling will be thoroughly uninteresting if it were applied to a game, unless you implement something like homing weaponry or quick ‘guided’ calculations of expected position before firing. The distances VS speed will make for very difficult firing, especially if the controls for ships are not impulse styled (IE- They can make hair-pin turns without having to directly combat their current momentum).

But anyway, I think that the lines could work, to a point:
Instead of checking the lines at first for actual collisions, check the bounding box that’s created by the object’s current position and its future position. Only objects intersecting like that will have to worry about actually colliding. I mean, yes, this will mostly be taken care of by your whole ‘withing X distance’ thing, but…

I don’t think that adjusting the relative velocities and grouping by velocity is the way to go. If you’re attempting to do something of a realistic simulation of travel, then it’s likely that the only time objects will all be traveling at near enough the same velocity is when they’re flying as a group and not under combat conditions (And at that point, it’s likely you can treat an entire squad as a single entity for any important collisions). Otherwise, various events/effects will cause all sorts of differences in speed that will drastically increase the number of ‘groupings’ that would be required (Impacts causing a change in velocities, changes in engine efficiency lowering the acceleration/max velocity of ships/objects, gravitational physics if you’re planning on having those affect the ships, evasive maneuvers, etc.).

#9

Hmm, after reading philfreys post, I had a brainwave…probably just a single one.

How about you find the line between the two points. Then considering the position-pointer of the object is in its exact middle, you can create an AABB reaching from the first position to the desired position, and check that for collisions.
You could check for collisions through this AABB incrementally, and if any are found, you can handle them using another sort of collision-detection of your own choice. This would just be for finding the general answer to the question “Are there any collisions?”.

http://img255.imageshack.us/img255/6862/fastcollisions.png

#10

That’s usually refered to as ‘swept’ collision detection, as you’re colliding against the volume made by sweeping the original object. For a moving sphere you’d usually sweep that into a capsule, as that’s easily defined by the start and end points, and the radius of the sphere. Googling ‘swept collision detection’ will get you loads of info.

#11

Off-topic, but this game is indeed awesome. ;D I ran a 10 person lan game a couple of months ago which was great fun - two ships each with their own captain ordering around their crews of 4 in the same galaxy. Great fun.

#12

My initial idea is separate axels and treat objects as segment from pos to nextPos. If segment pair collide with both x and y axel then check collision with more accurate means. Doing tow separate 1d segment to segment collision can be done very fast. Checking collision pairs is also fast.
Stuffing objects in order for 1d array can be done fast with radix sort.

#13

Did anyone just search the web for Collision Detection

In regards to Ultroman’s post, it describes what is known as “priori” collision detection. You calculate the trajectory of the objects and use the swept motion to figure out whether 2 or more bodies collide or not.

The other form of collision is known as “posteriori” collision detection. You have the object move and use it’s trajectory “shadow” to figure out if a collision has occurred. Then you fix the current object after the collision has occurred.

Both of these collision methods use the “swept collision” detection described. The fact is that it is slow to check every collision, so you have to dramatically reduce the amount of checks by checking 3 things.

  1. Position: If 2 objects are far apart from each other, chances are they aren’t going to collide.
  2. Direction: If 2 objects are moving in the same direction parallel to each other, chances are they will not collide.
  3. Velocity: If objects are not moving at all, or moving at the same speed, chances reduce that they will collide.

It is simplistic, and I didn’t list all the combinations of those attributes. But, reducing the amount of checks is key to having really fast robust collision detection. Most games don’t have much moving objects at once anyway.

Like in a FPS (First-Person Shooter) for example. Most of the time, collision detection is only used for world based actions (like wall collision and character -> object collision). Checking to see if 2 bullets shot by two players will collide most of the times is skipped. Why, because you are trying to reduce the amount of collisions. Even for games like, Asteroids, where you would think collision detection would be important. It just is skipped as rocks are allowed to phase through one another.

Bottom line is. Reduce the checks required. Quad-trees and the like help to narrow down the amount of collision checks. Then you can just focus on the rest of your game. Since most actions are based on what the player can “see”, collision detection is usually only important in small scale.

Speaking of which, maybe the game “Little Big Planet” would be a good research point for this. As most of the objects in that game seem to be constantly checking for collisions. But, even LBP has a limit on the amount of objects that can be created. So it goes to show you that constantly checking for collisions is just very expensive, and must be reduced.

#14

I don’t need to. Basic collision detection is easy…tuning to a specific case isn’t hard, but like I said…the devil’s in the details.

#15

Yes! Glad this sparked some interest again! ;D

@Roquen
Quadtrees probably aren’t what I’m looking for here… Creating meta objects is probably a good idea. An assigned group of objects could have fixed offsets to the group’s center position, so the group can be treated as a single object, and is only updated once. Collision detection is performed against the group, but between objects in the group.

@philfrei
For some reason I have a hard time understanding what you’re saying, so tell me if I got his right: You’d pretty much rasterize the movement line (or just a point at the destination?) and see which other objects cover the same “pixels” in the world. That sounds like a “bin check” with each “pixel” being a bin. It sounds like a pretty good way, but it would require a pretty good bin resolution though. It also pretty much seems like having a quadtree and adding lines to it except that a quadtree splits up when too many lines cover the same “pixel”. Considering the huge areas I have to cover, a quadtree sounds more useful in that case… Maybe I completely misunderstood you?

@UprightPath
The game would be a strategy game, so aiming is automatic, and missiles are of course homing. I just want it to be possible to dodge missiles using emergency thrusters or smart maneuvers. I agree that aiming railguns and other dumb projectiles will be hard, but that’s another story. Thanks for your input!

@Ultroman
That’s pretty much what I was trying to accomplish with the lines. They were just an approximation of those volumes (well, areas since it’s 2D) since they’re so small compared to the distance of the movement.

@Orangy Tang
I played Artemis on an IMAX projector, though each crew member had their own laptop. =D

@pitbuller
Yeah, those segments are the lines I’m talking about. The problem is that they’re too stretched out due high speed they have relative to a fixed point in space, forcing me to check for lots of collisions unless we can come up with a way to reduce the number of checks…

@ctomni231
The game isn’t an FPS game. It’s a realistic 2D space simulation strategy game, so everything has to be moving to stay in orbit.
The problem is that checking every object against every other object to see if there is any chance of collision scales really badly. Checking the position, direction and/or velocity of every object pair isn’t going to work very well…

#16

Hmmm… Well, if you are dealing with orbits instead of straight lines, it only means that the direction/velocity will be based on degrees/pi vector.

Regardless, you still are going to have to calculate the trajectory of each object the first time. You’ll need to do this in steps, to ensure you are not over-stressing your engine checking for collisions. I think the most stress for the engine will come at the beginning, when you have 30 planets, and the initial space objects. First you check them all to see if any have the potential for collisions.

As long as the speed for those objects don’t change, they can be omitted from the pair checks. The only time you will want to check for collisions is if another foreign body moves close to another objects range, if they are moving at different speeds, or if they are moving opposing directions. You can then check for collisions based on those attributes.

Even if objects are continuously moving, you don’t always have to check them for collisions. Setting flags for skipping these checks can save a lot of time when dealing with many moving objects.

#17

Another option would be to ignore ‘small’, fast moving non-controlled objects when it comes to actually doing collision checking. Instead, have that kind of weapon function on a hit-scan sort of way, then ignore them for the purpose of the game. It would reduce map clutter (Especially if you keep track of every projectile) and due to the speeds that you’re describing, it’s likely that any projectile that’s not controlled will be out of the combat zone after a single turn (Say they’re moving at 10k meter/sec) they get up to 120k m/t (per turn), which is, I hope, greater than the optimum combat distance of such weapons.

While it’d be cool to have a ship suddenly go down across the map because a mass driver round from that fight crossed the map and hit 'em. However, the chance of that happening is so small that it could probably be ignored for the purpose of the game.

For near atmosphere combat, keeping track of bullet sized objects becomes even less of an issue, since there will be a drain on their velocity, for the most part, due to the accumulation of dust and other objects/projectiles. I know that it doesn’t help much on the question of how to do collisions, but it should help with ‘what’ to do collisions with. Hah.

#18

@ theagentd, yes the root concept is a “bin” of one pixel, but with that bin holding a maximum of one reference for its sole occupant. In the most crude implementation of this idea, if the ship were a rectangle, say 10 x 20 pixels, it would be the sole occupant of 200 bins.

The collision check for each pixel is thus greatly simplified: is it already occupied or not?

public short isPointOccupied(int x, int y)
{
    return knownSpace[y * width + x];
}

– where (x, y) is one of the ship pixels, and KnownSpace is a short[] of all the points in your playing area, returning a -1 to indicate unoccupied, or else returns an index that gives you a direct handle to what you’ve collided into.

You call this check once for every new pixel in space you wish to occupy (you only have to collision test leading edges). Your backside position can be automatically be updated in the KnownSpace array without collision checking since you know you are moving into space you already occupy with your front end.

When I started thinking about this again, it occurred to me that a way to make this more efficient would be to make the set of points that correspond to the ship as small as possible but still always able to indicate a hit if the area it is being tested against is occupied.

Imagine for example that you have a list of contiguous points corresponding to the edge of the ship. Then, you have another similar list of points that echoes the shape of the ship at distance D on the interior, and all other moving objects are similarly configured.

If you never move a greater distance than D between collision checks on the knownSpace map, then you are guaranteed to register a “hit” if two objects collide, even if they are moving at each other both at a velocity that causes a displacement of D from the starting position of 1 pixel proximity. If the distance D is 4 pixels per frame ( = 240 pixels per second at 60fps), then the smallest object would have to tote around a representation of at least a diameter of 4 pixels to ensure you don’t encircle and miss it.

In this scenario, the representation for the 10 * 20 rectangular ship would have an outer band of 56 pixels to map in for its boundary edge, and an interior rectangle at 6 * 16 which would be 40, for 96 pixels total to check on the KnownSpaceMap instead of all 200. A larger ship would offer more of a discount. A 20 * 30 shape, for example, comes to 96 + 80 = 172 instead of 600, and an object that never moves would only need to register the border edge, not an interior edge, and would never initiate a collision check. Only moving objects need to check the space they move into. Recall, also only leading edges need be tested for collisions–back end pixels of the ship can have their position updated automatically.

There are likely other clever efficiencies to create representations of the ship’s area that still ensure overlapping boundaries will register a collision. But there will always be multiple locations per ship to manage on the map, and the question will be: will the number of checks per ship be less than the number of other ships you would have to check against? (But factor in that the check itself is considerably easier than tests such as “is this point within this shape” or “do two lines cross” which are no longer needed.)

I hope that explains the idea more clearly. As I said, it is kind of an inversion of the standard way of doing things, a radical departure. But under certain scenarios it could offer some interesting pickups in efficiency.