Wonky missiles algorithm

[ghost]

I think I need some help in nailing this, if anyone is interested.

The hack posted to Reddit is fun but we could do way better, I'm just not sure how.

Some restrictions:

• update() runs on increments of fractional frames, so however the algorithm works needs to support that
• basically it's easy to produce an infinite stream of identical bits on client/server, it looks like this part is a solved problem (xorhash32(pos.x+pos.y+id) or similar)
• update() on server vs. client might run with different fractions, so must pay careful attention to how bits are drained from the stream so they stay in sync

Ideas

• "X% of the time, missile flies at a right angle", I love this, but it might look ugly without a little bit of new animation.
• "aerodynamic instability". Think how a firework flies when it's had its support broken off. I think this would be the funniest option
• "semi self-correcting wobble". missile veers off wildly but still follows original line within some % of error. so what you get is basically a UI effect that could also take an unsuspecting plane by surprise, but the weapon is still usable at max distance

Sub-ideas:

• Richochet off walls. I don't know if this should be done for carrot, or if it could be kept in reserve for another missile type. I think ricochet for example could be the primary differentiator e.g. for an xplay baguette missile

Problems:

• just adding random numbers to speed.x/y doesn't produce the right result. They need to be capped and account for direction and suchlike

I wouldn't mind nailing it in frontend first, so that if it's necessary to patch it into Starmash that only needs to happen once, and it only needs copied into server once

---

for usopp:

client fires,

server 'spawns a mob', that message includes a bunch of variables, but most importantly (speed.x, speed.y), where e.g.

• speed.y > 0 = missile flies speed.y pixels up for each frame
• speed.y < 0 = flies down
• speed.x > 0 = ...

etc.

(x, y) are set based on angle of plane when it fired

For every frame, and for whatever reason for fractions of a frame, some calculation runs that can modify the speed and absolute position (which usually updates from speed)

It calculates a number 0..1 ("fracFrame") depending on how much of a full frame's worth of change should apply, so you can write

speed.x = fracFrame * (x change)
speed.y = fracFrame * (y change)

And things work out.

In my messing around, I summed 'fracFrame' up over each call into a variable 't', so it turns into the number of frames the missile has been alive for. Then I divided that number down and passed it into Math.sin() and added that to speed.

There is also 'spriteRot' which is the angle it's being fired at. I think the correct application is something like

speed.x = fracFrame * Math.sin(spriteRot) * Math.sin(t/7)
speed.y = fracFrame * Math.cos(spriteRot) * Math.sin(t/7)

But this caused an insane stop-start missile that made no sense at all.

We can also modify position directly, rather than via speed. But speed seems to be the correct variable to change

[ghost]

Non-random 'semi self correcting wobble', could be done by overlaying a sine wave on the missile's bearing. The period of the wave would determine the max error when missile reaches target. But how to add randomness to this?

[ghost]

What about some kind of scheme where random bits were used to pick a selection of periods, but somehow ensure that when all the periods were summed up, the target was about the same at the max missile distance?

[matastrb]

> speed.x = fracFrame * Math.sin(spriteRot) * Math.sin(t/7)
> speed.y = fracFrame * Math.cos(spriteRot) * Math.sin(t/7)

sin(t/7) would cause the problem as t varies with respect to frames. You can try to change it to exp(-t/7) which produces decaying velocity. Or change to speed.y ~ math.cos(t/7).
I was thinking about using cubic spline to create fancy trajectories. If we assume that the missile flies at a constant speed, then to know the completion time we need to calculate the travel distance (curve length) which is not easy (there exists implementation on google). So this idea doesn't seem practical at all.

[ghost]

Missiles have a 'maximum range' value.. what about something like assuming they will travel half of that and make two splines, one for each leg. Someone else suggested using splines too

[matastrb]

How about this? The total length is approximate max_range/cos(15deg). Could be more wonky but the simple estimate strays away.

[ghost]

I'll hopefully have another shot at it this weekend

[matastrb]

I think we should stick with less wonky curves which are easier to implement from both sides like parabola or elliptic.
For the parabola, we only need to implement the calculation of the inverse Vandermonde matrix (3x3).
I will work on it later (tomorrow :D).

By the way, do you know if javascript/typescript has a linear algebra library which could perform vector multiplication and matrix inverse? If yes then I only need to explain the idea.

[matastrb]

Simple ellipse curves. I assume that missiles can travel longer than max_range. However the line of sight distance between the start and destination is still bounded by max_range.

Assume that the starting point (plane current location) and the destination are given. The destination could be calculated for example at the max_range from the plane current location in the direction pointed by the plane (or with some other deviation). We use an ellipse to fit a curve between these two points.

First we calculate the center of the ellipse taking into account the desired orientation of the curve (upward or downward).

