Introduction

In this tutorial we'll look at the possible improvement of monster's path finding without relying on node graph. The following code was written during the Field Intensity development. For the sake of example we'll modify halflife-updated project, but the patches can also be applied to the vanilla HLSDK with minimal changes. You can find all changes in the tridepth branch of my halflife-updated fork.

Path finding in the original Half-Life

First, let's see how monsters find a path around obstacles in Half-Life.

The main function for path building is BuildRoute. First it just checks if the monster can walk a straight path from its origin to the goal, using CheckLocalMove. If it fails, it calls a FTriangulate function with the distance CheckLocalMove stopped at. It tries to find an apex (triangulation point) to overcome an obstacle. If this fails too, the node graph is used to build a route.

In this tutorial we're interested in the FTriangulate function, so let's take a closer look at how it works. First, it calculates vectors to the right and to the left from the monster (also bottom and top ones for flying monsters, but we won't focus on them). Then in the loop it advances left and right in fixed steps and checks if the path can be built from the monster's origin to the chosen point on the left (or right) and from that point to the goal.

CheckLocalMove fails to make a straight path

Let's help barney to reach the beer

• Make step to the right. Check if the goal is accessible from there.
• If yes, we found an apex!
• Make step to the left. Check if the goal is accessible from there.
• If yes, we found an apex!
• If couldn't find an apex from any side, continue the loop, making steps further to the left and right.

If an apex is found the path finding is considered successfull and the apex is added to the route table in the BuildRoute function.

The idea

The idea is to have more apex points then one.

One triangulation point would not be enough. So use more!

It's more like quadragulation (pentagulation, etc.), but let's call it multi-level triangulation, and let's call the number of levels a tridepth.

Modifying hlsdk

First, make some preparations. We want to change the signature of the FTriangulate function to make it recursivable (what? Being able to call itself recursively).

In dlls/basemonster.h change:

- virtual bool FTriangulate(const Vector& vecStart, const Vector& vecEnd, float flDist, CBaseEntity* pTargetEnt, Vector* pApex);
+ int FTriangulate(const Vector& vecStart, const Vector& vecEnd, float flDist, CBaseEntity* pTargetEnt, Vector* pApexes, int n = 1, int tries = 8, bool inner = false);

We've renamed pApex to pApexes as there will be more apex points. We've also added three new parameters.

• n is the number of triangulation levels left (1 by default, just like in Half-Life).
• tries is the number of steps the algorightm will try on each depth level (it's hardcoded as 8 in Half-Life, but we'll make it dynamic).
• inner is a flag to mark that we're going deeper (false on the first level of triangulation).

The function also return int now instead of boolean. The return value is the number of found apex points and it will be used in BuildRoute (later on that matter).

Don't forget to update the signature on the client side. The prediction code uses the same interfaces, so we should keep things in sync.

In cl_dll/hl/hl_baseentity.cpp change:

- bool CBaseMonster::FTriangulate(const Vector& vecStart, const Vector& vecEnd, float flDist, CBaseEntity* pTargetEnt, Vector* pApex) { return false; }
+ int CBaseMonster::FTriangulate(const Vector& vecStart, const Vector& vecEnd, float flDist, CBaseEntity* pTargetEnt, Vector* pApexes, int n, int tries, bool inner) { return 0; }

For simplicity we also removed FTriangulate override from the CFlyingMonster class (it just calls the base function anyway). If you want, you can also make FTriangulate non-virtual now.

In dlls/flyingmonster.h remove:

- bool FTriangulate(const Vector& vecStart, const Vector& vecEnd, float flDist, CBaseEntity* pTargetEnt, Vector* pApex) override;

In dlls/flyingmonster.cpp remove:

- bool CFlyingMonster::FTriangulate(const Vector& vecStart, const Vector& vecEnd, float flDist, CBaseEntity* pTargetEnt, Vector* pApex)
- {
- 	return CBaseMonster::FTriangulate(vecStart, vecEnd, flDist, pTargetEnt, pApex);
- }

Let's make changes to the function implementation!

In dlls/monster.cpp update the signature:

- bool CBaseMonster::FTriangulate(const Vector& vecStart, const Vector& vecEnd, float flDist, CBaseEntity* pTargetEnt, Vector* pApex)
+ int CBaseMonster::FTriangulate(const Vector& vecStart, const Vector& vecEnd, float flDist, CBaseEntity* pTargetEnt, Vector* pApexes, int n, int tries, bool inner)

Then change the calculation of vecLeft and vecRight. As our algorightm is gonna be multi-step we can't use pev->origin of the monster as a starting point (it's valid as a starting point only on the first level of triangulation). So we use vecStart here instead (it's the same as pev->origin if called from BuildRoute).

- vecLeft = pev->origin + (vecForward * (flDist + sizeX)) - vecDir * (sizeX * 3);
- vecRight = pev->origin + (vecForward * (flDist + sizeX)) + vecDir * (sizeX * 3);
+ vecLeft = vecStart + ( vecForward * ( flDist + ( inner ? 0 : sizeX ) ) ) - vecDir * ( inner ? sizeX : sizeX * 3 );
+ vecRight = vecStart + ( vecForward * ( flDist + ( inner ? 0 : sizeX ) ) ) + vecDir * ( inner ? sizeX : sizeX * 3 );

Don't forget about flying monsters:

- vecTop = pev->origin + (vecForward * flDist) + (vecDirUp * sizeZ * 3);
- vecBottom = pev->origin + (vecForward * flDist) - (vecDirUp * sizeZ * 3);
+ vecTop = vecStart + ( vecForward * flDist ) + ( vecDirUp * sizeZ * 3 );
+ vecBottom = vecStart + ( vecForward * flDist ) - ( vecDirUp *  sizeZ * 3 );

We also assign vecEnd to vecFarSide now.

- vecFarSide = m_Route[m_iRouteIndex].vecLocation;
+ vecFarSide = vecEnd;//m_Route[m_iRouteIndex].vecLocation; // since we use recursion these are not always the same anymore

Another change is somewhat arguable. Besides advancing to the left and right, and forward (from the monster's origin to the goal) by the distance passed into the function, the original algorightm also advances the vector forward by monster's size. We keep the original behavior for the top triangulation level, but will skip it on the inner levels. I don't remember why I did so actually, probably something went broken. I also thought that the initial shift to the right and left is too big on inner levels of recursion, so I omit multiplication by 3 here. You can experiment with it.

The number of trial steps is a variable now:

- for (i = 0; i < 8; i++)
+ for (i = 0; i < tries; i++)

Now to the interesting part.

- if (CheckLocalMove(pev->origin, vecRight, pTargetEnt, NULL) == LOCALMOVE_VALID)
- {
- 	if (CheckLocalMove(vecRight, vecFarSide, pTargetEnt, NULL) == LOCALMOVE_VALID)
- 	{
- 		if (pApex)
- 		{
- 			*pApex = vecRight;
- 		}
- 	}
- }
+ if (CheckLocalMove(vecStart, vecRight, pTargetEnt, &localMoveDist) == LOCALMOVE_VALID)
+ {
+ 	if (CheckLocalMove(vecRight, vecFarSide, pTargetEnt, &localMoveDist) == LOCALMOVE_VALID)
+ 	{
+ 		if (pApexes)
+ 		{
+ 			*pApexes = vecRight;
+ 		}
+ 		return 1;
+ 	}
+ 	else if (n>1 && pApexes)
+ 	{
+ 		result = FTriangulate(vecRight, vecFarSide, localMoveDist, pTargetEnt, pApexes+1, n-1, tries - 2, true);
+ 		if (result)
+ 		{
+ 			*pApexes = vecRight;
+ 			return result+1;
+ 		}
+ 	}
+ }
+ else if (n>1 && pApexes)
+ {
+ 	result = FTriangulate(vecStart, vecRight, localMoveDist, pTargetEnt, pApexes, n-1, tries - 2, true);
+ 	if (result)
+ 	{
+ 		if( CheckLocalMove( vecRight, vecFarSide, pTargetEnt, &localMoveDist ) == LOCALMOVE_VALID )
+ 		{
+ 			pApexes[n-1] = vecRight;
+ 			return result+1;
+ 		}
+ 	}
+ }

• If advancing right works on this step finds an apex, the algorightm works the same way as the original.
• If it could build the path from the start to the right point, but not from the right point to the end, we call a triangulation between the right point and the end point in an attempt to find an apex between these two points (taking into account the distance traveled in CheckLocalMove). This is where the recursion takes an action.
• If it failed to build a path between a starting point to the right one, it also goes on the deeper triangulation level (again, taking into account the distance traveled), and if an apex for this triangulation is found, it also tries to find a path between the right point to the end one. There's also some arithmetic involved to make sure that the intermediate point is assigned at the right place of the apex points array.

Do the same update with going left, using vecLeft instead of vecRight of course. I won't list it here. You can see the full patch in the commit anyway.

We can repeat the changes for going top and bottom, but again, for simplicity we don't focus on flying monsters here. So the only thing we change here is replacing pev->origin with vecStart to account for recursion.

Make sure the function returns integer value, not boolean.

- return false;
+ return 0;

We've done with FTriangulate, so let's move to BuildRoute.

Declare a constant (before the function) which will be our triangulation depth (I called it TRIDEPTH).

+ #define TRIDEPTH 3
bool CBaseMonster::BuildRoute(const Vector& vecGoal, int iMoveFlag, CBaseEntity* pTarget)

Turn vecApex into vecApexes array.

- Vector vecApex;
+ Vector vecApexes[TRIDEPTH];

Adjust the rest so it could assign more than one apex point as intermediate points for the route.

- else if (iLocalMove != LOCALMOVE_INVALID_DONT_TRIANGULATE && FTriangulate(pev->origin, vecGoal, flDist, pTarget, &vecApex))
- {
-	m_Route[0].vecLocation = vecApex;
-	m_Route[0].iType = (iMoveFlag | bits_MF_TO_DETOUR);
-
-	m_Route[1].vecLocation = vecGoal;
-	m_Route[1].iType = iMoveFlag | bits_MF_IS_GOAL;
-
-	RouteSimplify(pTarget);
-	return true;
-}
+ else if (iLocalMove != LOCALMOVE_INVALID_DONT_TRIANGULATE)
+ {
+ 	int result = FTriangulate(pev->origin, vecGoal, flDist, pTarget, vecApexes, TRIDEPTH);
+ 	if (result)
+ 	{
+ 		//ALERT(at_aiconsole, "Triangulated %d times\n", result);
+ 		// there is a slightly more complicated path that allows the monster to reach vecGoal
+ 		for (int i=0; i<result; ++i)
+ 		{
+ 			m_Route[i].vecLocation = vecApexes[i];
+ 			m_Route[i].iType = (iMoveFlag | bits_MF_TO_DETOUR);
+ 		}
+ 		m_Route[result].vecLocation = vecGoal;
+ 		m_Route[result].iType = iMoveFlag | bits_MF_IS_GOAL;
+ 		RouteSimplify( pTarget );
+ 		return true;
+ 	}
+ }

Full patch in one commit here.

Testing!

Now let's test the results (don't forget to update the libraries in your mod directory). As a test site we're going to use the crossfire map. There're 3 security guards on the map if loaded in singleplayer, but no nodes. Go to the barney in the bunker and make him follow you. Barney should follow you out of the room. Without the changes we introduced it would be really hard to get him out.

In this example we've set TRIDEPTH to 3 (you can make it dynamic via cvar but it's out of scope of this tutorial). It can be set to any positive number, but considering the brute-force nature of the algorightm and exponential growth of complexity, increasing this number leads to the performance problems very soon. It all comes down to the efficiency of WALK_MOVE engine function used internally by CheckLocalMove. In my experience the lag becomes notable already on three apex points in GoldSource (it might be different on Xash3D, but I haven't checked), and depending on the machine's performance, even on two apex points! Ideally we want to keep the number of CheckLocalMove calls at minimum.

Possible optimizations.

Decreasing the number of steps to the sides

Remember we've made the number of trial steps a variable? We can decrease the number of trial steps on deeper triangulation levels, passing another value in the recursion. Note that, however, this approach is more a crutch than an actual solution, and it will affect the results of the new algorightm.

Patch

Skipping deep triangulation in BuildNearestRoute

BuildNearestRoute is a last resort for a monster in an attempt to build a path to an enemy. I think it can live without deep triangulation.

Patch

Limiting deep triangulation to followers and scripted monsters

First of all a player wants his allies to follow him or her with less problems as possible. Enemies can continue using the original path finding algorightm. We can also apply a deep triangulation to the monsters in scripted sequences to increase chances that a scripted monster won't stuck on the halfway.

Patch

Optimizing the algorightm

The algorightm itself is not very good. Recursive nature makes the complexity grow exponentially even when it's not needed. E.g. in theory a monster might decide to triangulate to right side two times when it was easier to triangulate one time through the left side. Sadly I haven't done such optimizations myself yet. Maybe it's time to get to it now?

Recommendations

In Field Intensity we use tridepth value set to 2 with all implemented optimizations described above.