Challenge: Fit Charted Space into an 8 bit system

[robject]

If you're geeking out to the question, then you're in the right place.

Because I write code for fun, and because I do Traveller for fun, and because I think 8-bit computers are fun, I find myself writing Traveller code for a new-retro 8 bit platform. The hardware isn't important in this case.

Here is what's important:

(1) Data is loaded from an SD card. This means that there's actually plenty of room for Charted Space.
(2) The SD's file system is, I believe, FAT 32, so there is an upper limit on number of files per directory, and it's less than 2,000. It's safest to assume that the solution should only have a couple hundred files -- for example, 1 file per sector, 125 sectors.
(3) Assume we can't SEEK into a file. It might be doable, but I haven't been able to do it yet.
(4) Data is loaded into banked RAM. There is 512K available.
(5) Assume we can calculate trade codes on the fly.
(6) Assume we can z-encode the world name, if we really had to save a couple bytes per system.

***

Anyway back to the thing. I'm using Charted Space to run a Trader sim. Right now, that means the Marches plus Deneb, and that's it.

The current version is here: https://www.commanderx16.com/forum/index.php?/files/file/102-traveller-trader-wip/

But I think I can do better. I think I can access all of Charted Space in an elegant way. I think extraneous stuff can be eliminated, because the game itself won't be able to leverage all of that data.

The storage will be binary. The way we do this is to define the structure -- or structures -- that holds all relevant data. Then we fit it into files of an appropriate size -- whatever that is -- so that it's "easy" to find the data you want.

At a bare minimum, I think I'd need (most of) the world name, its UWP, its bases, un-calculatable trade codes, and Belt and GG presence.

typedef struct {
    char abbreviation[5];  // four chars + null
    unsigned char allegiance[8];
    unsigned int x;
    unsigned int y;
    unsigned char moreStuff[3];
    UWPline *restOfBank; // 430 of these in the rest of the bank
    // Then, 430 each in the next 2 banks.  Max = 1280 UWPs
} SectorHeader;

typedef struct {
   unsigned int zname[6];  // z-text can store ~15 chars

   int belt : 1; // belts present?
   int gg : 1;   // ggs present?
   int starport_and_bases_and_zone : 6;  // multiplexed list

   int siz: 4;   // 0-15
   int atm: 4;   // 0-15

   int hyd: 4;   // 0-15
   int pop: 4;   // 0-15

   int gov: 4;   // 0-15
   int law: 4;   // 0-15

   int tl: 5;    // 0-31
   int allegiance_index : 3;  // 8 allegiances listed in sector header

   int primary : 4; // multiplexed
   int companion : 4; // also multiplexed

   int companion_location : 2; // 0=binary, 1=near, 2=far
   int an : 1;   // ancients
   int cp : 1;   // capital
   int mr : 1;   // military
   int re : 1;   // reserve
   int rs : 1;   // research
   int sa : 1;   // satellite

} UWPline;       // 19 bytes

 

[whartung]

One sector per file, average of 640 systems per sector (50% populated), 18 bytes per is 11.5K per sector.

That means 512K Ram can hold 42ish sectors in RAM.

Store the the data in sector files, create an index of "System Name -> Sector ID" so you can find "Efate" easily.

Use an LRU cache to handle the sectors. Simply, if you need a sector, load it up and return a structure referencing the bank (and a pointer within that bank) to the sector. If the sector is already in RAM, don't load it. If you need room, toss out the oldest sector and load in the new one.

Since you don't have SEEK, you rely on the file names to do it for you. 2000 sectors is a LOT of sectors, pretty sure we don't reach that. That C code I posted can likely readily be adapted to this.

Obviously, if you're thrashing through all the sectors, it's going to take an big I/O hit. The best way to fix that is to just create indexes of things you want to search for, so as to not trash the Sector cache. But most operations should be fine, even if you have someone trading on the 4 corners of 4 sectors.

 

[robject]

Thanks Whartung. Actually it's not as bad as that -- there's only 2,000 SUBSECTORS, or 125 sectors. Quite doable.

