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

[Karlos]

Originally Posted by Karlos

What I don't get is, why wouldn't you just convert Lvl_ZoneAddsPtr_l into a straight list of pointers after loading the level data by adding Lvl_DataPtr_l to each element?

Then you can save the extra address addition step wherever you dereference.

Well that was a suspiciously easy improvement to make. It's now Lvl_ZonePtrsPtr_l, or in C parlance Zone **.

[abu_the_monkey]

Originally Posted by Karlos

Well that was a suspiciously easy improvement to make...

Good work, as ever

Originally Posted by Angus

Immediately thinks of conversation between Spock and Kirk, in The Wrath of Khan.
"Take us down, Mr Sulu, 300 metres."


..... sorry.

[Karlos]

Originally Posted by abu_the_monkey

Good work, as ever

Still haven't solved the actual PVS issue(s). I think that once all the level data, as represented at runtime is fully deciphered, it might be more achievable.

[Dunny]

FWIW I used your KarlosTKG engine to run the original levels (and then copied/modified the scripts so I can have the best of both worlds) and it's bleedin' marvellous what you chaps have done, it really is.

The official(?) RTG patch doesn't run well at all on a fast PiStorm - the first door won't open if you don't slow it down enough. KarlosTKG breezes right through.

[Karlos]

Just to be clear, there is no karlostkg engine. I just build pipper's (or some experimental version in my fork) and include that. KarkosTKG is just a game modification.

[Karlos]

Surprise finding of the day:

While debugging the various runtime data representation and PVS issues, my attention was drawn to what appears to be a zone ID list embedded in each zone (see https://github.com/0xABADCAFE/alienb...ce/defs.i#L332). The interpretation of this is a negative terminated list of words, evidenced by code motifs like this, examples of which occur in a few places:

	lea		ZoneT_ListOfGraph_w(a0),a0
.doallrooms:
	move.w	(a0),d0
	blt.s	.allroomsdone

I thought this might be related to the clips code as it's referenced from there.

I've added the ability to dump the zone structure during the PVS trace and to my surprise, the list only ever seems to contain the current zone itself, followed by -1 (which terminates iteration). There may be examples to the contrary, but I have yet to find one.

It is of course possible that some runtime behaviour changes this, perhaps the lists grow as the level is played, but if it turns out to be invariant, I have to wonder what it's for at all, given that the zone ID is the first member in the zone structure.

[Karlos]

It seems like there are some varying length word lists that live just before the zone itself in memory separate from the list described above. These are accessed via a word offset that's always negative. Coming from a C background, I find this somewhat odd but I guess it is what it is.

I've not found any occurrence of the previous list changing so I'm going to add a check that runs each frame and just compares the first element to the zone ID and the next to -1, for every zone. If it finds one that doesn't have this behaviour it will dump that zone.

I'm starting to suspect the list in question is some unfinished feature or vestigial left over from AB3D1. If it never changes, the code that depends on it can be changed to just use the embedded zone ID and avoid the looping.

[Karlos]

Originally Posted by Karlos

It is of course possible that some runtime behaviour changes this, perhaps the lists grow as the level is played, but if it turns out to be invariant, I have to wonder what it's for at all, given that the zone ID is the first member in the zone structure.

Well it turns out I misinterpreted the data because I was too keen to stop on -1. However, examining what the code in assign_clips does, I realise it's not a simple list at all. It's a list of 4 word tuples that only ends on the first tuple that has -1 for it's first word. The first word in each tuple is a zone ID, the successive words are something to do with clipping.

The overall array, however, is the (unordered) PVS for the zone it is attached to.

[abu_the_monkey]

@Karlos

sounds like you are making some good progress here

[Karlos]

Originally Posted by abu_the_monkey

@Karlos

sounds like you are making some good progress here

It's going to need some documenting, that's for sure. I'm not totally sure what the tuple structure is, beyond the first element being a zone ID and the second being some clipping related index. The next word after that always seems to be zero (haven't exhaustively tested that) and the last word, well I'm not sure.

[Karlos]

Something else to consider is that the zone ordering that happens at runtime seems to be independent of the players exact position*. If it's truly independent then I'm not sure why we are doing it at runtime at all. We could just work it out and reorder the embedded PVS list in each zone accordingly.

One thing at a time, mind.

*Correction: It's not independent. It just doesn't depend strongly enough for small movements to affect the end outcome.

[grond]

Originally Posted by Karlos

Something else to consider is that the zone ordering that happens at runtime seems to be independent of the players exact position. If it's truly independent then I'm not sure why we are doing it at runtime at all. We could just work it out and reorder the embedded PVS list in each zone accordingly.

Does the engine rotate the wall coordinates around the player or does it rotate the player view vector with player movement? If it is the latter, the data you are looking at might appear static but would be processed differently in some subroutine that considers the play view vector.

[Karlos]

Originally Posted by grond

Does the engine rotate the wall coordinates around the player or does it rotate the player view vector with player movement? If it is the latter, the data you are looking at might appear static but would be processed differently in some subroutine that considers the play view vector.

No. In fact, I already skip the OrderZones call per frame because it's so invariant. I originally had it running when, and only when the player's zone changes (you can probably find that discussion a few thousand pages back), but it turns out that wasn't robust enough - there were cases where crossing zones didn't seem to correctly trigger the call. So as a half-way measure, I do it based on the player's overall coordinate changing by more than some delta. See here: https://github.com/0xABADCAFE/alienb...rderzones.s#L9

