Memory-saving tricks in software of the 80's

  • 5 Replies
  • 123 Views

0 Members and 1 Guest are viewing this topic.

Offline marcm200

  • *
  • Fractal Freak
  • **
  • Posts: 741
« on: May 27, 2020, 07:28:28 AM »
I recently learned about some tricks, software developers employed for the Amstrad game Elite in the early 80's when memory was a concern back then.
(from a german podcast: https://www.stayforever.de/2014/09/folge-37-elite/

Does anyone know of further such brilliant ideas from other software?

Elite is one of my favourite games from the 80s. You're a starship pilot, flying the universe, trading goods and shooting enemies to climb the rating ladder of traders.

Trick 1
The developers use a system of 2-letter syllables that - in any combination - sound like alien planetary names. With that method they could just store a short bit pattern for every planet instead of a longer character string (La-ve, Le-eh-ti).

Trick 2
For the galaxies, the planets and where which goods are tradable and to what price, they use a (system of) equations, where, when a different seed is entered, a different bit string results that is interpreted as the desired planet (I haven't figured that part out yet). Sounds almost like a compression method to me.

It would be interesting to use the classic quadratic Mandelbrot equation to form such a planetary system - with different seeds and different max it resulting in different alien systems :)



Linkback: https://fractalforums.org/off-topic/29/memory-saving-tricks-in-software-of-the-80s/3526/

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 2165
« Reply #1 on: May 27, 2020, 07:59:40 AM »
Reminds me of the SMTP greeting: HELO

Offline hobold

  • *
  • Fractal Furball
  • ***
  • Posts: 298
« Reply #2 on: May 27, 2020, 11:19:46 AM »
Elite was procedurally generated. It was not the first game to do this. Pitfall was procedural, M.U.L.E.'s maps were procedural, too, for example. It was a common technique to work around the limited amounts of mass storage and main memory. It wasn't called "procedural" back then. And it isn't called "procedural" today, because today that word implies the (frequent) generation of fresh game content. Back then games re-generated a fixed set of game content, pre-selected by the game makers.

Initially, the procedural generators were flawed. They would sometimes create unplayable or otherwise buggy game content. That's why the game designers restricted their games to a small, hand picked subset of possible creations.

Later, in the 16 bit home computer era, procedural generators could be more sophisticated. They started to generate content with guarantees of playability and variety. I remember "Seven Cities of Gold" as my first encounter with a game that could create an entire new game world from scratch after you had played through the initial campaign (which was a manually created map of South America, if I remember correctly).

But most of the experimentation and exploration of possibilities was done outside the commercial video game industry. Rogue, Hack (and particularly Nethack) were all about procedurally generated dungeons as their core game mechanic. Some really weird experimentation continues until this day - I believe it was here on FractalForums that I was made aware of "Hyperrogue", which is set on the hyperbolic plane.


Data compression techniques are being employed, too. One of Sony's God of War games did some really heroic feats internally to let the Playstation shine in its brightest light. For example, it encoded a few extra bits of information by making intentional choices about the order in which they stored the three vertices of each surface facet. It is no coincidence that the end credits roll several hundred names. The Cell Processor was powerful, but a lot of ingenuity was necessary to overcome its limitations.

Offline marcm200

  • *
  • Fractal Freak
  • **
  • Posts: 741
« Reply #3 on: May 27, 2020, 07:36:03 PM »
Very interesting, thanks for the explanation. I wasn't aware that this method was so widespread and had never heard of it before.

But back in the 80s, my programming skills were at the beginner's state. I remember being very proud having managed to stop a text adventure from loading from datasette and look at the BASIC code lines to see which commands to enter where actually understood by the parser (I think the game's name was Thor trilogy with a guy named Llywenhuf or so), but it didn't help solvin the task :)

Offline marcm200

  • *
  • Fractal Freak
  • **
  • Posts: 741
« Reply #4 on: May 28, 2020, 06:52:07 PM »
A little computer experiment I'm conducting right now.

The "hello world" polynomial:

\[
f(x) = x^6+3x^5+394x^4+416x^3+234x^2+293x+258
 \]

\( f(466) = 10324913503655364 \) which can be interpreted to represent "hello world" by considering the binary bit string of the function value, split into groups of 5 bits taken as an entry to an alphabet. In a sense this is a procedural method, as there is another text hidden in the formula.

\( f(1262) = 4050368722319510032 \) which reads "cykl_tiffanyy" containing the name of an 80's female singer.
                       
The latter was put there by rearranging the alphabet as the two words are disjoint, so after constructing the polynomial with "hello world" I could freely move the alphabet at some points around to fit the desired letter shape without changing hello world's function value.

My goal here is to construct a polynomial for galac's minuscule Mandelbrot code https://fractalforums.org/programming/11/small-mandelbrot-set-in-c/2658/msg13599#msg13599 which only has 165 characters. I hope to get a function with not too many coefficients. For that I have to find an easy (or best not-to)-install BigInt library or try to write a maxima script to get the desired precision.

