Wolfenstein / DOOM for Oric : has this been done?

Want to talks about games you like, would like to see developed on the Oric, it's here.
User avatar
NekoNoNiaow
Flying Officer
Posts: 143
Joined: Sun Jan 15, 2006 10:08 pm
Location: Montreal, Canadia

Wolfenstein / DOOM for Oric : has this been done?

Post by NekoNoNiaow » Wed Mar 28, 2018 3:43 am

Hello,

I did a cursory search for "wolfenstein oric" and "doom oric" on Duck Duck Go and https://pout.net but I did not find any indication that anyone attempted to at least make a technical demonstration of these games on the Oric.

There have been some attempts on the C64, VIC 20, Spectrum and others, so I thought that the Oric might also have one but it looks like this is not the case. Can anyone confirm?

Thanks!

ThomH
Flying Officer
Posts: 147
Joined: Thu Oct 13, 2016 9:55 pm

Re: Wolfenstein / DOOM for Oric : has this been done?

Post by ThomH » Wed Mar 28, 2018 5:16 pm

I've not seen one. I definitely think something like that would be easily within the Oric's scope, and as to reproducing Doom in the sense that the other 8-bit versions do, the algorithm isn't even that hard I think: they don't do variable height sectors and the Spectrum Doom in particular is heavily oriented around individual separated rooms, so it looks like forward rendering with clip planes at x=y and x=-y, then filling a 1d display-width height buffer in order to decide which vertical spans actually to draw would be entirely sufficient. Obviously using closed doors to bound geometry you attempt to draw. It should actually be quite a bit less work than a Wolfenstein-type backward renderer.

So, in pseudo:

Code: Select all

struct Span {
    int height;
    int colour; // or texture, or whatever you're smart enough to draw
} spans[240];

draw_scene:
    spans[0...239].height = 0
    add_room(wherever the player is standing)
    for x in 0...239:
        draw span as per spans[location]
        (for Wolfenstein-esque presentation, centre spans vertically; for
        something more like Doom, draw them with e.g. 1/4 below the centre,
        3/4 above. Change that proportion overt time for head bouncing movement)

add_room:
    (sine, cosine) = lookup based on camera rotation
    for vertex in room:
        output position = (sine, cosine) * vertex position - camera location
        if output.x < -output.y:
            output flags |= 1
        if output.x > output.y:
            output flags |= 2
        if output.y < 1:
            output flags |= 4

    for edge in room:
        if (first vertex output flags) & (second vertex output flags):
            continue
        clip mask = (first vertex output flags) | (second vertex output flags)

        if clip mask & 1:
            determine point on line where x = -y and substitute it for whichever vertex has 1 set
        ... ditto for other two clip masks ...

        project vertices
        (optimisation: if no clipping, project and store projected locations with originals, to avoid reprojection)

        for screen area between projected vertices:
            using height of wall at location:
                if height > spans[location].height:
                    spans[location].height = height
                    spans[location].colour = this colour

    for all rooms connected to this one by doors:
        if door is open:
            add_room(connected room)
            // assumption here is that everything is so large and separated that
            // no circular traversals occur. Keep visited flags if required, though then
            // there's setup cost clearing them.

The `output position = (sine, cosine) * vertex position - camera location` can be optimised to mostly the classic 256-value lookup 8x8 multiply if you keep rooms at a relatively low precision and apply an additional two 8x16 multiplies per room to locate room centres.

Then you also need 16x16 divide and the ability to draw spans. I think a lot of these engines just say that, well, there can only be 400 (or whatever) sizes of output span, so precompile the code to draw a textured span at every one of those heights for every possible strip of texture.

Run-slice is probably best for mapping from projected points to wall heights, because your geometry is sparse. So that adds a need for 8x8 divide with remainder.

The argument in favour of forward rendering here is that the setup cost of transforming geometry is less than the per-column linear search of a Wolfenstein. The potential disadvantage is precision issues on the clipping, but you can hack around that by saying that if you clip to e.g. x = -y then obviously the projected x is column 0. Then only the projected y might be slightly off, but it should be acceptable.

Precision is why I've never managed to get a classic portal renderer to work well at 16-bit precision.

User avatar
Dbug
Site Admin
Posts: 2724
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Re: Wolfenstein / DOOM for Oric : has this been done?

