Issues with Navmesh and Pathfinding

[Lybra]

Hello everyone,

As a Computer Science/Software Engineering student - interested into Game Development - I decided to dedicate my bachelor thesis to the UDK. To be exact, I am trying to create a Point-and-Click Adventure type of game.

That means:

- indirect Pawn controls via Point-and-Click
- a rather static camera system
- rather small, narrow areas

So far, I have been successful in developing some of the core features...till now. For the actual pathfinding, I decided to use Navmeshes over Waypoints (for obvious reasons I guess). After following a couple of tutorials and the official documentation, I managed to create a basic, yet underwhelming, result:


http://www.youtube.com/watch?v=lxU-iiwLybI

As you can see, there are a couple of problems in it's actual state:

- pawn keeps bumping into obstacles
- pawn is taking detours from time to time
- infinite loops causing crashes
- ...

Navmesh Setup: http://85.25.34.39/navmesh.jpg


The actual code

PlayerController:

state LMBPressedState
{

function PlayerMove(float DeltaTime)
{
Pawn.FaceRotation(RInterpTo(Pawn.Rotation, Rotator(NextMoveLoc-Pawn.Location), DeltaTime, 20000, true),DeltaTime);
super.PlayerMove(DeltaTime);
}

function bool FindNavMeshPath(Vector Loc)
{
// Clear cache and constraints (ignore recycling for the moment)
NavigationHandle.PathConstraintList = none;
NavigationHandle.PathGoalList = none;

class'NavMeshPath_AlongLine'.static.AlongLine(Navi gationHandle, Loc);
class'NavMeshGoal_At'.static.AtLocation(Navigation Handle, Loc);

if (!NavigationHandle.FindPath())
{
return false;
}
return true;
}

Begin:
NavigationHandle.SetFinalDestination(HitLoc);

//Desired point directly reachable?
if(!NavigationHandle.PointReachable(HitLoc))
{
//if not, look for path
if(FindNavMeshPath(HitLoc))
{
FlushPersistentDebugLines();
NavigationHandle.DrawPathCache(,TRUE);
bFoundPath = true;
}
//no path found
else
{
//look for reachable point nearby
class'NavigationHandle'.static.GetValidPositionsFo rBox(HitLoc,Pawn.GetCollisionRadius()*6,Pawn.GetCo llisionExtent(),false,ValidPositions,10);
if(ValidPositions.Length > 0)
{
// no path found yet
bFoundPath = false;
// first location as distance reference
PathDistance = NavigationHandle.CalculatePathDistance(ValidPositi ons[0]);
NextMoveLoc = ValidPositions[0];
foreach ValidPositions(ValidLoc)
{
NavigationHandle.SetFinalDestination(ValidLoc);
if(FindNavMeshPath(ValidLoc))
{
FlushPersistentDebugLines();
NavigationHandle.DrawPathCache(,TRUE);
bFoundPath = true;
if(NavigationHandle.CalculatePathDistance(ValidLoc ) < PathDistance)
{
PathDistance = NavigationHandle.CalculatePathDistance(ValidLoc);
NextMoveLoc = ValidLoc;
}
}
}
NavigationHandle.SetFinalDestination(NextMoveLoc);
//clear the array
ValidPositions.Remove(0,ValidPositions.Length);
}
//found no nearby points
else
{
bFoundPath = false;
}
}
}
else
{
//point reachable, move there directly
MoveTo(HitLoc);
bFoundPath = false;
}

//pathfinding loop
while( Pawn != None && bFoundPath)
{
if( NavigationHandle.GetNextMoveLocation(NextMoveLoc, Pawn.GetCollisionRadius()) )
{
//prevent infinite loop
if(NextMoveLoc == PreviousLoc)
{
break;
}
if (!NavigationHandle.SuggestMovePreparation(NextMove Loc,self))
{
DrawDebugLine(Pawn.Location,NextMoveLoc,255,0,0,tr ue);
MoveTo(NextMoveLoc);
PreviousLoc = NextMoveLoc;
}
}
}
FlushPersistentDebugLines();

End:
GotoState('PlayerWaiting');
}


Scout


class SEGameScout extends UDKScout;

DefaultProperties
{
Begin Object NAME=CollisionCylinder
CollisionRadius=40
End Object

PathSizes.Empty

PathSizes(0)=(Desc=Human,Radius=20,Height=54)
PathSizes(1)=(Desc=Common,Radius=30,Height=96)
PathSizes(2)=(Desc=Max,Radius=50,Height=144)

TestJumpZ=0

MaxStepHeight=10
MaxJumpHeight=0
WalkableFloorZ=0.25

SizePersonFindName=Human

NavMeshGen_StartingHeightOffset=8.0
NavMeshGen_StepSize=20.0
NavMeshGen_EntityHalfHeight=24
NavMeshGen_MaxStepHeight=10.0

}


I already wasted a couple of days in a really tight schedule. To be honest, I didn't expect UDK to struggle with fundamental stuff like this, hopefully I am the one doing something wrong, something that can be fixed :)

Any help is greatly appreciated!

Thanks!

[meganaut]

Hi Lybra,

I have a couple of ideas about why this bahaviour is happening.
The MAIN problem i see here is that you are using some navmesh contraints that are far from helping you.
You have this:




class'NavMeshPath_AlongLine'.static.AlongLine(Navi gationHandle, Loc); class'NavMeshGoal_At'.static.AtLocation(Navigation Handle, Loc);

What you would be better off using is this:


class'NavMeshPath_Toward'.static.TowardPoint( NavigationHandle, Loc);
class'NavMeshPath_EnforceTwoWayEdges'.static.Enfor ceTwoWayEdges(NavigationHandle);
class'NavMeshGoal_At'.static.AtActor( NavigationHandle, Loc );

