5 ms·

Appreciate the comment, but I want stress that the problem really is the computational complexity. (Or at least, computational complexity really is a serious pr

Appreciate the comment, but I want stress that the problem really is the computational complexity. (Or at least, computational complexity really is a serious problem.) If everything in your world behaves like a bullet, physics is simple. If everything in your world behaves like a sword, physics is a nightmare. A lot of games with swords literally pretend that swords are made of bullets to get around this. No kidding. To spoil my deep explanation: in the sense games are concerned with, a bullet is a non-rotating length-0 inertially-controlled sword. That doesn’t generalize cheaply.

nwallin 7y ago
Spitballing here. Model a sword as a point of rotation e, (elbow, shoulder, whatever, have the animator figure it out) location of the tip point p, and the linear velocity vector v of its tip. Look at the letter 'F': The elbow is the point at the bottom, the travel of the tip is the top bar, the travel of the hilt (not modeled) is the shorter bottom bar. The travel of the tip is the parametric equation `tv + p`, which defines the line `(tv+p)d + e` You have one line for each sword. Solve for the intersection of the two lines. If t is outside the bounds of your framestep, they do not intersect. Do basic comparisons on the length of the arm/forearm + sword length to figure out if they connect. Bonus: gives you one character slashing the others' wrists for free. Piercing attacks are just hitscan. If you really need to model elbows that are moving (probably only for characters on horseback while galloping) you'll need to parameterize the elbow point. Use the character's velocity vector I guess; I wouldn't do anything more complicated than that. I suppose that also works for combination slashing/thrusting attacks? I'm too lazy to plug that into the line intersection formula, but it seems like a fairly basic linear algebra problem. Unless you're trying to make it super hyper realistic, (don't do that) I don't understand why the computational complexity is a problem.
- subroutine 7y ago
  Here is the maths for rotation of vectors around arbitrary axes: https://sites.google.com/site/glennmurray/Home/rotation-matrices-and-formulas/rotation-about-an-arbitrary-axis-in-3-dimensions https://sites.google.com/site/glennmurray/Home/rotation-matr... I've used these to simulate polymer growth branching in 3D. Determining if and where two lines in 3D space intersect requires determining the scalar parametric equations of the two lines, then solving 3 simultaneous equations using a method like gaussian elimination. Seems like the last step could be computationally taxing for a cpu if performed each time-tic during sword swings - not sure if modern GPUs are optimized for just this sort of problem.
  - nwallin 7y ago
    I'm aware. I deal with rotations and intersecting geometries at work too. There's a closed form 3x3 matrix inversion procedure which is very fast on CPUs. [1] We don't use it with pen and paper because it's too hard to remember and there's a lot of places to fuck up substitutions, but computers don't have problems with remembering obtuse formulas. (it's like the 2x2 inverse where you shuffle stuff around and divide by the determinant) So you're looking at about 60 instructions (one division operation) with no branching to solve Ax = b in R3. [2] The reciprocal throughput is 16.5 cycles, so 5.5ns on a 3GHz Skylake assuming everything's in cache. In gamedev you'll use an approximate reciprocal instead of the division, so the latency will be lower but AFAIK the throughput will be the same. The slow part of rotations is actually computing the sin/cos of the angles. You'll notice my model avoids anything to do with angles: there are no transcendental functions. This is non-physical for a few reasons, notably it's not possible to swing a sword more than 90 degrees in one frame. It's fine for a video game where you assume a full sword swing will take 15-30 frames and good enough is good enough, but it's not fine for scientific computing. Video games are all about faking it when nobody's looking. Also, my model starts with defining motion in terms of the scalar parametric equations of the lines. I did think about this before posting. :) [1] https://en.wikipedia.org/wiki/Invertible_matrix#Inversion_of_3_%C3%97_3_matrices https://en.wikipedia.org/wiki/Invertible_matrix#Inversion_of... [2] https://godbolt.org/z/ND6tTM https://godbolt.org/z/ND6tTM
    - subroutine 7y ago
      You sure did think about it, hah, thanks for sharing!
- ngold 7y ago
  What's the difference from a fighting game like sf2, where your legs and fist act as essentially the same thing as a sword. Dhalsim has some pretty long feet and arms in that game.
  - nwallin 7y ago
    Fighting games like SF2 usually work on 2D hit boxes. [1] You have boxes which are defined as things that do hitting, boxes which are defined as areas that can get hit, and boxes that define clipping. If a do-hitting box overlaps a get-hit box, a hit occurs. It's a simple, elegant system that's ideal for a game with a fixed 2D playworld and fixed 2D attacks. It doesn't work for a system with free form 3D sword combat. If you block up and to the right, and a sword comes in from up and to the right, you should block it, but if it comes from up and to the left you should get hit. https://www.youtube.com/watch?v=SB2CvPt87X8 https://www.youtube.com/watch?v=SB2CvPt87X8
- konceptz 7y ago
  That’s very complex compared to a model I was thinking about while reading this article. Consider that many forms of sword fighting remove the complexity by creating zones. I’ve been told that a skilled swordsman can identify 16-32 zones considering where an attack can come from or where to strike. Isn’t this a much easier model if you factor in the weight/mass/velocity of each particular character? This would be a little like auto-aim but you could still compute each path and create effects against one when they happen or not.
  - nwallin 7y ago
    Maybe. If you have 4-8 static blocks vs 16-32 attacks that would be fine, but if you need to calculate what happens when 16-32 attacks run into the same 16-32 attacks you have a combinatorial explosion problem which you then need to simplify. One of the reasons I like going straight to the linear algebra approach is that you do a batch of basic arithmetic which the CPU does quite fast without branching, and then you do one branch to determine hit vs not-hit. Pairing zones with zones sounds like nested if/else statements, but I hadn't dived into considering that approach.
Jasper_ 7y ago
Swords can be modelled as "oriented bounding boxes" or OBBs. OBB/OBB collision has been part of the toolkit for years and is not computationally complex. The computation of sword/sword collision is not the hard part. The gameplay mechanics to make it fun, are.
- BorisTheBrave 7y ago
  Actually no. Thin, quickly rotating objects are an area where a lot of collision detections libraries fall down - the simpler algorithms just look at the position of the objects each frame, and two swords can easily pass through each other in the time between frames. The problem is called tunelling, and though there are some features to deal with it, there aren't any ones that are simple, reliable and cheap.
  - tekromancr 7y ago
    Why wouldn't the blended ray+physics technique described in the article not work? I am imagining projecting a bunch of rays from the blade along the vector of travel each physics tick and using that to determine if a collision will occur during that tick. I've never tried to implement anything like that, so I am curious where that might Fail.

nwallin 7y ago

Spitballing here. Model a sword as a point of rotation e, (elbow, shoulder, whatever, have the animator figure it out) location of the tip point p, and the linear velocity vector v of its tip. Look at the letter 'F': The elbow is the point at the bottom, the travel of the tip is the top bar, the travel of the hilt (not modeled) is the shorter bottom bar. The travel of the tip is the parametric equation `tv + p`, which defines the line `(tv+p)d + e` You have one line for each sword. Solve for the intersection of the two lines. If t is outside the bounds of your framestep, they do not intersect. Do basic comparisons on the length of the arm/forearm + sword length to figure out if they connect. Bonus: gives you one character slashing the others' wrists for free. Piercing attacks are just hitscan. If you really need to model elbows that are moving (probably only for characters on horseback while galloping) you'll need to parameterize the elbow point. Use the character's velocity vector I guess; I wouldn't do anything more complicated than that. I suppose that also works for combination slashing/thrusting attacks? I'm too lazy to plug that into the line intersection formula, but it seems like a fairly basic linear algebra problem. Unless you're trying to make it super hyper realistic, (don't do that) I don't understand why the computational complexity is a problem.

subroutine 7y ago
Here is the maths for rotation of vectors around arbitrary axes: https://sites.google.com/site/glennmurray/Home/rotation-matrices-and-formulas/rotation-about-an-arbitrary-axis-in-3-dimensions https://sites.google.com/site/glennmurray/Home/rotation-matr... I've used these to simulate polymer growth branching in 3D. Determining if and where two lines in 3D space intersect requires determining the scalar parametric equations of the two lines, then solving 3 simultaneous equations using a method like gaussian elimination. Seems like the last step could be computationally taxing for a cpu if performed each time-tic during sword swings - not sure if modern GPUs are optimized for just this sort of problem.
- nwallin 7y ago
  I'm aware. I deal with rotations and intersecting geometries at work too. There's a closed form 3x3 matrix inversion procedure which is very fast on CPUs. [1] We don't use it with pen and paper because it's too hard to remember and there's a lot of places to fuck up substitutions, but computers don't have problems with remembering obtuse formulas. (it's like the 2x2 inverse where you shuffle stuff around and divide by the determinant) So you're looking at about 60 instructions (one division operation) with no branching to solve Ax = b in R3. [2] The reciprocal throughput is 16.5 cycles, so 5.5ns on a 3GHz Skylake assuming everything's in cache. In gamedev you'll use an approximate reciprocal instead of the division, so the latency will be lower but AFAIK the throughput will be the same. The slow part of rotations is actually computing the sin/cos of the angles. You'll notice my model avoids anything to do with angles: there are no transcendental functions. This is non-physical for a few reasons, notably it's not possible to swing a sword more than 90 degrees in one frame. It's fine for a video game where you assume a full sword swing will take 15-30 frames and good enough is good enough, but it's not fine for scientific computing. Video games are all about faking it when nobody's looking. Also, my model starts with defining motion in terms of the scalar parametric equations of the lines. I did think about this before posting. :) [1] https://en.wikipedia.org/wiki/Invertible_matrix#Inversion_of_3_%C3%97_3_matrices https://en.wikipedia.org/wiki/Invertible_matrix#Inversion_of... [2] https://godbolt.org/z/ND6tTM https://godbolt.org/z/ND6tTM
  - subroutine 7y ago
    You sure did think about it, hah, thanks for sharing!
ngold 7y ago
What's the difference from a fighting game like sf2, where your legs and fist act as essentially the same thing as a sword. Dhalsim has some pretty long feet and arms in that game.
- nwallin 7y ago
  Fighting games like SF2 usually work on 2D hit boxes. [1] You have boxes which are defined as things that do hitting, boxes which are defined as areas that can get hit, and boxes that define clipping. If a do-hitting box overlaps a get-hit box, a hit occurs. It's a simple, elegant system that's ideal for a game with a fixed 2D playworld and fixed 2D attacks. It doesn't work for a system with free form 3D sword combat. If you block up and to the right, and a sword comes in from up and to the right, you should block it, but if it comes from up and to the left you should get hit. https://www.youtube.com/watch?v=SB2CvPt87X8 https://www.youtube.com/watch?v=SB2CvPt87X8
konceptz 7y ago
That’s very complex compared to a model I was thinking about while reading this article. Consider that many forms of sword fighting remove the complexity by creating zones. I’ve been told that a skilled swordsman can identify 16-32 zones considering where an attack can come from or where to strike. Isn’t this a much easier model if you factor in the weight/mass/velocity of each particular character? This would be a little like auto-aim but you could still compute each path and create effects against one when they happen or not.
- nwallin 7y ago
  Maybe. If you have 4-8 static blocks vs 16-32 attacks that would be fine, but if you need to calculate what happens when 16-32 attacks run into the same 16-32 attacks you have a combinatorial explosion problem which you then need to simplify. One of the reasons I like going straight to the linear algebra approach is that you do a batch of basic arithmetic which the CPU does quite fast without branching, and then you do one branch to determine hit vs not-hit. Pairing zones with zones sounds like nested if/else statements, but I hadn't dived into considering that approach.

Jasper_ 7y ago

Swords can be modelled as "oriented bounding boxes" or OBBs. OBB/OBB collision has been part of the toolkit for years and is not computationally complex. The computation of sword/sword collision is not the hard part. The gameplay mechanics to make it fun, are.

BorisTheBrave 7y ago
Actually no. Thin, quickly rotating objects are an area where a lot of collision detections libraries fall down - the simpler algorithms just look at the position of the objects each frame, and two swords can easily pass through each other in the time between frames. The problem is called tunelling, and though there are some features to deal with it, there aren't any ones that are simple, reliable and cheap.
- tekromancr 7y ago
  Why wouldn't the blended ray+physics technique described in the article not work? I am imagining projecting a bunch of rays from the blade along the vector of travel each physics tick and using that to determine if a collision will occur during that tick. I've never tried to implement anything like that, so I am curious where that might Fail.