[VIDEO][FAST ALGORITHM] Draw Thrown Projectile Pathing, Shows Predicted 3D Bounces

[evernewjoy]

Dear Community,

I've seen a few posts asking how to do the projectile pathing as used in tomb raider and gears of war and other games, and I decided to develop my own algorithm.

After may iterations of mental attempts to find a simple fast accurate method,

I have come up with a surprisingly simple algorithm that has the following characteristics

1. Extremely accurate

2. Shows exact bounces of projectile exactly as it would move around world geometry if thrown

3. Fully dynamic, press of a button to activate, release to hide, and exact expected path of projectile is drawn correctly.

4. Actually very useful game mechanic to see exect predicted bounces against world geometry, really helps in a fully 3rd game and especially in fast paced third person action.

5. Fully 3D, so you could draw the expected pathing of an ally or friend in multiplayer and if they were drawing pathing you would see exactly where their projectile will land, even though looking from a different angle then they are.

6. Light weight / low cpu cost, can render new paths as character rotates/moves quite quickly

7. Code optimized so you can easily control how many pathnodes are drawn and at what 3d space intervals. Only need to change 2 numbers at any time.

~~~

ArrayCount() Mini-Tutorial

Included is a mini-tutorial on the value of ArrayCount() for code optimization for both the programmer as well as the unreal engine

~~~

Video

Here's a video showing my simple algorithm at work

~~~

Grenade Static Mesh In Video

The static mesh grenade in video was made by the awesome modeller and visionary Shaun Williams, the lead designer and founder of the Ghostship Open World FPS Survival-Horror Game

~~~ My Navmesh-Free AI in GhostShip Game ~~~

I am the lead and sole programmer for this project, and the alpha release already features my completely navmesh and pathnode free AI.

Literally my AI system just spawns in to the level and responds appropriate to level geometry it encounters and can jump on top of objects and chase the player down anywhere the player tries to hide in the often complicated and tight environments of the Ghostship Game.

The KickStarter / Fund-raiser for this project

Your interest and support is much appreciated

~~~

Fast Algorithm Code Sample For You

Pre-Requisites

I cannot show the entire workings of what is required for what you see in video because you need

1. a weapon or other way of choosing when to throw the projectile

2. a projectile static mesh to throw

3. a usage of kactor or projectile class based on your interests. I wrote my own physics engine for a utprojectile to cause it to behave like a kactor so it would work under all circumstances, even per-poly collision

However, the purpose of this tutorial is to show you the Algorithm that I created, and I am providing the complete code for that, which includes

1. generating full 3D pathing indicators on the fly to indicate exact path of a thrown projectile, including bounces.

2. ability to allow pathing to stay on, and move pawn around and have pathing re-generate itself

3. a fast, simple, efficient, way to do all this that is not tough on cpu

and for which a network implementation / replication should be pretty simple (replicate positions of spawned 3d pathing indicators of each player).

~~~

Copy Right Policy

************************************************** **************
My CopyRight Policy

If you use part or all of my algorithm and code please

give credit where credit is due, by posting a link to my tutorial hub:

(right click and get link address, this is abbreviated link)
http://forums.epicgames.com/threads/...de-and-Videos)

Also post on this page so others see this code as well and can benefit as you have.

And of course I'd like to know that all the time I've spent preparng these tutorials

has helped you

♥

-Rama
************************************************** **************

~~~

Algorithm Overview

1. Player activates pathing system

2. an invisible exact copy of the projectile to be thrown is actually thrown, it has collision

3. as projectile flies through air, a timer is going off and spawning static meshes that do NOT have collision (saves on efficiency/cpu cost)

4. Player deactivates pathing system or lifespan timer runs out, and all static meshes are destroyed

5. If player holds down button to continuously draw pathing,

algorithm determines whether player has moved enough to warrant a complete path recalculation,

making for ability of player to move around and rotate and see dynamic path updates that include projectile's reaction to world geometry

~~~

Code For You

Optimization Tip:

ArrayCount()

I use ArrayCount() which IS actually optimized because Arraycount is for static arrays only, whose count never changes, so unreal engine converts ArrayCount() to a number during compile time, as per unreal wiki sources.

Wiki Source On ArrayCount Optimization

“The*ArrayCount*pseudo-function can be used to get the length of a static array. Note that it is actually evaluated at compile time and replaced by an integer value in theUnrealScript bytecode. ”

~~~

Why Use ArrayCount for Static Arrays?

So that in your code you can just change the actual count of the static array when it is being declared, and then all your code is updated for all your iterators.

~~~

Your Weapon Class / Where you Throw Projectile

