Archive for category Unity Game Development

Calculating a lead on a target

Recently, Quadgnim, on the Unity 3d forums, asked me if I could help him figure out how the code for leading a target would work.  I thought about it for a minute, and then thought about it for a few more minutes.  And now after several hours, I’ve decided it was one of the more fun derivations I’ve done in a while.  So I’m going to share.

First, I’ll lay out the problem.  Consider a sniper, “A” and a target, “B”.  Sniper A is stationary and trying to track a target who is moving, for simplicity at some fixed speed in some arbitrary 3-dimensional direction.  Sniper A wants to fire on B, but if he fires where he sees B, then by the time the bullet arrives, B may have moved out of the way.  So the Sniper must aim at where B will be when the bullet get there.

Here’s a picture of the situation.

A fires on B with the solid red line. But B has moved to the dotted position B prime. A should have fired with the dotted red line.

This would be very simple if B were moving directly toward A or directly away from A.  Then we could either subtract or add that speed to our projectile speed and solve.  But we must concern ourselves with the perpendicular speed as well.  So where do we start?

In order to solve this, we must find a missing variable.  We know all the variables except time, that is the time at which our projectile will hit the target if we aimed properly.  Technically we don’t know where to aim, but if we knew the time, then because B is moving at a steady velocity we would just aim at B’s position plus the distance he travelled over that time, that looks like this

P_b + V_b \Delta t, where P_b is B’s position and V_b is B’s velocity.

So all we need to do is find the \Delta t and plug it into that equation and that’s where we know B will be and thus where Sniper A should aim.

But how do we actually solve this?  Well, let’s start with the naive approach: Lets just fire directly at B and solve for that \Delta t.  That’s pretty straight forward, we just need to find the distance from Sniper A to Target B and then divide by the speed of the projectile.  That looks like this:

\Delta t_{naive} = \frac{||P_b - P_a||}{s} where P_a and P_b are A and B’s positions and s is the speed of the projectile.

But the problem here is that we’ve missed the target by V_b \Delta t_{naive}.   Now we could take the approach that we find an initial \Delta t this way, call it \Delta t_1 and then use that to compute a new P_b and find a \Delta t_2.  That would look like this:

\Delta t_2 = \frac{||P_b + V_b \Delta t_1 - P_a||}{s}

We can continue to iterate this recurrence relation this way, finding \Delta t_3, \Delta t_4 \ldots and so on.  This is a pretty good way to solve a non-linear problem like this, if we don’t know of a closed form solution.  We just keep iterating until, if we’re lucky, we get a converged value, a \Delta t^*.

First find the time it takes to reach B0, then compute how far B has moved to B1. Re run the algorithm using B1 to find B2 and so on.

However, this may not converge.  I’ll return to this because it’ll be there in any solution we find, but intuitively we can guess that it’s a case where our Target is moving as fast or faster than our Sniper’s projectile.  Of course, this wouldn’t happen when we’re talking about humans and bullets, but we may not always be talking about that.  Luckily with a recurrence relation like this, it’s easy to check if we’re converging, we simply watch the change in value between each \Delta t_k and \Delta t_{k+1} and make sure the number is getting smaller.  If it grows or stays the same, we can’t solve the problem.

public float projectileSpeed;
public float lastError = Mathf.Infinity;

Vector3 CalculateLeadIterative (Vector3 previousPrediction) {
  Vector3 V = targetVelocity;
  Vector3 D = previousPrediction - sniper.position;
  float dt = D.magnitude / projectileSpeed;
  Vector3 pos = target.position + V * dt;
  float thisError = (pos - previousPrediction).magnitude;
  if (thisError >= lastError) {
    Debug.LogError ("No solution exists");
    lastError = -1; // -1 is signaling its wrong, never should be negative
  } else {
    lastError = thisError; // outside code checks when this is close enough to 0.
  }
  return pos;
 }

Here’s an example player showing this code working.

Okay, so we have a solution but it’s not really efficient.  If we could find a closed for solution, we could just plug the numbers in and get the answer back.  Maybe that’s possible.  Well let’s start with that recurrence relation we were using, but just get rid of the steps.  There’s only one \Delta t that we want, so let’s plug that in to both sides of the equation.

\Delta t = \frac{||P_b + V_b \Delta t - P_a||}{s}

