Forum posts

Ok, I have come up with an initial implementation using a mix of techniques:

1. Loop through all func_ladder entities using UTIL_FindEntityByClassname
2. Define a line going from the ladder entity's bounding box min and max (pev->absmin, pev->absmax)
3. Calculate the distance of the player's origin from that line (code for this below) and pick whichever ladder produces the lowest distance
4. Find the midpoint between the ladder's bounding box min and max, and then use UTIL_TRACEHULL from the player's origin to that midpoint to get the impact normal, which will be your ladder's surface normal. We use TRACEHULL rather than TRACELINE in case the ladder is a func_illusionary

There would be an issue with very fat ladder brushes since the distance from that line would be quite high, but these are generally very rare and it's unlikely to have a really fat ladder brush close to a thin ladder brush, so probably not an edge case worth investigating.

Vector UTIL_ClosestPointOnLine(Vector lineFrom, Vector lineTo, Vector point) {

        Vector vVector1 = point - lineFrom;
        Vector vVector2 = (lineTo - lineFrom);
        UTIL_NormalizeVector(&vVector2);

        float d = vDist3D(lineFrom, lineTo);
        float t = UTIL_GetDotProduct(vVector2, vVector1);

        if (t <= 0)
            return lineFrom;

        if (t >= d)
            return lineTo;

        Vector vVector3 = vVector2 * t;

        Vector vClosestPoint = lineFrom + vVector3;

        return vClosestPoint;
}

float UTIL_DistanceFromLine3D(Vector lineFrom, Vector lineTo, Vector point) {
    Vector nearestToLine = UTIL_ClosestPointOnLine(lineFrom, lineTo, point);
    return vDist3D(point, nearestToLine);
}

Hi all,

I'm wondering if it's possible when a player is on a ladder to obtain a reference to the func_ladder they're claiming on or, ideally, the surface normal they're climbing on?

The reason for this is I'm writing a bot to play some HL1 mods, and for ladder climbing it would be useful to tell the bot which direction to move in order to ascend/descend the ladder without relying on external hints like waypoints.

I've tried using traces, but I don't believe func_ladders collide so it just returns worldspawn, unless I'm missing a flag to allow func_ladders to block the trace.

Thanks!

Thank you for the help so far! Looking forward to what you can dig up. Using a trace is one idea, but the preference of course is to just be able to extract all the world clip vertices so that invisible walls are also taken into account.

For example, tracing func_illusionary won't help with the barricade at CT spawn in cs_militia: the AI will still think it can crouch under the barriers if the invisible wall can't be detected.

An additional thought to the above: the BSP renderer seems to have some issues with heavy artifacting of clipnodes as well. Looking at this section of map from ns_eclipse:Given that all I really want to do here is determine if a func_illusionary is solid or not, I wonder if it would be enough to perhaps query the BSP with a trace through the func_illusionary brush location to see if it hits something? Might save a lot of headaches. Problem is doing that from outside of GoldSrc...

Yeah I've already filtered those out. I also noticed that the BSP viewer code doesn't do anything with indices, so presumably it already just pushes the vertices in the order in which they're meant to be rendered, so the triangle indices would just be 1,2,3,4,5,6,7 etc. I've added that to my code.

This is what the code looks like now, it's mostly just a copy of the BSP viewer code, except I arbitrarily scale down everything by 1000 so at least the resulting map isn't insanely big:

