You could use sum of 4 to 5 sine waves (each with different amplitude, wavelength and phase difference). All 3 of those parameters could be random.
The resulting curve would be very smooth (since it is primarily sinusoidal) yet it'll look random (it's time period would be LCM of all 4 to 5 random wavelengths which is a huge number).
So the curve won't repeat for a long time, yet it will not be hard on memory. Concerning computational complexity, you can always tune it by changing number of sine terms with FPS.
It should look like this.
It's really easy to implement too. (even I could generate above image.. haha)
Hope this helps. Maths rocks. :D
(The basic idea here is a finite Fourier series which I think should be ideal for your use case)
Edit:
You can create each term like this and assign random values to all terms.
public class SineTerm {
private float amplitude;
private float waveLength;
private float phaseDifference;
public SineTerm(float amplitude, float waveLength, float phaseDifference) {
this.amplitude = amplitude;
this.waveLength = waveLength;
this.phaseDifference = phaseDifference;
}
public float evaluate(float x) {
return amplitude * (float) Math.sin(2 * Math.PI * x / waveLength + phaseDifference);
}
}
Now create an array of SineTerm
s and add all values returned by evaluate(x)
(use one coordinate of sprite as input). Use the output as other coordinate of sprite. You should be good to go.
The real trick would be in tuning those random numbers.
Good luck.