Author Topic: Physics of Cuboids! Or: How can I best do this?  (Read 3051 times)

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,183
Physics of Cuboids! Or: How can I best do this?
« on: June 22, 2014, 10:19:36 PM »
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?

Offline Shrugging Khan

  • Hero Member Mark III
  • *****
  • Posts: 1,217
  • Neinzul Y PzKpfw Tiger!
Re: Physics of Cuboids! Or: How can I best do this?
« Reply #1 on: June 23, 2014, 02:32:12 AM »
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.
The beatings shall continue
until morale improves!

Offline x4000

  • Chris Park, Arcen Games Founder and Lead Designer
  • Arcen Staff
  • Zenith Council Member Mark III
  • *****
  • Posts: 31,404
Re: Physics of Cuboids! Or: How can I best do this?
« Reply #2 on: June 23, 2014, 09:04:05 AM »
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.
Have ideas or bug reports for one of our games?  Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,183
Re: Physics of Cuboids! Or: How can I best do this?
« Reply #3 on: June 23, 2014, 10:25:59 AM »
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. :P 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!

Offline x4000

  • Chris Park, Arcen Games Founder and Lead Designer
  • Arcen Staff
  • Zenith Council Member Mark III
  • *****
  • Posts: 31,404
Re: Physics of Cuboids! Or: How can I best do this?
« Reply #4 on: June 23, 2014, 10:39:34 AM »
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.
Have ideas or bug reports for one of our games?  Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,183
Re: Physics of Cuboids! Or: How can I best do this?
« Reply #5 on: June 23, 2014, 11:52:04 AM »
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.

Quote
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.

Offline x4000

  • Chris Park, Arcen Games Founder and Lead Designer
  • Arcen Staff
  • Zenith Council Member Mark III
  • *****
  • Posts: 31,404
Re: Physics of Cuboids! Or: How can I best do this?
« Reply #6 on: June 23, 2014, 11:53:07 AM »
No problem!  And for a cone shape, yep, you've got a whole other challenge there. :)
Have ideas or bug reports for one of our games?  Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,183
Re: Physics of Cuboids! Or: How can I best do this?
« Reply #7 on: June 23, 2014, 01:20:36 PM »
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.

Offline NichG

  • Full Member
  • ***
  • Posts: 125
Re: Physics of Cuboids! Or: How can I best do this?
« Reply #8 on: June 23, 2014, 03:17:46 PM »
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.

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,183
Re: Physics of Cuboids! Or: How can I best do this?
« Reply #9 on: June 23, 2014, 05:55:53 PM »
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).

Offline NichG

  • Full Member
  • ***
  • Posts: 125
Re: Physics of Cuboids! Or: How can I best do this?
« Reply #10 on: June 23, 2014, 09:25:24 PM »
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?

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark V
  • *****
  • Posts: 4,183
Re: Physics of Cuboids! Or: How can I best do this?
« Reply #11 on: June 23, 2014, 09:48:37 PM »
Bingo,  exactly what I was looking for. It was just hard to parse without a reference. :)