4 ms·

The problem with sword combat isn't the computational complexity, but the fact that reporting a hit late is much more noticeable. If you are running across som

The problem with sword combat isn't the computational complexity, but the fact that reporting a hit late is much more noticeable. If you are running across some open space and a bullet hits you, the game can report you being hit 500ms later and it's perfectly fine. With sword, the player can actually see the sword hitting and it has to report the damage at the same moment. A game can compensate by having slower strike animations and preventing players to redirect sword mid hit. Dark Souls 3 does a pretty decent job there - once you press the attack button, you commit to a the attack animation and cannot change or cancel it. So, the receiving end can speed up the attack animation somewhat to compensate and show the sword hit approximately at the same time it hits "on the server". As long as you have good ping, the game feels close to real time - except that opponent attack animations feel somewhat faster than your own (so, harder to dodge and parry).

redistressed 7y ago
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
- 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.

redistressed 7y ago

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