28th December 2021 – Telengard – some more.

I’m visiting the baltic sea again – and that means I get to do some stuff that I don’t do at home. In this case my laptop (without any vectrex connection), Vide and I are trying to revisit Telengard.

In case you don’t know Telengard some links to get you up to date:

Homepage of Dan (creator of Telengard, sadly passed away 2014): “https://www.aquest.com/telen.htm“

Commented source of the Atari version, done by (another) Dan: “https://atarihq.com/danb/Telengard.shtml“

A modern take on things – (another “Dan”): two different Telengard versions: “https://github.com/shaefer“

Over the years in development, a pepped up C64 version: “https://csdb.dk/release/” (See also: “sys64738“)

Also a windows version was done by Travis Baldree: “http://buildingworlds.com/telengard/“
(he also did more modern games, like FATE and Torchlight)

Anyways – you can see I am not alone with my Telengard thoughts.

I have written in one of my last blog entries, that I started on a Vectrex version and that along the way I lost the already converted BASIC to “C” source code. Yea, I haven’t redone that yet. I decided that I wanted to start at another end of the road.

Last time took a break at the time I started to convert the dungeon generation part. Telengard has EXTENSIVE dungeons. Each level features a 200 x 200 map and there are 50 levels to the game. This makes for the small amount of two MILLION rooms.

The map is generated using procedural generation. The “bad” thing about those generation, it is done with floating point arithmetics.

Following is taken von Dan’s PDF (x,y,z being the coordinate of one room):
(Returned is a 16 bit integer word. The “low” byte containg information about walls and doors of a room. The “hi” byte containing the rooms “interior”.)

