Simple to code (?) improvement to collision detection

[munch]

Hi,

We all know that Spring's current collision detection has issues. It's especially noticeable if you drag out a line of turrets right next to each other. The main problems as I see it

1. the "side buldges" you get with collisions spheres - especially bad for tall/thin units
2. for short units, the fact that the bounding sphere is way taller than the unit itself - especially bad for short + wide units.

On this thread: http://taspring.clan-sy.com/phpbb/viewt ... c&start=20
Firecrack suggested using cylinders. I think this is an excellent idea that would solve most of the problems with spheres without being hard to implement or processor intensive. Here's the meat of the idea:

The way I guess Spring does spherical collision detection is simply by asking "how close is projectile P from the position of unit U"? Each unit has a fixed size R. If the projectile is closer than R then it has hit that unit, if it is further than R then it hasn't. So the psuedo-code is:

Code: Select all

collision_detected = sqrt((x1 - x2)^2 + (y1 -y2)^2 + (z1 - z2)^2) < unit_size

To go to cylinders, instead of just specifying a radius (which is used in all three dimensions for spheres), you also specify a height. The cylinder is then defined by a circle (of radius R) in the horizontal plane and a height (H) in the vertical axis. So now your pseudo-code looks like this:

Code: Select all

collision_detected = (sqrt((x1 - x2)^2 + (y1 - y2)^2) < unit_width)
                       AND (abs(z1 - z2) < unit_height);