When playing the dev build, the OZ count in the small window view is how many iterations of the orderzone code happened in the frame. You can see it's zero when standing in any one place (regardless of orientation) and updates every few frames as you move around.

[Angus]

Originally Posted by Karlos

You can see it's zero when standing in any one place (regardless of orientation) and updates every few frames as you move around.

I know nothing and should keep quiet, but.... related to the mapping in some obscure way?

[Karlos]

Originally Posted by Angus

I know nothing and should keep quiet, but.... related to the mapping in some obscure way?

It's part of the overall rendering solution. I can summarise:

1) The game map is made of "zones". In the map, a zone is a convex 2D shape. There's a formal definition to convex in this context, but the simplest way to think about it is that if you walked around the edge of the zone, at each corner you'd always turn in the same direction. So a triangle is always convex.

2) Zones can be joined together along an edge to make more complex shapes that don't have to be convex overall. Any room, corridor or courtyard in the map will be made of one or more zones sharing edges.

3) The player can only be standing in one zone at a time. It is possible to determine, ahead of time (when the map is built), which other zones in the map have any line of sight visibility from any given zone. This is the what I have been referring to as the "PVS", which is the Potentially Visible Set.

4) The game only has to consider these PVS zones for the player, it can ignore the rest. This is the most essential optimisation the engine because the fastest graphics are always the things you don't draw.

5) The game needs to work out which bits of the PVS are actually visible and render them. One part of that process is to arrange the zones in the set by distance. The game does this to minimise "overdraw". This is when you draw something, only to end up drawing over it again in a later step. This, as you can imagine, is very wasteful.

It is that last bit we are talking about just now. Ordering the zones in the PVS by their "distance" isn't affected by the player orientation, and it also doesn't seem to be affected by the player's position* within the zone. The latter aspect was a surprise to me, because I would absolutely expect it to. It is of course possible I've misinterpreted and it does somehow factor in the position, in which case even the optimisation I have now is basically invalid.

Correction:
* I have found out where in the code it does consider the player position:

https://github.com/0xABADCAFE/alienb...erzones.s#L179 - here

xoff and zoff in this code are the player coordinate.

The optimisation to skip zone ordering is still valid when the player has not moved much within a zone since, while the distances of the zones do change it rarely affects the outcome. If I move six inches in my house, the distances to each of the rooms has changed but the probability the ordering of the rooms by distance has changed is extremely small.

[Angus]

Thanks for the summary, Karlos. I'm still hugely impressed by what you guys are achieving and the expertise used to achieve it.

[Karlos]

Originally Posted by Angus

Thanks for the summary, Karlos. I'm still hugely impressed by what you guys are achieving and the expertise used to achieve it.

I have corrected the previous post with the findings for when I end up having to come back to this

[Karlos]

Back to the problem at hand, parts of the PVS are rendered and then overdrawn by what's closer in certain cases. What I've been able to determine thus far about it is:

1) It always does this though a closed door or raised lift. Lots of people noticed slowdowns near closed doors that seemingly improved when the door opened. The reason is that when the door is closed, everything behind it gets drawn, then the door gets drawn over the top.

2) Chunks of the PVS that should not be visible, become visible depending on how they are connected to the player zone. This is the one that is really grinding my gears and proving hard to get to the bottom of.

However, in the process I'm learning a lot more about the runtime representation of the game data and at some point, I am sure the root cause will be found and it will be fixable.

Fixing it is likely to bring significant performance improvements on slower machines since drawing stuff in TKG is more expensive than your typical texturemapped 2.5D game thanks to all the fancypants shading.

Once it is fixed, I intend to go back to the task of enhancing the modding experience for the purely selfish reasons of wanting my mod to be better.

[VladR]

I am back from hiking vacation and recovering from Covid I caught in the middle of woods (a very inconspicuous place to catch Covid ) and will see if I can catch up with your progress and hopefully , perhaps, offer some help here.

[VladR]

Originally Posted by Karlos

Back to the problem at hand, parts of the PVS are rendered and then overdrawn by what's closer in certain cases. What I've been able to determine thus far about it is:

1) It always does this though a closed door or raised lift. Lots of people noticed slowdowns near closed doors that seemingly improved when the door opened. The reason is that when the door is closed, everything behind it gets drawn, then the door gets drawn over the top.

2) Chunks of the PVS that should not be visible, become visible depending on how they are connected to the player zone. This is the one that is really grinding my gears and proving hard to get to the bottom of.

However, in the process I'm learning a lot more about the runtime representation of the game data and at some point, I am sure the root cause will be found and it will be fixable.

Fixing it is likely to bring significant performance improvements on slower machines since drawing stuff in TKG is more expensive than your typical texturemapped 2.5D game thanks to all the fancypants shading.

Once it is fixed, I intend to go back to the task of enhancing the modding experience for the purely selfish reasons of wanting my mod to be better.

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

The fix is actually easy - you simply check the visibility of all Nodes (rooms) against the bounding box/clipping polygon of the portal (e.g. door).
Given this is a portal-based engine, I assume it must have this kind of check (intersection between portal and polygons of a room) implemented already, correct ?

Of course, doing that will:

• instantly drop your average framerate (this will now become a new component of the rendering pipeline)
• raise your bad/worse framerate (you are not drawing invisible rooms)

That's a trade-off you can decide on after you extensively benchmark both cases (turned on and off).