Now they are spherical, I bet this makes collision detection easy. All you have to do is check the distance of the center point of the sphere from the path of the weapon, subtract the radius of the sphere, and you know if there is a hit if the number is negative.
If the hitbox is a rectagular solid, the calculation would not be so simple. You would have to determine if there is an intersection between the rectangular solid and a line.
The hitbox could also be a cylinder with a hemispherical top and bottom. This might be easier to deal with than a rectangular solid. you would have to calculate the distance between the points ont the two lines and see if at any point it is less than the radious of the cylinder.
I think there may be an economical method to check for the first point in which a line or a ballistic path intersects with a rectangular solid defined as a matrix, but it involves more math than I know at the moment.
Hitboxes
Moderator: Moderators
-
Guessmyname
- Posts: 3301
- Joined: 28 Apr 2005, 21:07
Re: Hitboxes
You're talking about locii, right? (Is this how it's spelt? I can't remember)Foe OfTheBee wrote:Now they are spherical, I bet this makes collision detection easy. All you have to do is check the distance of the center point of the sphere from the path of the weapon, subtract the radius of the sphere, and you know if there is a hit if the number is negative.
If the hitbox is a rectagular solid, the calculation would not be so simple. You would have to determine if there is an intersection between the rectangular solid and a line.
The hitbox could also be a cylinder with a hemispherical top and bottom. This might be easier to deal with than a rectangular solid. you would have to calculate the distance between the points ont the two lines and see if at any point it is less than the radious of the cylinder.
I think there may be an economical method to check for the first point in which a line or a ballistic path intersects with a rectangular solid defined as a matrix, but it involves more math than I know at the moment.
-
Felix the Cat
- Posts: 2383
- Joined: 15 Jun 2005, 17:30
Hmm.
A combination of economy and precision might be a two-phase hitsphere/mesh system.
When a projectile enters the hitsphere, a "potential hit" trigger is set on the projectile, and the extra calculations for possible collision with the mesh are then done. The mesh could be the unit's model or another mesh defined by the modder.
A two-phase hitsphere/hitsphere system might work as well: the modder can define several hitspheres of custom placement and radius for each unit, and Spring generates a "trigger" hitsphere that encompasses all of the unit's real hitspheres. Again, when a projectile enters the "trigger" hitsphere, calculations are done for the real hitspheres.
A combination of economy and precision might be a two-phase hitsphere/mesh system.
When a projectile enters the hitsphere, a "potential hit" trigger is set on the projectile, and the extra calculations for possible collision with the mesh are then done. The mesh could be the unit's model or another mesh defined by the modder.
A two-phase hitsphere/hitsphere system might work as well: the modder can define several hitspheres of custom placement and radius for each unit, and Spring generates a "trigger" hitsphere that encompasses all of the unit's real hitspheres. Again, when a projectile enters the "trigger" hitsphere, calculations are done for the real hitspheres.
Whatever solution, I hope one is implemented soon. I thought the one about multiple hit spheres sounded promising, but being able to use cubes instead or in addition to these spheres would be awesome.
Just looks odd having weapon explosions consistently be in a circle around the unit, not on the unit itself... in addition to the visual thing, there's also the game-breaking factor - a unit which is long and thin should be extremely maneuverable and difficult to hit head-on. Not so in current Spring.
Just looks odd having weapon explosions consistently be in a circle around the unit, not on the unit itself... in addition to the visual thing, there's also the game-breaking factor - a unit which is long and thin should be extremely maneuverable and difficult to hit head-on. Not so in current Spring.
a box that stays in one direction, aligned to the world is the cheapest computationally, just multiple if(xdist<xsize) tests, no multiplies or anything.
But the problem with anything else than spheres is that since spring units rotate in all three axes, only spheres stay the same. Other shapes would have to be rotated too before checking and it'd be expensive. (I don't know if too expensive though.)
Maybe a precheck with a box that encompasses all the possible rotated dimensions.
But the problem with anything else than spheres is that since spring units rotate in all three axes, only spheres stay the same. Other shapes would have to be rotated too before checking and it'd be expensive. (I don't know if too expensive though.)
Maybe a precheck with a box that encompasses all the possible rotated dimensions.
-
SwiftSpear
- Classic Community Lead
- Posts: 7287
- Joined: 12 Aug 2005, 09:29
Wait... it isn't harder to calculate a collision in a box in 3 dimensions... It's easier then calculated sphere collisions. In order to get any straight line query in a 3D environment you have to do a complicated set of calculations to triangulate one point from the other. To calculate hit collision in a box you only have to measure that all 3 of your of your 3 dimensional points for projectile location are between the highest and lowest points of the 3 box dimensions.
Rotating boxes would be more expensive, but if you're willing to do the triangulation for sphere hit detection they wouldn't be that bad. Elongated spheres would just be scary.
Rotating boxes would be more expensive, but if you're willing to do the triangulation for sphere hit detection they wouldn't be that bad. Elongated spheres would just be scary.
I think you're facing matrix transformations with a rotating box (multiply with the inverse of the unit's matrix, then do a normal box test), that's not pretty either. Getting an inverse is very expensive I think.
Also hit boxes are rarely used these days , probably because they are almost 50% wider when you attack them diagonally instead of coming from one of their major directions and cylinders work well enough for most things.
Also hit boxes are rarely used these days , probably because they are almost 50% wider when you attack them diagonally instead of coming from one of their major directions and cylinders work well enough for most things.
Depends. If it's a small matrix, it's no more expensive than any other geometry. If you can guarantee that it's invertible, I think it can be pretty fast. And if you can pre-compute it...KDR_11k wrote:I think you're facing matrix transformations with a rotating box (multiply with the inverse of the unit's matrix, then do a normal box test), that's not pretty either. Getting an inverse is very expensive I think.
One possible suggestion: make it so hit-geometry doesn't pitch, but just rotates. IIRC, that's what a lot of games (3D shooters, for example) do, and while it leads to some wonky results, it's generally Good Enough. Especially since most units spend most of their time standing straight up and down or at small angles from straight up and down, with a few notable exceptions. (Eg: Spiders in AA) Then you can provide a variety of hit-geometry, from cylinders for humanoid things to rectangles for stuff like tanks, ships, etc.
-
SwiftSpear
- Classic Community Lead
- Posts: 7287
- Joined: 12 Aug 2005, 09:29
What's 'messy', out of interest?jcnossen wrote:A rotation matrix could be a 3x3 orthonormal matrix, in which case transpose = inverse IIRC. So it's not really expensive, but I don't think anyone should be implementing this with the messy unit model system that we have today. Cleanup first, then add new features.
Um, things like having s3o and 3DO code mixed in with all sorts of things... the 3DO code, especially, is almost entirely un-abstracted, and is heavily mixed with the animation, BOS-interpretation, and other code sections. In short, it's kind've a mess in there... like a lot've things in Spring, this was obviously built to run first, and to be a model of pretty, clean coding second... and I don't think SJ was really planning ahead for new model formats, etc., when most of this was coded. I suspect when it's all cleaned up, it will help terrifically with certain issues, because file format won't be mixed up with the code that actually moves things around, looks at BOS code, etc.
I'm really overstating the problems to some extent- it's not incredibly awful or anything, but it's quite a bit of layers, and will probably take awhile to get cleaned up.
I'm really overstating the problems to some extent- it's not incredibly awful or anything, but it's quite a bit of layers, and will probably take awhile to get cleaned up.
-
Theotherguy
- Posts: 79
- Joined: 11 Jul 2005, 02:01
the more I think about hitboxes, the more complicated it seems. I was thinking that it could work by checking to see if the centerpoint of a projectile was coplanar with a side of a hitbox, but then I realized that that would only work if the projectiles couldn't travel outside the box.
couldn't you also do it using diagonals? ie, you could draw a line from each vertex of the box and then use some fancy algorithm to determine whether it lies inside the box?
Then again, I havent programmed anything in a 3d engine and all of my hit detection algortihms focused on brute-force, representing every possible pixel of my 2d game as an element of an array. (a method which was both incredibly slow and prone to errors)
couldn't you also do it using diagonals? ie, you could draw a line from each vertex of the box and then use some fancy algorithm to determine whether it lies inside the box?
Then again, I havent programmed anything in a 3d engine and all of my hit detection algortihms focused on brute-force, representing every possible pixel of my 2d game as an element of an array. (a method which was both incredibly slow and prone to errors)
@Theothitbox: You need to detect when the projectile is insicoordinatex. For a hitbox that is aligned with the full cordinates, it is easy. abs(projectile.xpos-unit.xpos) <= unit.hitbox.xsize && ...ysize... && ...zsize...
For a hitbox that is not aligned, you would need to do some cordinate transforms on the positions.
For a hitbox that is not aligned, you would need to do some cordinate transforms on the positions.
Yes and that latter case is what we're talking about with me thinking that that transformation needs a matrix inversion. By the way, the formula for matrix inversion with 3x3 matrices is here. That does look a bit more complicated (i.e. computationally expensive) than simply using cylinders.
While looking for the solution I ran across this.
Also, I don't think we need to invert a matrix. All we need to do is find the rotation from unit.FrontDir to [1,0,0], and apply it to (particle.location - unit.location), getting a new location where the easy check for both a cylinder and a rectangular prism apply.
[Edit] Or we could even change it to polar cords, change theta and phi, and transform it back to Cartesian. Of course, all of this should only be done after it has passed a check of a bounding sphere.[/Edit]
Also, I don't think we need to invert a matrix. All we need to do is find the rotation from unit.FrontDir to [1,0,0], and apply it to (particle.location - unit.location), getting a new location where the easy check for both a cylinder and a rectangular prism apply.
[Edit] Or we could even change it to polar cords, change theta and phi, and transform it back to Cartesian. Of course, all of this should only be done after it has passed a check of a bounding sphere.[/Edit]
Jcnossen is right, if the matrix is orthonormal, you don't need to invert costly but only transpose. Proof here:
http://en.wikipedia.org/wiki/Orthogonal_matrix
But that quaternion thing looks good too. Some research could be done.
http://en.wikipedia.org/wiki/Orthogonal_matrix
But that quaternion thing looks good too. Some research could be done.