04 October 2020, 13:59 | #1 |
Registered User
Join Date: Oct 2017
Location: Sunderland, England
Posts: 2,702
|
Most efficient way of storing x/y values over frames
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. Last edited by mcgeezer; 04 October 2020 at 14:13. |
04 October 2020, 14:45 | #2 | |
Defendit numerus
Join Date: Mar 2017
Location: Crossing the Rubicon
Age: 54
Posts: 4,491
|
Quote:
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. |
|
04 October 2020, 14:53 | #3 |
Registered User
Join Date: Oct 2017
Location: Sunderland, England
Posts: 2,702
|
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.
|
04 October 2020, 15:00 | #4 | |
Defendit numerus
Join Date: Mar 2017
Location: Crossing the Rubicon
Age: 54
Posts: 4,491
|
Quote:
Even a linear interpolation can be good if n is low.. |
|
04 October 2020, 15:30 | #5 |
Registered User
Join Date: Dec 2019
Location: Newcastle
Posts: 67
|
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 |
04 October 2020, 15:44 | #6 |
Registered User
Join Date: Dec 2019
Location: Newcastle
Posts: 67
|
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 |
04 October 2020, 15:47 | #7 | ||
Registered User
Join Date: Oct 2017
Location: Sunderland, England
Posts: 2,702
|
Quote:
Quote:
Thanks everyone for replies, I'll implement this and let you know results. |
||
04 October 2020, 22:53 | #8 |
Registered User
Join Date: Oct 2017
Location: Sunderland, England
Posts: 2,702
|
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. |
05 October 2020, 01:02 | #9 |
Registered User
Join Date: Jun 2016
Location: europe
Posts: 1,063
|
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. |
05 October 2020, 09:13 | #10 |
Registered User
|
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. Last edited by BastyCDGS; 05 October 2020 at 12:15. Reason: Attached sample code |
05 October 2020, 14:19 | #11 | ||
Registered User
Join Date: Oct 2017
Location: Sunderland, England
Posts: 2,702
|
Quote:
Quote:
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. |
||
06 October 2020, 10:16 | #12 | |
Lemon. / Core Design
Join Date: Mar 2016
Location: Tier 5
Posts: 1,213
|
Quote:
Some kind of floor direction map would work easiest for you |
|
06 October 2020, 19:46 | #13 | |
Registered User
Join Date: Jan 2019
Location: Germany
Posts: 3,310
|
Quote:
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. |
|
07 October 2020, 02:18 | #14 |
Registered User
Join Date: May 2018
Location: Ireland
Posts: 691
|
Could the logic for the drone cars be extracted from MAME? Just throwing it out there
|
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests) | |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Questions re: Efficient blitting | earok | Coders. Blitz Basic | 11 | 01 January 2017 06:41 |
Most efficient way to cool a MC 68060 CPU? | eXeler0 | Retrogaming General Discussion | 12 | 01 May 2015 17:44 |
Amiga's most efficient and cleanest coders. | lordofchaos | Retrogaming General Discussion | 47 | 10 February 2013 16:33 |
Storing retro computers and consoles | Bloodwych | Retrogaming General Discussion | 1 | 06 April 2008 21:32 |
problem storing games on disc | mrbob2 | support.Hardware | 3 | 22 December 2007 12:33 |
|
|