Post by Dbug » Wed Mar 28, 2018 5:57 pm

I did an attempt around 2001:
walls.zip
(7.66 KiB) Downloaded 67 times
It did not go very far because I did not manage to find a satisfactory way to avoid the fish eye effect, as well as how to get some decent looking walls with shading effect that don't cost too much cpu time.

ThomH
Flying Officer
Posts: 147
Joined: Thu Oct 13, 2016 9:55 pm

Re: Wolfenstein / DOOM for Oric : has this been done?

Post by ThomH » Wed Mar 28, 2018 7:22 pm

I assume that it's not all that helpful to make the standard recommendations?
  • don't associate angles one-to-one with screen columns — build a table of casting angle per column slice as an offset from the centre ahead of time as a function of atan, because you're solving for the angle inside a right-angled triangle between the viewer and the screen; and
  • multiply column heights by cosine of the casting angle because on that same right-angled triangle you've found the hypotenuse but you actually want the height.
So it's an extra lookup table and a multiply per column.

Alas I'm at work, so I cannot try the tape. Hence the boilerplate reply. Apologies.

EDIT: multiply, not divide. I drew a little diagram to convince myself. I'm sure it really clarifies everything! (EDIT2: impliedly, if not just using the stock result of 'multiply by cosine to project', because cos = adjacent/hypotenuse, you have hypotenuse but you want adjacent)
Attachments
B18D8B30-7CB1-49A1-B84A-66D181B4135C.jpeg

User avatar
Dbug
Site Admin
Posts: 2724
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Re: Wolfenstein / DOOM for Oric : has this been done?

Post by Dbug » Wed Mar 28, 2018 7:51 pm

It's a toy attempt I did 17 years ago during a weekend based on some released C example source code :)

It was mostly my way of saying that "but I did not find any indication that anyone attempted to at least make a technical demonstration of these games on the Oric." was not a correct statement :)

ThomH
Flying Officer
Posts: 147
Joined: Thu Oct 13, 2016 9:55 pm

Re: Wolfenstein / DOOM for Oric : has this been done?

Post by ThomH » Wed Mar 28, 2018 8:03 pm

Haha, so the amount of time I spent persuading myself that it's really a multiply by cosine rather than a divide was actually a substantial proportion of the original time spent on the demo!

I should spend my time firing up an assembler rather than drawing pictures.

User avatar
Chema
Game master
Posts: 2296
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Re: Wolfenstein / DOOM for Oric : has this been done?

Post by Chema » Wed Mar 28, 2018 8:09 pm

This is very interesting... do you reckon it is possible to do some kind of FPS game on the Oric??

I've seen the doom (?) speccy version and, while it is an incredible technical achievement, I don't see it as really playable. And the Z80 allows for some more CPU intensive things. Besides I think it was designed for the 128k model, which can change the screen memory on the fly, allowing fast double buffering...

ThomH
Flying Officer
Posts: 147
Joined: Thu Oct 13, 2016 9:55 pm

Re: Wolfenstein / DOOM for Oric : has this been done?

Post by ThomH » Wed Mar 28, 2018 8:35 pm

I guess you could use a small window and squeeze a double buffer into text mode, but I guess then you're probably at 64x48 or somewhere around that? I strongly suspect that's the equivalent of what the Vic Doom is doing, from looking at the window size.

Otherwise all I can think of is keeping the walls so that there's only a single colour per column, and using a comparison of each frame's new span list to the previous to cut actual drawing time down to the absolute minimum. It doesn't bode well for trying to add non-wall objects though.

Hopefully somebody else has a better idea?

User avatar
NekoNoNiaow
Flying Officer
Posts: 143
Joined: Sun Jan 15, 2006 10:08 pm
Location: Montreal, Canadia

Re: Wolfenstein / DOOM for Oric : has this been done?

Post by NekoNoNiaow » Thu Mar 29, 2018 5:26 am

Dbug wrote:
Wed Mar 28, 2018 7:51 pm
It was mostly my way of saying that "but I did not find any indication that anyone attempted to at least make a technical demonstration of these games on the Oric." was not a correct statement :)
Indeed my search was not thorough enough. ;)

I must admit I need a refresh on some details Thom. I did read the Wolfenstein and Catacomb sources when I contemplated ported these to the A500 but the memory is not fresh enough in my mind that I can comment sensibly on all of your points (forward-rendering, run-slice). I would need a piece of paper to draw a few diagrams on before I can comment on these matters. ;)