So, now we can’t easily find a solution for \Delta t because its on both sides of the equation, so we have to do the hard work of seeing whether or not we can isolate it.  I’m out of practice; there’s probably a shortcut I’m missing.  In the end I’ll show the work in case there’s a mistake I’ve made along the way.

So first, I’ll move the s out of the way.

s\Delta t = ||P_b + V_b \Delta t - P_a||

Square both sides because it’s a vector magnitude over there and I want to get rid of that square root so I can pull it apart.

s^2\Delta t^2 = ||P_b + V_b \Delta t - P_a||^2

Because I don’t know a shortcut for this, I’m going to pull the vectors apart.  But for now I’m just going to look at the x component because y and z will look exactly the same and we’ll just add them back in (again because we’re inside a vector magnitude).

\ldots (P_{b,x} + V_{b,x} \Delta t - P_{a,x})^2 \ldots

Doing the work of the full squaring, we get this.

\ldots P_{b,x}^2 + 2 P_{b,x} V_{b,x} \Delta t - 2 P_{b,x}P_{a,x} + V_{b,x}^2 \Delta t^2 - 2 P_{a,x} V_{b,x} \Delta t + P_{a,x}^2 \ldots

And then pulling together the like terms, we see we’re approaching a quadratic equation on \Delta t, which is promising because solving a quadratic equation is straight forward.

\ldots V_{b,x}^2 \Delta t^2 + 2 (P_{b,x} - P_{a,x}) V_{b,x} \Delta t + P_{b,x}^2 + P_{a,x}^2 - 2P_{a,x}P_{b,x} \ldots

That’s pretty close, but we can do one more simplification on those last three terms P_{b,x}^2 + P_{a,x}^2 - 2P_{a,x}P_{b,x}, that’s just a binomial.  I remembered one shortcut.  Yay!

\ldots V_{b,x}^2 \Delta t^2 + 2 (P_{b,x} - P_{a,x}) V_{b,x} \Delta t + (P_{b,x} - P_{a,x})^2 \ldots

Okay now, we need to pull in the other components, y and z.  I’ll do this for each term, so it’s not too messy.

The first term after adding in the other components looks like (V_{b,x}^2 + V_{b,y}^2 + V_{b,z}^2) \Delta t^2.  But we recognize that’s the square magnitude of V_b, so really we have ||V_b||^2 \Delta t^2.  This also works for the third term, which becomes ||P_b - P_a||^2.

The second term,

2[(P_{b,x} - P_{a,x})V_{b,x}+(P_{b,y} - P_{a,y})V_{b,y}+(P_{b,z} - P_{a,z})V_{b,z}]\Delta t,

if we look closely, is a dot product between the vector (P_b - P_a) and the vector V_b, which becomes 2 (P_b - P_a) \cdot V_b \Delta t.

So putting it all back together we’ve got,

s^2\Delta t^2=||V_b||^2\Delta t^2 + 2(P_b - P_a) \cdot V_b \Delta t + ||P_b - P_a||^2

And then pulling the s^2\Delta t^2 over, we finally have a quadratic equation.

0 = (||V_b||^2 - s^2)\Delta t^2 + 2(P_b - P_a) \cdot V_b \Delta t + ||P_b - P_a||^2

Finally, we can compute a solution as follows, using

A=||V_b||^2 - s^2,

B=2(P_b - P_a) \cdot V_b,

C=||P_b - P_a||^2.

and plug them into

\Delta t=\frac{-B\pm \sqrt{B^2 - 4AC}}{2A}

We’ll get two solutions for \Delta t.  One will be negative value of \Delta t.  We can see this as the point in the past where if the Target B, shot at the Sniper A then the projectile would have just now arrived.  But what we care about is the future where Sniper A fires at Target B, so we just need to find \Delta t larger than 0.   And we’re able to write out the code.

public float projectileSpeed;

Vector3 CalculateLead () {
  Vector3 V = targetVelocity;
  Vector3 D = target.position - sniper.position;
  float A = V.sqrMagnitude - projectileSpeed * projectileSpeed;
  float B = 2 * Vector3.Dot (D, V);
  float C = D.sqrMagnitude;
  if (A >= 0) {
    Debug.LogError ("No solution exists");
    return target.position;
  } else {
    float rt = Mathf.Sqrt (B*B - 4*A*C);
    float dt1 = (-B + rt) / (2 * A);
    float dt2 = (-B - rt) / (2 * A);
    float dt = (dt1 < 0 ? dt2 : dt1);
    return target.position + V * dt;
  }
 }

