🔥 HOT: Forums/post - HD Photos!

Forums

Sega Master System / Mark III / Game Gear
SG-1000 / SC-3000 / SF-7000 / OMV
Home - Forums - Games - Scans - Maps - Cheats - Credits
Music - Videos - Development - Hacks - Translations - Homebrew

View topic - Maze3d

Reply to topic Goto page 1, 2, 3  Next »
Author Message
  • Joined: 17 Jan 2020
  • Posts: 118
  • Location: Brisbane, AU
Reply with quote
Maze3d
Post Posted: Sun Jun 12, 2022 2:33 am
Last edited by under4mhz on Sun Jun 12, 2022 10:33 pm; edited 2 times in total
After our discussion of 3D graphics, I thought I’d have a look at optimising my Mazenstein3d code.

I converted the graphics to use tiles instead of lines, added a lut for the line angle division, removed the doors being in between the walls, cached the tile data to upload to the vdu and moved to sdcc 4.2.

Now that it’s tile based, it was fairly easy to port the code to SMS and GG.

The improvements moved the frame rate from 3.5fps up to 7fps for SMS and 9fps for GG. The SG(-1000) is running at 6fps, since it has no memory for tile caching. The poor little GameBoy(GB) port is running at 5fps, but that’s a reflection of the GB only being able to write to the vdu during vsync, my vdu library being written in C. Interestingly the ZX spectrum version runs at the same speed as the SG (but I wrote a bucket load of assembler in the vdu library to get it that fast).

The engine only casts one ray per column (32 for SMS and 20 for GG) and the heights between two columns are averaged to get the angle. If a corner is detected, the averaging is disabled, since these walls need to be sharp up to the edge.

This is why the GG is significantly faster here, since it builds only 60% of the scene that the SMS version does. It’s possible to make the scene wider for GG, but it would still be only 20 columns wide.

All the divide and multiply functions are unrolled loops. One divide that was possible to remove (and replaced with a lookup table(LUT)) was the 1/player rotation angle calculation, since this is constant and only dependent on the player view rotation.

The sdcc compiler with its new feature of passing parameters in registers generally gives about a 10% speed improvement. The SMS version using sdcc 4.1 runs at a flat 6fps, whereas the 4.2 version runs about 7fps. The ZX and GB ports didn't work properly in sdcc 4.2, I'll have to look into that at some point. The screenshots for GB and ZX are for 4.1 and are 10% slower than the others.

The doors are a bit deeper into the walls than before. This is because to render the doors half way between the walls, the map position (x,y) was halved, so the doors could fit in between. A single unit on the map is a wall thickness, and drawing something in between is difficult. By making the doors aligned with the walls, half the ray casting looks up could be removed.

All the tile data is written to a 1024b array (32 cols*16 rows*2b per tile), being (slightly) faster to randomly access an array and blit the data to the vdu.

The map is a simple text map stored as strings. These were taken from screenshots of the original maps. A custom converts the 8x8 tiles on the image to text characters. There are a large amount of unique tiles on the maps, but these have been culled down to wall, space, door and starting point for speed and a lack of tile space.

The tiles are split between door and wall colours. A tile is stored for each angle between horizontal and diagonal, for each of the 8 possible pixel heights for a tile. Each different colour requires its own tile set.

The walls look a bit wonky, since only one tile is rendered for the top of the wall. This means a line that crosses between two vertical tiles, will only render one of them for the column. This is why some columns have a flat top or aren't as sloped as expected. It’s a trade-off between accuracy and speed, the more visually accurate it is, the slower it’ll go. The trade off here is worth it, since once the player starts moving, the small rendering inaccuracies are generally forgiven (as long as the game is fast and fun).