Banked RAM is in 8K chunks. 11.5K average per sector is good -- fitting one sector into two banks (16K) gives room for a header and denser sectors as well.

 

[whartung]

Yea, having a sector consume two banks, it's probably worth "wasting space" and fitting 8 subsectors into one bank, and the other 8 in to the other. It's not that urgent, but you'll need to warp access to it all through bank aware code that knows how to demarcate things properly. Obviously, having subsectors A-H and I-P in their own banks is a trivial heuristic if you can make it work. Just may have issues when any really dense sectors (dunno if there are any). So, in that sense, it won't be universal.

But, 16K per sector is 32 sectors -- more than enough for a cache.

 

[coliver988]

does the language support bit-wise operators? You could stick several of the on/off fields into a single byte

int an : 1; // ancients int cp : 1; // capital int mr : 1; // military int re : 1; // reserve int rs : 1; // research int sa : 1; // satellite

 

[whartung]

That's what those are, those are C bitfields in the struct.

 

[robject]

you'll need to warp access to it all through bank aware code that knows how to demarcate things properly

Yessir! I actually implemented a Core War engine with the core crossing 10 banks (5 byte cell x 16000 cell memory core). I had to check for the memory boundary to switch banks. Not super fun, but the result was nice and tidy.

Commander X16 - Index page

Anyway.

With an index matrix in the header, I'll automagically know which bank each world is in. Since there's 600 ish worlds, if I use two byte indices, bitfields once again become my friend. I can spare 2K for a sector header.

typedef struct {
   int bank : 1;                // offset bank 
   int start_address: 13; // absolute byte offset within bank
} WorldOffset;

WorldOffset *index;      // overlays memory at index etc

Note that I just might be able to squeeze in a third bank. Maybe a fourth? Don't want to get greedy though. And why bother if I have everything I need?

Just may have issues when any really dense sectors (dunno if there are any). So, in that sense, it won't be universal.

You're right. And, I don't care, because it's just nonexistent in Charted Space. Gotta draw the line.

 

[robject]

As a comparison, the current map file contains the Marches and Deneb. It allocates 64 bytes per UWP, and empty hexes are included (a terrible waste of space!). I also designed a 48 byte version and 32 byte version, but didn't try them out.

All of them had conveniences built-in, for easy printing straight from the structure. After actually USING the 64b structure in code, I can safely say that those conveniences are not necessary.

All of them have these data:

• Location data -- column and row. I suspect that's not necessary.
• The sector abbreviation. In other words, we need to know what sector we're in. I can put that in headers though.
• The world name.
• Encoded UWP data.
• Bases.
• Zone
• Allegiance
• Belts + GGs
• Trade code index and Trade code flags
• Stellar data

Some also include nobility codes, the number of rockball worlds, world importance.

 

[robject]

So for the price of a 2,570 byte header on the first bank, a sector can take up two banks. If UWP structures are 18 bytes each, there's room for 767 UWPs, or slightly more than half. If I used three banks, then there's room for 1222 UWPs.

And that brings me to the next idea.

Strangely enough, losing the index frees up space for 142 UWPs.

Three banks, and toss the 2.5K map index. Instead, bring back those wasteful empty hexes, and fill all three banks with 1280 UWP records. It becomes trivially easy to map into the list -- it's representing a 32 x 40 grid of UWP records. Consider the benefits:

(1) Easy to compute location.
(2) Easy to compute bank.
(3) Empty hexes are useful for sinister purposes. The record is there... build a deep space calibration point.
(4) There's room for a header on all three banks, containing sector metadata.
(5) And the UWP record can have one extra byte (19 bytes).

 

[robject]

I can filter in a subset of base codes, then multiplex them in with the starport codes to span 5 bits, saving one bit. Then I multiplexed in Zone, saving another bit:

# ----------------------------------------------------------------------
#
#  Starport + Base Codes + Zone index
#
#  In case you ever want to compress these into 6 bits.
#
# ----------------------------------------------------------------------
my %spbz =
(
   'A'     => 0,  'AN'   => 1,  'AS'    => 2, 'ANS'   => 3,
   'AD'    => 4,                'AW'    => 5, 'ANW'   => 6,
   'B'     => 7,  'BN'   => 8,  'BS'    => 9, 'BNS'   => 10,
   'BD'    => 11,               'BW'    => 12, 'BNW'  => 13,
   'C'     => 14, 'CS'   => 15, 'D'     => 16, 'DS'   => 17,
   'E'     => 18, 'X'    => 19,

   # Amber zone
   'aA'     => 20, 'aAN'  => 21, 'aAS'  => 22, 'aANS'  => 23,
   'aAD'    => 24,               'aAW'  => 25, 'aANW'  => 26,
   'aB'     => 27, 'aBN'  => 28, 'aBS'  => 29, 'aBNS'  => 30,
   'aBD'    => 31,               'aBW'  => 32, 'aBNW'  => 33,
   'aC'     => 34, 'aCS'  => 35, 'aD'   => 36, 'aDS'   => 37,
   'aE'     => 38, 'aX'   => 39,

   # Red zone
   'rA'     => 40, 'rAN'  => 41, 'rAS'  => 42, 'rANS'  => 43,
   'rAD'    => 44,               'rAW'  => 45, 'rANW'  => 46,
   'rB'     => 47, 'rBN'  => 48, 'rBS'  => 49, 'rBNS'  => 50,
   'rBD'    => 51,               'rBW'  => 52, 'rBNW'  => 53,
   'rC'     => 54, 'rCS'  => 55, 'rD'   => 56, 'rDS'   => 57,
   'rE'     => 58, 'rX'   => 59,
);

 

[whartung]

Three banks, and toss the 2.5K map index.