def ellipseParameters(two_points,upward):
    # We find parameters a and b of the ellipse equation (x-c_x)^2/a^2+(y-c_y)^2/b^2=1
    # We take a = max_range for simplicity.
    A = two_points[0]
    B = two_points[1]
    #assume that A and B are 'max_range' apart
    max_range = sqrt((A[0]-B[0])**2 + (A[1]-B[1])**2)
    # center of ellipse
    # the calculation is quite nasty
    # if A[0] == B[0] or A[1] == B[1], shoot straight

    if upward:
        if A[0]<B[0] and A[1]>B[1]:
            C = [A[0]+max_range,A[1]]
            b = sqrt((B[1]-C[1])**2/(1-(B[0]-C[0])**2/max_range**2))
        if A[0]<B[0] and A[1]<B[1]:
            C = [B[0]-max_range,B[1]]
            b = sqrt((A[1]-C[1])**2/(1-(A[0]-C[0])**2/max_range**2))
        if A[0]>B[0] and A[1]>B[1]:
            C = [A[0]-max_range,A[1]]
            b = sqrt((B[1]-C[1])**2/(1-(B[0]-C[0])**2/max_range**2))
        if A[0]>B[0] and A[1]<B[1]:
            C = [B[0]+max_range,B[1]]
            b = sqrt((A[1]-C[1])**2/(1-(A[0]-C[0])**2/max_range**2))

    else:
        if A[0]<B[0] and A[1]>B[1]:
            C = [B[0]-max_range,B[1]]
            b = sqrt((A[1]-C[1])**2/(1-(A[0]-C[0])**2/max_range**2))    
        if A[0]<B[0] and A[1]<B[1]:
            C = [A[0]+max_range,A[1]]
            b = sqrt((B[1]-C[1])**2/(1-(B[0]-C[0])**2/max_range**2))
        if A[0]>B[0] and A[1]>B[1]:
            C = [B[0]+max_range,B[1]]
            b = sqrt((A[1]-C[1])**2/(1-(A[0]-C[0])**2/max_range**2))
        if A[0]>B[0] and A[1]<B[1]:
            C = [A[0]-max_range,A[1]]
            b = sqrt((B[1]-C[1])**2/(1-(B[0]-C[0])**2/max_range**2))

    return [max_range,b], C

Then we calculate the trajectory and the missile velocity direction based on the ellipse equation. numpy is used here as np.

def ellipseCurve(two_points,upward):
    # create a x vector
    x = np.linspace(two_points[0][0],two_points[1][0],100)
    # calculate ellipse's coefficients and center
    coefficients, center = ellipseParameters(two_points,upward)
    # y  coordinate and velocity direction calculations
    if not upward:
        # downward curve
        y = [center[1]+coefficients[1]/coefficients[0]*sqrt(coefficients[0]**2-(i-center[0])**2) for i in x]
        y_derivative = [-coefficients[1]/coefficients[0]*(i-center[0])/sqrt(coefficients[0]**2-(i-center[0])**2) for i in x]
    else:
        # upward curve
        y = [center[1]-coefficients[1]/coefficients[0]*sqrt(coefficients[0]**2-(i-center[0])**2) for i in x]
        y_derivative = [coefficients[1]/coefficients[0]*(i-center[0])/sqrt(coefficients[0]**2-(i-center[0])**2) for i in x]

    normalize_vel_x = [1/sqrt(i**2+1) for i in y_derivative]
    normalize_vel_y = [i/sqrt(i**2+1) for i in y_derivative]
    return [x,y],[normalize_vel_x,normalize_vel_y]

Testing the codes

## Tests
fig = plt.figure()
ax = plt.axes()
A = [1,4]
B = [8,5]
mid = [(A[0]+B[0])/2,(A[1]+B[1])/2]
two_points_first = [A,mid]
two_points_second= [mid,B]

plt.plot(A[0],A[1],marker='o',color = "red")
plt.plot(B[0],B[1],marker='o',color = "red")
plt.plot(mid[0],mid[1],marker='o',color = "red")
ax.annotate('Start',A)
ax.annotate('Des',B)
[x1,y1],_ = ellipseCurve(two_points_first,False)
[x2,y2],_  = ellipseCurve(two_points_second,True)
[x3,y3],[v3x,v3y] = ellipseCurve([A,B],False)
plt.plot(x1,y1)
plt.plot(x2,y2)
plt.plot(x3,y3)

## Plotting velocity 

reduce_x3 = x3[::15]
reduce_y3 = y3[::15]
reduce_v3x = v3x[::15]
reduce_v3y= v3y[::15]
for i in range(len(reduce_v3x)):
    ax.arrow(reduce_x3[i], reduce_y3[i], reduce_v3x[i], reduce_v3y[i], head_width=0.02, head_length=0.02, fc='lightblue', ec='black')