The graphics takes advantage of the (SMS’s) ability to flip the tiles vertically and use the sprite palette for tiles to make the floor tiles grey and the bottom row of tiles. It’s possible horizontal flip to remove half the wall tiles again to allow for more colours and possibly textures. The GameBoy doesn’t have this feature, and so runs out of tiles. Either the door will need to be rendered with edges of the wall colour, half the possible angles of the lines or make the doors the same colour as the walls. The ZX version run out of tiles as well, since only 256 tiles (1byte) are cached in the internal tile memory space that's been implemented. The SG version is blocky to allow border lines to be drawn on top of the walls. This gives better definition to the walls, and is worth the trade-off of the blocker look.

It is possible to add wall textures, but this will slow it down again. Each texture will have to be added during the wall rendering according to height, and each look up slowing it down. Right now, a single tile is used for the walls, which can be written quickly. The number of tiles would be large as well, requiring 32 tiles for each texture, one for each of the 32 possible angles, and that is if the same texture is used into the distance.

The great thing about demos is that we don’t have to worry about trivial details such as opponents and pickups. Which will slow the engine down significantly. So look at these results with that in mind.

Tile space is needed for each of these on the screen, for each zoom level. Each item on the screen will need its own set of tiles, each zoom level loaded as required. This will limit the number of objects on the screen at once.

There’s definitely some more gains to be had here. The function that does the searching for walls (ray casting) is all in C, which can be written in assembler for a double speed improvement. As can the code to write the scene to the cache.

Being a (pseudo) 3D engine, it’s one of the few games where nearly everything is an inner loop and could be re-written in assembler for a speed improvement. Basically, anything labelled “Self Time” in the profile graph below would likely be halved if written in assembler. That’s probably about a 20% improvement, so maybe another 2fps. I’m probably not going to do that. Z80 assembler is fun, but time consuming and unreadable after a week (though somehow incredibly clear at the time).

Adding enemies will probably take 1 or 2fps away, and if I rewrite the rendering and casting code in assembler, it may end up steady at about 6fps on an SMS.

Next, I’ll probably work on supporting making the rooms different colours. The doors will be marked as a colour and upon opening, the palette will be updated to reflect the rooms’s colour. Two sets of tiles can be used to flip between the current wall colour and the next, so the existing room will have the same colour walls.

I’ll also work on making it a complete game with all the levels (minus any enemies), so that it’s a complete game in its own right. That’ll at least make it a more interesting and playable game, even if it’s not a first person shooter.

I'll probably port it to Amstrad CPC 464 and Microbee as well, becausing porting stuff to other platforms is fun (and easy, after the first one).
Maze3dSMS.png (13.01 KB)
Maze3dSMS.png
Maze3dSG.png (12.38 KB)
Maze3dSG.png
Maze3dProfile.png (28.86 KB)
Maze3dProfile.png
Maze3dMapCode.png (17.47 KB)
Maze3dMapCode.png
Maze3dLines.png (11.83 KB)
Maze3dLines.png
Maze3dGG.png (11.36 KB)
Maze3dGG.png
Maze3dGB.png (10.19 KB)
Maze3dGB.png
Maze3dZX.png (14.9 KB)
Maze3dZX.png
Maze3d-1.01.zip (127.27 KB)

  View user's profile Send private message Visit poster's website
  • Joined: 25 Feb 2006
  • Posts: 970
  • Location: Belo Horizonte, MG, Brazil
Reply with quote
Post Posted: Sun Jun 12, 2022 1:27 pm
Awesome project, and awesome technical explanation.
Would there be any demo ROMs/source code/video recordings available?
Please, keep us updated. ;)
  View user's profile Send private message Visit poster's website
  • Joined: 06 Mar 2022
  • Posts: 810
  • Location: London, UK
Reply with quote
Post Posted: Sun Jun 12, 2022 6:19 pm
Yeah this is really great stuff, very impressive!
  View user's profile Send private message Visit poster's website
  • Joined: 08 Apr 2005
  • Posts: 492
  • Location: Netherlands
