Download

How to make collision detection for fast melee combat?

Hi!

I think fast melee combat at low FPS is a known issue, so I’m planning ahead and hope to have it solved when the time comes to actually implement it.

I figured that i can use sockets attached to the skeleton to read the position of the tip and base of the weapon.

Tho, during low FPS situations they can move quite a bit, especially for long staffs!

A potential solution to this would be to check the distance between current (0) and previous (-1) frame and then construct the poses for in-between times (if you are allowed to do this in Unreal) and get the socket positions for those in-between times as well, to do extra “ghost” collision checks.

An alternative to the previous idea could be to save the positions for 4 frames in a row and do catmull-rom interpolation to get a curved trail to follow for the time-span between previous frame (-1) and the one before the previous one (-2), having the collisions lag 1 frame.

Then for the fun part:
How to actually check for collision given those points from earlier step?

  1. triangles vs capsule
  2. capsule vs capsule
  3. tons of rays vs capsule

As I’m using C++ so I guess I’m allowed to write my own collision checks, so it gets so hard to choose what to pick!

Is there anyone who got a melee system that works at low FPS?

[EDIT]
This is the level of craziness I’m going for, still making it playable at low FPS:

[EDIT2]
I’m working on a different solution now, check post #14 for more info

Per-Bone Sword Collision, FPS Independent Accuracy

Hi there!

I wrote a per-bone sword collision system during the UE4 Beta that works well at any FPS, it’s not that complicated!

I made several sockets along the weapon and retained the previous tick socket positions and trace horizontally to the next/current tick’s positions

Whether there are 5 or 50 points in the melee swing (varies by frame rate / tick rate), because the trace is horizontal along the swing path, it connects contiguously / continously and does not miss.


**Chosker**

Forum member Chosker has an excellent tutorial on melee combat and is working on a project that has gone past the Beta stages that is multiplayer melee combat focused.

**More Videos**

I have over 80 UE4 videos on my [you tube channel](https://www.youtube.com/channel/UCBc38LaldK4qi1V-g_DJPyA/videos) and a few features here on the wiki:

**Wiki Link**
https://wiki.unrealengine.com/Victory_Game_Videos#Per-Bone_Sword_Collision

Enjoy!

Rama

Thanks Rama!

Not to sound arrogant, but how well does your implementation deal with a character holding a long staff at the tip and spinning like a tornado at crazy speeds?

In this case during low FPS, the character might rotate 90-180 degrees (yaw) making the tip of the staff move along a curve, while tracing between current and previous frame position will go along a line taking a significant shortcut!

just to quickly clarify, my tutorials do not include a fighting system, nor is my game multiplayer. nevertheless do give it a look if you’re interested in swordfighting games :wink:

Michael: the method used by Rama is the same I used in my implementation ], and it works wonders with any length.
you’ll see it in the pictures of my implementation, that the traces are about sweeping through the trajectory, which means that as long as there’s an actual curve trajectory it will be able to sweep through it.
extreme cases (more than 90 degrees of rotation in one tick) would still fail though. for example if you move 180 degrees in one tick then the sweep between the previous position and the current position would be a straight line that goes through your own character. but for such extreme cases where extreme movements happen during one tick you won’t find any other working solution

Well, what about my idea?

Before this, I made my own game from scratch and used AssImp for the animation part:

There I could ask the animation code to generate the pose from the keyframes for any point in time, so I could detect that the weapon moved a lot and for example split up the time step in 8 parts and generate the poses for those frames making the code behave as if the FPS was much higher!

Tho, that animation system does not use any blending, so it is much simpler.

What I’m trying to do is to make a game like Ninja Gaiden, so the attacks are exactly as animated and not dynamic in any way so I guess I could pre-compute stuff and save in data files, or port that AssImp based animation code to Unreal so I’ll have to export everything as FBX for Unreal and as DAE for AssImp.

As you probably notice; I’m new to Unreal and don’t know how to use it efficiently, but I do have some experience rolling my own stuff in C++.

I don’t know if you’d be able to get a socket location from the animation data, I guess it could be worth a shot.
however if your weapon is an attachment you won’t have such an easy time “recreating” where the socket is in relation to the attachment in relation to the character :eek:

Hmm, you are right, it will be a lot of work.

