Doom Source code weirdness - P_PathTraverse Edition

[Graf Zahl]

The subfunction which collects linedef intercepts uses the following code to check if the trace actually crosses the line:

		// avoid precision problems with two routines
		if ( trace.dx > FRACUNIT*16
			 || trace.dy > FRACUNIT*16
			 || trace.dx < -FRACUNIT*16
			 || trace.dy < -FRACUNIT*16)
		{
			s1 = P_PointOnDivlineSide (ld->v1->x, ld->v1->y, &trace);
			s2 = P_PointOnDivlineSide (ld->v2->x, ld->v2->y, &trace);
		}
		else
		{
			s1 = P_PointOnLineSide (trace.x, trace.y, ld);
			s2 = P_PointOnLineSide (trace.x+trace.dx, trace.y+trace.dy, ld);
		}
		
		if (s1 == s2) continue;	// line isn't crossed
		
		// hit the line
		P_MakeDivline (ld, &dl);
		frac = P_InterceptVector (&trace, &dl);

		if (frac < 0) continue;	// behind source

I am a bit puzzled by this as it looks quite a bit wrong to me.
As I see it, it:

1. for short traces below 16 map units it never checks if the actual line is even touched. If I understand this correctly, the trace may well pass beside the line.

2. For long traces it looks like the endpoint is never checked. It looks like it can actually reach past the intended endpoint, if there's more lines in the current blockmap block. Shouldn't something like ('if (frac > 1) continue;' be here if this is supposed to be correct?


What's really interesting is that the old 1.2 sight checking code as present in Heretic and Hexen performs quite different checks that actually look correct to me:

	if (P_PointOnDivlineSide (ld->v1->x, ld->v1->y, &trace) ==
		P_PointOnDivlineSide (ld->v2->x, ld->v2->y, &trace))
	{
		return true;		// line isn't crossed
	}
	P_MakeDivline (ld, &dl);
	if (P_PointOnDivlineSide (trace.x, trace.y, &dl) ==
		P_PointOnDivlineSide (trace.x+trace.dx, trace.y+trace.dy, &dl))
	{
		return true;		// line isn't crossed
	}

Of course it skips the P_InterceptVector call as it doesn't need the fractional position.
My impression is that the main reason this never caused any issues is that there's so few situations where P_PathTraverse actually needs to be precise when linedef intercepts are being needed.

I'm not really sure if this actually is an issue or just a misunderstanding on my part.
So can anyone here shed some light upon this?

[printz]

I saw the <16 issue as well, but I assumed that none of the calls in Doom use attackranges lower than 16 (I may be wrong). Stuff like gunshots, autoaim, switches, player melee attacks use some constant value for attackrange such as 64, 1024, 2048, always greater than 16 in any direction.

EDIT: actually in P_SlideMove three such traverses are called with reasonably low trace lengths, but that function is one big "kludgy mess" as either id or Kreimeier admitted.

The second problem, about frac > 1, is cancelled in P_TraverseIntercepts where such intercepts (with frac > FRACUNIT as given in the function parameter) are rejected.

[Graf Zahl]

printz said:

The second problem, about frac > 1, is cancelled in P_TraverseIntercepts where such intercepts (with frac > FRACUNIT as given in the function parameter) are rejected.

Good to know. It's still needlessly inefficient to add them to the list just to discard them again, the way the intercepts are traversed they add needless overhead.

I didn't notice that the other end was checked because it didn't use the FRACUNIT constant but a variable that got stored in.

If P_SlideTraverse is the only place where the short range case matters, I don't care. I've never experienced any glitches that may be related to this code so it isn't an issue there.

[kb1]

Graf Zahl said:

...
My impression is that the main reason this never caused any issues...

This is the number one statement in this thread. Doom was built empirically, changed until it was fun. Period. This, of course leads to weirdness. Honestly, I'm surprised there's not more than there is :)

[Linguica]

I just spent some time puzzling this out. The Doom functions don't (directly) calculate if or where 2 line segments intersect. Instead, they just calculate if the infinite lines drawn from those segments intersect, and if so, applies the algorithm found here: http://stackoverflow.com/a/1968345. (If you rename the variables and shuffle it around, it's the same one.) The algorithm tells you where the infinite lines *would* intersect as a value of how far along one line segment that intersection is. If the intersection point is between 0 and 1 you know the segments themselves intersect, and otherwise you can just throw out the value.

edit: it just occurred to me that this still doesn't seem to guarantee that the line segments actually cross - P_PointOnLineSide checks the endpoints of the trace against the linedef, and then P_InterceptVector returns the distance along the trace that the (extended to infinite) linedef crosses, but I don't see where it's guaranteed that the linedef actually crosses the trace. Though I feel like if there wasn't a check in the code for this somewhere, it ought to have been obvious? But then again, P_PathTraverse (which calls P_BlockLinesIterator, which calls PIT_AddLineIntercepts, which calls P_PointOnLineSide) is only used in 4 places: P_SlideMove, P_AimLineAttack, P_LineAttack, and P_UseLines, and the latter 3 are all pretty much guaranteed to have traces longer than 16 units since they all start or end inside a player or monster.

If P_SlideMove was returning false positives, i.e. thinking traces were crossing linedefs when they actually weren't, how would this manifest itself? I guess via player movement near a wall sometimes being arbitrarily stopped short by a "phantom" linedef collision. I guess I need to think about if this is something that actually happens.

[Graf Zahl]

Linguica said:

If P_SlideMove was returning false positives, i.e. thinking traces were crossing linedefs when they actually weren't, how would this manifest itself? I guess via player movement near a wall sometimes being arbitrarily stopped short by a "phantom" linedef collision. I guess I need to think about if this is something that actually happens.

P_SlideMove is one of the most glitch ridden messes in the Doom engine.
Just in the first map in Hexen there's two places where the player SHOULD slide along a corner between two walls but actually seems to get stuck. Who knows if this code is responsible.

Got to test that...

[Linguica]

Welp, I am 99% sure that the game *does* fuck up and register phantom linedef hits / slides. I just made a sample level, wiggled around in it a little, and analyzed the output. Here's a GIF illustrating what happened during one interesting tic:



Player movement generally works as follows: first the game tries to just move the player to the spot it wants. If this fails, it then casts 3 tracers from the 3 corners of the player with the magnitude / direction of the desired move, and calculates if any of them hit any linedefs, and if so, which linedef is hit the soonest.

The player's trailing corner emits a short trace and believes it hits the 1S linedef over on the right side of the picture. The engine accepts this, moves that corner up to the infinitely extended line for that linedef, and then tries to project the remaining "momentum", so to speak, to be redirected along the direction of the line. At this point, the engine calculates which side of the linedef the player is on. As you can see, the center of the player is on the front side of the linedef, but the trailing corner is actually still ever so slightly *behind* it. This means that when the engine calculates the angle to move the player for the sliding portion, it's out of the normal range it expects, and so to "correct" this, the engine just *adds 180 degrees* to the angle, and because of this, moves the player precisely AWAY from the proper direction of momentum.

I'm pretty sure this is the cause of the weird "elastic" collisions people report where sometimes they seem to suddenly jerk in the opposite direction from their movement for no apparent reason.

[pritch]

Linguica said:

I'm pretty sure this is the cause of the weird "elastic" collisions people report where sometimes they seem to suddenly jerk in the opposite direction from their movement for no apparent reason.

I'm sold.

And somewhat relieved because I always wondered if I was emitting faulty ESP or something causing that...

[Graf Zahl]

Well, how fitting that I finally decided to remove that code from ZDoom today... ;)


Can you post that test level? This might be interesting for analysis.

[kb1]

Linguica said:

Welp, I am 99% sure that the game *does* fuck up and register phantom linedef hits / slides. I just made a sample level, wiggled around in it a little, and analyzed the output.

This reeks of another empirical "write some code, try it against 1 test case...bam! it works, let's leave it in" coding sessions. In fact, I would bet that was the case:

Some one was moving thru a level, bumping against a wall, and "it just didn't feel right". This code was an attempt to solve the issue.

It would be interesting to simply disable the code (in a way that you can toggle it on and off during a game), and see just how often it helps.

Woah, Graf beat me to it. But, honestly, ZDoom is not the most isolated test case to just see this single difference, is it?

[Linguica]

Graf Zahl said:

Can you post that test level? This might be interesting for analysis.

I already deleted that one, but made another one to try and provoke the elastic collision behavior:

https://www.doomworld.com/linguica/hax/elastic.wad

If you run back and forth and slide against the burning barrels, you can get the behavior pretty often (in vanilla, obviously).

All I'm doing here is holding forward and turning back and forth:

[kb1]

Linguica said:

I already deleted that one, but made another one to try and provoke the elastic collision behavior:

https://www.doomworld.com/linguica/hax/elastic.wad

If you run back and forth and slide against the burning barrels, you can get the behavior pretty often (in vanilla, obviously).

All I'm doing here is holding forward and turning back and forth:

http://i.imgur.com/GqI3JYo.gif

So, what's the fix? (without simply removing the code, obviously). Is it enough to disable the thrust when it's >=90 degrees from player angle, or if so, reverse the thrust? Or should we do more line intersection checks to calculate the angle properly? I have difficulty understanding exactly what's going on - I'll need to study your analysis some more, and maybe mock it up. Thanks for your efforts, by the way.

What I find annoying is when you hit that one place on the wall when sliding stops, as if you're stuck in a crevice - that's probably caused by this as well, right?

[Linguica]

The fix is just to properly check if you've crossed a line. The normal way to check if 2 line segments intersect is to take the endpoints of segment A and check if they're on opposite sides of segment B, and then take the endpoints of segment B and check if they're on opposite sides of segment A. For whatever reason, Doom stops after the first half of this (for a certain subset of intercept checks, at least).

[Linguica]

Also for any demos with inexplicable intercepts overflows, this is also a likely culprit since it results in many intercepts for lines the player is not touching.