Bug in blockmap line traverser

Is there something that doesn't work right in the latest GZDoom? Post about it here.

Moderator: GZDoom Developers

Forum rules
Please construct and post a simple demo whenever possible for all bug reports. Please provide links to everything.

If you can include a wad demonstrating the problem, please do so. Bug reports that include fully-constructed demos have a much better chance of being investigated in a timely manner than those that don't.

Please make a new topic for every bug. Don't combine multiple bugs into a single topic. Thanks!

Bug in blockmap line traverser

Postby ketmar » Sat Dec 28, 2019 8:17 am

in the attached map, SS soldier sees player (and becomes alerted), even though there is no unobscured LOS. it seems that blockmap traverser hits "// neither xintercept nor yintercept match!" condition, which caused early exit, and the engine stopped LOS checking at the first blockmap tile.

checked with devbuild g55975a2ae, clean config. but the bug exists for a long time (prolly from the first ZDoom versions with blockmap sight checks).

older version of that same code is used in k8vavoom, and it has the same bug. this doesn't happen so often, and most of the time it only forces some monsters to awake prematurely (which is quite hard to notice), so that's prolly why it wasn't spotted before.


p.s.: thanks to id0 for making me aware of this bug.
You do not have the required permissions to view the files attached to this post.
User avatar
ketmar
k8vavoom developer
 
Joined: 01 Oct 2016

Re: Bug in blockmap line traverser

Postby Graf Zahl » Sat Dec 28, 2019 8:32 am

I wonder how that case can be even reached. As for a fix, it may be a good idea to treat this error case as returning false from P_CheckSight instead of true.
User avatar
Graf Zahl
Lead GZDoom+Raze Developer
Lead GZDoom+Raze Developer
 
Joined: 19 Jul 2003
Location: Germany

Re: Bug in blockmap line traverser

Postby ketmar » Sat Dec 28, 2019 8:48 am

this is deep flaw in traverser -- it didn't even reached the destination, it aborts on the very first blockmap tile -- which is definitely wrong. it seems that the whole math there is fubared. returning "false" won't fix it. i hoped that you'll fix it for me for free ;-), but it seems that i have to try to understand what Randi did there. eh...

it somehow looks like this (debug log from k8vavoom, but the code is essentially the same):
Debug: 000: xt1=0; yt1=0; xt2=2; yt2=5; mxstep=1; mystep=1; xstep=0.428571; ystep=2.33333; partialx=0.75; partialy=0.75; xitc=0.571429; yitc=2
Debug: 001: xt1=0; yt1=0; xt2=2; yt2=5; mxstep=1; mystep=1; xstep=0.428571; ystep=2.33333; partialx=0.75; partialy=0.75; xitc=0.571429; yitc=2
Debug: *** cind=1! map=(0,0); intercept=(0.571429,2); step=(0.428571,2.33333); mapstep=(1,1)
Debug: *** EXIT: map=(0,1); intercept=(1,2); step=(0.428571,2.33333); mapstep=(1,1)
Debug: *** SCREWED! map=(0,1); intercept=(1,2); step=(0.428571,2.33333); mapstep=(1,1)

here, it should step from tile (0,0) to tile (2,5), but gives up at tile (0,1) -- because "[xy]intercept" desyncs with "map[xy]".
User avatar
ketmar
k8vavoom developer
 
Joined: 01 Oct 2016

Re: Bug in blockmap line traverser

Postby Graf Zahl » Sat Dec 28, 2019 8:54 am

Don't blame Randi, the FUBAR probably originates at id.
I've spent quite some time fixing that thing but this particular scenario never crossed my way before.

But now you made me curious.
User avatar
Graf Zahl
Lead GZDoom+Raze Developer
Lead GZDoom+Raze Developer
 
Joined: 19 Jul 2003
Location: Germany

Re: Bug in blockmap line traverser

Postby Graf Zahl » Sat Dec 28, 2019 9:08 am

So, what happens is that the second iteration precisely hits the right border between two blocks. And nothing in there deals with this case.
The problem is, I cannot fix this particular edge case without making things worse.

For now I just did what I said earlier - return failure for the sight check.A true fix will require a lot more thinking.
User avatar
Graf Zahl
Lead GZDoom+Raze Developer
Lead GZDoom+Raze Developer
 
Joined: 19 Jul 2003
Location: Germany

Re: Bug in blockmap line traverser

Postby ketmar » Sat Dec 28, 2019 9:42 am

it looks like this whole thing should be replaced with a proper DDA implementation. i'll try to do that in k8vavoom, and will back to you if i'll succeed.

p.s.: as a possible workaround, you can introduce a cvar to switch to a bsp-based caster, so people can choose between faster, but partially broken implementation, and slower, but better working one.
User avatar
ketmar
k8vavoom developer
 
Joined: 01 Oct 2016

Re: Bug in blockmap line traverser

Postby Graf Zahl » Sat Dec 28, 2019 9:47 am

