Jump to content
Search In
  • More options...
Find results that contain...
Find results in...
Sign in to follow this  
entryway

Immediate noclip at level start

Recommended Posts

Maes said:

Essentially the Doom engine ruins what were perfectly adequate unsigned 9-bit integers by interpreting them as signed. Fail.



I wouldn't call something 'fail' that was unthinkable 18 years ago, When Doom was developed nobody could ever imagine maps getting as large as some are now.

Well, anyway, I have always considered anything beyond -16383,16383 fundamentally unsafe when it comes to coordinates so in the end this is merely a fix for maps that exceed the bounds of stability.

Share this post


Link to post
Graf Zahl said:

Well, anyway, I have always considered anything beyond -16383,16383 fundamentally unsafe when it comes to coordinates so in the end this is merely a fix for maps that exceed the bounds of stability.


-16383,16383 is also unsafe. I can't kill imp on map within this range (Memories) even with two ssg shots. I have moved submap29 to the left (now it is within -16k..+15k) and looks like I can kill imps again.

Share this post


Link to post
Graf Zahl said:

I wouldn't call something 'fail' that was unthinkable 18 years ago, When Doom was developed nobody could ever imagine maps getting as large as some are now.


Maybe not a fail from from a practical standpoint (map size), but it certainly was a fail from a logical and numerical standpoint: unlike hardcoded limits such as limited visplanes etc., this was simply a result of neglecting basic binary arithmetic.

Graf Zahl said:

Well, anyway, I have always considered anything beyond -16383,16383 fundamentally unsafe when it comes to coordinates so in the end this is merely a fix for maps that exceed the bounds of stability.


That particular limit doesn't stem from the blockmap itself at all. Blockmap calculations can be done at 100% accuracy for normal projectiles, things, line intercepts etc. as long as the extended blockmap index fix is in place, unless you have a single object with a radius that encompasses a distance range greater than -16383,16383. Then the fixed_t calculations would fail, but if you could do them with greater accuracy the extended blockmap fix would be able to accomodate them with no problem.

E.g. if you could properly do a 32K- (-32K) operation which would result in a distance of 64K, the extended blockmap fix would correctly interpet this distance as 512 bmap blocks (top bits all ones).

The real bitch to fix is ApproxDistance: that one actually controls melee range, missile range, player locating by monsters, line-thing slides, missile targetting etc. and it's mathematically obvious how the -16383,16383 limit hurts it a lot.

Share this post


Link to post