Here’s an example player showing this code working.

Before I conclude, I want to look at some of the properties that come out of the quadratic solution and how they relate to intuition about the problem.
Going back to the discussion of impossible cases we see that in A.  Seeing it in the bottom of the fraction, we know that if A is zero this will blow up.  That happens when Target B’s velocity is the same as the projectile speed.  But looking under the square root we see that if B’s velocity is larger than projectile speed, we get imaginary results, which since we’re looking for a physical solution we want to avoid.

Finally, looking at the numerator of the quadratic solution

-B \pm \sqrt{B^2 - 4AC}

Lets make the following substitutions:  ||V_b|| will be V.  ||P_a - P_b|| will be D.  And we’ll replace the dot product in B with ||V|| ||D|| cos \theta.  And what we wind up with is,

-2||V|| ||D|| cos \theta \pm \sqrt{4||V||^2 ||D||^2 cos^2 \theta - 4(||V||^2 - s^2)||D||^2}

Expanding under the square root we get,

-2||V|| ||D|| cos \theta \pm 2\sqrt{||V||^2 ||D||^2 cos^2 \theta-||V||^2||D||^2+s^2||D||^2}

And then simplifying,

-2||V|| ||D|| cos \theta \pm 2\sqrt{||V||^2 ||D||^2 (cos^2 \theta - 1)+s^2||D||^2}
Because, sin^2 \theta + cos^2 \theta = 1, we get,
-2||V|| ||D|| cos \theta \pm 2\sqrt{s^2||D||^2-||V||^2||D||^2sin^2\theta}

Which is another binomial under the square root, giving,

-2||V|| ||D|| cos \theta \pm 2\sqrt{(s||D||-||V|| ||D||sin\theta)^2}

Removing the square root,

-2||V|| ||D|| cos \theta \pm 2(s||D||-||V|| ||D||sin\theta)

Pulling out the ||D|| and the extra minus sin, and put this back in with the denominator (which lets us get rid of the 2 all together).

\frac{||D|| (||V|| cos \theta \pm (||V|| sin\theta - s))}{||V||^2 - s^2}
Seeing this, our earlier intuitions about the problem pop right out.  The cos\theta term represents how fast Target B is moving either directly toward or directly away from Sniper A.  The sin\theta term represents how fast Target B is moving perpendicular to Sniper A.  Pull the math all the way to its final conclusion we’re able to find the patterns that make sense with our original intuition.
I love me some math.

2 Comments

Optimization of Draw Calls

I want to talk about what I think is a pretty cool trick for optimizing the number of draw calls in Netstorm 2 an RTS.  Dealing with draw calls in an RTS is more challenging than, say, an FPS because the player can create a large number of objects over the course of the game.  In an FPS, you know how many objects there will be (except maybe for missiles).  In an RTS, the point of the game is to dynamically create units for your army, and each one of these might be a draw call, which means it can get pretty expensive, pretty quickly.

The Bridges of RisingStorm County

There are a large number of bridge units built in a game of Netstorm

Netstorm has an additional challenge: one of the principle “units” a player will place is a bridge.  This is free (although limited to how many you can place every few seconds) and is used to maneuver.  It is in the player’s best interest to place bridges as fast as possible.  In an average game there are hundreds of bridge pieces being built.

Bridges of RisingStorm

The bridges have Tetris-like shapes

Each bridge piece is a Tetris-like shape that is made up of smaller atomic pieces, e.g., a straight, a corner and a tee.  Each of these under normal circumstances will be a separate draw call.  However, thanks to the Mesh Combiner script provided with Unity, these are very easily combined into the Tetris-like shapes.  However, there are still hundreds of Tetris-like shapes to deal with.

Small diversion:  A few years ago, a friend of mine and I worked on a game engine ourselves.  For better or worse, I pushed us into using threads aggressively.  One cool benefit was that since systems acted in independent threads, we could avoid the situation where the may game loop has to run as fast as possible to service any possible need.  Thus the CPU would only be used as much as it was needed, which for many situations was hardly at all.

In order to deal with these many independent systems we set up a publish/subscribe mechanism to decouple dependencies between the systems.  We also had several systems which would only run based on certain events happening, rather than running in a loop.  We created a central dispatch and scheduler which we called the Hub to manage the execution of these systems and dispatch messages to them.

