Touch links

[Baker]

FitzQuake 0.85 has a touch links fix that apparently breaks the "White Room" mod. Quakespasm has the "right" solution according to what I've read.

I'm interested in this problem except ... I don't understand the problem at all. So I don't even get the issue, any aspects of the problem or why it works or doesn't work or what it is doing so I don't know what these fixes are looking to fix or why one works and another one doesn't.

is that I'd like to implement Quakespasm's fix for this, but can't even describe the problem nor do I know really what it is fixing and can't develop a test case.

Short version: wats server touchlinks do? how is this a problem and when does it happen and how does Quakespasm's fix solve that and metlslime's fix solves it sometimes but I guess can also break it sometimes? Or is White Room doing something "bad"?

[Spike]

SV_LinkEdict links the entity into the world.
basically there's a small bsp tree (constructed in a grid like an octtree, I don't remember the technical name) that it uses to track which entities are where
each area has two lists. one for solid ents and one for triggers.

SV_TouchLinks:
walks through the nodes that are within the area stated. for each area, walk through the 'trigger' list and invoke the touch function on each.

here's the bug that you're probably refering to:
the touch function inside the trigger list invokes touch functions. if the touch function moves the entities around, they will call SV_(Un)LinkEdict. this will change the links that SV_TouchLinks is currently walking through.
This will result in infinite loops and crashes and stuff.

to reproduce in vanilla:
map e2m2
shoot one button
fly/rocketjump/whatever over the bridge that isn't there yet.
this will result in a killtarget remove() of the trigger_once that you just walked through.
the qc will then return to the engine and back to sv_touchlinks. touchlinks will try to continue walking the list which is now set to NULL or something... CRASH!

the q2 solution to this is to build a list of all the ents that are within the box, then to invoke touch functions on each found. you do need to make sure its not removed by a prior touch function though, but the spawn() deadtime of 2 secs avoids any remove()+spawn() issues.
just validating the links within SV_TouchLinks is probably not 100% correct, and would be slow if it was.

[szo]

QuakeSpasm currently uses Bill Currie's solution from QuakeForge. Here is the relevant QF commit:
http://quake.git.sourceforge.net/git/gi ... c7136d97b7

[r00k]

Hmm this was an old bug, I thought MH or Spike posted a fix, I'll have to search my source but I cannot reproduce this bug in Qrack, and the white room works.

[szo]

[...] I cannot reproduce this bug in Qrack

If you are testing with e2m2 buttons, make sure that you start the map in easy (0) skill

[r00k]

ya
]skill 0
]map e2m2
]god
]impulse 9

shoot one button
kill demon
rj across
touch trigger_once
"sequence completed"

Okay, wqpro crashes, now i need to diff world.c...

Code: Select all

void SV_TouchLinks ( edict_t *ent, areanode_t *node )
{
	link_t		*l, *next;
	edict_t		*touch;
	int			old_self, old_other;

loc0:
// touch linked edicts
	for (l = node->trigger_edicts.next ; l != &node->trigger_edicts ; l = next)
	{
		if (!l)
		{
			Con_Printf ("SV_TouchLinks: null link\n");
			break;
		}

		next = l->next;
		touch = EDICT_FROM_AREA(l);
		if (touch == ent)
			continue;
		if (!touch->v.touch || touch->v.solid != SOLID_TRIGGER)
			continue;
		if (ent->v.absmin[0] > touch->v.absmax[0]
		|| ent->v.absmin[1] > touch->v.absmax[1]
		|| ent->v.absmin[2] > touch->v.absmax[2]
		|| ent->v.absmax[0] < touch->v.absmin[0]
		|| ent->v.absmax[1] < touch->v.absmin[1]
		|| ent->v.absmax[2] < touch->v.absmin[2] )
			continue;
		old_self = pr_global_struct->self;
		old_other = pr_global_struct->other;

		pr_global_struct->self = EDICT_TO_PROG(touch);
		pr_global_struct->other = EDICT_TO_PROG(ent);
		pr_global_struct->time = sv.time;
		PR_ExecuteProgram (touch->v.touch);

		//MH: the PR_ExecuteProgram above can alter the linked edicts
		if (next != l->next && l->next)
		{
			Con_DPrintf ("Warning: fixed up link in SV_TouchLinks\n");
			next = l->next;
		}

		pr_global_struct->self = old_self;
		pr_global_struct->other = old_other;
	}
	
// recurse down both sides
	if (node->axis == -1)
		return;
	
	// LordHavoc: optimized recursion
//	if (ent->v.absmax[node->axis] > node->dist) SV_TouchLinks (ent, node->children[0]);
//	if (ent->v.absmin[node->axis] < node->dist) SV_TouchLinks (ent, node->children[1]);
	if (ent->v.absmax[node->axis] > node->dist)
	{
		if (ent->v.absmin[node->axis] < node->dist)
			SV_TouchLinks(ent, node->children[1]); // order reversed to reduce code
		node = node->children[0];
		goto loc0;
	}
	else
	{
		if (ent->v.absmin[node->axis] < node->dist)
		{
			node = node->children[1];
			goto loc0;
		}
	}
}

K in developer 1 i see that "Warning: fixed up link in SV_TouchLinks" when I rj.

[mh]

The criminal struct is called "areanodes", and is used to store which edicts are in reasonably close proximity, so that collision and other interaction tests can be restricted to sub-groups of edicts rather than needing to exponentially increase as edict numbers increase. It's a basic "divide-and-conquer" strategy (for the curious there is optimization potential in this for big maps - just create more areanodes).

The bug happens because SV_TouchLinks does a linear walk through the edicts in a node, and as part of that walk will call PR_ExecuteProgram if entities touch. On occasion this call to PR_ExecuteProgram may free an edict that has yet to be hit in this walk, or may even relink the edicts in that node, meaning that it can create infinite loops or dereference NULL pointers.

I'm not too familiar with the QS fix; my fix is to copy off the list of edicts that touch to scratch memory during the initial linear walk, then run the touch functions for any edicts that I copied off during a second pass. That works because nothing is modified during the critical first pass.

[taniwha]

Heh, I very vaguely remember that fix (ie, on seeing the patch, it feels familiar). It's nice to know that my fix is holding up well

I wonder what caused me to fix it.

[taniwha]

Heh, after having that patch pointed out, I got to worrying about it.

sv_link_prev is never set (not really a problem). I guess I was thinking ahead to when something might be doing reverse searches.

sv_link_next points to the local "next" variable, thus next gets updated as necessary.

However, there does seem to be a potential problem: if an entity is moved, it will be re-linked. This might cause an entity to be touched twice (or even an infinite loop). I need to check further.

[Baker]

Thanks for all the various info everyone. I'm reading it right now, but I don't have anything smart to say except (@Spike yeah ... E2M2 crash is familiar).

LOL @ MH "The criminal struct ..." .

More: Ok ... with all the descriptives above of what is causing the issue and how it arises, still not familiar with areanodes but I can change that.

LOL #2 @ R00k: Has fix and didn't know it plus didn't remember doing it. Easy enough to relate to that.

[r00k]

LOL #2 @ R00k: Has fix and didn't know it plus didn't remember doing it. Easy enough to relate to that.

Im just a QC coder; ANd not much else than keeping my .prj happy ;P
To All the guys here on Inside3d, really I am just a player, and i learnd some Qc, and pasted code from quakesource. and your help really just is my avenue as a player to keep playing.
B y fixzing bugs in the origina source etc. and pusing my tokeep playing. we have a bout 20 active now...
So im drunk but i thank you all who helped me play a better day...
burp!

___
http://www.quakeone.com/cax