This should resolve SOME of your problems.

The other possible issue i can see initially is that your code to look for a reachable point nearby might be a little off. (but you should test this, its just not how i would normally do it.)

At anyrate, changing the navigation goal contraint to point based rather than line based should work better for you.

-Mega

[Lybra]

Hi Mega,

Thanks for your reply!



What you would be better off using is this:


class'NavMeshPath_Toward'.static.TowardPoint( NavigationHandle, Loc);
class'NavMeshPath_EnforceTwoWayEdges'.static.Enfor ceTwoWayEdges(NavigationHandle);
class'NavMeshGoal_At'.static.AtActor( NavigationHandle, Loc );

This should resolve SOME of your problems.


Sadly enough, it doesn't. That's pretty much what I started with and ended up changing. Just to be sure I double checked it right now and I am positive it's even worse:


http://www.youtube.com/watch?v=8z5UroQf7_I




The other possible issue i can see initially is that your code to look for a reachable point nearby might be a little off. (but you should test this, its just not how i would normally do it.)


This part of the code actually works pretty well and is only used when the player clicks somewhere outside the defined navmesh. The issues occur even if you click on a valid point inside the mesh.

Anyway, thanks a lot. If you have any other ideas, please let me know. I really have to get this right :(

[Lybra]

/bump

navmesh/pathfinding working fine for everyone else?

[ferrous]

Yup, I've been in the same boat, I based my script on a tutorial from here: http://x9productions.com/blog/?page_id=357. I was never able to get NavMesh pathfinding working with mouse clicks. The actor would take ineffecient paths, get stuck, bump into things, and I'd get hangs/crashes.

My contraints are:

// Create constraints
class'NavMeshPath_Toward'.static.TowardPoint( NavigationHandle, NavigationDestination );
class'NavMeshGoal_At'.static.AtLocation( NavigationHandle, NavigationDestination, 20, );

I would love to see a working example!

[meganaut]

Well, By the look of it the issue is with the point reachable if statement. I cant see an instance of the Pawn moving directly when clearly it should be. This is also shown by the way that the player will "look for a reachable point" once he gets close to the clicked position.

SO... either you have overwritten the pointreachable function incorrectly.. or your hitLoc is not on the navmesh / below the navmesh.
I'm quite sure that teh location doesnt have to be directly ON the navmesh. but there might be issues if it is below. You should draw a debugsphere at your click position so you can see if it is above or below the navmesh.

Thats all I can think of. Your code looks solid... but the actual application of that code isnt flowing the way you intended. So you have to look at why that if statement is working incorrectly.

-Mega

[ferrous]

Doesn't something like NavigationHandle.ComputeValidFinalDestination( NavigationDestination ); ensure that the final destination is on the navmesh?

[Lybra]

/Push

I've come to a point where I tried EVERYTHING. So far the forums are full of unresolved problems with Navmesh and Pathfinding....
Did ANYONE ever manage to get this stuff working or is Epic just being lazy for months? I really can't see what makes UE3 the "best engine", so far it is only risking my graduation (yes I am upset about this).

[tegleg]

my experiences with navmesh led me to writing my own nav system from scratch, there are also problems navigating over any kind of distance.

unfortunately epic are becoming notorious for leaving things broken in favour of adding big new features (that are also broken)
hopefully they will realise this is an important issue (along with many others) and fix it before udk becomes some kind of joke.
people seem to be steadily abandoning udk in favour of more stable engines, such a shame as udk could be really really good.

[Lybra]

my experiences with navmesh led me to writing my own nav system from scratch, there are also problems navigating over any kind of distance.

Believe me, if I had the time, I would do the same...

Thanks for sharing your thoughts!

[Lybra]

Update:

I redid the pathfinding code after looking at some parts of the DungeonDefenders source:



var Vector NextMoveLocation;

event bool GeneratePathToLocation(Vector Goal,optional float WithinDistance,optional bool bAllowPartialPath)
{
if(NavigationHandle == none)
{
InitNavigationHandle();
}
NavigationHandle.SetFinalDestination(Goal);
// point is directly reachable, no path needed
if(NavigationHandle.PointReachable(Goal,,false))
{
`log("GeneratePathToLocation: point reachable, returning TRUE");
NextMoveLocation = Goal;
return true;
}
NavigationHandle.ClearConstraints();

class'NavMeshPath_Toward'.static.TowardPoint(Navig ationHandle,Goal);
class'NavMeshGoal_At'.static.AtLocation(Navigation Handle,Goal,WithinDistance,bAllowPartialPath,true) ;

if(NavigationHandle.FindPath())
{
`log("GeneratePathToLocation: Found a path!");
if(NavigationHandle.GetNextMoveLocation(NextMoveLo cation, PlayerPawn.GetCollisionRadius()))
{
DrawDebugPoint(NextMoveLocation,10.f,MakeLinearCol or(1.f,0.f,0.f,1.f),true);
if(VSize(NextMoveLocation) == 0)
{
`log("GeneratePathToLocation: NextMoveLocation size == 0!");
return false;
}
else if(!NavigationHandle.PointReachable(NextMoveLocati on))
{
//this shouldn't happen, but it does :(
`log("GeneratePathToLocation: NextMoveLocation not reachable!");
return false;
}
return true;
}
}
`log("GeneratePathToLocation: No path found!");
return false;
}


For some weird reason GetNextMoveLocation() returns unreachable locations at certain points in the world. Any Ideas? :(

[U F O]

Dude This **** is weird :( me too am in the same boat :D