Most efficient way of storing x/y values over frames

[mcgeezer]

Hi all,

I'm trying to work out the best way I can store a large number of x/y positions over a fairly large number of frames.

The application is the drone cars that go around the circuit in Super Sprint, I need to record their X/Y positions but if a car takes 30 seconds to do a lap at 60 FPS then it takes a fair amount of ram.

X range is 0-511 and Y rand is 0-384.

30 * 60 = 1800 * 2 words = 7200 bytes, for three laps that then goes to 21600 - far too big.

Does anyone have some decent algorithms they could share to do this thing and store the data more efficiently?

Cheers,
Geezer

One solution I have at the moment is this.

Have two starting position word values.
Then have a series of bytes.

Bits 6 & 7 control the x any y move direction.
Bits 0-2 control the value to add/subtract (based on bit 6) from the current x position
Bits 3-5 control the value to add/subtract (based on bit 7) from the current y position.

This gets me to 5.4kb of uncompressed data which is decent.

[ross]

Originally Posted by mcgeezer

Bits 6 & 7 control the x any y move direction.
Bits 0-2 control the value to add/subtract (based on bit 6) from the current x position
Bits 3-5 control the value to add/subtract (based on bit 7) from the current y position.

Hi Graeme, why you need control bits?
If you have signed values for direction you can simply use 0 for no movement.
So you could use more bits for delta or less bit for movement (like 6 or 4, instead of 8).

And you can use bitfield instructions to extract values.

[mcgeezer]

Originally Posted by ross

Hi Graeme, why you need control bits?
If you have signed values for direction you can simply use 0 for no movement.
So you could use more bits for delta or less bit for movement (like 6 or 4, instead of 8).

And you can use bitfield instructions to extract values.

Ahh good shout Ross, i need to be able move the cars in at least 8 pixels in any direction per frame so i can remove the control bits for sure, but i don’t think i gain any space efficiency.

[ross]

Originally Posted by mcgeezer

Ahh good shout Ross, i need to be able move the cars in at least 8 pixels in any direction per frame so i can remove the control bits for sure, but i don’t think i gain any space efficiency.

And if you store only changes every n frames and then real-time interpolate?
Even a linear interpolation can be good if n is low..

[DMWCashy]

You could store using Delta of Deltas, so instead of storing the difference between frames, you store the difference between the difference of frames and use some sort of bit encoding to store no changes/variant size.

This would result in a much shorter amount of memory use, as it would only use memory when the vector changes, but is also indeterministic to what the final size would be, depending on the amount of vector changes in the drones position.

Is this for a replay function ?

Looking forward to this game

[DMWCashy]

For example, take the following sequence of say x values:-

0 8 16 24 32 40 48 56 60

This could be stored as

8 134 68

8 = Initial delta of delta

134 = 6 repeats - top bit set to indicate RLE

68 = -4 difference in delta of delta

[mcgeezer]

Originally Posted by ross

And if you store only changes every n frames and then real-time interpolate?
Even a linear interpolation can be good if n is low..

Yes, I think I'll store just every other frame and interpolate the position for the missing frame. For duplicate frames when the car doesn't move I could just set the value to 00 and then have the following byte be the number of frames to wait.

Originally Posted by DMWCashy

You could store using Delta of Deltas, so instead of storing the difference between frames, you store the difference between the difference of frames and use some sort of bit encoding to store no changes/variant size.

This would result in a much shorter amount of memory use, as it would only use memory when the vector changes, but is also indeterministic to what the final size would be, depending on the amount of vector changes in the drones position.

Is this for a replay function ?

Looking forward to this game

Yeah, this is essentially what I'm doing... probably down to about 1.5Kb now for each drone car running three laps... which is nice and efficient.

Thanks everyone for replies, I'll implement this and let you know results.

[mcgeezer]

ugghhh...

So I tried using x/y deltas... the only problem is I can't modify the speed at which the cars go around the circuit which will break the game difficulty.