That's 20 sectors, again more than enough for a cache. And that's the real goal here. We already know that any large scale scouring of the data that relies on the detailed sector data is going to crush the cache anyways (actually, if you know you're going to do that, ignore the LRU part and just keep reusing one slot, so only one sector is lost -- the rest of the cache is intact), but most of your operations are local. Ships just don't cross 20 sectors that quickly. Unless you're planning some large trading empire. But even then you could have 5 ships doing an awful "4 corners" route and not notice anything.

 

[robject]

Nope, you got it exactly right. In the corners, you might cross three (or four) sectors in three or four jumps. But usually, you're in one sector. That's a nice abstraction.

And, I think a sectors aren't too big to casually load into the cache when needed.

 

[robject]

Now that I have a working application that uses star data, I can think about the problem again, but without committing myself to a change of course.

I have 32 bytes of data for each hex.

My translator is simple, using TravellerMap to this abridged binary format. The format is derived strictly from the data available in TAB files -- no indexing or table lookups.

One file per sector. I truncate the sectors to 16K if necessary -- so far, it's not necessary, but I'll have to consider it later.

The file has a small header (32 bytes) that contains the name of the sector, its abbreviation, and the number of hexes. Not storing the sector offset but I should.

I just lay out populated hexes as you go. I don't store empty hexes. I also don't store indexes -- applications have to scan for the hex they want, or build up an in-memory index.

A program could statically load up a dozen sectors. Or it could swap sector data as needed. Doesn't matter.

Because we load specific sectors into specific banks, we don't need to store the sector ID in hex data.

Record data:

$00-01  Hex col, row
$02-11  System name, null terminated
$12     Starport letter
$13-15  Siz-Atm, Hyd-Pop, Gov-Law encoded into nybbles
$16     TL as a 1 byte integer
$17     Bitfields for B, GG, Zone, Naval and Scout bases (mapped)
$18-1a  Bitfields for 22 trade remarks
$1b-1c  Allegiance (2 chars)
$1d-1e  Primary star, binary encoded
$1f     Terminating null byte

 

[Dominator]

Since it is a fixed record size, does the last byte $1f need to be a null? Maybe reserved for future use?

 

[RogerD]

32 byte system in C++

class StarSystem {
    unsigned int col: 5; // 0-31
    unsigned int row: 6; // 0-39
    unsigned int starport: 3; // ABCDEX
    unsigned int size: 4; // Max 10, but this allows 16.
    unsigned int atmosphere: 4; // 0-15
    unsigned int hydrographics: 4; // 0-10
    unsigned int population: 4; // 0-10, allows up to 16
    unsigned int government: 4; // 0-15
    unsigned int law: 5; // 0-20
    unsigned int tech: 6; // 0-33
    unsigned int gasGiant: 1;
    unsigned int belts: 1;
    unsigned int naval: 1;
    unsigned int scout: 1;
    unsigned int zone: 2; // Green, Amber, Red
    unsigned int allegiance: 7; // could have more or less bits here as desired.
    unsigned int starType: 3; //OBAFGKM
    unsigned int starSize: 3; //Ia, Ib, II, III, IV, V, VI, D
    unsigned char name[20];
};

 

[RogerD]

Riffing on it a bit more, if you want to represent a single system, you can do it in 8 bytes, but really you only need 46 bits if you're willing to do some computation, allowing for 4 allegiances per sector. An entire sector would be easily represented in 32*40*8 bytes = 10240 bytes ignoring names. You could get this down to about 3/4 that amount (7680 bytes), fitting each system in 48 bits by encoding the values through multiplication. You could save space on consecutive empty hexes by run-length encoding the empty hexes, but the worst case (every other hex or more has a system) is still the same. Using variable record lengths for empty hexes you could save a minor amount of space since at most only 11 bits are needed to count off to the end of a sector.

Mostly though memory is cheap these days and we don't bother with any of this.

#include <iostream>
#include <tgmath.h>

class StarSystem {
    unsigned int starport: 3; // ABCDEX-  (7)
    unsigned int size: 4; // Max 10, but this allows 16. (11)
    unsigned int atmosphere: 4; // 0-15 (11)
    unsigned int hydrographics: 4; // 0-10 (11 - using flux)
    unsigned int population: 4; // 0-10, allows up to 16 (11 - using flux)
    unsigned int government: 4; // 0-15 (11 - using flux)
    unsigned int law: 4; // 0-20 (11 - using flux)
    unsigned int tech: 3; // 0-33 (6 - 1d6 + mods)
    unsigned int belts: 2; // 0-3 (4)
    unsigned int gasGiants: 3; //0-5 (6)
    unsigned int naval: 1; // boolean (2)
    unsigned int scout: 1; // boolean (2)
    unsigned int zone: 2; // Green, Amber, Red (3)
    unsigned int allegiance: 2; // could have more or less bits here as desired. (4)
    unsigned int starType: 3; //OBAFGKM (7)
    unsigned int starDecimal: 4; //0-9  (10)
    unsigned int starSize: 3; //Ia, Ib, II, III, IV, V, VI, D (8)
};

int main() {
    std::cout << sizeof(StarSystem) << std::endl;
    auto multipledOutNumber = 7.0 * 11 * 11 * 11 * 11 * 11 * 11 * 6 * 4 * 6 * 2 * 2 * 3 * 4 * 7 * 10 * 8;
    std::cout << multipledOutNumber << std::endl;
    std::cout << log2(multipledOutNumber) << std::endl;
    return 0;
}

running it:

8
4.80005e+13
45.4481

 

[whartung]

Mostly though memory is cheap these days and we don't bother with any of this.

He's doing this on an 8-bit machine with paged RAM.

 

[RogerD]

He's doing this on an 8-bit machine with paged RAM.

I know. The solution I gave should give minimum memory but certainly you would need to pay attention to efficiency since that CPU is probably slow also. Certinly a tradeoff here.

 

[aramis]

I know. The solution I gave should give minimum memory but certainly you would need to pay attention to efficiency since that CPU is probably slow also. Certinly a tradeoff here.

WDC65C02S at 8 MHz...