You dont have to use a UT weapon at all for this code to work

//======== Thrown Projectile ============
var YourProjectilePathNode pnode;
var vector throwDir;
var vector pawnRot;
var vector spawnLoc;
var YourProjectileObject p;

//simply change this static array count and the timer frequency
//to reduce or increase number of path nodes drawn
var YourProjectilePathNode pathNodes[20]; 

var YourProjectileObject tracer;
var int curPathNodeCount;
//=================================

//============ Draw 3D Path ===============
function stopDrawingPathNodes() {
	
	if(tracer != none){
		tracer.destroy();
	}
	ClearTimer('drawPathNodes');
	clearPathNodes();
}
function startDrawingPathNodes() {
	
	//already running
	if (isTimerActive('drawPathNodes')) return;
	
	//clear any remaining previous path nodes
	clearPathNodes();
	
	//throw the tracer
	tracer = throwTracer();
	
	//hide
	tracer.setHidden(true);
	
	curPathNodeCount = 0;

	//~~~~~~~~~~~~~~~
	// Main Timer
	//
	// Change duration of this timer to control 
	// how spaced out the pathnodes are
	//
	//~~~~~~~~~~~~~~~ 
	SetTimer(0.05, true, 'drawPathNodes');
	
	//~~~~~~~~~~~~~~~~~
	// Max Life Span
	//~~~~~~~~~~~~~~~~~

	//max life span of 12 seconds
	SetTimer(12, false, 'clearPathNodes');
}

function drawPathNodes() {
	
	//end case
	if (curPathNodeCount >= ArrayCount(pathNodes) ) {
		ClearTimer('drawPathNodes');
		return;
	}
	
	//lost tracer case
	if (tracer == none) {
		ClearTimer('drawPathNodes');
		return;
	}
	
	createPathNode();
	
}
function clearPathNodes() {
	
	for (v = 0; v < ArrayCount(pathNodes); v++ ) {
		if (pathNodes[v] == none) continue;
		pathNodes[v].Destroy();
	}
}
function createPathNode() {
	
	//end case
	if (curPathNodeCount >= ArrayCount(pathNodes)) return;
	
	//lost the tracer
	if (tracer == none) return;
	
	pnode = spawn(Class'YourProjectilePathNode',,, tracer.Location, rot(0, 0, 0),, true);
	
	//code to set a material instance for your path node, as I use in video to make
	// the object glow different colors through code
	//pnode.staticmeshcomponent.setMaterial(0, pc.thirdpTargetingMat);
	
	pathNodes[curPathNodeCount] = pnode;
	curPathNodeCount++;
	
}
function YourProjectileObject throwTracer() {
	
	//pc is ref to your controller class
	//see my other tutorials on giving
	//this class a ref to your pc using
	//post begin play
	pawnRot = Vector(pc.pawn.Rotation);
	throwDir = pawnRot;// * 1000;
	throwDir.z *= 3;
	
	spawnLoc = pc.pawn.Location + pawnRot * 64;
	spawnLoc.z += 64;
	
	//spawn
	p = spawn(Class'YourProjectileObject',,, spawnLoc, rot(0, 0, 0) );
	
	//init
	//p.InitializeProjectile(pc, throwDir);
	//implementation dependent
	return p; 

}
//========================================================

~~~

YourProjectileObject Class

This is implementation dependent, as to whether you are using an actual Kactor or a projectile.

As I said I wrote my own physics engine for a ut projectile for maximum use in all types of collision including per poly.

~~~

YourProjectilePathNode Class

Notice how in default properties I am doing a lot to make the rendering of each pathnode as light on the cpu as possible, cancelling all the features like shadowing and collision that are really not needed anyways.

class YourProjectilePathNode extends StaticMeshActor placeable; 

DefaultProperties
{
	
	Begin Object Name=StaticMeshComponent0
		
		//saves on efficiency
		CastShadow = false						
		bUsePrecomputedShadows=false

                //Collision Off
		BlockRigidBody		= false
		BlockZeroExtent		= false
		BlockNonZeroExtent	= false
		
		//replace with your chosen 3d mesh
		//scale3d = (x=0.137,y=0.137,z=0.137)
		StaticMesh=StaticMesh'ramaPackage3.StaticMesh.lattice_sphere'
		
		//RB Collision
		//efficiency
		bNotifyRigidBodyCollision = false
		ScriptRigidBodyCollisionThreshold = 1
		RBCollideWithChannels=(Default=false)
		
		//efficiency
		bAllowAmbientOcclusion=false
	End Object
	CollisionComponent=StaticMeshComponent0
	
	bStatic=false
	bMovable=true
	
	//Collision Off
	bCollideActors=	  false
	bBlockActors=	  false
	bWorldGeometry= false
		
}