1103 XO=1.6915:YO=1.4278:ZO=1.2462:W0=4694
...
/***************************************************************
/* Generate map
/***************************************************************
10010 Q=X*XO+Y*YO+Z*ZO+X*YO+Y*ZO+Z*XO:

/* HI = Q & 0xFF
HI=USR(LG,ONE,Q,TF-ONE):
Q=X*Y*ZO+Y*Z*XO+Z*X*YO

/* IF Q & 0x03 <> 0 then goto 10030
10020 IF USR(LG,ONE,Q,THREE)<>ZERO THEN 10030

/* Q = Q << 2
10022 Q=Q/FOUR:

/* Q = Q & 0x0F
Q=USR(LG,ONE,Q,15):

/* If Q > 9 then Q = Q - 9
IF Q>NIN THEN Q=Q-NIN

/* HI = HI + (Q >>8)
10024 HI=HI+Q*TF

/* If at left or right edge of maze turn on left wall
10030 IF X=ONE OR X=201 THEN HI=USR(LG,TWO,HI,12)

/* if at top of bottom of maze turn on top wall
10035 IF Y=ONE OR Y=201 THEN HI=USR(LG,TWO,HI,THREE)
10040 HI=INT(HI):RETURN

After some research, the “C” translation is pretty straight forward:

const float XO = 1.6915;
const float YO = 1.4278;
const float ZO = 1.2462;
const unsigned long W0 = 4694;

#define uint_16 unsigned long int
uint_16 getMapPos(unsigned char x, unsigned char y, unsigned char z)
{
	// room walls
	// Atari Dan Boris
	float q = x*XO + y*YO + z*ZO + x*YO + y*ZO + z*XO;
	unsigned char lo = (unsigned char) (((unsigned char) q) & 0xff);
	
	// special items
	q = x*y*ZO + y*z*XO + z*x*YO;
	unsigned char hi = (unsigned char) q;
	if ((hi & 3) == 0)
	{
		hi = (hi>>2) &0xf;
		if (hi > 9) hi = hi - 9;
	}

        // edges
	if ((x == 1) || (x == 201)) h = h | 12;
	if ((y == 1) || (y == 201)) h = h | 3;
	return ((uint_16)lo) + (((uint_16)hi) << 8);
}

The VECTREX gist of the problem is, that the machine does not support “float”. But I tried it anyway – I used the gcc “C” compiler that comes with Vide and tried compiling it.
… and oh wonder – gcc has actually built in a “soft-fp” library. I can’t remember that I ever built it, and where it came from – but gcc6809 supports float!

Nearly.

Somehow the function “__fixunssfsi(float f)” did not make it into the distribution (convert float to signed integer).
WHAT THE F***!

I looked at the sources of soft-fp. But that is typicall distribution crap. It uses so many macros and meta macros and “#ifdef” that no sane person should try to get to grips with it. IMHO such distributions are plane stupid. But I am getting carried away.

I did not build that missing function from those sources. I read up on Wikipedia how floating points are managed (https://de.wikipedia.org/wiki/IEEE_754) and for the time beeing I use my own implementation (which just works and is not optimzed in any way):

unsigned char *bb;
unsigned char vz = 0;
signed char ee = 0;
unsigned long long man = 0;
// with this define only the integer part is used  NO rounding when converting to int
#define NO_ROUND 1 
// 32 bit
signed long long int __fixunssfsi(float f)
{
	bb = (unsigned char *) &f;
	vz = bb[0] & 0x80;
	ee = (signed char) (bb[0] << 1);
	ee += (signed char) ((bb[1]&0x80)?(unsigned char)1:(unsigned char)0);
	man = bb[3];
	man +=  ((unsigned long long) bb[2]) * 256;
	man +=  ((unsigned long long)(bb[1]&0x7f))* 256* 256;
	
	if ((unsigned char)ee == 0xff)
	{
		if (man ==0) return 0; // infinite
		else return 0; // NaN
	}
	if (ee != 0)
	{
		man += 0x800000; // implicit 24th bit set
		ee -= 127;
	}
	else
	{
		ee = -126; // result smaller 0 - can be neglected (using just integers)
	}
	
	if ((vz==1) && (ee > 31)) return 0; // overflow 32 bit
	
	#define EXP_MID 23
	if (ee==EXP_MID) return (signed long long int) (vz?(-man):man);
	if (ee>EXP_MID) return (signed long long int) (vz?(-(man<<(ee-EXP_MID))):(man<<(ee-EXP_MID)));
	
	unsigned long long r = (unsigned long long ) (man<<(32-(EXP_MID-ee)));
	man = man>>(EXP_MID-ee);

	#ifndef NO_ROUND
	if (r>0x80000000) man +=1; // rounding
	if (r==0x80000000) man += (man&1); // rounding
	#endif

	return (signed long long int) (vz?(-man):man);
}

The float arithmetic is 32bit (1bit sign, 8bit exponent, 23bit mantisse).

As I discovered later – the old Microsoft BASICs (as e.g. used with the C64) all use a 40bit floating point arithmetic. In some cases the dungeon generation will have slight (rounding) differences because of that (or I implement a 40bit floating point arithmetic myself – but that would be far, far in the future).

THAN the real trial began.

I wanted the map to be exactly (apart from above mentioned 32bit / 40bit float differences) the same dungeon as I remembered from the C64 version.

I am not going too deeply into this – but it took me longer than anything else from above.

There were two points, that took me completly off guard.

1) Dungeon generation algorithms differ!

Above you see the implementation from the Atai sources, following are sources from the C64 version:

10010 Q=X*XO+Y*YO+Z*ZO+(X+XO)*(Y+YO)*(Z+ZO)
10020 H%=(Q-INT(Q))*W0:IFFNS(H%)>5THENH%=H%ANDTH
10025 IFINT(H%/TF)>0THENH%=(INT((Q*10-INT(Q*10))*15+1)*TF)OR(H%ANDTH)
10030 IFX=1ORX=201THENH%=H%OR12
10035 IFY=1ORY=201THENH%=H%OR3
10040 RETURN

I don’t know why this was changed (first line, the building of “Q”), but I didn’t notice those differences for a couple of hours. But even after implementing the correct generator – the dungeon still looked completely different.

You can not imagine all the places where one might look for bugs… In the meanwhile I powered up a C64 emulator, and actually executed the above generator code and compared the results with the vectrex coding.

… and to my astonishment… the output was the same!

What??? But… the displayed dungeon is different…

2) The starting coordinates differ!

This was a really mean one. In the Atari sources the program (line 1600) is initialized with:

/* Set starting position in dungeon
CX=TWO:CY=70:

The C64 source actually shows:

1600 CX=25:CY=13:EX=0:SU=1:CS=1:PRINT"YOUR NAME, NOBLE SIRE? ";

I don’t know why that took me so long to figure out, especially since the dungeon generator is different. It stands to reason, that Dan “looked for a location” that actually has an “Inn” at the starting position and just use those coordinates. But in hindsight one is always so much the smarter.

Anyway, after 3 days of work:
(It is not COMPLETELY the same (the upper right doors) – these are probably mentioned rounding differences, the generated numbers differ by exactly “1” (which changes a wall to a door), also the “original” version (C64) already has a line of sight implemented, the door below the Inn can only be seen if the player moves)

Update 30th January 2021:

40bit floating points get the desired results!