Yes, I have had the same thought every time I looked at the code - but so far have managed to get around its issues without doing it each time it came up. This is one of the most crucial routines in the entire engine, nothing to toy around with.
Fortunately this issue requires some strict grid alignment to trigger so it's really rare and unlikely to happen when the player is moving around.
User avatar
Graf Zahl
Lead GZDoom+Raze Developer
Lead GZDoom+Raze Developer
 
Joined: 19 Jul 2003
Location: Germany

Re: Bug in blockmap line traverser

Postby ketmar » Sat Dec 28, 2019 9:54 am

(sighs) for k8vavoom it is quite essential. i tried to use this code to calculate lightmaps with raycasting, and got alot of light leaking artifacts. back then i thought that it was some floating point precision issue, and simply switched the tracer back to BSP-based. but now i see the real cause of the leaking light bug.

and k8vavoom can trigger lightmap recalculation when some geometry changed, or a light source was moved (like a lamp on a lift -- it goes down with the lift, and the engine should recalc static lightmaps), so using faster tracer is better there.

fun fact: this is part of Doom II MAP31. with the original MAP31, the bug is not there. but if you'll run any nodes builder on it (so nodes builder will recalc blockmap), the bug will appear. and it always appears in k8vavoom, because k8vavoom always rebuilds blockmap from scratch...

(wow, alot of "k8vavoom" search spam in this post! ;-)
User avatar
ketmar
k8vavoom developer
 
Joined: 01 Oct 2016

Re: Bug in blockmap line traverser

Postby Enjay » Sat Dec 28, 2019 10:31 am

Indeed, starting GZDoom with gennodes 1 and warping to map 31 causes a cry of "schutzstaffel" to come through the wall to my right but without generating new nodes, the SS guy doesn't wake.

In the past, in several maps, I have noticed enemies being awake and wandering when I thought they had no good reason to be doing so. Whether it was due to this issue or something else, I can't say - but it could be related.
User avatar
Enjay
Everyone is a moon, and has a dark side which he never shows to anybody. Twain
 
 
 
Joined: 15 Jul 2003
Location: Scotland

Re: Bug in blockmap line traverser

Postby Graf Zahl » Sat Dec 28, 2019 10:43 am

Well, that won't happen anymore with the next version. Ketmar's problems nonwithstanding, the far bigger screwup here was to let a lost check return successfully seeing the target. Obviously that needs to report the opposite.
User avatar
Graf Zahl
Lead GZDoom+Raze Developer
Lead GZDoom+Raze Developer
 
Joined: 19 Jul 2003
Location: Germany

Re: Bug in blockmap line traverser

Postby ketmar » Sat Dec 28, 2019 11:00 am

>Obviously that needs to report the opposite.
actually, this will only reverse the problem. now some enemies will be blind sometimes. of course, the player will eventually move to the position where LOS check will succeed, and it is prolly better to have some enemies with very poor eyesight than enemies with superman-like ESP powers. ;-)

p.s.: also, the same code seems to be used to fill interceptions array with lines and things. while it is usually used on a short distance, and most of the time it never leaving the blockmap tile where the player is, it can cause troubles too.

as Graf said, that code is one of the most important engine functions. how did id managed to screw it up so badly?! (obvious rhetorical question ;-)
User avatar
ketmar
k8vavoom developer
 
Joined: 01 Oct 2016

Re: Bug in blockmap line traverser

Postby Graf Zahl » Sat Dec 28, 2019 11:11 am

ketmar wrote:as Graf said, that code is one of the most important engine functions. how did id managed to screw it up so badly?! (obvious rhetorical question ;-)


Don't ask me. Don't forget that the original did not even have the corner case and lost a lot more traces - to the point that they completely replaced their sight checking code.
Your bug is harmless by comparison - it can only trigger in constructed scenarios or right at map starts or when exiting a teleporter. As soon as the player moves the condition required to trigger it are no longer present.

Using this algorithm for something so far less fault tolerant as creating lightmaps is of course a bigger issue than a 1 in 10000 chance of a sight check not returning a proper result.
User avatar
Graf Zahl
Lead GZDoom+Raze Developer
Lead GZDoom+Raze Developer
 
Joined: 19 Jul 2003
Location: Germany

Re: Bug in blockmap line traverser

Postby ketmar » Sat Dec 28, 2019 3:27 pm

here's DDA code i came up with. it seems to work, but i'd like to have another pair of eyes on it.

Spoiler:
User avatar
ketmar
k8vavoom developer
 
Joined: 01 Oct 2016

Re: Bug in blockmap line traverser

Postby ketmar » Mon Dec 30, 2019 4:41 am

this code seems to work with k8vavoom so far. so i think i'll go with it for now, until somebody will come with something better.
User avatar
ketmar
k8vavoom developer
 
Joined: 01 Oct 2016

Re: Bug in blockmap line traverser

Postby Graf Zahl » Mon Dec 30, 2019 4:44 am

I'll try this out myself when I find a bit of time.
I cannot really say I was ever too happy with the strange math in the original version.
User avatar
Graf Zahl
Lead GZDoom+Raze Developer
Lead GZDoom+Raze Developer
 
Joined: 19 Jul 2003
Location: Germany

Next

Return to Bugs

Who is online

Users browsing this forum: No registered users and 0 guests