Graf Zahl Posted December 3, 2011 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. 0 Share this post Link to post
entryway Posted December 3, 2011 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. 0 Share this post Link to post
Maes Posted December 3, 2011 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. 0 Share this post Link to post
entryway Posted December 3, 2011 Maes, correct? http://prboom-plus.sf.net/blockmap.patch.zip I replaced ">>MAPBLOCKSHIFT" with P_GetSafeBlockX/Y everywhere except P_GroupLines Looks like I still have problems with shooting enemies in some directions 0 Share this post Link to post
Maes Posted December 3, 2011 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 :-( 0 Share this post Link to post
entryway Posted December 3, 2011 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 0 Share this post Link to post
Maes Posted December 3, 2011 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 ;-) 0 Share this post Link to post
entryway Posted December 3, 2011 Like this? http://pastebin.com/wGmaJfs3 0 Share this post Link to post
Maes Posted December 4, 2011 entryway said:Like this? http://pastebin.com/wGmaJfs3 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. 0 Share this post Link to post
Maes Posted December 4, 2011 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 ;-) 0 Share this post Link to post
entryway Posted December 4, 2011 Maes said:I used the above getSafeBlock function though, no idea what your 64 version looks like It was the same as P_GetSafeBlockX, but with int64 argument. I've removed it: http://pastebin.com/8N5azytS Correct? 0 Share this post Link to post
Maes Posted December 4, 2011 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. 0 Share this post Link to post
entryway Posted December 4, 2011 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) 0 Share this post Link to post
Maes Posted December 4, 2011 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? 0 Share this post Link to post
entryway Posted December 4, 2011 Maes said:http://pastebin.com/HK2JWJCF 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') 0 Share this post Link to post
Maes Posted December 4, 2011 Hmm yeah I see it now. Okey dokey, adopting fix ;-) 0 Share this post Link to post
entryway Posted December 4, 2011 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)? 0 Share this post Link to post
Maes Posted December 4, 2011 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. 0 Share this post Link to post
entryway Posted December 4, 2011 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? 0 Share this post Link to post
Maes Posted December 4, 2011 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 ;-) 0 Share this post Link to post
entryway Posted December 4, 2011 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 0 Share this post Link to post
tempun Posted December 9, 2011 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? 0 Share this post Link to post
entryway Posted December 13, 2011 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 0 Share this post Link to post
tempun Posted December 14, 2011 entryway said:btw, I have added it to prboom-plus but there's no build yet? 0 Share this post Link to post