Offline marcm200

  • *
  • Fractal Freak
  • **
  • Posts: 741
« Reply #5 on: June 02, 2020, 09:28:40 AM »
"Unsuccessful"

My attempt to compress the minuscule Mset C++ code further with polynomials did not work out. I can get a degree 60 (or other values)-polynomial, but the coefficients need ~440 characters. Even when compressing the base-10 digits to 4-bits, it is larger. It would only be a real compression if there were dozens of further useful programs in the function, but that hasn't been checked.

f(573581) is the Mset code.

Code: [Select]
f(x)=1x^60+494909x^58+259608x^57+425095x^56+40841x^55+178391x^54+191621x^53+283425x^52+461670x^51+534905x^50+151072x^49+183731x^48+322972x^47+145831x^46+398309x^45+338400x^44+147633x^43+309140x^42+161885x^41+526228x^40+547671x^39+437832x^38+470014x^37+154908x^36+25101x^35+46522x^34+133400x^33+77489x^32+565023x^31+94601x^30+565928x^29+89285x^28+214388x^27+363429x^26+453734x^25+368200x^24+507710x^23+292355x^22+460582x^21+445855x^20+145903x^19+242247x^18+332658x^17+366709x^16+443238x^15+464339x^14+375398x^13+326013x^12+342471x^11+47923x^10+229840x^9+132373x^8+353308x^7+358992x^6+70375x^5+161701x^4+90693x^3+104430x^2+310541x+511163

Maxima code to produce the polynomial from the input (too large to display) number which reoresents the C++ characters in 7-bit ASCII appended to form a long bit string.
Code: [Select]
N:2^1147+2^1146+2^1144+2^1143+2^1141+2^1140+2^1139+2^1134+2^1133+2^1132+2^1130+2^1127+2^1126+2^1125+2^1123+2^1122+2^1121+2^1118+2^1116+2^1111+2^1109+2^1106+2^1105+2^1104+2^1103+2^1102+2^1100+2^1099+2^1098+2^1097+2^1094+2^1093+2^1091+2^1090+2^1088+2^1087+2^1084+2^1083+2^1081+2^1080+2^1079+2^1078+2^1077+2^1076+2^1071+2^1070+2^1069+2^1068+2^1066+2^1062+2^1056+2^1055+2^1054+2^1053+2^1048+2^1046+2^1045+2^1042+2^1041+2^1040+2^1039+2^1036+2^1034+2^1032+2^1031+2^1028+2^1027+2^1026+2^1024+2^1020+2^1018+2^1017+2^1014+2^1013+2^1008+2^1006+2^1004+2^1003+2^1000+2^999+2^995+2^992+2^991+2^990+2^989+2^987+2^985+2^984+2^980+2^978+2^976+2^975+2^972+2^971+2^969+2^967+2^966+2^964+2^963+2^962+2^960+2^959+2^958+2^957+2^954+2^953+2^951+2^950+2^948+2^947+2^946+2^945+2^944+2^943+2^942+2^939+2^936+2^934+2^929+2^928+2^927+2^925+2^924+2^923+2^922+2^918+2^915+2^914+2^913+2^912+2^911+2^908+2^906+2^905+2^903+2^901+2^900+2^896+2^894+2^893+2^892+2^890+2^889+2^888+2^887+2^883+2^880+2^878+2^877+2^875+2^873+2^872+2^871+2^870+2^868+2^866+2^864+2^863+2^862+2^859+2^858+2^854+2^852+2^850+2^847+2^846+2^845+2^844+2^843+2^841+2^840+2^839+2^838+2^835+2^834+2^832+2^831+2^829+2^828+2^827+2^826+2^825+2^824+2^823+2^820+2^817+2^815+2^811+2^810+2^805+2^803+2^802+2^801+2^800+2^798+2^796+2^794+2^793+2^791+2^789+2^788+2^785+2^784+2^782+2^781+2^780+2^778+2^777+2^776+2^775+2^770+2^768+2^767+2^766+2^765+2^761+2^760+2^756+2^754+2^753+2^752+2^750+2^749+2^748+2^747+2^742+2^740+2^738+2^736+2^735+2^733+2^732+2^731+2^730+2^728+2^726+2^724+2^723+2^722+2^719+2^718+2^714+2^712+2^710+2^707+2^706+2^705+2^704+2^703+2^701+2^700+2^699+2^698+2^697+2^696+2^691+2^690+2^689+2^688+2^686+2^685+2^684+2^683+2^682+2^679+2^677+2^676+2^675+2^674+2^672+2^671+2^670+2^669+2^667+2^663+2^662+2^661+2^660+2^658+2^657+2^656+2^654+2^652+2^651+2^649+2^648+2^647+2^646+2^644+2^642+2^641+2^635+2^634+2^633+2^631+2^630+2^629+2^628+2^627+2^625+2^624+2^623+2^622+2^621+2^619+2^615+2^614+2^612+2^609+2^608+2^607+2^605+2^604+2^601+2^600+2^597+2^595+2^593+2^591+2^586+2^584+2^582+2^581+2^579+2^577+2^575+2^574+2^573+2^572+2^570+2^568+2^567+2^565+2^564+2^563+2^562+2^558+2^557+2^556+2^553+2^551+2^550+2^549+2^544+2^542+2^539+2^538+2^537+2^536+2^535+2^533+2^532+2^531+2^530+2^529+2^527+2^523+2^522+2^521+2^520+2^518+2^517+2^516+2^515+2^514+2^509+2^507+2^506+2^503+2^502+2^501+2^500+2^495+2^494+2^493+2^492+2^490+2^489+2^488+2^487+2^486+2^481+2^479+2^477+2^475+2^474+2^473+2^472+2^467+2^465+2^464+2^462+2^461+2^460+2^459+2^458+2^455+2^453+2^451+2^449+2^447+2^446+2^445+2^444+2^441+2^439+2^437+2^435+2^434+2^433+2^432+2^427+2^425+2^423+2^422+2^419+2^418+2^417+2^416+2^413+2^411+2^410+2^409+2^408+2^406+2^404+2^403+2^400+2^397+2^395+2^393+2^391+2^390+2^389+2^387+2^383+2^381+2^379+2^377+2^376+2^375+2^374+2^371+2^369+2^367+2^365+2^364+2^363+2^362+2^358+2^355+2^354+2^353+2^351+2^350+2^349+2^348+2^347+2^346+2^341+2^339+2^337+2^335+2^334+2^333+2^332+2^327+2^325+2^323+2^322+2^321+2^320+2^319+2^318+2^315+2^313+2^311+2^309+2^307+2^306+2^305+2^304+2^301+2^299+2^298+2^297+2^296+2^295+2^292+2^291+2^289+2^285+2^284+2^283+2^282+2^281+2^280+2^279+2^278+2^276+2^274+2^273+2^271+2^270+2^269+2^268+2^266+2^264+2^263+2^262+2^259+2^257+2^256+2^255+2^252+2^250+2^249+2^248+2^246+2^243+2^242+2^236+2^235+2^234+2^232+2^231+2^230+2^229+2^228+2^227+2^226+2^224+2^223+2^222+2^221+2^216+2^215+2^214+2^212+2^210+2^209+2^208+2^207+2^205+2^202+2^201+2^197+2^196+2^195+2^194+2^192+2^188+2^187+2^182+2^181+2^180+2^179+2^176+2^173+2^171+2^167+2^166+2^164+2^162+2^161+2^159+2^158+2^157+2^156+2^155+2^152+2^151+2^150+2^147+2^145+2^144+2^143+2^138+2^137+2^136+2^135+2^134+2^133+2^131+2^130+2^128+2^124+2^123+2^121+2^120+2^117+2^116+2^115+2^113+2^110+2^109+2^107+2^103+2^102+2^99+2^96+2^94+2^91+2^89+2^88+2^87+2^85+2^84+2^83+2^82+2^81+2^80+2^79+2^77+2^76+2^75+2^74+2^69+2^68+2^67+2^65+2^63+2^62+2^61+2^60+2^58+2^55+2^54+2^53+2^50+2^49+2^47+2^45+2^40+2^36+2^33+2^29+2^26+2^24+2^21+2^19+2^18+2^17+2^15+2^14+2^13+2^12+2^11+2^10+2^9+2^7+2^6+2^5+2^4+2^3+2^2+2^0;