if (map->isValid())
	{

		int numTris = 0;
		int vertCounter = 0;
		int triCounter = 0;

		Clipper clipper;

		int clipnodeLeafCount = 0;

		vector<NodeVolumeCuts> solidNodes = map->get_model_leaf_volume_cuts(0, 1);

		vector<CMesh> meshes;
		vector<vec3> allVerts;
		vector<int> modelIndices;
		int IndiceCounter = 0;

		int indicesOffset = 0;

		// This bit is the same as the BSP viewer
		for (int k = 0; k < solidNodes.size(); k++)
		{
			meshes.push_back(clipper.clip(solidNodes[k].cuts));
			clipnodeLeafCount++;
		}

		for (int m = 0; m < meshes.size(); m++)
		{
			CMesh& mesh = meshes[m];

			for (int face = 0; face < mesh.faces.size(); face++)
			{

				if (!mesh.faces[face].visible)
				{
					continue;
				}
				set<int> uniqueFaceVerts;

				for (int edge = 0; edge < mesh.faces[face].edges.size(); edge++)
				{
					for (int v = 0; v < 2; v++)
					{
						int vertIdx = mesh.edges[mesh.faces[face].edges[edge]].verts[v];
						if (!mesh.verts[vertIdx].visible)
						{
							continue;
						}
						uniqueFaceVerts.insert(vertIdx);
					}
				}

				vector<vec3> faceVerts;
				for (auto vertIdx : uniqueFaceVerts)
				{
					faceVerts.push_back(mesh.verts[vertIdx].pos);
				}

				faceVerts = getSortedPlanarVerts(faceVerts);

				if (faceVerts.size() < 3)
				{
					//logf("Degenerate clipnode face discarded\n");
					continue;
				}

				vec3 normal = getNormalFromVerts(faceVerts);

				if (dotProduct(mesh.faces[face].normal, normal) > 0)
				{
					reverse(faceVerts.begin(), faceVerts.end());
					normal = normal.invert();
				}

				// convert from TRIANGLE_FAN style verts to TRIANGLES
				for (int k = 2; k < faceVerts.size(); k++)
				{
					allVerts.push_back(faceVerts[0]);
					modelIndices.push_back(IndiceCounter++);
					allVerts.push_back(faceVerts[k - 1]);
					modelIndices.push_back(IndiceCounter++);
					allVerts.push_back(faceVerts[k]);
					modelIndices.push_back(IndiceCounter++);

					numTris++;
				}
			}
		}


		// Add the verts into the float array
		TriData->ntris = numTris;

		for (int i = 0; i < allVerts.size(); i++)
		{
			TriData->verts[vertCounter++] = allVerts[i].x * 0.001f;
			TriData->verts[vertCounter++] = allVerts[i].y * 0.001f;
			TriData->verts[vertCounter++] = allVerts[i].z * 0.001f;
		}

		for (int i = 0; i < modelIndices.size(); i++)
		{
			TriData->tris[triCounter++] = modelIndices[i];
		}

		TriData->nverts = vertCounter / 3;

		return true;

	}