plt.show()

Results

Perhaps the orientation of the velocity needs to be changed when we swap Start with Destiation.

[ghost]

This is code I can copy, thanks so much for this :) But looking at it, does this mean the wonky missile will always follow same path? Can we introduce some random seed into it somehow?

[matastrb]

There are several options to modify the trajectory by adding randomness.

• The random seed can be calculated as you proposed before.

• I think because the curve is in general longer than the straight line, we can select a random speed scale for example 1.2<= velocity_scale<=1.4. The velocity in the code can be modified as

vel_x = velocity_scale*normalize_vel_x 

vel_y = velocity_scale*normalize_vel_y

• Assume that the plane is oriented at the angle alpha w.r.t the horizontal axis. In the above calculation the destination is at the distance max_range such that Start-Destination has the angle alpha w.r.t the x-axis. We can change the destination such that the angle between Start-Destination and the x-axis is alpha+beta where beta is randomly chosen between -5° and 5°. Also the distance could be a randomly scaled version of max_range.

• You can also select the curve as follows. Throw a random number between 0 and 4. If the outcome is 0 then no fancy curve is produced. If it is 1 then we output a simple curve with upward=True. If 2 then we output upward=False. If 3 then we output a composition curve (see the above Figure) with upward_1 = True and upward_2 = False. And if 4, then a composition curve with upward_1= False and upward_2 = True is produced.

[matastrb]

wonky curves using spline

Detailed implementation

# Generic natural cubic spline algorithm
# Taken from wikipedia  
def cubicSpline(datapoints):
    #the sought  after curves have the form
    # s_i(x) = a_i + b_i(x-x_i) + c_i(x-x_i)^2 + d_i(x-x_i)^3
    n = len(datapoints)
    a = [datapoints[i][1] for i in range(n)]
    b = [0]*(n-1)
    d = [0]*(n-1)
    h = [datapoints[i+1][0]-datapoints[i][0] for i in range(n-1)]
    alpha = [3/h[i]*(a[i+1]-a[i]) - 3/h[i-1]*(a[i]-a[i-1]) for i in range(1,n-1)]
    alpha.insert(0,0)
    mu = [0]*n
    z = [0]*n
    l = [0]*n
    for i in range(1,n-1):
        l[i] = 2*(datapoints[i+1][0]-datapoints[i-1][0])-h[i-1]*mu[i-1]
        mu[i] = h[i]/l[i]
        z[i] = (alpha[i]-h[i-1]*z[i-1])/l[i]
    c = [0]*n
    for i in range(n-2,-1,-1):
        c[i] = z[i]-mu[i]*c[i+1]
        b[i] = (a[i+1]-a[i])/h[i] - h[i]*(c[i+1]+2*c[i])/3
        d[i] = (c[i+1]-c[i])/(3*h[i])
    return a,b,c,d

Then we interpolate middle values

def naturalSplineCurve(datapoints):
    a,b,c,d = cubicSpline(datapoints)
    x = []
    y = []
    normalized_vel_x = []
    normalized_vel_y = []
    for i in range(len(datapoints)-1):
        # a better implemtation would assign for each interval [x[i],x[i+1]] a proportional
        # number of points, rather than a fixed number of points in this implementation.
        xi = np.linspace(datapoints[i][0],datapoints[i+1][0],30)
        yi = [a[i]+b[i]*(t-datapoints[i][0]) + c[i]*(t-datapoints[i][0])**2 + d[i]*(t-datapoints[i][0])**3 for t in xi]
        x.extend(xi)
        y.extend(yi)
        yi_derivative = [b[i] + 2*c[i]*(t-datapoints[i][0]) + 3*d[i]*(t-datapoints[i][0])**2 for t in xi]
        vel_xi = [1/sqrt(t**2+1) for t in yi_derivative]
        vel_yi = [t/sqrt(t**2+1) for t in yi_derivative]
        normalized_vel_x.extend(vel_xi)
        normalized_vel_y.extend(vel_yi)
    
    return x,y,normalized_vel_x,normalized_vel_y

Random midpoint selection

def fancySplineCurve(twopoints):
    A = twopoints[0]
    B = twopoints[1]
    # Assume that A[0]<B[0]
    # convex combination coefficient for a third point
    alpha = random.uniform(0,1)
    
    #upward or downward direction
    upward = random.uniform(0,1)>0.5
    #deviation
    beta = random.uniform(0,0.75)
    if upward:
        C = [A[0]*alpha + B[0]*(1-alpha),A[1]*alpha + B[1]*(1-alpha)+beta]
    else:
        C = [A[0]*alpha + B[0]*(1-alpha),A[1]*alpha + B[1]*(1-alpha)-beta]

    return naturalSplineCurve([A,C,B])