So, I came up with an other solution:
If I reduce the “Engine Scalability Settings” to Low and then Play as Standalone from the editor i can get “decent” fps. So I can make an offline tool that plays the animations and saves the positions of the sockets (in character space coords) and puts them in a list, and draws the result on screen. Then if I press a button then that will be passed to an “AI” that tries to match 2 bezier-splines to those points (base & tip of weapon) and shows the progress on screen. Then when/if I’m happy with the result, I press an other button and the control-points for those splines will be saved to a file, to be used in the game later. So given those 2 splines i can approximate the location for those sockets for any point in time, and given 2 sockets I can get a line-segment representing the weapon! And as this is rather deterministic, so I can have an other worker-thread calculate the in-between data given those splines and current+previous character positions+rotations, potentially lagging 1 frame behind (unless it uses 2 old frame-positions to predict the next position+rotation of the character)!

What do you guys think about this?

Is it overkill or something the should even make it into the engine as a plugin for us doing crazy hack 'n slash stuff?

As we are getting more and more CPU-cores we need to find new ways to keep them busy. So even if this seems like lots of useless calculations it is better than just having some core just idling when not having anything to do.

I have done an implementation which uses interpolated animation poses (i.e. replaying the animation step-wise during each tick) to determine socket locations, and it worked pretty well.
In addition to this, I used a sphere sweep trace, where the sphere size determined the max gap between interpolation “notches”, which pretty much meant not even small objects were missed during the traces.

I’ve pasted my Weapon’s .h and .cpp files, as well as my Weapon_Melee’s .h and .cpp files here if you’d like to try and decipher it:

Weapon.h
Weapon.cpp
Weapon_Melee.h
Weapon_Melee.cpp

This was done quite a long time ago so I don’t really remember all the details offhand, but please feel free to ask if something’s unclear and and I’ll check what I can remember.

I’m no expert at animation by any means, but I do think that sub-stepping the animation or curve as has been suggested is a good approach. We use sub-stepping (break down large time chunks in to smaller ones) in a lot of places where simulation is impacted in a negative way by low framerates. For example ProjectileMovementComponent, CharacterMovementComponent, and SpringArmComponent all support sub-stepping.

Thank you guys for your input!

I got the idea for using a Bezier curve from playing around with Cinema 4D that has FCurves to specify how to go between one key and the next key.

So I believe that curves can be a compact way to store a description of the motion of the weapons, and is cheaper to compute than constructing a hierarchy of matrices from key frames, so I’ll go with that.

Regarding the collision detection, I’ll consider the weapon and character to both be capsules, which can be simplified to line-segment vs capsule (using Minkowski).

If you want to implement your own collision then feel free, but the Engine collision methods using PhysX should take care of things for you, and allow you flexibility in terms of shapes supported if you decide to change it later. Also I would think you’d want to test against many different objects in the world, maybe even shapes on the skeletal mesh of enemies, so the complexity of your own solution could go up.

The scenario that this is designed for is like those found in Devil May Cry 4 and Ninja Gaiden Sigma 1, where there will be 1 player vs a few really dangerous enemies.

So the important part is that a swing won’t miss if the FPS drops for some reason. Things like hitting the heart or head of the enemy won’t be implemented, as this is a 3rd person hack 'n slash game using predefined attacks, where the focus is on going nuts and do crazy combos.

Therefore I feel like making my own lightweight collision-code, as that will give me some extra control, and can be tweaked using knowledge specific to this game, that is not general enough to make it into the Engine / PhysX (like updating, creating and destroying collision shapes rapidly or cache some calculation results, etc).

I came up with a slightly different partial solution that I felt like sharing.

anu1.png

Character rotating at low speed

anu2.png

Character rotating at higher speed

Character rotating and moving at high speed

The green lines are showing the line between the sockets.
The red lines are computed.


FVector curBase = GetMesh()->GetSocketLocation(FName("StaffBottomSocket")), curTip = GetMesh()->GetSocketLocation(FName("StaffTopSocket"));
const int sub = 32;
float curLength = (curBase - curTip).Size();
float prevLength = (prevBase - prevTip).Size();
for (int i = 1; i < sub; i++)
{
	FVector tmpBase = FMath::Lerp(curBase, prevBase, i / float(sub));
	FVector tmpTip = FMath::Lerp(curTip, prevTip, i / float(sub));
	FVector tmpOff = (tmpTip - tmpBase);
	tmpOff.Normalize();
	DrawDebugLine(GetWorld(), tmpBase, tmpBase + tmpOff*FMath::Lerp(curLength, prevLength, i / float(sub)), FColor::Red, false, 1 / 15.0f * 2);
}
prevBase = curBase;
prevTip = curTip;
DrawDebugLine(GetWorld(), curBase, curTip, FColor::Green, false, 1 / 15.0f *2);


The code is rather simple and lerps between current and previous socket location.

The interesting part here is that it tries to keep the length of the line consistent by normalizing it and then scale by the expected length.

(The length of the line should in fact be constant, but this is for making it more general)

It is not a perfect solution but I thought it was good enough to share.

Like rel bladestorm