8-bit heaven: Traveller in BASIC

[robject]

WARNING: OSBOLETE-LY FABULOUS

You've been warned.

This week I created a sequential data file containing the Spinward Marches using BASIC. The file consists of single encoded strings, separated by newlines, with fixed-position data: the mainworld name comes last. Here's a brief form of how the file was created (a Perl script generated the BASIC code, which I then copy-pasted into the VICE emulator running Commodore 64 ROMs).

100 ns = 463
110 f$ = "0:stars,seq,write"
120 gosub 200 : rem create starchart
130 ns = 18
140 f$ = "0:ships,seq,write"
150 gosub 200 : rem create ship catalog
199 end
200 open 2,8,2, f$
210 for i = 1 to ns
220 read uwp$
230 print# 2, uwp$
240 next
250 close 2
299 return
1000 data GJFA 03 A788899-C NS Regina
[I]... and so on for 462 more worlds ...[/I]

The data is, in order: coordinates; P and GG counts; UWP; bases (two characters mandatory, where a space means 'no base'); and world name.

Here, coordinates are compressed, and represent the sector location, offset from a remote (0,0), where Stinj Tianz is (11,11), and hex position within that sector. Sector (16,15 = GxFx) is the Spinward Marches. Hex position is in base-40 (0-9, A-Z, @=37, #=38, $=39). This lets me calculate hex distances without having to deal with borders.

(Yes, I went way overboard with the coordinates. Sue me. If GDW had simply gone with 8x8 subsectors the problem would be more tractable).

Extraction of these strings is purely positional. The only tricky extraction is the world name, which is retrieved via:

na$ = left$( uwp$, len(uwp$)-22 )

Ship class data, meanwhile, is similarly encoded, using the QSP for starters, but also including some additional metrics.

2000 data A-BS11-9 111 Trader
2010 data S-AA22-B 202 Scout
... 16 more entries ...

The data here starts with the QSP (e.g. A-BS11), then the TL of the ship (9), then offset metrics for crew comfort, passenger demand, and fighting effectiveness, which is a WAG meant to approximate the ability to fight and take a punch.

 

[robject]

I don't think I'll have space problems. But there's the possibility of running out of memory.

Bottom Line

By destructively squeezing world data, I can get a sector into under 7.5k, instead of a rather fatty 13.7k. While 6k bytes means a 30k program instead of a 24k program, I'm not that thrilled about super-compressing my data to where I couldn't read it if I wanted to.

But read on.


Numbers

By the way, working on an 8-bit machine means memory is tight.

463 worlds, with an average length of 30 characters, is 13.7k. If your program storage is, for example, 38,911 bytes, then you've got 24.4k left for the program.


Squeezing the UWP

There's lots of wasted space here.

GJFA 03 A788899-C NS Regina

First, let's toss the extended location data and just retain the sector hex number in two characters' space.

JA 03 A788899-C NS Regina

Next, let's simplify down to two bases: N and S. Everything else either factors down to one of those, or is discarded. Next, we assume the same thing for the Starport code. Now we can overlay bases onto starport and represent them with one letter: A-E is 0 thru 4, a Scout base adds 5, a Naval base adds 10, and an 'X' port is 24.

JA 03 F788899-C Regina # F = Starport A(0) + Scout(5) + Naval(10) = 15

Then, we similarly reduce the GG and Asteroid Belt values into a single flag, indicating the presence of them: a space if neither are there, a B for a Belt Only, G for GG only, and "2" for both.

JA G F788899-C Regina

Finally, remove spaces and the dash. The result is dense, but that's okay.

JAGF788899CRegina

If world names are an average of 8 characters, then the average length is 19 characters for this UWP. 36% more space efficient. And in these slow 8-bit worlds, that also translates to I/O read speed.


Destructive Squeezing

If you really really needed more space, what could you throw out?

Let's consider the UWP. Do we really use it? Well, yes, some of it. How much? Well, the starport. And I like to know the type of atmosphere, and if we can refuel from the planet. Government type is meaningful "sugar". Law level? Maybe less important unless the program deals exclusively with exploring cities... which I don't plan on doing. And TL? Yeah, I sort of want to know that.

So: starport, atmosphere, hydrographics, government, and TL.

JAGF889CRegina

Average length is down to 16 characters. 46% shorter.

 

[Enoff]

Awesome!

 

[robject]

The Other Solution

Another solution is to store subsectors instead of sectors.

A subsector file would take just over 1k. It's light enough to load as needed.

And a 174k diskette could hold several sectors' worth.

No downside. I can even trim some of the extra data away; for example, the file name maps to its Charted Space offset. Thus without additional compression the file size already shrinks a bit (every bit helps).

spin.a

"spin" maps to sector (15,16) or whatever.
".a" maps to hexes 0101-0810.


Real Numbers

Using 2 characters for the hex position, combining base codes into one character, and combining asteroid + GG presence into one character, the average length is 24 characters, for a total space for the sector at 10,317 bytes.

But... I think encoding the hex position into anything other than 0101 - 3240 may be more trouble than it's worth.

 

[Adam Dray]

I have to ask: Why?

Is this just a "can I figure out how to squeeze a sector into a C64 BASIC program and run it on an emulator" experiment?



Have you considered packing the fields? I don't know how characters are represented on the C64, but they range 0-255, right, so at least 8 bits / 1 byte. The UWP is basically a hex number. Convert pairs of hex digits to a byte to cut the storage for the UWP by half (from 8 bytes to 4).

Similarly the "JA" location can be packed, since the range for each character is just 26 characters wide, right? (I can't remember what that particular data represents: is it just the sector coords? if so, it's considerably less than 26 each.) Really, if it's anything less than 16 possibilities per character, than the whole thing will fit in one 8-bit byte.

You can pack each character of the name in 4-bit nybbles if you're willing to limit the range to 26 capital letters and up to 6 special characters like an apostrophe or a dash. 4 bits gives you 32 possibilities. That will cut down storage for your system names by half.

Your bases ought to be represented by a single bit each. One byte gives you up to 8 booleans that way. (Or if you have a 4-bit nybble left over from some other piece of data, store four of them there.) I assume you're familiar with bitmasking techniques to set and check them? These work nicely in BASIC, too.

Consider that each numbered program line and each DATA token will eat up some memory. Consider packing as much as you can into each line, which is probably limited by the STRING length of 256 characters.

If I'm understanding you, then you're writing a temporary BASIC program to write out the data to a file in a packed format. This should let you write bytes nicely, but you might need to change to a binary format. I have never actually written a C64 BASIC program, but I've written more BASIC on other platforms than I care to admit. I might be way off base about some of the details here, though.

 

[robject]

Yeah, without moving to a binary format there are inefficiencies. The benefits to using character encodings is readability - so at least for now I can see what data is coming in without having to write a translator. And potentially bases don't have to be a full bit each... 3 bits for the starport, 1 bit for the GG, 1 bit for the AS, and 3 bits for all possible base combinations.

But, that crosses my threshold for effort.

So the real reason I was doing this is because I'm writing a BASIC program to do a little Traveller. Which is in itself a bit ridiculous. And this is the most memory-intensive part of the program. SO I don't mind squeezing it just a little bit, but not too much (for now).

The nice thing about using the two-character hex encoding is that I'm using a contiguous PETSCII block (0 thru U, i.e. 0x30 - 0x58), so it's easy to translate from one character to the hex number.

The next bottleneck *might* be the distance formula. If it's too slow, I'll have to write a short ML routine to take care of that. No matter what, there's going to be a loop of some kind, even if it's pruned back... One thing at a time though.

 

[whartung]

But what are you doing that makes you want to do this on a C-64? Even an emulated one?

I went full cycle on a retro kick a couple of years ago. I was all set up to build a simple 6502 machine from the board up. After thinking it through I ended up writing a simulator (and an assembler) instead, and then porting the Fig-FORTH to it.

I got through all that, and it all worked (fun times bringing a large assembly language program up when both your assembler AND your CPU are buggy).

And that was enough to scratch the itch and be done with it, and thankfully I don't have bunch of stuff around building a microcomputer cluttering up a box somewhere collecting dust.

Writing simulators is an interesting past time, for sure. Reading up on the detail that this one guy went through to make his Atari 800 simulator work -- just a crazy amount of effort. My simple one is just interpreting the machine language, his runs at the cycle level, following the clock.

But using them -- I dunno. Just never got that bug, beyond playing some old game for a few minutes.

So, just curious what you're doing on a C-64 simulator.

 

[Adam Dray]

Yeah, I'm curious, too!

This seems to me like learning how to flintknap.

 

[GypsyComet]

Eh, maybe. As the simplest of the interpreter languages it still sits, old and ancestral, at the base of what are now called the scripting languages. Some of us old code monkeys who dug into this stuff in the 70s and 80s but didn't pursue a programming career can still think in BASIC when all the other languages that followed would need significant refreshing.

No need to go back to the C64, though. The inefficiencies of BASIC that were so important to work around back then are literally lost in the round-off of machines just a decade later, never mind those available now.

 

[aramis]

Eh, maybe. As the simplest of the interpreter languages it still sits, old and ancestral, at the base of what are now called the scripting languages. Some of us old code monkeys who dug into this stuff in the 70s and 80s but didn't pursue a programming career can still think in BASIC when all the other languages that followed would need significant refreshing.

No need to go back to the C64, though. The inefficiencies of BASIC that were so important to work around back then are literally lost in the round-off of machines just a decade later, never mind those available now.

Another advantage of BASIC is that that which will run on a C64 will likely be compilable for modern machines on a variety of flavors of basic. Hell, I've got a basic compiler for my PalmOS and Android devices. And for my Mac.

QB64 will take all those old mumblesoft/microsoft and QBasic programs, and recompile them for modern Mac, modern windows, or Android... I just recompiled some QB code I wrote in 1993 to MacOS X 10.10... had to reverse 3 \ into /...

The new generation's equivalent to BASIC is likely to be (depending upon home machine) Python, Java/Android†, or Swift. All of which are non-trivial to covert basic to/from, but are close enough that a command reference allows the hobbyist programmer to make the switch from BASIC.

 

[Enoff]

Whatever your muse, thinking and writing programs in whatever environment inspires you, is all that really counts.

 

[Enoff]

Well just setup WinVice x64 on my win7 laptop and I have C64emu on my tablet.

 

[ShawnDriscoll]

Been running my old Traveller software on my ZX81 emulator on my Windows 10 machine. It counts as BASIC.

 

[aramis]

Been running my old Traveller software on my ZX81 emulator on my Windows 10 machine. It counts as BASIC.

Oy, yeah, another flavor of basic I've used. (I still have a hardware TS1000)

 

[ShawnDriscoll]

Oy, yeah, another flavor of basic I've used. (I still have a hardware TS1000)

I still have my ZX81 and 2068 somewhere. No TV for them. And I'm not a hardware hacker. So they are in great condition still. Just can't use them. Easier to fire up the emulator anyway.

 

[estar]

The Other Solution

Another solution is to store subsectors instead of sectors.

Or you could do what Galactic did and make storage file based. Still do the packing but just make a directory structure to keep everything organized. Consider load times and the limited view you have on-screen there is little advantage to cramming everything into memory.

 

[aramis]

Or you could do what Galactic did and make storage file based. Still do the packing but just make a directory structure to keep everything organized. Consider load times and the limited view you have on-screen there is little advantage to cramming everything into memory.

Depending upon view sizes, that can be quite a lot, actually, if one doesn't want artificial boundaries to be an issue. If your window is one subsector in size, you need to be able to load 4 subsectors at a time, as you can scroll diagonally to put both boundaries on-screen at once.