How is a 3D game like Ant Attack implemented?

[druellan]

And Alien Evolution has a similar style, not sure if it uses the same technique: https://spectrumcomputing.co.uk/index.php?cat=96&id=149

[Firefox]

https://spectrumcomputing.co.uk/index.p ... 6&id=21605

Something quite similar looking although not even close to being in the same league in game play!

Source code is there too if you want to take a look.

It runs nicely enough, but what do you actually do? Am I missing the instructions somewhere?

[Firefox]

Excellent interview with Sandy White about how he created Ant Attack. He comes across as a really nice bloke!

[media]https://www.youtube.com/watch?v=RdrgBwSH9W8[/media]

I really wish he'd write a bit about his custom development hardware he made for his Spectrum. All there is is this tiny photo and what he mentions in the video.

I've finally found the "Softy" that he talks about in the video! It's one of these:



(There are photos and adverts for the first four generations of Softy on this page, and you can download a PDF of the first Softy's manual.)

So it turns out that a Softy is a kind mash-up of a ZX80, an EPROM programmer, and a ROM emulator. There's no BASIC interpreter or anything, just a little monitor-type program which allows you to edit hex values on a telly. The keyboard only has hex digits and monitor commands on it! It can emulate an EPROM via a cable that plugs into a DIP socket on the target system. It can also program EPROMs using the ZIF socket next to the keyboard.

If you zoom in on the tiny photo from Sandy's website above, you can make out that the thing in the foreground is a Softy, which has a big ribbon cable plugged into a homebrew Spectrum peripheral which is sitting in the mid-ground in the photo.

I'm still not entirely sure what his homebrew Spectrum peripheral did or how he actually used it, though.

If you compare a dump of Ant Attack to the hand assembled code on the sheet of lined A4, exactly those values are at the start address written on the sheet.

The Softy only has 1kB internally for buffering data in an emulated ROM, so... I'm guessing his peripheral disabled the Spectrum's ROM and replaced it with some kind of monitor ROM (probably much smaller than 16kB is size) that allowed data to be copied back and forth between the 1kB Softy area and the Spectrum's upper RAM?

Don't know how he would've saved his work between sessions. On EPROMs? On tape? (The Softy has a tape interface as well as the Spectrum.)

[Alessandro]

In the answers to his website's guestbook, Sandy tells some interesting stories about the game. For instance, he replied to me (almost 19 years ago! ) that by placing an AM radio beside the Spectrum while running Ant Attack, you can tune it to the RF produced by the Z80 chip and the circuit board, so you can actually hear the program executing, and that he used this method for debugging the code sometimes. By listening to the sound of the code executing, he was, for example, able to understand where it had got stuck if it crashed.

[Morkin]

In the answers to his website's guestbook, Sandy tells some interesting stories about the game. For instance, he replied to me (almost 19 years ago! ) that by placing an AM radio beside the Spectrum while running Ant Attack, you can tune it to the RF produced by the Z80 chip and the circuit board, so you can actually hear the program executing, and that he used this method for debugging the code sometimes. By listening to the sound of the code executing, he was, for example, able to understand where it had got stuck if it crashed.

...Holy cr@p....

[Joefish]

https://spectrumcomputing.co.uk/index.p ... 6&id=21605
Source code is there too if you want to take a look.

Nice. It never occurred ot me that the blocks are all either columns of a certain height, or a single block floating at height.
That allows for both memory and speed optimisations, and you don't even realise there are things it can't do, like one block floating above another.
You could probably use the same optimisation for something like Knight Lore, except for perhaps wanting to put a deadly object under a disappearing platform. Although Head Over Heels would just use a deadly floor instead...

[Firefox]

In the answers to his website's guestbook, Sandy tells some interesting stories about the game.

Many thanks for the tip, Alessandro!
On the first page is this gem:

Ufff...too many hours playing AA on my B&W TV... Could you explain what are the devices that are
plugging in your speccy in the photo? Thanks for make me the life more funny (and sorry for my poor
english

Hi Droky, I spent too many hours in front of a B&W TV too, writing AA! I wonder if they still make
B&W TVs? Anyway, glad you have enjoyed playing AA! One of the devices in the photo is a "Softy"
ROM emulator, and the other is a home-made adaptor which mapped the Softy into 4K of the Spectrum's
memory. Apart from the city data, and some BASIC to do scoring screens, AA fitted entirely into that
4K! The advantage was that if the Speccy crashed, it didn't take my machine code with it!

So now I'm thinking that Sandy actually used a 16k Spectrum and his mysterious homebrew peripheral was actually a combined ROM + RAM pack. (Also, Sandy must have had a Softy 2 which could emulate 4kB ROMs - the original could only do 2kB.) I don't think it could have been a 48k Spectrum because it's not possible to override the upper memory from the edge connector (unlike the ZX81).

The Hacking 3D Ant Attack page has some good info on the memory layout of the game.

From that I think the ROM + RAM pack was probably organised like this:

Code: Select all

8000 4kB  Softy  (emulated ROM containing machine code)
9000 4kB  EPROM (text messages + ammo box / girl graphics)
a000 4kB  RAM   (screen buffer)
b000 4kB  RAM   (buffers, state info, then graphics data from b700 on)
c000 4kB  RAM?  (city data)
d000 4kB  RAM?  (city data)
e000 4kB  RAM?  (city data)
f000 4kB  RAM?  (city data)

It seems likely the second 4k chunk was an EPROM, because it has text messages at the start, sprite images at the end, and blank padding inbetween - it's all stuff that isn't altered at run time. The rest of the sprite data is split off into the end of the fourth 4kB chunk, which must be RAM because there are buffers and modifiable state info at the start.

The city map could be in EPROM, but Sandy mentions several times that the unused aeroplane sprite was used in early development to indicate which block on the map was being edited.

Phew! Fun detective work! I'd still *really* like to see some decent photos of his homebrew gizmo, though.

[Seven.FFF]

So now I'm thinking that Sandy actually used a 16k Spectrum and his mysterious homebrew peripheral was actually a combined ROM + RAM pack. (Also, Sandy must have had a Softy 2 which could emulate 4kB ROMs - the original could only do 2kB.) I don't think it could have been a 48k Spectrum because it's not possible to override the upper memory from the edge connector (unlike the ZX81).

If he was this kind of homebrew legend then he could have modded his board to get access to all the address lines before the ULA, couldn't he?

[Ralf]

In the answers to his website's guestbook, Sandy tells some interesting stories about the game. For instance, he replied to me (almost 19 years ago! ) that by placing an AM radio beside the Spectrum while running Ant Attack, you can tune it to the RF produced by the Z80 chip and the circuit board, so you can actually hear the program executing, and that he used this method for debugging the code sometimes. By listening to the sound of the code executing, he was, for example, able to understand where it had got stuck if it crashed.

"Sound of code" would make a great name for an album of some psychedelic nerdcore music

[Firefox]

If he was this kind of homebrew legend then he could have modded his board to get access to all the address lines before the ULA, couldn't he?

I mean, it's possible, but he'd have to replace a 48k Spectrum's upper RAM's RAS/CAS generation logic on the main board with something more complicated that cut a 4kB or 8kB hole in the address map to allow the homebrew peripheral to respond to the address range without causing contention. The 16k Spectrum doesn't have that fitted, so it's much easier to build a plug-in gizmo that takes care of the whole top 32kB of the address map (essentially just a slightly fancier RAM pack).

I don't know for sure, I'm just having fun geeking out and trying to piece together how he did it from the scant clues available.

[WhatHoSnorkers]

In the answers to his website's guestbook, Sandy tells some interesting stories about the game. For instance, he replied to me (almost 19 years ago! ) that by placing an AM radio beside the Spectrum while running Ant Attack, you can tune it to the RF produced by the Z80 chip and the circuit board, so you can actually hear the program executing, and that he used this method for debugging the code sometimes. By listening to the sound of the code executing, he was, for example, able to understand where it had got stuck if it crashed.

I have a book on Software Testing from the old days, and this sort of thing was quite common back in the day. There's an album by Johan Johansson where he has a recording of music his father made by putting a radio inside an IBM 1401 computer and running various programs; quite haunting.

[Joefish]

I need to have a go at something like this myself. I didn't think it could all be redrawn every frame fast enough, but with some optimisations it seems that's exactly what is going on. And drawing either a column or a floating block, rather than every possible combination of 8 block positions in a stack, allows for even more optimisation. I've got an idea for a different approach to the rendering though...

[CST]

Ant Attack as an introduction to programming

https://happy-computing.weebly.com/tape.html

Pretty nice, but unfinished...

[Tommo]

Apologies, I’m unable to view a video where I am so I don’t know whether this is already addressed but because Ant Attack uses a regular grid of fixed-size blocks, there’s no need to draw back-to-front. You can very cheaply populate the screen — sprites aside — with no overdraw whatsoever by walking the level data from front to back and stopping as soon as you hit something to populate a triangular grid; since the triangles are a fixed shape they’re just bitmaps in the end.

Since the sprites can move only in integer grid positions it’s also easy to paint them on top without much complexity.

It’s only if you introduce map elements that are not exactly grid aligned that you need to start coming up with solutions that involve overdraw.

[Joefish]

If that's what you think, go ahead and try it! But that's not how Ant Attack or any of these other isometric games work.

That's how voxel-based games on PCs work, but the Spectrum doesn't have the processing power to work like that. Any one block might only be partly obscuring another block. So do you divide all your blocks up into 8 triangles and check against all 8 x 1/8s of the blocks that may be behind it? Or is it quicker just to draw them all over the top of each other?

[Tommo]

because Ant Attack uses a regular grid of fixed-size blocks, there’s no need to draw back-to-front.
...
It’s only if you introduce map elements that are not exactly grid aligned that you need to start coming up with solutions that involve overdraw.

If that's what you think, go ahead and try it! But that's not how Ant Attack or any of these other isometric games work.

I'd love to hear your list of "any of those other isometric games" that use a regular grid of fixed-size blocks. Have you got a single example beyond Zombie Zombie?

That's how voxel-based games on PCs work,

It's not even close to how voxel-based games on PCs work.

but the Spectrum doesn't have the processing power to work like that. Any one block might only be partly obscuring another block. So do you divide all your blocks up into 8 triangles and check against all 8 x 1/8s of the blocks that may be behind it? Or is it quicker just to draw them all over the top of each other?

Once again: traverse the map to figure out which surfaces are visible. Because it's regular, and all cubes exactly fill a block.

So, no, at no point are you going to work forwards from cubes.

It looks like I last implemented it 16 years ago, here's the entire casting function:

Code: Select all

#define GetByte(x, y)	( ((x) < -64) || ((y) < -64) || ((x) > 63) || ((y) > 63) ) ? 0 : map[((x+64) << 7) | (y+64)]

void LaunchRay(int mapx, int mapy, int x, int y)
{
	int mask = 0x20;
	int byte1, byte2, byte3, byte4;
	int leftempty = 1, rightempty = 1;

	byte4 = GetByte(mapx, mapy);

	while(mask && (leftempty || rightempty))
	{
		byte1 = byte4;
		byte2 = GetByte(mapx + LeftX, mapy + LeftY); //left one
		byte3 = GetByte(mapx + DownX, mapy + DownY); //up one

		mapx += LeftX + DownX;
		mapy += LeftY + DownY;
		byte4 = GetByte(mapx, mapy); //left & up one

		if(leftempty)
		{
			if(byte1&mask)
			{
				draw_sprite(back, ul, x, y);
				leftempty = 0;
			}
			else
			{
				if(byte2&mask)
				{
					draw_sprite(back, mr, x, y);
					leftempty = 0;
				}
				else
					if(byte4&mask)
					{
						draw_sprite(back, bl, x, y);
						leftempty = 0;
					}
			}
		}

		if(rightempty)
		{
			if(byte1&mask)
			{
				draw_sprite(back, ur, x+left->w, y);
				rightempty = 0;
			}
			else
			{
				if(byte3&mask)
				{
					draw_sprite(back, ml, x+left->w, y);
					rightempty = 0;
				}
				else
					if(byte4&mask)
					{
						draw_sprite(back, br, x+left->w, y);
						rightempty = 0;
					}
			}
		}

		mask >>= 1;
	}

	if(leftempty && byte4)
		draw_sprite(back, shadowl, x, y);
	if(rightempty && byte4)
		draw_sprite(back, shadowr, x+left->w, y);
}

Which part of that is too expensive for a Spectrum, exactly? You'd probably unroll it differently, but that's about it.

That's casting into exactly the Ant Attack data format, by the way. Here's some sample output:



`draw_sprite` is an Allegro 4.x call, because as I said this code is 16 years old. It doesn't actually need a 'sprite' routine, they're always character-square aligned and never overlap; even with my inclusion of shadows there's a grand total of five of them. Get rid of the shadows and it'd be three.

EDIT: oh, and this is also exactly how Snake, Rattle & Roll on the NES works per its tile set, except that Rare have gone one step further and allowed for split blocks that have a different graphic for their left and right parts.

So, no, despite your claim that the algorithm above is intractable for some unspecified reason, Rare didn't somehow manage to draw from back to front, to a constructed bitmap, fast enough to scroll, on a NES.

[rastersoft]

Apologies, I’m unable to view a video where I am so I don’t know whether this is already addressed but because Ant Attack uses a regular grid of fixed-size blocks, there’s no need to draw back-to-front. You can very cheaply populate the screen — sprites aside — with no overdraw whatsoever by walking the level data from front to back and stopping as soon as you hit something to populate a triangular grid; since the triangles are a fixed shape they’re just bitmaps in the end.

Since the sprites can move only in integer grid positions it’s also easy to paint them on top without much complexity.

It’s only if you introduce map elements that are not exactly grid aligned that you need to start coming up with solutions that involve overdraw.

That doesn't work when you can do pixel-by-pixel drawing, or when elements can occupy more than one block, or when you have transparency... like in an isometric game, where the screen grid doesn't coincide with the map grid.

[Tommo]

It’s only if you introduce map elements that are not exactly grid aligned that you need to start coming up with solutions that involve overdraw.

That doesn't work when you can do pixel-by-pixel drawing, or when elements can occupy more than one block, or when you have transparency... like in an isometric game, where the screen grid doesn't coincide with the map grid.

I don't know how to state this any more clearly: the different with Ant Attack, and only Ant Attack, and not all those other isometric titles, and only Ant Attack, and Zombie Zombie is:

• no in-game elements ever occupy more than one block;
• I distinguished the level from the sprites because then: the level has no transparency; and
• the screen grid exactly coincides with the map grid if the screen grid is isosceles triangles.

Seriously, the code is just up there. It's not complicated. The Ant Attack data format is one byte per map column, blocks either filled or empty.

Per isosceles triangle, starting from the roof:

Code: Select all

If the top block you started on is occupied, fill with the horizontal-surface colour and stop.

Otherwise:
while(not at floor) {
    move one block diagonally back.
    
    If it is occupied, fill with wall colour and stop. 
    If the the block below is occupied, fill with horizontal-surface colour and stop.
}

Use two wall colours, one for left-facing triangles, one for right. That gives you the different north/south and east/west faces.

So:

• that's the algorithm in pseudo code;
• a concrete C implementation with sample output is above; and
• I've given you an obvious example of that algorithm in production, regardless of whether Sandy White ever figured it out.

EDIT:
These are 16-year old builds so there's little I can do about them now, but you can see a Windows build of the above code here. To hit that 16-year-old point again, you can also download a Mac version... if you happen to be rocking a PowerPC.

EDIT2:
Oh, and those isosceles triangles are 8 pixels wide and 8 pixels along the vertical edge to match Ant Attack, I think. So the total number to pass through the loop above for scene construction is two times the number of character squares.

[Joefish]

Since this is a Spectrum forum, how about a version that runs on a Spectrum then? Otherwise, you've proved nothing.
I don't care if your algorithm works, or was used on a console with a block-mapped screen. Show it running on a Spectrum at a higher frame rate than Ant Attack.

[Tommo]

Since this is a Spectrum forum, how about a version that runs on a Spectrum?

Out of curiosity, how many constructive conversations have you taken part in lately that involve rolling eyes at people?

I'm being attacked on two fronts here, so I just want to clarify: Rastersoft contends that the algorithm wouldn't work, you merely think it'd be the somewhat nebulous too slow? So can you provide a quantification? Size of display, frame rate, etc?

EDIT: you edited as I was asking. Have we any idea what the frame rate of Ant Attack is?

My Z80 skills are meagre, so I hope you'll accept something that is sufficiently fast to prove that a more competent programmer could do a more competent job. I mean, you could argue against me all day that there's no way a Spectrum could scroll at 25Hz since your only retort seems to be "I'm not telling you why, but that's too slow ", and it's very improbable that I could get a Spectrum to scroll at 25Hz, but obviously Joffa could.

EDIT2: minor correction to the above; having sketched it out on a piece of paper each maximum-six-step walk through the map gives the final no-overdraw output for a full 64 pixels. So it's the equivalent of one walk per character square.

Each step through the map is three byte fetches and three ANDs.

[rastersoft]

I don't know how to state this any more clearly: the different with Ant Attack, and only Ant Attack, and not all those other isometric titles, and only Ant Attack, and Zombie Zombie is:

• no in-game elements ever occupy more than one block;
• I distinguished the level from the sprites because then: the level has no transparency; and
• the screen grid exactly coincides with the map grid if the screen grid is isosceles triangles.

OK, now I understand it... The point is to divide each character in an isosceles triangle. That makes sense.

[Tommo]

I don't know how to state this any more clearly: the different with Ant Attack, and only Ant Attack, and not all those other isometric titles, and only Ant Attack, and Zombie Zombie is:

• no in-game elements ever occupy more than one block;
• I distinguished the level from the sprites because then: the level has no transparency; and
• the screen grid exactly coincides with the map grid if the screen grid is isosceles triangles.

OK, now I understand it... The point is to divide each character in an isosceles triangle. That makes sense.

If you're good at hieroglyphics, here's the version I just sketched out on paper to persuade myself that I still know what I'm talking about. Plus hopefully to persuade myself that even at my long-decayed remedial level, doing it in Z80 would be achievable.

So, yeah, the bands on the left are the individual triangles you'll try to fill, on the right I calculate that you could use 16 UDGs total (if you'll permit the appropriation of the BASIC term) if you wanted to keep all drawing strictly in terms of complete character squares, and then underneath I restate the algorithm.

Based on my handwriting, you'll have to trust me on that latter part.



EDIT: no, wait, I’m still not quite reporting correctly. At most six times [three fetches and three ANDs] to decide the output colour for 128 pixels, no overdraw. Because it’s two such isosceles triangles at a time. Which can then easily be mapped to 8x8 tiles of which only 16 predrawn combinations are required.

So I keep talking about triangles but there’s no edge scanning or complicated span compositing, it’s just an unmasked blit — exactly one source graphics byte fetched for each screen byte — no shifting or any other manipulation. Just fetch and store.

(and add sprites post hoc; they’re also grid aligned in Ant Attack so that’s really easy compared to a Knight Lore, Bobby Bearing, etc)

[Joefish]

My Z80 skills are meagre, so I hope you'll accept something that is sufficiently fast to prove that a more competent programmer could do a more competent job.

So what you're saying is, your knowledge of the Spectrum is meagre, but you still think you know better than everyone on a dedicated Spectrum forum?

I mean, you could argue against me all day that there's no way a Spectrum could scroll at 25Hz since your only retort seems to be "I'm not telling you why, but that's too slow ", and it's very improbable that I could get a Spectrum to scroll at 25Hz, but obviously Joffa could

I don't need you to tell me what Joffa could or couldn't do, when Joffa himself has already told me at length what he could or couldn't do.
And I think it's hilarious that you still think 25Hz is a fast scroll.
https://spectrumcomputing.co.uk/entry/3 ... um/50Hurts

Each step through the map is three byte fetches and three ANDs.

No, each of your steps through the map goes through a seemingly endless set of nested if/else conditions when it would be far, far faster to simply draw the block over whatever's there and move on. That is why your method will be slower. Because of all those conditional jumps you'll be making before you even think about drawing a single pixel.

[Tommo]

My Z80 skills are meagre, so I hope you'll accept something that is sufficiently fast to prove that a more competent programmer could do a more competent job.

So what you're saying is, your knowledge of the Spectrum is meagre, but you still think you know better than everyone on a dedicated Spectrum forum?

No, that's not even close to what I'm saying. You've one hell of an ego though, especially for somebody plucking claims out of thin air. The only person I'm still in disagreement here is you, so by implication you're asserting that if somebody knows something better than you do then they know better than everybody on a dedicated Spectrum forum? I was unaware that you were at the pinnacle.

If you must insist on being so incredibly tedious, a partial personal retro softography, limited to what I've ever chucked onto Youtube:

• a 3d engine for the SAM Coupé;
• a 50Hz full-screen scroller for the SAM Coupé (no, really);
• Mode 7 on the Atari Lynx.

It'd be interesting to know which statement you disagree with, though:

1. the Ant Attack level geometry can be drawn directly, no overdraw, using the isosceles triangles as depicted above;
2. that it's trivial to do so by combining adjacent triangles into a 'UDG'-esque lookup table, reducing drawing to load and store;
3. that the colour for two such triangles can be picked in, in the worst case, six times (three byte fetches and three ANDs)*.

If anybody else can see what Joefish's problem is, other than that *gasp* somebody dared to disagree with him, I'd be grateful of the assist.

* the Ant Attack level is six blocks high.

At each level the test is: (1) is this block solid?; if not then: (2) is the back wall on the left solid; and/or (3) is the back right solid?

Continue until you hit the floor or have filled both blocks.

Those three tests are three byte fetches and three ANDs per level, six levels total.

On a real Z80 implementation you'd have three versions of the inner loop, one that's still checking both triangles, one that's checking only the left, one that's checking only the right. The C implementation above doesn't do that because on its target processing is cheaper than the cost of trifurcated code.

Each step through the map is three byte fetches and three ANDs.

No, each of your steps through the map goes through a seemingly endless set of nested if/else conditions when it would be far, far faster to simply draw the block over whatever's there and move on. That is why your method will be slower. Because of all those conditional jumps you'll be making before you even think about drawing a single pixel.

Oh, so your problem is that you can't read code. Or pseudocode. Or my handwriting.

Actually, the last one is also my problem.

[Bedazzle]

How you produced this image?