It will take me a while to check the patch (I'm not used to reading SVN patches) but I can give you a list of the functions I changed:

P_SetThingPosition
p_CheckThingPosition
P_PathTrasverse
P_RadiusAttack
P_TeleportMove
P_UnsetThingPosition
P_GroupLines
A_VileChase

Edit: seems you got them right (some functions are Boom-only, no Mocha analogues yet :-). Do you have a particular test map we can test it with? I can only certify that non-hitscan attacks and item pickups/mobj collisions do work reliably e.g. on your test map or on the northern cliff of europe.wad.

I do have some problems with hitscan attacks though (e.g. I can't shoot the west wall in test272.wad unless I go into the block containing it). The reverse does work however (shooting east from west).

We need a ridiculously large map with repeated pillars/monsters/item pickups all over it for testing :-p

Doombuilder 1 however is unstable when you exceed a certain map dimension :-(

Share this post


Link to post
Maes said:

I do have some problems with hitscan attacks though (e.g. I can't shoot the west wall in test272.wad unless I go into the block containing it). The reverse does work however (shooting east from west)

Yes

Share this post


Link to post

The most probable source of trouble seems to be P_PathTrasverse: there are a lot of (x2-x1) type of operations done in there, and we know how "well" those can turn out. Even with correct blockmap indexes, those will remain incorrect on too large distances.

The only way to fix it would be to blow those operations internally to greater precision.

Edit: yup, that's the cause. In the case of your simple test map, when doomguy is firing at the east wall ahead of him the PathTrasverse calculation calls the SafeBlockX function with a negative argument, when it shouldn't have.

Doomguy's actual x2 position: 14175.984375
bmaporgx:-20992.000000
Computed difference x2-=bmaporgx: -30368.015625 which is WRONG (should be 35237.984375). This causes even the getSafeBlock functions to return a negative index when a positive one should be returned (that is, if you passed it a positive x2 value).

However, if you could compute it properly at that point (maybe a new, specialized FixedAbsDiff function that returns only unsigned 16.16 numbers with a 0...65535.65535 range?) and you passed the unsigned 0...64K value to the existing getSafeBlock functions, it would be fixed, at least in that point of the code, and the correct extended blockmap address would be returned.

The reason why there are no problems shooting from the other direction are a bit more complex to explain, but they have the same root cause.

The catch is that you'd have to discern between "negative values that originate from within the blockmap" (and are thus wrong) and "negative values that occur because the player is outside the blockmap" (which should be preserved in order to allow targetting in the void). Mixed cases should be a conundrum...ahhh, good old fixed_t ;-)

Share this post


Link to post
entryway said:


Something like that, but there are other subtleties as well. E.g. I'd replace the FixedDiv (y2-y1,abs(x2-x1)) expressions with a specialized function that does (b-a)/abs(d-c), by taking into account internal overflows as well.

I gotta see if fixing just the blockmap addressing part would be enough.

P.S.: don't you ever sleep? :-p

Edit: Yeah, using longs for that particular place does fix the blockmap indexes, however there's the problem of all the other y2-y1, x2-x1 etc. calculations. Those remain wrong even after getting the blockmap indexes right if you still use fixed_t for the rest of the calculations.

I am using this function:

    public final int getSafeBlockX(long blockx){
    	// Interpret as positive if positive
    	if (blockx>0){
    		blockx>>>=MAPBLOCKSHIFT;
    		return (int) blockx;
    		}
    	else {
    		blockx>>=MAPBLOCKSHIFT;
    		return (int) blockx;    		
    	}
    }
As a guide, when you shoot parallel to the x/y axis, a line is traced between your current position and a map block up to 16 positions away (e.g. shooting from your starting position straight ahead, you should get a maximum trace from block _x1,_y1: 266,0 to _x2, _y2: 282,0 (2048 units, hardcoded hitscan/autoaim range).

Shooting from the opposite direction, you should get a trace from block (268,0) to (252,0). By strafing full left then turning 90 degrees right from the start and shooting the south wall, you should get a trace from (266,1) to (266, -15).

In principle, this part of the deal seems to work correctly without wraparounds or other funky effects, so any further problems must occur further down. I'd analyze the ystep/xstep stuff next.

I believe the problem will be ultimately solvable, but that the resulting P_PathTrasverse function will be so different and full of hacks that it will make more sense to have two of them: one normal, and one specifically to deal with extended maps, in order to preserve performance when you don't need all this fudging.

Share this post


Link to post

Great news entryway, adapting your proposed solution seems to work (I used the above getSafeBlock function though, no idea what your 64 version looks like). I can now shoot and get puffs in all 4 directions in the test room, and it appears to preserve demo compatibility. It's not even that full of hacks, after all ;-)

For any port authors that want to do this themselves, the extended precision _x1,_y1,_x2,_y2 coordinates shown in entryway's snippet relative to the blockmap's origin only need to appear in the blockmap calculations, and in the yintercept/xintercept calculations. Nowhere else. I saw that they can be omitted from the partial/xstep/ystep calculations as well with no change in functionality, so the less 64-bit stuff being used, the better.

So...now to test it in a full-scale, deliberately limit-breaking map ;-)

Share this post


Link to post
entryway said:

It was the same as P_GetSafeBlockX, but with int64 argument. I've removed it:
http://pastebin.com/8N5azytS

Correct?


Yes, your inlined version tested out correctly even when backported to Mocha. I noticed that you don't need the mapxl/mapyl variables (they work fine even if you use x1,x2 and not _x1,_x2), so if you want to shave some CPU cycles by not using 64-bit longs unnecessarily...

I also tested a version of the original getSafeBlockX with a long/int64 argument, preserving the 0x1FF hack, and it worked just fine as the sign-discerning version or as doing no sign/ANDing (but only if used in PathTrasverse). No obvious demo desyncs even with the extended blockmap trick on, at least for Mocha Doom.

Share this post


Link to post
Maes said:

I noticed that you don't need the mapxl/mapyl variables (they work fine even if you use x1,x2 and not _x1,_x2), so if you want to shave some CPU cycles by not using 64-bit longs unnecessarily...

Does not work witout mapx1/y1 (it is used in xintercept/yintercept too)

Share this post


Link to post
entryway said:

Does not work witout mapx1/y1 (it is used in xintercept/yintercept too)


http://pastebin.com/HK2JWJCF

*shrug* had no problems keeping x1/y1 for those calculations, but maybe I didn't look hard enough. Didn't give me any problems in test272.wad or Europe.wad. Can you provide a specific instance/map where they cause stuff not to work?

Share this post


Link to post
Maes said:

yintercept = (int) ((_y1>>MAPBTOFRAC) + FixedMul (partial, ystep));


(_y1>>MAPBTOFRAC) == mapy1
I just use it in both places, you calculate it twice (_y1>>MAPBTOFRAC for 'yintercept' and y1>>MAPBTOFRAC for 'partial')

Share this post


Link to post

Hmm yeah I see it now. Okey dokey, adopting fix ;-)

Share this post


Link to post
Maes said:

Hmm yeah I see it now. Okey dokey, adopting fix ;-)

Is there an easy way to detect necessity of int64 math (which will lead to desynches)?

Share this post


Link to post
entryway said:

Is there an easy way to detect necessity of int64 math (which will lead to desynches)?


Yes: check if x1/x2 -bmaporgx or y1/y2 -bmaporgy operations result in an overflow/underflow, aka if they are more than 32K units apart (which can't be expressed in fixed_t). An easy way to do this is to see if the same operations done with fixed_t and int_64 math give the same results, bitwise (after you cast the fixed_t result to int_64). If not, then you have an anomalous situation.

P_PathTrasverse seems to be the only place in the code where this matters (so far), so you can detect potentially erroneous situations by checking for this particular kind of overflow/underflow. How you handle them afterwards, is up to compatibility/user preference/desire to play very large maps correctly.

Share this post


Link to post
Maes said:

An easy way to do this is to see if the same operations done with fixed_t and int_64 math give the same results, bitwise (after you cast the fixed_t result to int_64). If not, then you have an anomalous situation.

Not really easy. I'll leave it as is.

Now I need nice user-friendly option name for this



Can you suggest any?

Share this post


Link to post

If you mean a check to determine it preemptively during map loading and not during runtime, then the mere presence of a blockmap with even one dimension > 255 or the existence of a maximum distance between the map's bounds exceeding 32K units should be enough to sound the alarm (and maybe give the player a warning that the map he's about to play requires extended blockmap support in order to play glitch-free, unless the user knows what he's doing and wants to leave it disabled).

Specifically, both your test map and Europe.wad should generate a warning.

As for the name...well, "512x512 Blockmap support", "Extended Blockmap Support" or "Support Large Blockmaps" sound about right. The blockmap isn't really "fixed", it's simply interpreted as it should have been ;-)

Or you could even call it "Fix clipping problems in large levels". Doesn't get more user-friendly than that ;-)

Share this post


Link to post
Maes said:

Or you could even call it "Fix clipping problems in large levels". Doesn't get more user-friendly than that ;-)

^^ This

Those options can be changed in runtime, but they are not applied during demorecording/playback

Share this post


Link to post
entryway said:

We only could 'fix' it for all complevel if doom/boom would crash on such situations (then we 'just' fix a crash)

how about enabling the fix if non-vanilla nodes are detected then?

Share this post


Link to post
tempun said:

how about enabling the fix if non-vanilla nodes are detected then?

PrBoom-Plus supports DeePBSP v4 extended nodes and ZDoom's uncompressed extended nodes about 1.5 years (since 2.5.0.7). Hence we can't suddenly enable this fix permanently after 1.5 years because of compatibility issues.

btw, I have added it to prboom-plus

Share this post


Link to post

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  
×