Recently, I saw a way of bringing back some aspects of the Hub into Unity.  Specifically the dispatcher and the scheduler.  The dispatcher uses Unity’s SendMessage interface, but instead of needing to know which game object you want to send to, you just send the message to the dispatcher.  Any gameobject that wants to see that message simply needs to register for it.  One of the ways I use this inside Netstorm is to turn shadows on and off when the FPS are too low or safely high enough.  When the FPS drops below 15, a message is sent to the dispatcher saying “LowFPS” and the shadows disable.  Once the FPS goes back above 60 another message is sent and shadows are turned back on.  Because the FPS checker doesn’t know who is getting the message other effects could also register for the low and high FPS to decide when to turn off.  I could also use this for Level of Detail changes.

But, going back to the bridges, there’s an even cooler trick.  Running the mesh combiner is expensive and Unity’s dynamic batching is limited to 300 polygon object.  It would be nice to have something in between that we can choose to run as needed.  This is where the scheduler comes in.

It works as follows, when a bridge is placed it checks to see if it has been connected to another bridge or if it is independent.  If it’s independent it creates a parent object that contains a scheduled mesh combiner.  This mesh combiner will run 3 seconds after it has started.  However, if another bridge is placed connected it’ll child itself with that existing bridge’s parent and the scheduler will be pushed back by 3 seconds.  Once the player stops building a particule bridge path for 3 seconds the combiner will finally run and combine all the bridges.

Here’s what the code looks like:

public class MeshRecombiner : MonoBehaviour {
    public float recombineDelay = 10.0f;

