George (& others who have suggestions),
I've been tinkering with a the beginnings of a top-down space exploration/combat game and I've started to think about collision detection. In transcendence, I notice that the visible outline of ships and their effective outlines for the purpose of collision detection are really well-synchronized.
How do you do that efficiently? Is it a bounding polygon inside a bounding sphere? Do you derive boundaries from the images? Also, do you do a full O(n^2) pairwise collision check, or do you use any tricks, e.g., partitioning a system into sections?
Chris
Collision detection
-
george moromisato
- Developer
- Posts: 2997
- Joined: Thu Jul 24, 2003 9:53 pm
- Contact:
I love pontificating about game design, so forgive me for the rambling post:
First of all, the advice that I give everyone who wants to write a game is to go breadth-first. Don't spend a lot of time on every detail of the game. Instead, try to get as much of the whole game done as possible. The sooner you get to a point where the game is playable (even in a rudimentary, non-fun way) the lower the chance that you will abandon the game. [And make no mistake: the biggest threat to your game is the chance that you will abandon it before you finish.]
In order to make progress, you might be better off doing lame, O(n^2), rectangle-intersection collision detection and then move on to some other part of the game.
My next piece of unsolicited advice is to avoid premature optimization. If you know that you need to model thousands of particles, each of which can collide with any other particle, then you might need something better than O(n^2)--such as partitioning a system into sections. But if all you have is dozens of ships and (maybe) hundreds of laser blasts then O(n^2) might be fine (at least for modern CPUs).
OK, now to actually answer your question (sorry that you had to read this far):
Transcendence uses multiple methods depending on the kind of collision that we're talking about.
For a missile/beam hitting something, each beam iterates over all the objects in the system (essentially an O(m x n) algorithm, which approaches O(n^2) if every ship fires a shot).
The algorithm is something like this:
1. For each beam B do:
2.... For each object O do:
3....... If the position of B is in the bounding rect of O then:
4.......... See if the position of B is inside the bitmask of O
(this is done by computing the position of B in the
pixel coordinates of O and seeing if the pixel at
that point is part of the object bitmask)
There is a little bit of extra computation to backtrack from position of B out to the edge of the object. I do this brute force only once I determine that B hit O (by simply iterating along B's path of motion and testing the bitmask).
Collision detection between the ship and the arena walls (or a wreck and another wreck) is done similarly except for two things:
1. I keep a side list of the objects that can block things (that way, I reduce the n in the O(n^2) algorithm).
2. Instead of a point-in-object test I see if two objects overlap by computing the overlapping rect of the two objects. Then for every pixel in the overlapping rect, I see if the pixel is inside the bitmask for both objects--if so, then the objects collided.
For collision detection between an object and a particle field, I do a quick test on the bounds of the particle field and then individual tests (point-in-object) for every particle.
For particle fields, sometimes I cheat: for example, when a beam is passing through an explosion field, I only check every tenth particle or so (which is equivalent to saying that a beam has a 10% chance of hitting a particle--but cheaper to execute).
When modelling particle weapons (such as the PK25 or the plasma torch) I do check every single particle.
Hope that helps and good luck!
First of all, the advice that I give everyone who wants to write a game is to go breadth-first. Don't spend a lot of time on every detail of the game. Instead, try to get as much of the whole game done as possible. The sooner you get to a point where the game is playable (even in a rudimentary, non-fun way) the lower the chance that you will abandon the game. [And make no mistake: the biggest threat to your game is the chance that you will abandon it before you finish.]
In order to make progress, you might be better off doing lame, O(n^2), rectangle-intersection collision detection and then move on to some other part of the game.
My next piece of unsolicited advice is to avoid premature optimization. If you know that you need to model thousands of particles, each of which can collide with any other particle, then you might need something better than O(n^2)--such as partitioning a system into sections. But if all you have is dozens of ships and (maybe) hundreds of laser blasts then O(n^2) might be fine (at least for modern CPUs).
OK, now to actually answer your question (sorry that you had to read this far):
Transcendence uses multiple methods depending on the kind of collision that we're talking about.
For a missile/beam hitting something, each beam iterates over all the objects in the system (essentially an O(m x n) algorithm, which approaches O(n^2) if every ship fires a shot).
The algorithm is something like this:
1. For each beam B do:
2.... For each object O do:
3....... If the position of B is in the bounding rect of O then:
4.......... See if the position of B is inside the bitmask of O
(this is done by computing the position of B in the
pixel coordinates of O and seeing if the pixel at
that point is part of the object bitmask)
There is a little bit of extra computation to backtrack from position of B out to the edge of the object. I do this brute force only once I determine that B hit O (by simply iterating along B's path of motion and testing the bitmask).
Collision detection between the ship and the arena walls (or a wreck and another wreck) is done similarly except for two things:
1. I keep a side list of the objects that can block things (that way, I reduce the n in the O(n^2) algorithm).
2. Instead of a point-in-object test I see if two objects overlap by computing the overlapping rect of the two objects. Then for every pixel in the overlapping rect, I see if the pixel is inside the bitmask for both objects--if so, then the objects collided.
For collision detection between an object and a particle field, I do a quick test on the bounds of the particle field and then individual tests (point-in-object) for every particle.
For particle fields, sometimes I cheat: for example, when a beam is passing through an explosion field, I only check every tenth particle or so (which is equivalent to saying that a beam has a 10% chance of hitting a particle--but cheaper to execute).
When modelling particle weapons (such as the PK25 or the plasma torch) I do check every single particle.
Hope that helps and good luck!
Thanks for the info, and the advice! Based on my own limited experience, I think you're absolutely right in your breadth-first suggestion.
I've implemented collision detection that checks every projectile against the bounding circles of hostile ships, but the secondary bitmask bit is interesting. It makes perfect sense in transcendence, but I'm uncertain as to how to apply it to my particular problem: I'm trying to support very fast-moving projectiles, and consequently my collision detection algo basically asks "will the projectile intersect the circle at any point over the next time slice?" rather than "has the projectile collided in this time slice?" As far as I can tell, that's hard to do with a bitmask--I guess I could play a little game where I compute tiny slices between an analytically-determined bound-entry and bound-exit point (I'd love to hear better solutions, naturally!).
Anyway, I'll take your advice and improve the controls, shipbuilding, projectile graphics, and playability before I go further in this aspect.
I've implemented collision detection that checks every projectile against the bounding circles of hostile ships, but the secondary bitmask bit is interesting. It makes perfect sense in transcendence, but I'm uncertain as to how to apply it to my particular problem: I'm trying to support very fast-moving projectiles, and consequently my collision detection algo basically asks "will the projectile intersect the circle at any point over the next time slice?" rather than "has the projectile collided in this time slice?" As far as I can tell, that's hard to do with a bitmask--I guess I could play a little game where I compute tiny slices between an analytically-determined bound-entry and bound-exit point (I'd love to hear better solutions, naturally!).
Anyway, I'll take your advice and improve the controls, shipbuilding, projectile graphics, and playability before I go further in this aspect.
-
george moromisato
- Developer
- Posts: 2997
- Joined: Thu Jul 24, 2003 9:53 pm
- Contact:
Yup. Essentially you would be testing a series of points along the line to see if they are inside the bitmask. Obviously you would only do this after your line-in-circle test succeeded, so the expensive part would not happen that often.namer4 wrote:I guess I could play a little game where I compute tiny slices between an analytically-determined bound-entry and bound-exit point (I'd love to hear better solutions, naturally!).
I think this is a pretty good solution--simple to implement and computationally cheap. It may seem a brute-force, but that's OK--no need to optimize this until it proves to be a performance bottleneck.
Good luck--and definitely let us know as you progress further.