Do you have pointers to what you call run-slice? I assume you are referring to a particular algorithm but a cursory search does not give any useful results.

I think most of the focus would be on the rendering routine, as you said, geometry would be sparse so drawing time will dominate the effort by a wide margin.

One problem notably with rendering vertical spans one after another is that if working in HIRES mode then the display is essentially a 1bp bitmap from the point of view of the drawing routine so every screen byte which needs to be filled with span pixels will essentially be written to six times and read 5 times. Sure, it is not necessary to write to the entire screen but this nevertheless requires 6+5=11 times the bandwidth of a chunky pixel mode such as VGA 256 colors.

240 * 11 read/write cycles = 2640, so even assuming a ridiculously unrealistic average height of four pixels per span, the code would need to be fast enough to read/write 2640 * 4 = 10560 bytes per frame. Which is likely out of reach already, so horizontal resolution needs to be severely limited in order to cover the whole screen horizontally. (Unless I am miscalculating, please correct me if that is the case.)

Resolution could be made variable, increasing for columns closer to the center of the screen, where the attention of the player will be centered anyway. Starting with 6 pixels wide columns on the edges of the screen would allow fast(er) rendering of the less interesting areas.

As for higher resolution spans I think I have a few ideas which might speed up merging them together without incurring too much of a penalty but I would need to test them with a prototype first.

It is hard at this stage to know what could be made to fit in one frame though, as Thom said, we might have to fire the assembler. :D

User avatar
NekoNoNiaow
Flying Officer
Posts: 143
Joined: Sun Jan 15, 2006 10:08 pm
Location: Montreal, Canadia

Re: Wolfenstein / DOOM for Oric : has this been done?

Post by NekoNoNiaow » Thu Mar 29, 2018 5:31 am

ThomH wrote:
Wed Mar 28, 2018 8:35 pm
Otherwise all I can think of is keeping the walls so that there's only a single colour per column, and using a comparison of each frame's new span list to the previous to cut actual drawing time down to the absolute minimum. It doesn't bode well for trying to add non-wall objects though.
Rendering objects and walls on different scanlines seems like a potential compromise.
"Objects" scanlines could be rendered using only paper color changes (so 6 pixels granularity) and switch to bitmap data to render objects.
This would both give some color to the walls but also allow for an outline for objects which could help them be more visible against a possibly very noisy 1 bit background.

User avatar
Dbug
Site Admin
Posts: 2724
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Re: Wolfenstein / DOOM for Oric : has this been done?

Post by Dbug » Thu Mar 29, 2018 7:05 am

Regarding the performance that can be achieved, it's really all a question of what you want it to look like :)

Basically the key points are:
- How "high def" should it be
- Do we want fine details (textures, recognizable logos or patterns)
- What about shading (dithering or color change based on distance or light sources)
- What about colors (walls vs sprites, ...)

There are many ways to achieve that, could be in HIRES; could be in TEXT, could be using alternate lines for walls and sprites to limit color clashes, could be using AIC to suppress clashes entirely.

In my test, all the magic code is in "gencode.s" and "_DrawCompleteColumn" which basically is a generated lists of "sta" which draws each column in two sections, one doing the walls, one doing the roof and floor, by jumping directly at the right location in the code to avoid time wasted in loop unrolling.

It would be easy to modify it to use a combination of "sta" and "sty" to display a two value dithering pattern without any performance impact.

ThomH
Flying Officer
Posts: 147
Joined: Thu Oct 13, 2016 9:55 pm

Re: Wolfenstein / DOOM for Oric : has this been done?

Post by ThomH » Thu Mar 29, 2018 6:09 pm

NekoNoNiaow wrote:
Thu Mar 29, 2018 5:26 am
Do you have pointers to what you call run-slice? I assume you are referring to a particular algorithm but a cursory search does not give any useful results.
Oh, sorry — it's actually the much lesser-seen Bresenham algorithm. Much easier to derive though:

If the target line is (x, y) and, for agument's sake, x is greater than y, compute:

Code: Select all

run = x / y
error = x % y
Then you're going to draw a bunch of horizontal runs that are either 'run' in length or 'run+1', depending on the accumulation of error. The extremely naive version would be:

Code: Select all

working error = run / 2	; you're looking to transition each time error crosses 0.5 — where rounding should change — so bias the counter
while y--:
    working error -= error
    if working error < 0:
        draw 'run+1' pixels as a horizontal slice on the current line
        working error += run
    else:
        draw 'run pixels'

    move to next line
And apply standard Bresenham observations about symmetry as to dealing with y > x and various different signs of things.

So classic Bresenham makes a decision every pixel with negligible setup cost. Run slice makes a decision only every line, but incurs a setup cost. In a generic line drawing algorithm you'd probably switch between them based on a heuristic like major axis length is at least 8 pixels, major axis length is at least double minor. I'm asserting that for plotting Wolfenstein/Doom-esque wall edges in a low-geometry world, it's very rare that ordinary Bresenham will be the better choice.

(aside: approximately 8 pixels of classic Bresenham is also approximately the cost of an 8x8 divide with remainder, because the inner loops are very similar)
NekoNoNiaow wrote:
Thu Mar 29, 2018 5:26 am
One problem notably with rendering vertical spans one after another is that if working in HIRES mode then the display is essentially a 1bp bitmap from the point of view of the drawing routine so every screen byte which needs to be filled with span pixels will essentially be written to six times and read 5 times. Sure, it is not necessary to write to the entire screen but this nevertheless requires 6+5=11 times the bandwidth of a chunky pixel mode such as VGA 256 colors.

240 * 11 read/write cycles = 2640, so even assuming a ridiculously unrealistic average height of four pixels per span, the code would need to be fast enough to read/write 2640 * 4 = 10560 bytes per frame. Which is likely out of reach already, so horizontal resolution needs to be severely limited in order to cover the whole screen horizontally. (Unless I am miscalculating, please correct me if that is the case.)
The only optimisation I can think to offer is that if you're doing sufficiently low-resolution textures (or no textures at all) and have space for RLE versions of every slice at every scale, and are building your list of spans ahead of time, you can do what amounts to a merge sort to write six spans at a time. As in something like:

Code: Select all

list_pointers[6] = { proper texture slice at proper scale for column 1, that for column 2 ...}
output byte = background colour

while not yet at bottom of display:
    next_event = min of head of all things beyond list_pointers[6]
    while(output y < next_event):
        write output byte
        increment y
    apply change [i]or changes[/i] to byte as dictated by event location, increment those list pointers
I'm sure there are algorithmically better ways to find the next event, like a priority queue, but I think that this probably falls under the umbrella of lower complexity algorithms often actually being slower for very small data sets for practical reasons.
NekoNoNiaow wrote:
Thu Mar 29, 2018 5:31 am
Rendering objects and walls on different scanlines seems like a potential compromise.
I think that's what the Vic Doom is doing?
NekoNoNiaow wrote:
Thu Mar 29, 2018 5:31 am
"Objects" scanlines could be rendered using only paper color changes (so 6 pixels granularity) and switch to bitmap data to render objects.
This would both give some color to the walls but also allow for an outline for objects which could help them be more visible against a possibly very noisy 1 bit background.
I think that's the best solution! Objects are x6, and deliberately sparse.

User avatar
Xeron
Emulation expert
Posts: 385
Joined: Sat Mar 07, 2009 5:18 pm
Contact:

Re: Wolfenstein / DOOM for Oric : has this been done?

Post by Xeron » Thu Mar 29, 2018 10:22 pm

Our, to avoid fisheye, you just add a constant to all your distances, iirc. Simples.

User avatar
NekoNoNiaow
Flying Officer
Posts: 143
Joined: Sun Jan 15, 2006 10:08 pm
Location: Montreal, Canadia

Re: Wolfenstein / DOOM for Oric : has this been done?

Post by NekoNoNiaow » Sat Mar 31, 2018 6:44 am