    private bool dirty;
    void CheckRecombine () {
        if (dirty) {
            Recombine ();
            dirty = false;
        }
    }
    void MarkDirty () {
        foreach (Transform child in transform) {
            if (child.name == "Combined mesh") {
                child.parent = null;
                Destroy (child.gameObject);
            } else {
                child.gameObject.SendMessage ("MarkDirty", null,
                    SendMessageOptions.DontRequireReceiver);
            }
        }
        if (!dirty) {
            Scheduler.GetInstance().AddSchedule (recombineDelay, "CheckRecombine", false, gameObject);
            dirty = true;
        } else {
            Scheduler.GetInstance().AddSchedule (recombineDelay, "CheckRecombine", gameObject);
        }
    }

Notice a few things.  First off, there is a function called “Recombine” which is called by “CheckRecombine”.  “CheckRecombine” is what will be called by the scheduler.  “Recombine” is essentially the “Start” routine from the “MeshCombiner” class that comes default in Unity.  One change is that a child object “Combined mesh” is always created regardless of whether there’s only one material.  This is to simplify the “MarkDirty” code.  The “MarkDirty” function is called when a child is added or removed or modified in some way that requires recombining (e.g., a material has changed on the child).  This “MarkDirty” then disables all the current combinations sends message to all the children who should enable their individual renderers again.  It then sets up the scheduler to call it.

Here’s an example of a simple child which can be combined:

function Start () {
    transform.parent.gameObject.SendMessage ("MarkDirty");
    enabled = false;
}

function MarkDirty () {
    var renderers;
    renderers = GetComponentsInChildren (Renderer);
    for (var r in renderers) {
        r.enabled = true;
    }
}

The final piece to this code is of course the Dispatcher and Scheduler.  However, they are much to large to copy and paste here.  Instead, they exist on github here: https://github.com/tosos/Geewhiz under the project Geewhiz which is the name of the previous game engine I worked on.

Using this method in a situation like the screenshot shown above with all the bridges the draw calls can be taken from something like 700 in that image (with all effects added including shadows) and reduced to on the order of 200, which if it had been enabled at the time the screen shot was taken would have likely taken the frame rate from 3 to something more like 15, at least.  These days it is possibly to get much higher frame rates during multiplayer games of Netstorm.

Hopefully you will be able to get similar speed ups with dynamically created objects using a combination of these techniques.  Drop a line in the comments here if you are able to find some use with these.

1 Comment

Refactoring Part 2

Now I’m finally going to talk about specifics.

In the last post I mentioned attempting to refactor the build panel into both an in-game construction device and a level editor device.  It turns out one of the issues that had been bothering me for a while was in the bridge display.  Every time you place a bridge a new random one takes it’s place.  I put this in the build panel, because it was the obvious place to do so, but it bugged me that there was so much code in the build panel for just displaying icons and now it also had to be responsible for managing bridge replacement when all the other icons for other units and structures just stayed there (for the most part).

The level editor didn’t need this whole bridge mechanism, it just needed a panel that would show icons and allow you to drag them onto the field.  I finally had a reason to split out the bridge code.  It was beautiful.  At least mostly, I still haven’t entirely pulled out old assumptions.  I tore all the code that handled bridges into a separate file.  Because it was well separated I could remove a number of if checks and actually shrink the code somewhat because now I could assume that I was only dealing with bridges in that code.

I’ve been talking about assumptions a lot.  Back in school, it would have been called “invariants”.  Invariants are great, it means you *know* a certain thing is going to be true (or false) at a given time and so there’s no need to check.  Good coding practice will tell you to check anyway, and that’s true, but now you replace an “if this do this” to “assume this or throw an exception” and if your code never throws that exception during testing you did well.

So assumptions aren’t bad, they’ll make the code more efficient in the long run, but may also make it less general.  There’s a choice to make.  I could have written the level editor without reusing the build panel, but I was predicting when I made the choice that there would be a lot of repeated code and not much efficiency to be had.  As I said, it really was the same thing.  But in general, if there’s that choice to be made, I’ll usually pick the one with the smaller code, because smaller code looks like it was easier to do.

It turns out there are another couple bonuses which might be had from refactoring, but which I haven’t yet attained.  I’ll get to the bonuses in a few paragraphs (see that foreshadowing). The stumbling block I’m sitting on is that the bridge piece when placed notifies the build panel that it has been placed so that the build panel knows to randomly select a new piece of bridge to put in there.  Once I split out that bridge control code, the bridge piece was notifying the wrong system.

My assumption, for efficiency was to have the bridge piece just grab the build panel, because every draggable grabs the build panel.  In fact, it’s in the base class.  The build panel is supposed to know enough about all construction to darken the icon while any of its objects is being placed and not allow you to click a new one until you either place or cancel the last one.  So each object which is in the build panel needs to tell it when it’s placed so that the build panel knows it can relinquish the lock on the display.

I could use a publish subscribe model as I mentioned previously for the pathfinder, notifying any subscribers when the bridge is placed.  This would allow both the build panel and the bridge controller to get notifications and each do the appropriate thing with a good split. But this is a larger chunk of code that I’d have to write and in reality, it’s only this one case.  So having a full publish/subscribe is a bit over the top and a little to much architecting.  At least it feels that way…

I mentioned bonuses that I haven’t yet attained.  I haven’t attained them because currently the build panel still assumes there are icons for bridges at the top and still in the build panel.   The build panel then has to call into functions in the bridge controller to let it know when it gets notification from a bridge piece.  There’s a level of pointless indirection in that call.  The first bonus then would be that the level editor uses that space to place icons like “save/load” and “quit” as well as other editor specific icons like the player’s priest (his avatar in the game) which sets his starting location.  But because the build panel currently assumes bridges in those locations, the save/load button becomes “bridge slot 1″ (by a function call, SetBridgeIcon (1, “Save Icon”) normally used by the bridge controller when a new bridge is ready to replace the icon) and the priest icon is “bridge slot 6″.  Just arbitrary bridge locations instead of arbitrary icon locations.  And it looks silly.

The other bonus I would receive by fixing this is that there is a bug in Unity with the gui elements.  Because I’m changing the icons, on these buttons it redraws them.  For some reason, Unity’s gui doesn’t remove old draw elements, so as you place bridges, the draw calls goes steadily upwards.  Likely it’s drawing nothing, but a draw call is a call out to the graphics card and bridging is a very common thing so much that thousands of bridges will be placed during a game.  1000′s of draw calls will cripple the graphics performance.

By just establishing a graphical placeholder in the build panel and letting either the editor or the bridge controller actually draw in the icons they  need I can remove the sillyness in the editor of setting “Bridge Icons” and in the bridge controller I can optimize out the GUI bug.

So I still haven’t arrived at a solution.  I may just go ahead and write a publish/subscribe mechanism with as many assumptions as I can put in to keep the code as small as possible.  And maybe I’ll figure out a way to refactor it into something smaller later.

No Comments

Switch to our mobile site