What is missing though is the conversion from clip local units to world units. When I render the resulting mesh it looks like this regardless of which map I use as an input (the below is meant to be de_dust):For reference, to rule out the possibility of the issue being with the rendering of the mesh itself, this is what it looks like when I render it by extracting the faces and edges from the BSP tree (but of course that's missing CLIP brushes):

Thanks Admer456! Here is my code, which is mostly lifted from the BSP viewer, hopefully the comments make sense:

Bsp* map = new Bsp(filename);

	if (map->isValid())
	{

		int numTris = 0;
		int vertCounter = 0;
		int triCounter = 0;

		Clipper clipper;

		int clipnodeLeafCount = 0;

		vector<NodeVolumeCuts> solidNodes = map->get_model_leaf_volume_cuts(0, 1);

		vector<CMesh> meshes;
		vector<vec3> allVerts;
		vector<int> modelIndices;

		int indicesOffset = 0;

		// This bit is the same as the BSP viewer
		for (int k = 0; k < solidNodes.size(); k++)
		{
			meshes.push_back(clipper.clip(solidNodes[k].cuts));
			clipnodeLeafCount++;
		}

		for (int m = 0; m < meshes.size(); m++)
		{
			CMesh& mesh = meshes[m];

			for (int face = 0; face < mesh.faces.size(); face++)
			{

				if (!mesh.faces[face].visible)
				{
					continue;
				}

				// First add all the vertices to the vertex pool, then in a moment we'll define the indices that form each triangle
				for (int v = 0; v < mesh.verts.size(); v++)
				{
					allVerts.push_back(mesh.verts[v].pos);
				}


				// My understanding is that the indices held in the edges index into the verts array for that mesh, so if we want to combine
				// all meshes into a single soup, we need to offset the index number by the total number of indices already present
				for (int edge = 0; edge < mesh.faces[face].edges.size(); edge++)
				{
					modelIndices.push_back(mesh.edges[mesh.faces[face].edges[edge]].verts[0] + indicesOffset);
					modelIndices.push_back(mesh.edges[mesh.faces[face].edges[edge]].verts[1] + indicesOffset);
				}

				int indexCounter = 1;
				int totalIndices = (mesh.faces[face].edges.size() - 2);

				numTris += totalIndices;

				// Now we need to break the convex shape into triangles, fanning out from the first index and adding them into the
				// total indices array
				for (int x = 0; x < totalIndices; x++)
				{

					TriData->tris[triCounter++] = modelIndices[0];
					TriData->tris[triCounter++] = modelIndices[++indexCounter];
					TriData->tris[triCounter++] = modelIndices[indexCounter - 1];

				}

			}

			indicesOffset += mesh.verts.size();
		}


		// Add the verts into the float array
		TriData->ntris = numTris;

		for (int i = 0; i < allVerts.size(); i++)
		{
			TriData->verts[vertCounter++] = allVerts[i].x;
			TriData->verts[vertCounter++] = allVerts[i].y;
			TriData->verts[vertCounter++] = allVerts[i].z;
		}

		TriData->nverts = vertCounter / 3;

		return true;

}

Basically, TriData is a structure which contains an array of raw floats representing each vertex and an array of integers representing the indices that form the triangles. Effectively, it's the same format as an OBJ model.

The above approach works fine if I'm just extracting the vertices and edges direct from the map itself, but falls apart when trying to do it with the clip nodes. I'm not sure if this is because my approach isn't compatible with the way clip nodes are represented, or if it's incompatible with wootguy's mesh setup (or both...)

Ok so I've been having a play with it, but I've noticed something strange. The BSP viewer tool takes models and their collision planes and uses a "Clipper" object to carve each model into a mesh object by its various planes. The mesh holds a set of vertices, edges and faces. What I'm finding though is that the vertices produced in the meshes have insanely high or low values (e.g. -1317821 for an X coordinate).

The BSP viewer produces the exact same results as me, so it's not a mistake on my part. It must be doing something in the clipnode buffer to reduce the coordinates back down to something sane, but I can't see where it's doing it. As far as I can see, it's loading those huge values into the buffer for rendering. Any ideas on what I'm missing here?

I think the answer can be found in BspGuy's source code, since that one renders clipnodes. Or at least seems to.

Yes, you're right! It does. The actual collision hulls don't match the original brushwork however, as you can see, the collision hull is considerably larger than the original brush:I wonder if this is because it actually does a point test for player collision at the centre of the player hull, and simply expands the collision hulls to account for player height and width. It may be possible to retrieve the original collision hull by scaling it down by player radius and half height.

Looks like I need to do some digging now. I'll update if I find anything!

Hi everyone,

I have a bit of a challenge. I want to generate a navmesh for HL maps as I'm creating a bot for some HL1 mods (especially Natural Selection) which have limited or no bot support.

To do this, I'm currently extracting all of the vertices from the BSP file and rendering them into a triangle mesh. Vertices exist for all visible entities in the BSP file, but I am excluding func_illusionary entities since these do not collide and therefore should be excluded from navmesh generation.

The challenge I have is clip brushes. These are used for things like chain-link fences and railings where the visual brush is a func_illusionary and then a brush with the CLIP texture is added to prevent players walking through them. The problem is that brushes with the CLIP texture are special cases and do NOT appear in the list of vertices (presumably because they're never rendered): they exist only as collision hulls.

The result is that right now, I only have two choices: include func_illusionary entities in navmesh generation, and have the AI unable to walk through things like the cs_747 curtains and other decorative features, or exclude them and have the AI try to walk through the chain-link fence in cs_militia.

The preferred option of course is to have the clip brushes retrieved and added to the list of vertices, but currently I have no idea how to do this. I've had a look at the hlbsp project's breakdown of the v30 map format here and the map optimisation tutorial here, but I'm still unsure how to convert the planes into a set of triangles. As far as I can see, they're defined as a set of infinitely wide and tall planes with a normal and distance from origin.

Has anyone managed to do this before?