Optimising projectile continuously calculated impact point

Question

Gday all. Apologies for cross post but in hindsight I think this is much better here than the forums.

I am working on a hobby arcadey flight combat game and trying to get CCIP working.

I am not using physics for the projectiles, code in use below:

 void Update () {
         //Check where the bullet needs to go this frame
         bulletSpeed = (bulletTransform.forward * (bulletFireSpeed * Time.deltaTime)) - (Vector3.up * Time.deltaTime * downwardSpeed);
 
         newPosition = transform.position + bulletSpeed;
 
         //raycast to ensure we wont go through terrain or object
         if (!Physics.Linecast(bulletTransform.position, newPosition, out ray))
         {
             bulletTransform.position = newPosition;
         }else
         {
             Impact(ray);
         }
 
 
         downwardSpeed += 5.0f * Time.deltaTime;
 
     }

That all works fine with no issues whatsoever.

The issue is trying to calculate the impact point... My first attempt was just to replicate the bullet code in a function that would step by step simulate a bullet flight path (ie. raycast current loc, loc + speed, if ok then move to new position and repeat, when hit, return hit point as the CCIP reticule loc)

             if (!Physics.Linecast(simulatedBullet.position, newPosition, out ray))
             {
                 simulatedBullet.position = newPosition;
             }else
             {
                 impactFound = true;
                 Debug.Log(cycles);
                 return ray.point;
             }

That killed framerate as it generally went through 150-200 cycles before finding the impact point (if it got to 1000 cycles it would exit and hide the reticule)

So attempt 2... instead of linecast (oh yea... expensive!) I decided to use the terrain sample height (as I already have the position of the simulated bullet)

             if (simulatedBullet.position.y > Terrain.activeTerrain.SampleHeight(simulatedBullet.position))
             {
                 simulatedBullet.position = newPosition;
             }else
             {
                 impactFound = true;
                 Debug.Log(cycles);
                 return newPosition;
             }

That was slightly better but still devestated frame rate...

The current (quite inadequate) implementation involves using the sampleheight idea above but including a yield time.deltatime every X cycles (I found 10 to be the absolute maximum cycles per frame)

Obviously these ideas are not the way to go... I am assuming I will need to come up with a parabolic equation to simulate the bullet's flight but that will have it's own headaches as far as undulating terrain impact points (and the linecast is the only one that takes into account non terrain objects - eg other planes etc)

So my question is.... Can anyone see an alternate way (that is much nicer on processing power) to calculate it? The 'easy' option I can think of is to tinker with my current 'physics' setup to make the vertical speed constant then I can just do a single linecast from origin to the terrain but that is taking a pretty big hit which I would really prefer not to do... Thoughts?

Answer 1

Your second approach with the linecast looks like the best one to me. The only problem are those 100+ iterations, which is insane :D

What i would do is to create an octree to aid me in deciding the amount of neccessary linecasts and their length. In case you don't know what an octree is: octree

So basically the octree would divide the game world into cubes/volumes. Lets assume the edge length of each volume is 200 units. Further assume that every enemy plane and obstacle is represented in the octree, including terrain. Once we've done that, it's easy to check if a certain volume has obstacles in it, or not. Tha basic idea is that it's much faster to check that, instead of making unneccessary linecasts. In the best case (empty volume), we can traverse 200 units without a linecast!

Let's take an example bullet. The bullet leaves the players plane and checks if the volume it's in is empty. If thats the case we don't use a linecast inside this volume and proceed to the next volume in the predicted flight path. Then again we check if the volume has obstacles. This time there is an enemy plane! That means we have to linecast through this volume, just in case we hit that sucker. Sadly out bullet missed the enemy plane and travels into the next volume. This time there are no obstacles in the volume and we can skip it entirely, not using a single linecast! Rinse and repeat...

In the end all you have to do is to balance the size of the volumes your octree has. Smaller volumes lead to bigger memory footprint and lookup time, but reduce the amount of needed linecasts and their length. There is also a need for constant relocation of the obstacles, because the enemy planes are moving and that adds some overhead. Still that is overhead once per obstacle every couple of frames and all of your bullets can use that octree, which makes if a very fast solution for problems found in almost every game.

I hope you survived reading through this and apologies for not being a native english speaker. =)

Answer 2

I have an alternative idea how exclude unneccessary raycasts. Cant say wich is faster, i guess only experiment could say :)

At startup:

make "trajectory bounds" collider. At startup make a gameobject that is not visible but contains a box collider, set isTrigger to true. You will move and deform it et every frame (see below).
store objects that are intersecting this collider now. make an ArrayList that would be store, and add a colliders to it at OnTriggerEnter handler and remove at OnTriggerExit. So now you will have an array of colliders that intersect your "trajectory bounds" collider. They are "collision candidates".

Now per-frame algorythm in general:

step 1. calculate trajectore bounds At this step you should calculate a bounds of projectile path. You could use Bounds type to store it. Actualy, to do so, you need a coordinates of 3 points - spawn point, the highest point of the trajectory and point where projectile hit the ground. Spawn point is known, two others could be calculated. Find a little of math ingoogle: the equations of the trajectory of a body thrown at an angle to the horizon, the method how to find an parabolla and horizontal line intersection point, and how to find a parabola extremum point coordinates (the only parabola extremum is higher point). To simplify this step - you could find a lower point of your terrain once at startup, and always calculate third point as point, where projectile would hit a terrain if it was flat and all at this minimum height. Make calculations in 2D, at the plane of trajectory.
step 2. rotate and deform "trajectory bounds" collider. rotate your "trajectory bounds collider" accordingly to "launch y-angle" and deform it to match calculated trajectory bounds.
step 3. check collision candidates, level 1. now you cuold roughly check candidates. For each of them check 2 the most distant points of bound: if they both all above/below trajectory parabola then candidate is not needed anymore (because it doesnt intersects with trajectory). If one of them above and another below - candidate may be hit by projectile, it proceeds next level - store them in somewhere. Note that bounds is the cube that is always orienter straight along axis (their edges are always horizintal and vertical and parallel to axis) - it makes it not necessarily to check all 4 points of bounds. To detect if point above or blow parabola - use paraola equation to find trajectory y with given x, and compare it with candidate bounds point's y.
step 4. raytracing. And now you need as few raytracings as you have collision candidates proceeds all previous checks. Fast but more rougn method - is find a point where trajectory hits a candidate bounds cube (you already found it's 2D representation at prev step as (bounds x, y=parabola(x))on trajectory plane, you even could store it there for each candidate at that step. You just need to find an angle (as a first derivative of parabola function in 2D), and then convert coordinated and vector to 3D and get a ray to raytrace. And you could use a max bounds side as ray kength (ray shorter - raytrace faster).
step 4. select a nearest. This is obviously - if two or more colliders a hit by raytrace - you need a nearest of them. You even could do this check in previous step by excluding candidate (without raytracing them) if you already have a closer candidate hit by raytrace.

In the end you will very fiew raytracings each frame.

I hope you will handle a math part of this :). for me it would be quite hard if I had to implement this :) I just remember general things from high school, but not details already... But not impossible :)

Hope it would be helpful..

Optimising projectile continuously calculated impact point

2 Replies

Your answer

Follow this Question

Related Questions