Reply with quote
Post Posted: Sun Jun 12, 2022 10:29 pm
Oh my...very interested to see this developing!
  View user's profile Send private message Visit poster's website
  • Joined: 17 Jan 2020
  • Posts: 118
  • Location: Brisbane, AU
Reply with quote
Post Posted: Sun Jun 12, 2022 11:47 pm
I've attached Demo ROMS for your platform of choice.
Maze3d-1.01.zip (127.27 KB)

  View user's profile Send private message Visit poster's website
  • Joined: 03 Dec 2021
  • Posts: 126
  • Location: Italy
Reply with quote
Post Posted: Mon Jun 20, 2022 12:12 pm
This already looks incredible, congrats and keep up the great work!

I am yet completely ignorant in programming for the SMS (although I am about to begin), so please forgive me if this does not make much sense.
I once saw a video of toy story the videogame for the genesis made by its main developer who explained that for the FPS part he basically draw only half of the screen (either bottom or top) and the rest was just mirrored, as the 3d scene was symmetric along the horizontal center line. Would the SMS be able to do that, or is it something that you already do/ are considering?

Again, sorry of this question does not make much sense, and keep up with the neat project ;)
  View user's profile Send private message
  • Joined: 03 Dec 2021
  • Posts: 126
  • Location: Italy
Reply with quote
Post Posted: Mon Jun 20, 2022 1:13 pm
under4mhz wrote
The graphics takes advantage of the (SMS’s) ability to flip the tiles vertically and use the sprite palette for tiles to make the floor tiles grey and the bottom row of tiles.


Oh, I guess this means you are already doing it :)
  View user's profile Send private message
  • Joined: 06 Mar 2022
  • Posts: 810
  • Location: London, UK
Reply with quote
Post Posted: Mon Jun 20, 2022 1:31 pm
You can't mirror the whole screen down or across the middle, if that's what you mean (*)

(I was actually unaware of the mega drive / genesis being able to do that, and although there are a couple of great YouTube videos on fancy stuff in ToyStory, I couldn't find reference to that)

You can mirror individual 8x8 background tiles either horizontally, or vertically, or both at the same time, by setting bits 9 and 10 in the 16 bit entry for that tile in the screen map - that's what under4MHz is referring to here.

You can't mirror sprite tiles, so they will always always facing the same way. See this thread for an interesting discussion of the only alternative, which is to design a left-facing and right-facing tile (for horizontal scrolling games).

* Note, just thinking there are numerous mask bits in some of the VDP registers which might (?) allow repeating sections of the screen, although I can't think of how they would literally reflect portions of it.

UPDATE: yeah looks like from this guide you can clear bit 0 of register 2 which will have the effect of repeating the top 16 rows of the screen in the bottom 8 rows of the screen. Again, not reflected, just repeated.
  View user's profile Send private message Visit poster's website
  • Joined: 03 Dec 2021
  • Posts: 126
  • Location: Italy
Reply with quote
Post Posted: Mon Jun 20, 2022 1:52 pm
Thank you for your feedback, really appreciate that :)

willbritton wrote