The main point about both spheres and cylinders is that they both work independent of the unit's orientation. All you have to know is the unit's position, and its size (expressed as either one or two parameters), so the calculation is extremely simple. The main issue in changing to the above (I'm guessing) will be in calculating the height and width of each unit's bounding cylinder - I've no idea how the game gets the radius for the unit's bounding sphere.

One obvious issue with this is that it works well for buildings which are always upright, but what about mobile units which may be going up a hill etc.? It's true that the bounding cylinder is not perfect if the unit isn't on flat ground (or flying straight and level), but unless it's very steep ground it will still match the unit's actually shape better than a bounding sphere does. The problem with the sphere is, it makes no assumptions at all about which way the unit is facing -it caters for all possible orientations, including those which rarely or never happen, such as a unit lying on its side - this is true even for buildings! Assuming the unit is close to a "flat" orientation covers most cases, and even when the unit isn't flat, the mismatch is still fairly small.

I hope this helps. What do the devs think?

Munch

PS Caveat: I haven't looked at the current collision detection code, so I'm making some assumptions here!

[IMSabbel]

Well, i saw a cvs checkin about doing footprint check after succeded sphereical collision test a few weeks ago... so maybe its already implemented...

[munch]

Footprint check - what a great idea! In fact that's a simpler version of an idea somebody just had on the other thread (in help&bugs see above post for link to thread), but I guess it works for all units - static and mobile - AND it's quick to code. I guess the only downside is that it doesn't fix the height problem for short, wide units like tanks and plants and of course the footprint square (I'm assuming that's what you see when you select a unit) is a very rough size guide, being smaller than some of the units (e.g. radar towers and MTs are bigger at the top than the bottom) and bigger than others e.g. peewees or AKs or freakers etc. are dwarfed by their footprint.

Still a welcome improvement though since it should help solve the adjacent turrets damaging each other problem.

Unfortunately I don't think any of these ideas will fix the basic problem for MTs though, which is that their footprint is smaller than the length of their weapon (for ARM at least). That means if they're built right next to each other, the weapon can easily start out in the adjacent MT's bounding box, or even be inside the adjacent MT! The footprint check combined with make sure turrets have a big enough footprint in the first place however, should fix this. So... can we update turret footprints to be slightly larger where they need to be? Especiallly ARM MTs

Ta

Munch

PS Here's the other idea for building collision detection (from the other thread), which does fix the height problem:

Hum, for building collision, would it be possible, once we know we are in collision with the sphere, to check if we are over the footprint?
It must be easy to detect..
Like that, we have go a sort of rectangle.

Actually it's an utterly brilliant idea. It should in fact reduce CPU load. Here's why: TA has this quirk - you can't rotate buildings, they're always built alligned to the "game grid" and they're always built bolt upright, even if you build them on a slope. That means you can skip the pythagoras you need to do the bounding sphere, and just go straight to checking the bounding box, like this:

Code: Select all

collision_detected = (abs(x1 - x2) < building_width)
                 AND (abs(y1 - y2) < building_length)
                 AND (abs(z1 - z2) < building_height);

Of course you have to compute the bounding box first to make this work!

Cheers

Munch

[AF]

Didnt somebody post the code to change the spheres geometry into ovals that where stretched in the Y axis, so that their diamaters where accurate to the width of the unit itself, thus solving the problem in most cases? Damn ti was the one who made all those models of trees who got into that big flame somewhere and was threatened with beign abnned, ahk why cant I remember!!

[cain]

the last time i saw it, it did a spheric collision check on the 2d map, and if it succeded it checked for height collision, so that was already doing cilindric checks.

[el_muchacho]

I wonder how complex it would be to make a modular collision geometry in function of the degrees of liberty of each unit.

Say :
- a bounding box for plants and solar collectors,
- a cylinder for turrets and boats
- a sphere for moving units.

Plants are horizontal and always facing the same direction in Spring, so that the collision scheme with them is just a matter of checking if (x,y,z) are within the bounding box, a fairly precise (much more satisfying than a sphere as plants are vaguely rectangular in shape) and very fast verification (no sqrt).

Turrets and boats can only rotate on the horizontal plane, so that the cylinder seems the best geometry for them, while moving units can rotate around the 3 axes, so that the sphere is the best collision geometry for them.

Actually, this makes me think that there might be some possible optimizations as well for the unit movements, as the rotation matrices are simpler for rotations around a single axis, but I'm not sure the result is worth the trouble (in fact I really doubt it).



Thinking a little more about it, another more ambitious but much more fruitful idea would be a "real" collision scheme, where all units are described by bounding boxes. The question here is how to avoid trigonometric calcs as these boxes can take any orientation.

In fact it's possible with a simple table lookup : all one has to do is to make a sine and cosine table of, say, 180 values (every 2 degrees).
In order to look in the table, the actual unit orientations in radians should be simply multiplied by 100 and then truncated into an integer that gives the index in the table (so that there is no need for a bisection search). This gives approximately the angle in the sine/cosine table, which is actually somewhat longer than 200 lines.

Therefore, all the sine/cosine computations are simply replaced by a multiplication and a read in a table. Since the collision detection doesn't need a high precision (a 2 degree precision should be more than enough), I guess this method could work and save a lot of sqrt calculations, while being more precise than spheroids.

Did I forget anything ? (Yes, the maths, I know. )

[el_muchacho]

Indeed, I forgot the maths, and it changes everything.

Working out the maths, one immediately stumbles upon the main problem, which is, for an exact answer to "collision or not ?", one must tests each of the 8 corners of the bounding box against the 8 corners of the other unit box instead of simply calculating the distance of the centers of the two units.

Ok, for each unit, one must keep a table of the 8 (x,y,z) coordinates of each corner, i.e 24 floats/unit. These coordinates are updated when the position of the unit is calculated, using the sin/cos tables for instance or the rotation matrices. (In fact, the rotation matrices probably have already been calculated, so that the sin/cos tables are no longer necessary).

Now, during the collision detection routine, one should test that each of unit 1 bounding box (BB for short) corner is or is not within the coordinates of unit 2 BB. Worst case is when the answer is yes, of course. To minimize the risk of worst case, I guess it would be a good idea to make the difference between front and back of the unit, as collisions 99% happen front first.

[SJ]

You should also remember that the majority of collision tests in spring is ray against unit rather than point against unit. Its not hard to collide a ray against a cylinder either of course, I would be interested to see how the results looked if someone did implement it.

[el_muchacho]

As a side note to my pevious post, I believe the speed vector points towards the front face and the acceleration vector more or less points towards the corner that has a good chance to hit first. This assuming the direction of the movement doesn't change to quickly between 2 position calculations (which is the case in Spring). Maybe this can be exploited.
Or more simply a first approx with the spheres and then a precise test with boxes.

[el_muchacho]

Interesting articles: http://graphics.idav.ucdavis.edu/resear ... weep_prune
http://graphics.idav.ucdavis.edu/research/VADOP

Edit : Actually, there is a whole research group on the subject here:
http://www.cs.unc.edu/~geom/collide/index.shtml

[[K.B.] Napalm Cobra]

Of the styles el_muchacho listed bounding box is the most accurate, so why only use if for factories?

I suggest a combination of both sphere and bounding box, with sphere used to approximate and cut down on unnecissary collisions and if that detects a collision use bounding box for the unit, or preferably for each piece to get a more accurate result.

[Maelstrom]

Didn't I suggest that at one stage?

Ah well what ever method is decided on, as long as it is better than the current version I will be happy.

[munch]

You should also remember that the majority of collision tests in spring is ray against unit rather than point against unit. Its not hard to collide a ray against a cylinder either of course, I would be interested to see how the results looked if someone did implement it.

Hi SJ,

Thanks that's helpful. Just to clarify what do you mean by rays exactly? I think of lines, rays and line segments like this:

line - extends to inifinity in both directions
ray - extends from a single point to inifinity (e.g. beam laser)
line segment - extends from one point to another (e.g. ordinary laser, or path of any projectile across a frame)

I'm guessing you're talking about what I'd call line-segments? I hadn't thought of that. I guess that means you're currently doing a "shortest distance between a line (projectile line segment) and a point (unit position)"? The obvious solution to that is to use the "shortest distance between two skewed lines" algorithm, which is a bit more complicated, but still not too bad, and of course would work at any orientation, so that units going up hills or aircraft doing rolls could be correctly represented. The only thing is that the skew lines algorithm is for infinite lines, not line segments - looks nice in theory but might need a bit of work.

I guess the main problem is the adjacent turrets hitting each other issue, which should be fixed if the footprint check has been added and the footprints are made to be the right size (so that the unit's weapon is always within the footprint).

Munch

[SJ]

Most of the checks are for really short line segments (as far as the projectile moves in one frame) while the one that takes the most time is the ones that check if a weapon can fire without hitting friendlies which are obviously from the weapon to the tested enemy. To make this somewhat more complicated these tests arent strictly line segments but rather tests a "curved cone" (see CGameHelper::TestTrajectoryCone). The functions you would need to modify in order to test a new collision detection system would be mostly CProjectileHandler::CheckUnitCol and a few different ones in CGameHelper (TraceRay, GuiTraceRay, GuiTraceRayFeature, TraceRayTeam, TestCone, TestTrajectoryCone) and of course the unit loading functions to calculate whatever data you might need from there.