Physics of Cuboids! Or: How can I best do this?

[Draco18s]

I'm trying to set up a semi-smart targeting algorithm to find the best direction to fire a penetrating beam-like weapon (I think the Spire beam is the closest, but mine is going to be fairly wide, similar to the heavy beam, just not multiple sub-beams).

For radial blast weapons (i.e. grenades) this was pretty easy in unity:

Physics.OverlapSphere around the firing entity, collect a list of all enemies in range, then do a smaller overlapping sphere on each one looking for the largest number of hits.  It won't find the perfect shot, but it will aim towards groups.

But for a line-based AOE this gets more complicated.  There isn't a Physics.OverlapBox.  I can't use colliders because I don't want to wait for next-frames (can't, even).  Simple rays won't work, as they don't have the area coverage.  I can't do Bounds.Intersects as the target area isn't aligned to the axis.

Best solution I've come up with is to do small radial OverlapSpheres along the path from A to B and doing a check every interval.  It won't catch some locations, though, as they aren't space-filling spheres.

Any other ideas?

[Shrugging Khan]

Sounds like you need a Physics.CapsuleCast:
http://docs.unity3d.com/412/Documentation/ScriptReference/Physics.CapsuleCast.html
http://docs.unity3d.com/ScriptReference/Physics.CapsuleCast.html

Otherwise, how about using several tightly packed Physics.RaycastAll, runnin roughly along hte edges of the beam and one throught he middle? Maybe with others in between, depending on how wide your beam is? Wouldn't be perfect, of course.

[x4000]

Otherwise, how about using several tightly packed Physics.RaycastAll, runnin roughly along hte edges of the beam and one throught he middle? Maybe with others in between, depending on how wide your beam is? Wouldn't be perfect, of course.

We were rolling our own stuff (being that it was 2D and thus much simpler math), but for line of sight in Bionic Dues this is pretty much what we did in order to even out corners and whatnot.  The really nice thing about this is that it is able to early out -- if you detect a hit with one of the lines, you can stop checking the other lines since you already know there was a hit.

[Draco18s]

Yeah, I saw the CapsuleCast too.

Problem was that I was trying to double-up on the function* being used and the CapsuleCastAll (also RaycastAll) uses a RaycastHit return type, whereas OverlapSphere uses Collider[].

*Specifically a given component that does the same thing and doesn't give a damn what shape its trying to find.  Refactoring one class into two classes just because they actually do different things is playing hell with my trying to do any Unit Testing.  Which I've already given up on, as its basically useless for the code I have written.  And for the parts I did unit test, its also useless as it's not a clearcut case of "2+2 = 4" but rather a menagerie of values modifying a collection of things and any time I decide that "that number is too big" I have to not only fix the object, but the unit test!

We were rolling our own stuff (being that it was 2D and thus much simpler math), but for line of sight in Bionic Dues this is pretty much what we did in order to even out corners and whatnot.  The really nice thing about this is that it is able to early out -- if you detect a hit with one of the lines, you can stop checking the other lines since you already know there was a hit.

Well for my use-case, not so much. I'm trying to get a "number of hits" for any given direction so that the firing pattern hits the direction that returned the most valid targets.

I may have to use RaycastAll, as I've got a cone-shape to handle too.  And capsule cast won't work for that at all!

[x4000]

Ah, right, the number of points on a given line that can be hit by a beam.  We do that a lot, too (in AI War and otherwise).  What we (mainly Keith) can tell you from experience is that depending on the number of targets, even just detecting the best target in 2D space to hit the most targets with a thin line is very CPU intensive.  Our method is to just get a list of targets in firing range, do a cast to each one and see how many total targets are hit, and then hang on to the one with the most hits.  With a few hundred targets in a small area, it was bloody expensive.  And that's without having anything like blocking walls or whatever.