(I was actually unaware of the mega drive / genesis being able to do that, and although there are a couple of great YouTube videos on fancy stuff in ToyStory, I couldn't find reference to that)


I was referring to this video actually, even though I am totally unaware on how it works (about t=4:30 it talks about it):

  View user's profile Send private message
  • Joined: 06 Mar 2022
  • Posts: 810
  • Location: London, UK
Reply with quote
Post Posted: Mon Jun 20, 2022 6:22 pm
Ah, okay, so actually what I think is happening here is that there's a fixed screen map and he's updating the tile definitions continuously.

Forgive me if you already know this stuff, but basically the SMS (and Megadrive I believe) has a screen map of 32x24 tiles. Each tile is 8x8 pixels. That means in the VRAM of the VDP there's a table of 768 entries each of which references a tile definition (aka patterns). There are space for 512 (ish...) patterns for the SMS.

For most games, like 2D-scrollers, there is a fixed set of tiles and the screen map simply determines where those tiles are placed on the screen. So for example, you might have the top 20 rows of 32 tiles be tile #1 which is plain blue - for the sky; and the bottom 4 rows of 32 tiles be tile #2 which is plain green - for the grass. This way you only need 2 background tiles to draw the whole screen. Those 2 tile never change, but what you can do is change the screen map so that different tiles are sky and different ones are grass. For example, to create the effect of a set of "steps" going up or down hill.

Alternatively, you could instead create a fixed screenmap, so it might look something like this:

1 2 3 4 5 6 7 8 9 10 11 12 .......... 32
33, 34, 35, 36, 37, 38, 39...........64
...
...
736, 737, 738, 739..........768


(that's assuming you can define 768 different tiles, which in the SMS you can't, but see below!)

This way, instead of changing the screen map in response to user action, you keep the screenmap fixed but change the tile definitions. e.g. if you change the definition for tile #1 it changes the top left 8x8 pixels of the screen, and if you change the definition for tile #32 it changes the top right 8x8 pixels of the screen.

This allows you to more finely control the actual pixels on screen without being limited to a fixed set of tiles. However it's significantly slower because (for the SMS) you need to update 4 bytes of data for each tile, instead of just 1 to modify a single tile reference in the screen map.

Now, in this Toy Story 3D example they are doing the fixed screen map technique, but they are storing a screen map which mirrors itself.

e.g. it looks like this:

1 2 3 4 5 6 7 8 9 10 11 12 .......... 32
33, 34, 35, 36, 37, 38, 39...........64
...
321, 322, 323, 324............352
353, 354, 355, 356............384 // this is halfway down the screen
353, 354, 355, 356............384
321, 322, 323, 324............352
...
33, 34, 35, 36, 37, 38, 39...........64
1 2 3 4 5 6 7 8 9 10 11 12 .......... 32


Crucially, when the screen reflects on rows 13 and above, the tiles are also flipped in the x-axis ("vertical flip")

This means that:

1. You now only need 384 tile definitions instead of 768- win!
2. The screen is automatically reflected in the x-axis, i.e. when you update tile #1 it updates both the top left 8x8 pixels in the screen and the bottom left 8x8 pixels in the screen.
3. It's half as many tiles needed to update - win win!

Now, is this technique possible on the SMS? In theory, yes. However in practice writing to VRAM on the SMS is significantly slower than in the Megadrive. How much slower I'll have to work out on the back of an enveloper, but the Megadrive support something called DMA which means the CPU can write directly to VRAM, whereas the SMS needs to "talk" to its VDP via a relatively slow interface which only allows a certain limited throughput of data. Will update with some more specifics when I get the chance but I think this would put the theoretical throughput too low for a reasonable 3D experience based on this technique.
  View user's profile Send private message Visit poster's website
  • Joined: 05 Sep 2013
  • Posts: 4315
  • Location: Stockholm, Sweden
Reply with quote
Post Posted: Tue Jun 21, 2022 7:05 am
the only way to mirror the top half of the background is to reuse the same tiles vertically flipped and arranged bottom-up in the bottom part of the screen - yes, it takes time but fortunately you can write to the VDP even outside of vBlank, you just have to accept to do it slower.
  View user's profile Send private message Visit poster's website
  • Joined: 15 Aug 2019
  • Posts: 318
  • Location: Lancashire UK
Reply with quote
Post Posted: Thu Jun 30, 2022 1:44 pm
I realise it's early days but this is awesome. Wolfenstein 3D running on Sega Master System. WOW!!
  View user's profile Send private message Visit poster's website
  • Joined: 08 Apr 2005
  • Posts: 492
  • Location: Netherlands
Reply with quote
Post Posted: Thu Jun 30, 2022 2:40 pm
Hope it gets updated!
  View user's profile Send private message Visit poster's website
  • Joined: 09 Jun 2014
  • Posts: 488
Reply with quote