It looks like I'll have to store the x/y coordinates, wheel angle of the car and number of frames. This way I can easily scale the array at set speeds to position the car.

Feels like I'm learning the hard way coding the game.

[a/b]

Did you consider using (b)splines, so only use a handful of control points and then generate all the in-between coordinates? Turning could be controlled through deltas between previous and current position. Variable speed could be emulated by doing smaller/larger increments of the parameter.
Not sure if that covers all your bases, it's something you generally decide early on and then build other systems on top of that, so maybe it's too late for this kind of approach.

[BastyCDGS]

Another possibility is to store only the player key presses (one byte per frame with zero byte meaning no key input) instead of the coordinates and RLE compression (very fast).

If there is random enemy movement involved, also store the seed at the beginning and reuse it during replay.

EDIT: Attached m68k Asm sample code which I did back in the day with on-the-fly RLE compression.

Lumps.s: Compresses input from RAW: console to RAM:
LumpsPlayback.s: Decompresses input from RAM: to RAW: console, duplicating keypresses.

[mcgeezer]

Originally Posted by a/b

Did you consider using (b)splines, so only use a handful of control points and then generate all the in-between coordinates? Turning could be controlled through deltas between previous and current position. Variable speed could be emulated by doing smaller/larger increments of the parameter.
Not sure if that covers all your bases, it's something you generally decide early on and then build other systems on top of that, so maybe it's too late for this kind of approach.

No, it's pretty early on at this point so I have a blank page to work at.

Originally Posted by BastyCDGS

Another possibility is to store only the player key presses (one byte per frame with zero byte meaning no key input) instead of the coordinates and RLE compression (very fast).

If there is random enemy movement involved, also store the seed at the beginning and reuse it during replay.

EDIT: Attached m68k Asm sample code which I did back in the day with on-the-fly RLE compression.

Lumps.s: Compresses input from RAW: console to RAM:
LumpsPlayback.s: Decompresses input from RAM: to RAW: console, duplicating keypresses.

Thanks for the suggestions guys, I'll look into them.

The drone cars need to interact with the environment, they can be pushed off course by other cars, different levels will assign different attributes to the cars (max speed, throttle and traction).

I think it might have been Dan that mentioned doing a kind of circuit guide for the cars, so if they go off track they can be guided back on... I think I'll try this approach next.

It's certainly an interesting one to figure out properly.

[DanScott]

Originally Posted by mcgeezer

I think it might have been Dan that mentioned doing a kind of circuit guide for the cars, so if they go off track they can be guided back on... I think I'll try this approach next.

It's certainly an interesting one to figure out properly.

I was wondering why on earth you'd want to store fixed paths for the drone cars... with them being able to leave the path via collisions etc, it's definitely not a good way to do it.

Some kind of floor direction map would work easiest for you

[Thomas Richter]

Originally Posted by mcgeezer

Does anyone have some decent algorithms they could share to do this thing and store the data more efficiently?

You already gave one, delta-compression - all provided the deltas are within the range available by the encoder. But, one way or another, it all depends on the statistics of the data, and on how much complexity you can affort to uncompress the data.


Another extension is "variable length coding", that is, code those deltas which appear often with less bits, those that appear less often with more bits. A simple code for that (often close enough to ideal) is to spend one bit for the sign bit, and then a unary code for the deltas, i.e. delta = 0 => 0, delta = 1 => 10, delta = 2 => 110, delta = 3 => 1110


A more refined method is to split the delta value into a unary and a binary part, i.e. code delta/2^x with the unary code above, code the least significant bits of delta (i.e. delta mod 2^x) directly (i.e. just inject into the stream).


Of course this requires bitpacking and bit-unpacking, and whether you can pay for that I do not know.


Note that the above code is simple, though not ideal. Such codes are more complex.

[lmimmfn]

Could the logic for the drone cars be extracted from MAME? Just throwing it out there