Approximating smooth motion in discrete steps

approximate_spacing.py

# Problem:
#   Making an NES game, want smooth motion but don't want to store sub-pixel precision.
# Solution:
#   Approximate smooth motion in discrete steps.
#
#   Investigate a few methods, and compare them by smoothness.
#   Use standard deviation as a measure of smoothness.
#   (Lower deviation total is better.)
#
# Result:
# VAL    step_store        step_phi          step_near_phi     step_bit_reverse  
# TOTAL  48.539788         79.034628         77.678354         70.186199         

import math

PRECISION = 256 # bits of precision for velocity
STEPS = 256 * 128 # number of steps to evaluate for each case

# Method 1: store subpixel position (for comparison)
def step_store(v):
    s = []
    sub = 0
    for i in range(STEPS):
        sub += v
        if (sub > PRECISION):
            s.append(1)
            sub -= PRECISION
        else:
            s.append(0)
    return s

# Method 2: phi increment
def step_phi(v):
    s = []
    sub = 0
    for i in range(STEPS):
        sub = (sub + 159) % PRECISION
        s.append(1 if (v > sub) else 0)
    return s

# Method 3: near-phi increment (157 is prime, is this any better?)
def step_near_phi(v):
    s = []
    sub = 0
    for i in range(STEPS):
        sub = (sub + 157) % PRECISION
        s.append(1 if (v > sub) else 0)
    return s

# Method 4: bit reverse (good for powers of two, some irregularity elsewhere)
def bit_reverse(v):
    x = 0
    for i in range(8):
        x = (x << 1) | (v & 1)
        v >>= 1
    return x
def step_bit_reverse(v):
    s = []
    sub = 0
    for i in range(STEPS):
        sub = (sub + 1) % PRECISION
        s.append(1 if (v > bit_reverse(sub)) else 0)
    return s

# evaluate a single run
def steps_evaluate(v,f):
    s = f(v)
    # count distance between 1s
    d = []
    l = 0
    first = True
    for b in s:
        l += 1
        if (b == 1):
            if first:
                first = False
            else:
                d.append(l)
                l = 0
    # compute standard deviation from expected mean
    mean = PRECISION / v
    sd = math.sqrt(sum([(x-mean)**2 for x in d])/len(d))
    return sd / mean # scale relative to mean for comparison

TRIALS = [ step_store, step_phi, step_near_phi, step_bit_reverse ]

totals = [ 0 ] * len(TRIALS)
print("VAL    " + "".join(["%-18s" % (f.__name__) for f in TRIALS]))
for i in range(1,PRECISION):
     s = "%-6d " % (i)
     for j in range(len(TRIALS)):
         f = TRIALS[j]
         d = steps_evaluate(i,f)
         s += "%-18f" % (d)
         totals[j] += d
     print(s)
print("TOTAL  " + "".join(["%-18f" % (t) for t in totals]))