Personally, depending on your CPU target requirements and the complexity of the scene you have, I think you are barking up the wrong tree trying to have volume on this beam.  It's pretty common to have something that LOOKS like it has volume actually just be a simple ray in shooter-style games.  Particularly if you are talking about AI targeting, for instance, I think you are getting into the "good enough for government work" territory.  That last 10% of improved accuracy might be 90% of your CPU load, and a programming pain in the rear, too.

Personally I would try it with just a ray, see how it goes, and if later it "feels wrong," then look at more computationally-expensive models.  But where you can shave CPU costs, or think you even might be able to, it is always a good idea in my experience, heh.

[Draco18s]

Our method is to just get a list of targets in firing range, do a cast to each one and see how many total targets are hit, and then hang on to the one with the most hits.  With a few hundred targets in a small area, it was bloody expensive.  And that's without having anything like blocking walls or whatever.

That's essentially what I'm going for:
Not the best line but doing a cast towards each target looking for the most hits.  I don't have to worry about hundreds of targets though.  I will keep that in mind, though: if it hits some threshold it says "good enough" and goes with it.

Personally I would try it with just a ray, see how it goes, and if later it "feels wrong," then look at more computationally-expensive models.  But where you can shave CPU costs, or think you even might be able to, it is always a good idea in my experience, heh.

I don't think one ray is going to be enough...Certainly won't be for a cone-shaped emanation.

Anyway, thanks.

[x4000]

No problem!  And for a cone shape, yep, you've got a whole other challenge there.

[Draco18s]

I've got it set up to do 3 rays at 10 degrees apart.  Not sure that's dense enough yet, but preliminary eyeballing says it should be OK.

[NichG]

One thing that could make it a lot faster would be if you could just use the centroids of your various targets and check if a point is inside a volume, rather than doing a raycast against collision geometry.

Basically, a beam with volume is a cylinder. A cylinder has a direction vector 'd', a start point 's', and a radius 'r'. For each point 'p' you want to check, you can calculate:

rp^2 = ( (p-s)-[(p-s) dot d] d )^2

If rp^2<r^2, then its inside the cylinder (this will also hit targets behind the shooter, so you should also check that [(p-s) dot d] is positive)

My guess is that that would be faster than doing multiple raycasts against capsules (even if Unity does it efficiently, a raycast against a capsule is checking two line-sphere intersections and a line-cylinder intersection for each object). Also, this lets you do a cone with the same code basically - you just make r a linear function of [(p-s) dot d] but the rest is the same.

If you want to efficiently compute the best cylinder to hit a bunch of points, that could get costly but I wonder if there's a way to do that calculation efficiently without doing N^2 checks (which is roughly what you're proposing I think?). My guess is that what you should do there is project the point cloud of targets into spherical coordinates, so now you have a 2D map of the 'target density', and then you just want to place a circle on that 2D map that contains the most points - something you could do with an iterative optimization where you cut off the optimization after 3 or 4 iterations, so its O(N) point-circle intersection checks with the optimality of the solution degrading as N increases.

[Draco18s]

You'll probably have to expand that math a bit (or type the variables).

But yes.  Something like that would speed things up.

Spent most of the day trying to mix "follow this path" and "avoid other creeps" logics.  Most of the attempts failed spectacularly with the creeps flying off into the void.  Biggest problem is that because they are all aiming at a path-point (that in a lot of cases is only +1 unit away from the last point) they tend to crowd together and no amount of horizontal push will fix that (too much offset on the target and they'll miss, causing them to circle around, which is bad, not enough offset and they clump).

[NichG]

You'll probably have to expand that math a bit (or type the variables).

Not sure exactly what you mean, but basically they're all vectors:

- 's' is the vector position of the shooter
- 'd' is the unit vector direction in which the shooter is firing
- 'p' is the vector centroid of the target you want to check
- 'r' is a scalar radius of the beam
- 'rp' is the distance from the target to the beam center

Does that help?

[Draco18s]

Bingo,  exactly what I was looking for. It was just hard to parse without a reference.