Bug in blockmap line traverser

Bugs that have been investigated and resolved somehow.

Moderator: GZDoom Developers

Forum rules
Please don't bump threads here if you have a problem - it will often be forgotten about if you do. Instead, make a new thread here.
User avatar
ketmar
Posts: 160
Joined: Sat Oct 01, 2016 6:26 am
Contact:

Bug in blockmap line traverser

Post by ketmar »

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.
Attachments
alert_map01_one.wad
(83.8 KiB) Downloaded 33 times
User avatar
Graf Zahl
Lead GZDoom+Raze Developer
Lead GZDoom+Raze Developer
Posts: 49056
Joined: Sat Jul 19, 2003 10:19 am
Location: Germany

Re: Bug in blockmap line traverser

Post by Graf Zahl »

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
ketmar
Posts: 160
Joined: Sat Oct 01, 2016 6:26 am
Contact:

Re: Bug in blockmap line traverser

Post by ketmar »

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
Graf Zahl
Lead GZDoom+Raze Developer
Lead GZDoom+Raze Developer
Posts: 49056
Joined: Sat Jul 19, 2003 10:19 am
Location: Germany

Re: Bug in blockmap line traverser

Post by Graf Zahl »

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
Posts: 49056
Joined: Sat Jul 19, 2003 10:19 am
Location: Germany

Re: Bug in blockmap line traverser

Post by Graf Zahl »

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
ketmar
Posts: 160
Joined: Sat Oct 01, 2016 6:26 am
Contact:

Re: Bug in blockmap line traverser

Post by ketmar »

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
Graf Zahl
Lead GZDoom+Raze Developer
Lead GZDoom+Raze Developer
Posts: 49056
Joined: Sat Jul 19, 2003 10:19 am
Location: Germany

Re: Bug in blockmap line traverser

Post by Graf Zahl »

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
ketmar
Posts: 160
Joined: Sat Oct 01, 2016 6:26 am
Contact:

Re: Bug in blockmap line traverser

Post by ketmar »

(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
Enjay
 
 
Posts: 26517
Joined: Tue Jul 15, 2003 4:58 pm
Location: Scotland
Contact:

Re: Bug in blockmap line traverser

Post by Enjay »

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
Graf Zahl
Lead GZDoom+Raze Developer
Lead GZDoom+Raze Developer
Posts: 49056
Joined: Sat Jul 19, 2003 10:19 am
Location: Germany

Re: Bug in blockmap line traverser

Post by Graf Zahl »

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
ketmar
Posts: 160
Joined: Sat Oct 01, 2016 6:26 am
Contact:

Re: Bug in blockmap line traverser

Post by ketmar »

>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
Graf Zahl
Lead GZDoom+Raze Developer
Lead GZDoom+Raze Developer
Posts: 49056
Joined: Sat Jul 19, 2003 10:19 am
Location: Germany

Re: Bug in blockmap line traverser

Post by Graf Zahl »

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
ketmar
Posts: 160
Joined: Sat Oct 01, 2016 6:26 am
Contact:

Re: Bug in blockmap line traverser

Post by ketmar »

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
Posts: 160
Joined: Sat Oct 01, 2016 6:26 am
Contact:

Re: Bug in blockmap line traverser

Post by ketmar »

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
Graf Zahl
Lead GZDoom+Raze Developer
Lead GZDoom+Raze Developer
Posts: 49056
Joined: Sat Jul 19, 2003 10:19 am
Location: Germany

Re: Bug in blockmap line traverser

Post by Graf Zahl »

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.
Post Reply

Return to “Closed Bugs [GZDoom]”