Leaving tracks at convenient intervals with navmesh

I’m working on a system that allows bad guys to leave footprints at some reasonable interval, so the player can track them across the map. The basic idea is really simple: I draw a path from their start point to their current location, and add a footprint (currently denoted by a debugsphere) at intervals:

	UNavigationPath *tpath;
	UNavigationSystem* NavSys = UNavigationSystem::GetCurrent(GetWorld());
	if (!NavSys){

	tpath = NavSys->FindPathToLocationSynchronously(GetWorld(), StartPoint, EndPoint);

	if (tpath != NULL)
		int32 NodeInterval = 2;
		FVector lastLocation = FVector(0, 0, 0);
		for (int pointiter = 0; pointiter < tpath->PathPoints.Num()/NodeInterval; pointiter++)
			FVector distanceVec = (tpath->PathPoints[pointiter*NodeInterval] - lastLocation);
			if (distanceVec.Size() > 1000){
				DrawDebugSphere(GetWorld(), tpath->PathPoints[pointiter*NodeInterval], 10.0f, 12, FColor(255, 0, 0));
				lastLocation = tpath->PathPoints[pointiter*NodeInterval];

This mostly works, but different terrain types need vastly different intervals of clues: long, straight roads only need a handful of footprints over time, but narrow alleys or sewers with tons of twists and turns need lots and lots of footprints. The solution I’m using now is to simply apply a different interval and minimum distance between nodes in different circumstances, but that in turn makes it hard to track somebody across multiple terrain types.

So is there an obvious way to make this more dynamically responsive to the situation? The general idea I’m trying to encapsulate is that the number of footprints goes up with the complexity of the path, but I’m really not sure how to express that other than with a straight interval.

I think you already have the right idea. Let the pathing system calculate a path from you to the bad guy first. Then process this path using some metric (count the number of turns) and have this change the density of the footprints. The counting could be as simple as checking the dot product between the current-to-next and current-to-previous PathPoint vectors. A dot product value of 1 means the bad guy turned around 180 degrees, where 0 means he turned left or right and -1 means he went in a straight line.

An alternative to this would be to let the bad guys keep track of the turns along their way for the past X seconds they take as and when they make these decisions in the AI.
A third way using just simple volumes placed in the level with the properties you need would be much easier to implement but probably harder to fine-tune and more time consuming to set up per level.

Ooh, the dot product sounds like an excellent idea, I never considered using the entity’s actual facing to calculate it- thanks for the feedback and idea! :slight_smile: