Compileable version of Alien Breed 3D II - The Killing Grounds

[Karlos]

That's a potential workaround, but it would be nice to fix the root cause as the existing clipping is great when it works as expected.

Note that this was a common behavior, back in the day. So, it's understandable it behaves that way.

Given how extreme the overdraw is in these examples and the fact that it works for some positions in a zone and not others sways me towards this is a bug rather than a known implementation choice.

[VladR]

Originally Posted by Karlos

I have limited time so what I've been doing is creating simple levels and then hex dumping the level files to try and get more insight into the data. It's frustrated slightly by the fact that several of them (not all) are packed in that =SB= format and need to be decrunched first.

There's some structure poking after these are loaded too, but hopefully with a bit of patience we can figure out what the end runtime representation of the data is, and that should make interpreting the code easier.

OK, hard stop. Right here. You can burn through a lot of time deciphering the intent of the ASM code.

But if you have the PVS and level data, why don't you spend a single weekend implementing a simple 2D portal code on PC (DiretcX/SDL/whatever engine), inside say, Visual Studio ? You don't need full renderer for that - just the wireframe of the nodes (rooms).

And once you have a reference, high-level, C++ based portal code running, you can very quickly replace that entire part of the pipeline. Without having to spend so much time on slow debugging of poorly documented original ASM code.
It could literally stay as a C/C++ code and you would simply link it, manually. And later, once everything works, you could port it by hand to ASM in half day.

What do you think of that approach ?

[VladR]

Originally Posted by Karlos

That's a potential workaround, but it would be nice to fix the root cause as the existing clipping is great when it works as expected.

Yes, it would. But do you actually enjoy doing the hex debugging that much ?

The cost of writing a new visibility component might seem daunting at first, but since it's C/C++ and you debug it on PC, it can really be done during a single weekend.

Integrating with Amiga codebase might take a bit more, yes.

But you will suddenly have an opportunity to scale the engine radically, as you can simply later create better versions for 060 or RPi5, very quickly, in C (and just call different version at run-time based on some bool flag).

[Karlos]

Originally Posted by VladR

OK, hard stop. Right here. You can burn through a lot of time deciphering the intent of the ASM code.

...

What do you think of that approach ?

It's a good one. How soon can you get started?

That's more or less what I was alluding to a few posts back when I suggested that the mechanism could be replaced in theory.

[VladR]

Originally Posted by Karlos

It's a good one. How soon can you get started?

That's more or less what I was alluding to a few posts back when I suggested that the mechanism could be replaced in theory.

Yeah, it's actually quite tempting as I never wrote a portal-based SW rasterizer.

On the other hand, I don't want to promise much, because of few things:

• I got, like, dozens of projects in various stage of completion across 6-7 HW platforms
• The amount of free time right now is not very conducive to bigger projects
• which is why I recently spent time on OCS-based HiRes rasterizer, reusing a lot of older code for a certain compo, but since I was testing against emulator, and the code was crashing or glitching on an actual OCS HW, I'd have to implement OS-safe way of dealing with RAM/copper/etc., for which I ran out of time, as it's end of October (hence, next year)
• I need 250x more time I have now for the RTG-based Vampire game (to resume), so that one is out of question.

I could maybe help with smaller things here that need to be rewritten, but I certainly wouldn't consider trying to debug or comprehend an old ASM codebase with minimum comments - that to me brings no joy (been there, done that).


Is this engine used for some other games ? Or would all work that goes into this project contribute solely to AB 3D II ?

[Karlos]

Originally Posted by VladR

Yeah, it's actually quite tempting as I never wrote a portal-based SW rasterizer.

...

Is this engine used for some other games ? Or would all work that goes into this project contribute solely to AB 3D II ?

Alas no. It's just for the game. However, the ability to mod it is being slowly improved upon.

[VladR]

Originally Posted by Karlos

Alas no. It's just for the game. However, the ability to mod it is being slowly improved upon.

That's too bad.


I just went back few pages and re-read your description of how the renderer works and it's most definitely not a Portal-based engine, because if it was, it would be rendering front-to-back, not the other way around.

Correct me if I'm wrong, but looks like this is the high-level algorithm:

1. Grab List of all potential zones from the PVS pre-processing
2. Sort by Z (center of zone) : back-to-front
3. Clip&Render each zone

It's basically brute-force at its simplest. Of course, that in itself doesn't make it quick to decipher from ASM, merely quick to implement (from scratch)

[Karlos]

The clipping does seem to be portal like when it works, e.g. the nothing is rendered past the horizontal extents of a connecting space.

Running the Dev build and turning off wall either flat or shaded wall rendering, depending on what you are looking at, makes it very apparent that only the visible sections of adjoining zones are being rendered when the solution is working. It just seems to have a lot of failure case.

[VladR]

Originally Posted by Karlos

The clipping does seem to be portal like when it works, e.g. the nothing is rendered past the horizontal extents of a connecting space.

Running the Dev build and turning off wall either flat or shaded wall rendering, depending on what you are looking at, makes it very apparent that only the visible sections of adjoining zones are being rendered when the solution is working. It just seems to have a lot of failure case.

Right.

Unfortunately, portal-like clipping is not very helpful here given the drastic overdraw.

A portal-like engine (e.g. Duke Nukem's Build engine) renders front-to-back and completely avoids the overdraw cluster*uckery of Doom, completely bypassing the need for BSP Compiler, and as a bonus, giving you option of dynamic scenes.

An actual portal-like engine, in your particular test case, wouldn't draw all those rooms in the distance (only for them to get overdrawn by huge wall right in front of the player).

It would only draw whatever portion of the scene is visible through the door (the portal rectangle) - if (and only if) the door portal would be within the view frustum (and then all other polygons would be clipped against the portal polygon).

Have you seen Bisqwit's Portal vid ? He's got an amazing slow-mo of the Portal Traversal algo, wall by wall, starting at 13:42.

To avoid recursion, he's using circular queue, you can see that in the slow-mo, after each pass the next portals (red polygons) are added to the end of queue.

[ Show youtube player ]

Note that his test room is quite a complex case, with lots of small crevices under the stairs and such (plus pillars, plus top room, etc.) that would wreak havoc if they were sorted by simple center of polygon in a non-portal engine.

Note, at the end of the traversal, for those distant portals at the top of the stairs, where only couple vertical scanlines are visible, that only those particular scanlines are rasterized.

Nothing is wasted, yet it handles such complex case with ease.

Brutal Elegance

[Karlos]

Originally Posted by VladR

But do you actually enjoy doing the hex debugging that much ?.

I mean you say that but I think I'm becoming a bit of a hex addict...

[Angus]

Originally Posted by Karlos

I mean you say that but I think I'm becoming a bit of a hex addict...

Ah, yes the Weinstein defence.

[abu_the_monkey]

at some point I will have a look at the latest stuff but, work and home life is a little manic at the mo.

not sure I could offer much, but a fresh set of eyes mind.

[Karlos]

Busy also. I get bursts of time to look at stuff.

[VladR]

Originally Posted by Karlos

The clipping does seem to be portal like when it works, e.g. the nothing is rendered past the horizontal extents of a connecting space.

So, I just implemented a Portal-like SW rasterizer and, man, what a difference !

The front-to-back rasterizer is just awesome - there's no overdraw of invisible walls (that I can tell).

I was worried how would it work with the recursion - say when a room through which you can see into 4 other rooms pops into view, but portal handles that case extremely elegantly (by actually avoiding recursion in the first place!).

Just one simple visibility check for the portal XPOS bounds, and if the portal is out of screen, none of the other checks for other connected rooms happen!

Which is obvious, when you think about it - it's front-to-back after all.
I just spent so much time working with back-to-front algorithms in past, that my brain has been hardwired for Z-sorting, this just blows my mind


Another amazing thing, that just happened to be a by-product of the design, is a backface culling. Since the vertices are in clock-wise order, a simple condition (xp1 < xp2) is enough to determine backface culling!


And, of course, if you see only 6 pixels wide strip of the 600-px long wall through the portal, you only render those 6 pixels (not 600).

And there's no BSP cluster*uckery! And you can adjust the 3D mesh of rooms real-time without the offline pre-processing!

You could link windows to outer space or closet doors to caves - there's no real-world limitations - each portal is a separate entity that doesn't have to fit withint the same world-space bounds (as in a regular level editor).



I know you are enjoying your hex hacking, but this is waaaay more fun Just scrap the whole old component and rewrite new one in C

[Karlos]

So, hex hacking isn't just for masochistic kicks, there are still countless unnamed immediate structure offsets, weirdly named ad-hoc identifiers, pointers to pointers, global state and undocumented data in the level files that needs a light shining on it. Have a look at the old source folder to see whT I mean.

While the traversal and rendering code is relatively isolated, I don't think it's completely trivial to replace it just yet - there will be all kinds of screws and bits and pieces left over. Once it's tidied up enough, we can think about replacing it, if that becomes necessary

[GWhizz]

Excellent Job

[GWhizz]

Awesome

[Karlos]

@VladR

Just one simple visibility check for the portal XPOS bounds, and if the portal is out of screen, none of the other checks for other connected rooms happen!

Which is obvious, when you think about it - it's front-to-back after all.
I just spent so much time working with back-to-front algorithms in past, that my brain has been hardwired for Z-sorting, this just blows my mind

That and the rendering of visible sections only is the key point of portal rendering. However you do still need to care about other things that this approach alone doesn't help with. For one, to operate this in a 2.5D screen space, you have to transform your entire level and know where the screen space horizontal extent of each zone (at least those in front of the player) in order to know if they overlap your on screen portal or not. TKG supports 250+ zones with 800 points, which isn't that much for any half modern CPU, but on a real 68030 you don't want to be doing that much transformation.

This is why the precalculate PVS data that says which zones are theoretically visible from the current zone is still important. You only need to transform those before testing against your portal algorithm.

[VladR]

Originally Posted by Karlos

@VladR



That and the rendering of visible sections only is the key point of portal rendering. However you do still need to care about other things that this approach alone doesn't help with. For one, to operate this in a 2.5D screen space, you have to transform your entire level and know where the screen space horizontal extent of each zone (at least those in front of the player) in order to know if they overlap your on screen portal or not. TKG supports 250+ zones with 800 points, which isn't that much for any half modern CPU, but on a real 68030 you don't want to be doing that much transformation.

This is why the precalculate PVS data that says which zones are theoretically visible from the current zone is still important. You only need to transform those before testing against your portal algorithm.

Well, of course I wouldn't be doing 3D transform on an entire level. That'd be insane

Depending on how much time you have, there's many solutions for this, here's just first 5 from the top of my head:

1. [1 hour] Manhattan Distance check

foreach (sector S in LevelSectors)
  if (Distance (S.Center) < ThresholdDistance)
    PVS.AddIfNotPresent (S.SectorIndex)

This would reduce the transform to only fixed distance Manhattan "radius" from player (regardless of level size). Not bad for almost zero work. And Manhattan distance doesn't use any muls, just add/sub.

2. [2-4 hours] X-levels deep Node traversal (Breadth-First Search)

• for each sector you insert its children, then children children, then repeat 2-3 more times.
• number of times of the loop depends on how many sectors does the straight line go through
• unless the levels contain long chained corridors, where you can see through 5-6 rooms from where you are standing (not the case usually), a depth of 3-4 should be enough

3. [1 day] Quadtree

• 4 levels of Quadtree will give you a factor of (16x16) = 256 times less checks
• quadtree can be very useful for great many other things

4. [2 days] Loose Octtree

• this would tightly follow the contours of the level, thus removing unnecessary splits and checks for areas that contain no sectors
• probably not really necessary, but it does reduce the checks, so it's probably worth spending 1 more day on this

5. [3-5 days] Actual visibility test for each portal

• you cast rays in a circle (from the portal center) and record any portals the ray intersects
• can be run-time (during loading time)
• most precise solution as it detects the actual visible nodes
• this is the most precise, obviously

[Karlos]

You know where the repo is. Now git forking!

Well, of course I wouldn't be doing 3D transform on an entire level. That'd be insane

I mean you say that, but there's also a rotating auto map. This seemingly does rotate the entire level when it's active but I think it's not a full 3D transformation, just translate/2D rotate and scale.