coeff:[];
maxexp:60;
seed:truncate(N^(1/maxexp));
Nk:N;
eq:0;

for kinv:0 step 1 unless kinv>maxexp do (
k:maxexp-kinv,
c:truncate(Nk/(seed^k)),
Nk:Nk-c*seed^k,
coeff:append(coeff,[[k,c]]),
eq:eq+c*x^k
)$
display(coeff);
display(eq);
N-subst(x=seed,eq);
display(f(seed)=C_code);



clip
FragM does not use video card memory

Started by SCORPION on Fragmentarium

1 Replies
93 Views
Last post October 27, 2019, 03:01:20 AM
by 3DickUlus
sad
Thread Error Count: Not Enough Memory

Started by eat vyvanse on Fractal Programs Discussion, Help, & Support

1 Replies
316 Views
Last post March 01, 2019, 02:54:00 AM
by eat vyvanse
question
Software Help

Started by Sunshower on Fractal Programs Discussion, Help, & Support

2 Replies
159 Views
Last post July 27, 2019, 07:40:58 AM
by mclarekin
question
What is the best 3D Fractal software for a VFX pipeline?

Started by FractalHQ on Fractal Programs Discussion, Help, & Support

1 Replies
352 Views
Last post June 23, 2019, 07:45:34 PM
by 3DickUlus
clip
Sharing pm-files Jux software.

Started by Caleidoscope on Xenodream

21 Replies
239 Views
Last post June 18, 2020, 02:59:43 PM
by Caleidoscope