~~~

player controller class


these are the values I used to determine if the player moved enough to warrant a complete pathing recalculation

These recalculations are done every tick that the pathing system is active

//optimization
//global var declarations
//to avoid reallocating memory space every playertick
var rotator oldRot;
var vector oldLoc;
var float changeInRot;
var float changeInLoc;
var bool drawingProjectilePathing

function StartDrawingPathing(){
	drawingProjectilePathing = true;

	oldRot = Rotation;
	oldLoc = pawn.Location;
		
	//draw pathing
	//if using ut weapon var below is ref to your weapon instance
	//if not using a weapon, this is ref to the class where you put the code
	//above, or you could put the code above into this controller class
	ReferenceToYourProjectileSourceClass.startDrawingPathNodes();
}

function StopDrawingPathing(){
	
	drawingProjectilePathing = false;

	ReferenceToYourProjectileSourceClass.stopDrawingPathNodes();
}

Simulated Event PlayerTick(Float DT) {
	super.playertick(DT);

   if(drawingProjectilePathing) {
		
	//calc change in player rot and position
	changeInRot = Vsize(Vector(Rotation) - Vector(oldRot));
	changeInLoc = Vsize(pawn.Location - oldLoc);
		
	//if player moved or rotated enough
	if(changeInRot > 0.14 || changeInLoc > 23 ){
	  oldRot = Rotation;
	  oldLoc = pawn.Location;
			
	  //restart drawing of pathing
	  ReferenceToYourProjectileSourceClass.stopDrawingPathNodes();
	  ReferenceToYourProjectileSourceClass.startDrawingPathNodes();
   }
}

~~~

Summary

See video for summary of results of this algorithm I am providing you with

1. its fast

2. its fun

3. its accurate

4. its dynamic to any terrain or environmental blocking of projectile path

5. you can move around with pathing turned on and get constant sense of what your projectile will do when thrown

6. It's full 3D pathing, see action from any angle and the pathing is still accurate

7. its low cpu cost for what it provides!!

Enjoy!

Rama

[ryanjon2040]

Awesome Rama!! Been looking for this.

[Uditt Lamba]

Great tut... will help me a lot! Thanks!
Keep doing the noble work!

[Neoptolemus]

Quick tip: if you change the path-drawing grenade's customtimedilation value to something like 10, you can make it look like the path is drawn instantly rather than at the same speed the real thing is drawn.

[goncalofsilva.25]

Seems very useful and informative for people starting with UDK, but... since only one player is drawing at the moment, I don't understand why would you spawn and destroy objects at run-time (which I believe to be very expensive operations) instead of using the existing DebugDraw() calls in the Actor class. Out of the box, I don't believe this is as fast as you claim it to be.

Maybe you can show some speed comparisons for the more sceptical? Either way, if you're going to use this system you should optimize it further using an Object pool pattern and avoid all those Spawn/Destroy calls.

[Neoptolemus]

Hi evernewjoy, I've adapted your tutorial a bit. The "scouting" grenade runs at a time dilation of 40 so it finishes its arc almost immediately. Instead of drawing spheres periodically, it stores its current location in the player controller array. When the grenade "explodes", it signals the player controller that it has finished its path, and the player controller then draws debug lines between each point in a "join the dots" manner.

The result is quite effective I think, though I'm not sure what such a high time dilation will do when faced with a low framerate. I'm guessing you'll end up with only a few points being registered, leading to mostly flat arcs, so perhaps I could add a check where if bDropDetail is true then all it will do is mark the end location so it skips everything else but at least it shows you where the grenade will end up.

Here is a video of the result, let me know what you think!

[evernewjoy]

Wow your video is awesome!

Thanks for sharing!

That's not time dilation, that is the deliberate behavior of my code,

I did not want to recalculate pathing every tick for efficiency purposes

buuuut

you can easily change this to suit your needs!


Here is a version with NO deliberate delay

Simulated Event PlayerTick(Float DT) {
	super.playertick(DT);

   if(drawingProjectilePathing) {
	/*
	//calc change in player rot and position
	changeInRot = Vsize(Vector(Rotation) - Vector(oldRot));
	changeInLoc = Vsize(pawn.Location - oldLoc);
		
	//if player moved or rotated enough
	if(changeInRot > 0.14 || changeInLoc > 23 ){
	  oldRot = Rotation;
	  oldLoc = pawn.Location;
	*/

	  //restart drawing of pathing
	  ReferenceToYourProjectileSourceClass.stopDrawingPathNodes();
	  ReferenceToYourProjectileSourceClass.startDrawingPathNodes();
   }
}

Here is a version of my code that has much tighter behavior, but is not instantaneous constant recalcuations of pathing

Simulated Event PlayerTick(Float DT) {
	super.playertick(DT);

   if(drawingProjectilePathing) {
	
	//calc change in player rot and position
	changeInRot = Vsize(Vector(Rotation) - Vector(oldRot));
	changeInLoc = Vsize(pawn.Location - oldLoc);
		
	//if player moved or rotated enough
	if(changeInRot > 0.05 || changeInLoc > 7 ){
	  oldRot = Rotation;
	  oldLoc = pawn.Location;
	
	  //restart drawing of pathing
	  ReferenceToYourProjectileSourceClass.stopDrawingPathNodes();
	  ReferenceToYourProjectileSourceClass.startDrawingPathNodes();
   }
}

~~~

Let Me Know Of Your Success

Do post another video showing the corrected behavior when you get it the way you want it!

having SOME delay rather than recalculating every tick is probably best

adjust the numbers I highlighted to be small enough to get desired result

Rama

[evernewjoy]

Dear GonCalofSilva,

Seems very useful and informative for people starting with UDK, but... since only one player is drawing at the moment, I don't understand why would you spawn and destroy objects at run-time (which I believe to be very expensive operations) instead of using the existing DebugDraw() calls in the Actor class. Out of the box, I don't believe this is as fast as you claim it to be.

Maybe you can show some speed comparisons for the more sceptical? Either way, if you're going to use this system you should optimize it further using an Object pool pattern and avoid all those Spawn/Destroy calls.

You are absolutely correct, spawning/destroying constantly is not as efficient/fast as my new algorithm, posted below:

In this algorithm

1. all the objects (20 in my code) are spawned only ONCE and never destroyed (similar to your object pool concept you shared, thanks for the link )

2. the objects that are created only a single time and then moved around are also destroyed only once, when the weapon using them as indicators is destroyed.

3. I use move, which is whole lot faster than SetLocation, to move the objects around (Setlocation rehashes collision and is therefore noticeably slower than move)


I have a problem with this algorithm though, which is only reason I am not replacing my original post algorithm.

I cannot figure out how to use move or setlocation while the object is hidden, and have it update its position properly.

I was originally just hiding the objects when not in use, but I could not get the movements to occur properly while object was hidden, so instead I never hide the object but move it far below the player, but above the killZ.

I fully know this is not ideal, but I cannot understand why just hiding/showing the object and moving it around is not working.

Anyone have any suggestions let me know

The code below works and IS much faster than the original post code.

I just would like to resolve the hiding/showing + moving issue and then it will be good to go

~~~

Faster Algorithm That Uses Move Instead of Spawning/Destroying/SetLocation

var YourPlayerControllerClass pc;

//============Display Path ============
var YourProjectilePathNode pathNodes[20]; 
var YourProjectileClass tracer;
var int curPathNodeCount;
//=================================

var int v;
var vector vc;
var YourProjectilePathNode pnode;

simulated function PostBeginPlay() {
	
	//~~~~~~~~~~~~~~~~~~~~~~~~
	super.PostBeginPlay();
	//~~~~~~~~~~~~~~~~~~~~~~~~
	pc = YourGameInfoClass(WorldInfo.Game).currentPlayer;
	
	createNodesRunOnceEntireGame();
}

//============ Draw Path ===============


//=================
//Memory Management
//=================

//Create Once For Entire Life of this Weapon
function createNodesRunOnceEntireGame() {
	for (v = 0; v < ArrayCount(pathNodes); v++ ) {
		
		//last spawn parameter makes sure spawning occurs regardless of obstructing collision
		pnode = spawn(Class'YourProjectilePathNode',,, 
                                                 pc.pawn.Location, rot(0, 0, 0),, true);
		
		pnode.staticmeshcomponent.setMaterial(0, pc.thirdpTargetingMat);
		pathNodes[v] = pnode;
		
		//pc.optimize("node set"@v);
	}
	
	//hide from view
	clearPathNodes();
}

//when this class is destroyed,
//destroy the objects spawned into world
//to act as path node indicators

//this is an actor event and is called by unreal engine
simulated event Destroyed() {
	super.Destroyed();
	for (v = 0; v < ArrayCount(pathNodes); v++ ) {
		if (pathNodes[v] == none) continue;
		pathNodes[v].destroy();
	}
}

function stopDrawingPathNodes() {
	
	if(tracer != none){
		tracer.destroy();
	}
	ClearTimer('drawPathNodes');
	clearPathNodes();
}
function startDrawingPathNodes() {
	
	//already running
	if (isTimerActive('drawPathNodes')) return;
	
	//clear any remaining previous path nodes
	//clearPathNodes();
	
	//throw the tracer
	tracer = throwTracer();
	
	//hide
	tracer.setHidden(true);
	
	curPathNodeCount = 0;
	SetTimer(0.05, true, 'drawPathNodes');
	
	//max life span of 12 seconds
	SetTimer(12, false, 'clearPathNodes');
}



function drawPathNodes() {
	
	//end case
	if (curPathNodeCount >= ArrayCount(pathNodes) ) {
		ClearTimer('drawPathNodes');
		return;
	}
	
	//lost tracer case
	if (tracer == none) {
		ClearTimer('drawPathNodes');
		return;
	}
	
	positionPathNode();
	
}
function clearPathNodes() {
	
	//position doesnt update if hidden for some reason
	//so move node way far away from player to simulated being hidden
	//still faster than spawning/destroying
	
	//would like to know how to make location update properly even while its hidden
	//some sort of low-level or native optimization that is getting in the way here
	for (v = 0; v < ArrayCount(pathNodes); v++ ) {
		
		//set the loc
		vc.x = (v + 1) * 4000;
		vc.y = (v + 1) * 4000;
		vc.z = pc.pawn.Location.z - (v + 1) * 4000;
		
                //make sure not going below killz
                if (vc.z < worldinfo.killz) 
			vc.z = worldinfo.killz + 5;
		
		pathNodes[v].move(pc.pawn.Location + vc - pathNodes[v].Location);
	}
}

function positionPathNode() {
	
	//end case
	if (curPathNodeCount >= ArrayCount(pathNodes)) return;
	
	//lost the tracer
	if (tracer == none) return;

	//move is way faster than SetLocation
	//this code says "move path node the amount that is the difference
	//between its current location and the desired goal position"
	pathNodes[curPathNodeCount].move(
                           tracer.Location - pathNodes[curPathNodeCount].Location
        );
	
	curPathNodeCount++;
	
}

[Neoptolemus]

Wow your video is awesome!

Thanks for sharing!

That's not time dilation, that is the deliberate behavior of my code,

I did not want to recalculate pathing every tick for efficiency purposes

buuuut

you can easily change this to suit your needs!

Thanks! I think you misunderstood me about the custom time dilation though. The sped-up time dilation is applied to the actual "scouting" projectile itself. If you see your first video you can see the preview arc being drawn at the same rate as the actual grenade moves, that is to say there is a one second delay between you priming the grenade and the arc finishing being drawn. By applying a high time dilation to the "scouting" projectile, it means the path is drawn instantly, so when you hold down the throw button you see the arc instantly rather than waiting for it to finish drawing. Hope this is a bit clearer!

To achieve this you can simply put CustomTimeDilation=20 into the default properties of your scouting projectile which will make it run in fast-forward, giving you a much quicker result.

[evernewjoy]

oooh I see

That's a great idea btw, thanks for mentioning it to everyone.


My response was to what I saw in your video where the redrawing of the arc was pretty infrequent, and I wanted to let you know how you could make it happen more often.

Let me know if you encounter any issues with raising the time dilation later on in your game development!


I personally like the slower drawing because it feels like the computer assisted aiming mechanism is taking time to calculate things, just a personal choice really


But thanks for showing everyone a way around that if that's their preference



Rama

[Kelt'ar]

Your tutorials are amazing!
DO you take requests?

[evernewjoy]

Yay I'm glad you like them!

I can always hear requests yes, though usually my tutorials are based on what I myself am working on

Rama

[Ouroboross]

Yes ! Thank you so much, been looking for this for a while now and didn't see you've posted a code a week ago !!

But, I still have some issues, as I have 4 different weapons firing 4 different projectiles, I was trying to make them inherit from one single class, which is inherited from UTWeapon itself. And nothing happens, I don't know why.
I've created my own mesh for the Scouting Projectile, as the real projectiles are some particle systems with mesh datas. I thought it could come from here.

If you could help me, I'd really appreciate, I'd love to share a video of my game to you with your system implemented, I'd give you back the whole credit !
Tranks a lot for this, I'll keep trying to make it work, waiting for some help

[evernewjoy]

If you post your code, all the critical parts relating to when you fire your projectile / use the targeting feature / spawn the tracer /scouting projectile

then I / rest of Community can be of more help

Rama

[nonder]

I cannot figure out how to use move or setlocation while the object is hidden, and have it update its position properly.

I did not test it but you can try to hide just component, not actor.