ThomH wrote:
Thu Mar 29, 2018 6:09 pm
So classic Bresenham makes a decision every pixel with negligible setup cost. Run slice makes a decision only every line, but incurs a setup cost. In a generic line drawing algorithm you'd probably switch between them based on a heuristic like major axis length is at least 8 pixels, major axis length is at least double minor. I'm asserting that for plotting Wolfenstein/Doom-esque wall edges in a low-geometry world, it's very rare that ordinary Bresenham will be the better choice.
Oki, I would never have guessed you were talking about Bresenham. ;)
And indeed, I have rarely seen cases where classic Bresenham was a good general choice given its enormous per step cost, except for very small lines.
ThomH wrote:
Thu Mar 29, 2018 6:09 pm
The only optimisation I can think to offer is that if you're doing sufficiently low-resolution textures (or no textures at all) and have space for RLE versions of every slice at every scale, and are building your list of spans ahead of time, you can do what amounts to a merge sort to write six spans at a time. As in something like:
It took me some time (it is late, I should be sleeping :D ) to understand what you meant but I think I might grasp what you mean by RLE slices:
essentially, every vertical slice/span is stored as an RLE stream, taking advantage of the fact that close-up (or low-res) textures will repeat vertically for near-constant number of pixels (in that slice)
A merging loop then goes over six of these lists and updates the output byte as a function of the advancement in each RLE list.

That is an interesting idea indeed but I have a feeling that it will require a lot work to minimize the memory reads/writes needed to just update the state of the algorithm. This said, I also feel there might be room for mathematical trickery since the run lengths of each span will be fairly predictable.
Definitely worth exploring.
ThomH wrote:
Thu Mar 29, 2018 6:09 pm
I'm sure there are algorithmically better ways to find the next event, like a priority queue, but I think that this probably falls under the umbrella of lower complexity algorithms often actually being slower for very small data sets for practical reasons.
Could be, especially if the part "apply change or changes to byte as dictated by even location, increment list pointers" ends up requiring more read/writes than we save. ;)
Hard to say at this stage though.
ThomH wrote:
Thu Mar 29, 2018 6:09 pm
NekoNoNiaow wrote:
Thu Mar 29, 2018 5:31 am
Rendering objects and walls on different scanlines seems like a potential compromise.
I think that's what the Vic Doom is doing?
I just checked and it does not use this technique. It uses a very small window, with constant horizontal resolution and 1 pixel vertical resolution.
I could count up to six colors (the VIC20 can do 16). (For reference: https://www.youtube.com/watch?v=WFMM3F_-bx0)

But they likely use the "bitmapped" mode of the VIC20 which is actually a multicolor text mode where characters are organized in memory so that the code can treat it as a bitmap.

The Oric could do the same with text mode, this could have the advantage of allowing to invert the X & Y axis, thus reducing the amount of computations needed to draw vertically, especially If all bytes of a character are sequential in memory (I have not checked).
Xeron wrote:
Thu Mar 29, 2018 10:22 pm
Our, to avoid fisheye, you just add a constant to all your distances, iirc. Simples.
I actually love the fisheye effect and never understood why Carmack got rid of it.
It compensates for the fact that the player views the world through a very narrow window and kinda recreates the fact that humans have a 180 degrees horizontal field of view.
Combined with reduced resolution at the edges this would actually be quite faithful to how human vision works. ;)

User avatar
NekoNoNiaow
Flying Officer
Posts: 143
Joined: Sun Jan 15, 2006 10:08 pm
Location: Montreal, Canadia

Re: Wolfenstein / DOOM for Oric : has this been done?

Post by NekoNoNiaow » Sat Mar 31, 2018 6:51 am

Dbug wrote:
Thu Mar 29, 2018 7:05 am
Regarding the performance that can be achieved, it's really all a question of what you want it to look like :)

Basically the key points are:
- How "high def" should it be
- Do we want fine details (textures, recognizable logos or patterns)
- What about shading (dithering or color change based on distance or light sources)
- What about colors (walls vs sprites, ...)
Choose your compromises, choose your fate. (wink wink) ;)
Dbug wrote:
Thu Mar 29, 2018 7:05 am
There are many ways to achieve that, could be in HIRES; could be in TEXT, could be using alternate lines for walls and sprites to limit color clashes, could be using AIC to suppress clashes entirely.
AIC would imply HIRES right?
Dbug wrote:
Thu Mar 29, 2018 7:05 am
In my test, all the magic code is in "gencode.s" and "_DrawCompleteColumn" which basically is a generated lists of "sta" which draws each column in two sections, one doing the walls, one doing the roof and floor, by jumping directly at the right location in the code to avoid time wasted in loop unrolling.

It would be easy to modify it to use a combination of "sta" and "sty" to display a two value dithering pattern without any performance impact.
I have downloaded your code, will give it a look this weekend. ;)

Post Reply