DoN's 3D-Pathfinding / Flying-AI system (with full source!)

[Ryan Darcey]

Thank you so much, [MENTION=14603]VSZ[/MENTION]! Did some more investigating based on your suggestions and logged my findings below.

1) Low FPS: Don't lower the query timeout for obtaining performance. Instead lower "Max Path Solver Iterations Per Tick" and "Max Collision Solver Iterations Per Tick". Even an infinitely long query-timeout should not affect your performance as long the amount of work you're doing per tick is fixed and predictable. Btw what's the CPU you're testing on?

I'm running with an Intel Core i5-4690K Processor (3.5 GHz) w/ a debug build. My game tick idles at 5-6ms without any path solver queries, and then it spikes to 18ms when it fails to solve a path query with only 200 iterations set for the max. If I set the path solver iteration max to the default of 500, I spike all the way up to 50ms for the game tick when it fails to solve. Yikes!

2) Direct path via line-trace != Direct path via collision-sweep:

Line-trace is only a preliminary test to prove if a requested path is straight line. Only by sweeping the entire collision shape from origin to destination that is confirmed. If the usecase in your pic was truly straight-line you wouldn't even have to worry about query-timeout/etc, the solution is returned instantly (synchronously). I suggest confirming what's happening here by placing a breakpoint in ADonNavigationManager::SchedulePathfindingTask Line no: 2045. If it's not a direct path, find out which collision object was hit. You can also enter log DoNNavigationLog Verbose into the console and look for "Optimizer hit ....." to know what is blocking the path but you'll have to pick that out from the super-verbose logs.

This verbose debug is GREAT! Thanks so much for the heads up there. I noticed that IsDirectPathLineSweep is returning false in ADonNavigationManager::SchedulePathfindingTask b/c it's hitting the player pawn's collision capsule. Is that expected? Here are my collision settings for the collision capsule:

https://drive.google.com/open?id=0B9...UFtWGc1UFlFTEE

If I set the capsule to "No Collision", all of my direct line pathing succeeds. So, I assume my collision on the capsule is a major culprit w/ regard to my issues. What have a screwed up here? O_o

3) Hanging issue This is not performance related. It's a bug where the solution generator gets caught up in a circular chain while trying to link path nodes from destination to origin.

To resolve your immediate issue try adding this line at the beginning of the loop:

if(VolumeSolution.Contains(*nextVolume))
     break;

I haven't tested it or anything though, but hope it provides the general idea.

YES! This fixed the hang

4) Next steps:
First find out which obstacle is blocking your bot from taking a direct path. Rest assured there is something blocking it, that's why the asynchronous code path is even coming into play. Is a prop or weapon of your bot (or its destination) set to WorldStatic and blocking itself from moving anywhere?

Second, offset your destination around a bit and away from obstacles till you find a sweet spot where it works. The sample project shows this in action with the "good bot origin / bad bot origin" example. Increasing the "tweakMagnitudes" like I told CineBeast in this post might also help.

YAS! increasing those "tweakMagnitudes" values cleaned up the remaining failures when it was trying to path around more complex landscape geo. I made them 10x bigger cause the scale of my world is so much larger. Maybe worth exposing those for the user to edit instead of hard coding?

Next, the infinite loop is only a symptom of something else going fundamentally wrong in path generation but without a solid repro it's hard for me to debug it. I haven't seen it in my project either.

Yeah...that's weird. At least I have a fix for my hang and now that my path finding isn't failing on the time, those instances where it was hanging aren't occuring.

Thank you so much, [MENTION=14603]VSZ[/MENTION]. I hope I can pay you back one day for all your help

[VSZ]

I'm running .... w/ a debug build.

Debug builds are painfully slow for CPU intensive stuff (which this plugin really is). Unless I'm chasing a particularly complex bug I prefer DevelopmentEditor.

it's hitting the player pawn's collision capsule. Is that expected?

Sounds like a bug. Ideally all collision on your pawn should be ignored. Try this fix: Go to the function bool ADonNavigationManager::IsDirectPathSweep(UPrimitiveComponent* CollisionComponent and comment out the following lines (including the else statement):

if (CollisionShapeInflation == 0.f)
{
	bHit = GetWorld()->ComponentSweepMulti(OutHits, CollisionComponent, Start, End, FRotator(), collisionParams);
}
else

I've had this fix in my local 4.11 branch for a while on a related bug, it might fix yours too.

(TweakMagnitudes) Maybe worth exposing those for the user to edit instead of hard coding?

Definitely. Like so many things in the plugin I simply didn't have time to do that. It's a small task sure, but there's like a gazillion small tasks waiting to be taken up elsewhere too!

Thank you so much, [MENTION=14603]VSZ[/MENTION]. I hope I can pay you back one day for all your help

NP, glad to help!

[Ryan Darcey]

Sounds like a bug. Ideally all collision on your pawn should be ignored. Try this fix: Go to the function bool ADonNavigationManager::IsDirectPathSweep(UPrimitiveComponent* CollisionComponent and comment out the following lines (including the else statement):

if (CollisionShapeInflation == 0.f)
{
	bHit = GetWorld()->ComponentSweepMulti(OutHits, CollisionComponent, Start, End, FRotator(), collisionParams);
}
else

I've had this fix in my local 4.11 branch for a while on a related bug, it might fix yours too.

Yeah! This seems like a good fix for the unexpected pawn collisions. Thanks!

I'm still noticing a some path finding fails that seem like they should be successes, but will have to dig deeper and let you know if I can pinpoint exactly what's going on. At least a majority of my issues are now cleaned up.

[JayWebb]

This is a really great plugin and i highly recommend this.
I have one question about this. Will EQS work with this type of ai path finding? I want Ai to look for a hiding spot by checking the environment and not use the Goal Cues. Any help would be great.

[VSZ]

[MENTION=67058]JayWebb[/MENTION] Hey, you can use EQS or any mechanism you deem fit to determine a hiding spot for your AI and just feed the result from that (in this case, your hiding spot as an FVector) into either the Fly To node (if you're using behavior trees) or the pathfinding API (for fully customized queries). The goal cues you mention are just an example from the sample project for new users to easily test the system (by dragging the cue around map), they have little to do with the plugin itself.

I haven't used EQS myself so I don't know how you would set it up to find good hiding spots, but if all else fails you can just use good-old line-tracing/sweeping/etc and query the environmental geometry that way.

[Ryan Darcey]

Hey, [MENTION=14603]VSZ[/MENTION]. I'm still trying to debug some of these instances where the pathfinding is failing. It's not as obvious as the previous use cases I had before. Even with verbose logs on, this is the only information that's being written out in these instances.

DoNNavigationLog:Error: Query timed out for Actor Sentinel_Pawn_C_0. Num iterations : 23000
DoNNavigationLog: Found empty pathsolution in Fly To node. Aborting task...

Are there specific functions I should focus on stepping through to determine why it's unable to find a solution? Is there some way to narrow down at which point along the path the solution is failing (start, end, in between)? Is there a way to display the raw path as it's being calculated so I can see how far it got to the desired location?

This is the sort of weird behavior I'm seeing:

1) Request a path solution and fail at some location.
2) Move slightly closer in direction of enemy and request path again. Path succeeds.
3) Very quickly as enemy is pathing to success location, move back to the original fail location and request a path again. Path succeeds.

So, this behavior makes me think there's nothing wrong with the enemies origin or the final desired destination. Something having to do with distance away from the enemy seems to be making the pathfinding fail, but I can't say for sure. That's just the behavior I'm seeing. I think pointing me to key functions that I should focus on debugging will help me the most

Thanks again for any help!

[VSZ]

With a high VoxelSize like 2000 it is quite possible that there is "no solution" for the path you've requested.

Manual Verification:

First manually verify that there is a contiguous chain of green voxels from origin to destination. The origin and destination themselves can be red ("tweakmagnitudes" should take care of that if configured right).

1) Set DrawDebugVolumes to true inside DebugParams
2) Turn voxel visualization on (refer the sample project's level blueprint) and
3) PIE, fly around from origin to destination to see how navigable the voxels really are.

Debugging code:

If you see no issues there then it's time to dive into the code. Debugging these functions is advisable:
1) ADonNavigationManager::SchedulePathfindingTask
This is the starting point, useful just to confirm that the origin and destination volumes (or vectors if you're using the Unbound/Infinite manager) are being calculated right.

2) ADonNavigationManager::TickNavigationSolver
This is called each tick to solve the query. If you're sure your path definitely has a solution then this is the place to check out exactly why a certain volume that looked navigable (when you eyeballed it in the editor) isn't considered navigable or isn't considered as a valid neighboring node.

--

Tips for debugging:
Use DrawDebugText or something like that to tag the voxels on screen so you can correlate your expected solution chain while debugging. I might add that as a debug tool in the future but for now you'll have to code it in.

Finally, don't rely on your bot's live behavior to provide your test cases. That makes things unpredictable and can be very frustrating to debug. Instead use an actor as a goal cue (even a simple sphere will do) that you can carefully place around your map and generate various test cases with it. That's the best way to not only debug things, but also to confirm that all the pathfinding usecases for your project are met by the plugin.

Initial setup can be time-consuming but once you're past that phase you likely won't have to worry about pathfinding again and can shift focus to things like gameplay and AI behavior.

[Ryan Darcey]

[MENTION=14603]VSZ[/MENTION], thanks for the advice! So, I haven't quite figured out what's going on yet, but I think I have some interesting debug for you to look at. This video clip shows some debug output for 2 queries; a path fail and a path success. The path fail destination is the lone green voxel at the beginning of the clip. The path success destination is where my little eyeball pawn is at the beginning of the clip.

Make sure you download this clip instead of streaming it if the streaming quality is poor.

https://drive.google.com/open?id=0B9...i1CZlZ4QlA5ZXc

The debug points you see rendering are coming from this function I altered:

void ADonNavigationManager::TickNavigationSolver(FDonNavigationQueryTask& task)
{	
	auto& data = task.Data;

	data.SolverIterationCount++;

	if (!data.Frontier.empty())
	{
		// Move towards goal by fetching the "best neighbor" of the previous volume from the Frontier priority queue
		// The best neighbor is defined as the node most likely to lead us towards the goal
		auto currentVolume = data.Frontier.get(); 

#if !UE_BUILD_SHIPPING
		if (task.Data.DebugParams.DrawDebugVolumes)
		{
			DrawDebugPoint_Safe(GetWorld(), currentVolume->Location, debugPointSize, FColor::Green, true, -1.f);
		}
#endif //!UE_BUILD_SHIPPING

		// Have we reached the goal?
		if (currentVolume == data.DestinationVolume)
		{
			data.bGoalFound = true;
			return;
		}

		// Discover all neighbors for current volume:
		const auto& neighbors = FindOrSetupNeighborsForVolume(currentVolume);
		
		// Evaluate each neighbor for suitability, assign points, add to Frontier
		for (auto neighbor : neighbors)
		{	

#if !UE_BUILD_SHIPPING
			if (task.Data.DebugParams.DrawDebugVolumes)
			{
				DrawDebugPoint_Safe(GetWorld(), neighbor->Location, debugPointSize*0.5f, FColor::White, true, -1.f);
			}
#endif //!UE_BUILD_SHIPPING

			ExpandFrontierTowardsTarget(task, currentVolume, neighbor);
		}
	}
}

The path fail generated that crazy dish shaped set of debug points. The path success generated the much more direct set of debug points to the success location.

The destinations are very close to each other and clearly seem like each should have a valid path from the origin. Any suggestions for looking further into this? Thanks again for your help!

[VSZ]

Those debug points clearly indicate an obstacle preventing the solver from moving towards the goal. So instead it fans out in other directions producing that dish shape.

Again, the manual verification process from my previous post is the only way we can understand what is blocking the path. Here voxel visualization (pick it up from the sample project) is far more important than debug points because knowing how large the voxels are, which voxels are red (blocked by obstacle) and which ones are green (free to navigate) is crucial to understanding which obstacle is blocking your path.

With a high voxel size like 2000 even a tiny stone with collision enabled inside a voxel will block the entire 2000 x 2000 x 2000 volume! In your case we need to understand a) what obstacle is blocking the path and b) decrease the voxel size till we find an optimal value that is neither too small (to be practical for your large map) nor too large (to allow for accurate pathfinding).

[BrUnO XaVIeR]

Wow... Exactly this is in my "Need to do, must have list"; and here's an already built system. Time saver.
This is awesome!

[Ryan Darcey]

Again, the manual verification process from my previous post is the only way we can understand what is blocking the path. Here voxel visualization (pick it up from the sample project) is far more important than debug points because knowing how large the voxels are, which voxels are red (blocked by obstacle) and which ones are green (free to navigate) is crucial to understanding which obstacle is blocking your path.

Sorry, I should have mentioned that I already completed this step. It's a giant sea of green voxels from the origin to the final destination.

https://drive.google.com/open?id=0B9...G5JVVBIbXVaNUk

For reference, here's a shot of voxel size in relation to the AI unit trying to path around the level.

https://drive.google.com/open?id=0B9...jlac3BIZk51Rnc

Here are my nav manager settings.

https://drive.google.com/open?id=0B9...UFEVVlqLXBfa2s

Here are my tweak magnitudes in code:

const float ADonNavigationManager::tweakMagnitudes[3] = { 2000, 2000, 2000 };

Here's the debug implementation I modified from your sample level to display the green voxel path from start to end.

https://drive.google.com/open?id=0B9...1F1QjZ0eWtvbFU

Finally, I added some more debug display to show voxels that fail the "CanNavigate" test during the navigation solver tick. Here's the modified code.

bool ADonNavigationManager::CanNavigate(FDonNavigationVoxel* Volume)
{
	if (!Volume->bIsInitialized)
		UpdateVoxelCollision(*Volume);

	bool bCanNavigate = Volume->CanNavigate();

#if !UE_BUILD_SHIPPING
	if (!bCanNavigate)
	{
		DrawDebugPoint_Safe(GetWorld(), Volume->Location, debugPointSize*2.f, FColor::Red, true, -1.f);
	}
#endif //!UE_BUILD_SHIPPING

	return bCanNavigate;
}

Here are the results. It doesn't look like there's anything blocking the AI unit in the direction it wants to travel. There must be something else veering the navigation solver away from the goal destination?

https://drive.google.com/open?id=0B9...mlaX0ZETUhON3c

Just to be clear, there are many examples of pathfinding working perfectly around the level. There seems to be some edge case I'm hitting that has a not obvious fail.

Thanks again for your patience. I understand you're busy and there's not really any reason you should be helping me out, so I appreciate any insight you have to offer. Hopefully this uncovers a real bug, or at the very least, calls to attention an example of improper user settings, if that happens to end up being the case.

[VSZ]

[MENTION=43607]rcdarcey[/MENTION] Looking at those screenshots I'd have to agree with you, everything looks fine and the voxel size actually looks small enough to even increase it further without impact.

Your last screenshot tells me that the voxels we care about are not even considered as valid neighbors so they never even reach the CanNavigate test!

This could be a bug in the function ADonNavigationManager::FindOrSetupNeighborsForVolume that I haven't yet encountered myself. Two quick brute-force checks I can think of:-
1) Disable partial-caching of neighbors by commenting out the entire if (NavGraphCache.Contains(Volume)) block
2) Inside AppendImplictDOFNeighborsForVolume try removing all the CanNavigate checks for the X, Y and Z blocks. Those checks are actually needed, but bypassing them will help us narrow down the root cause.

Thanks for reporting these issues, it will make life easier for new users trying to onboard the plugin.

Wow... Exactly this is in my "Need to do, must have list"; and here's an already built system. Time saver. This is awesome!

Thanks Bruno! Incidentally I'll need your Save plugin next month so I look forward to checking that out soon.

[Ryan Darcey]

This could be a bug in the function ADonNavigationManager::FindOrSetupNeighborsForVolume that I haven't yet encountered myself. Two quick brute-force checks I can think of:-
1) Disable partial-caching of neighbors by commenting out the entire if (NavGraphCache.Contains(Volume)) block
2) Inside AppendImplictDOFNeighborsForVolume try removing all the CanNavigate checks for the X, Y and Z blocks. Those checks are actually needed, but bypassing them will help us narrow down the root cause.

So, here's what my 2 functions now look like, and the path finder is still failing exactly the same as before O_o

TArray<FDonNavigationVoxel*> ADonNavigationManager::FindOrSetupNeighborsForVolume(FDonNavigationVoxel* Volume)
{
// 	if (NavGraphCache.Contains(Volume))
// 	{
// 		auto neighbors = *NavGraphCache.Find(Volume); // copy by value so we don't pollute the cache implicit DOFs
// 
// 		AppendImplictDOFNeighborsForVolume(Volume->X, Volume->Y, Volume->Z, neighbors);
// 
// 		return neighbors;
// 	}
// 	else
	{
		// Neighbors not found, Lazy loading of NAV Graph for given volume commences...
		TArray<FDonNavigationVoxel*> neighbors;
		DiscoverNeighborsForVolume(Volume->X, Volume->Y, Volume->Z, neighbors);
		NavGraphCache.Add(Volume, neighbors);

		AppendImplictDOFNeighborsForVolume(Volume->X, Volume->Y, Volume->Z, neighbors);

		return neighbors;
	}
}

void ADonNavigationManager::AppendImplictDOFNeighborsForVolume(int32 x, int32 y, int32 z, TArray<FDonNavigationVoxel*>& Neighbors)
{
	bool bNeedsValidaion = x == 0 || y == 0 || z == 0 || x == XGridSize - 1 || y == YGridSize - 1 || z == ZGridSize - 1;

// 	if (!bNeedsValidaion || (IsValidVolume(x + 1, y, z + 1) && IsValidVolume(x - 1, y, z + 1) && IsValidVolume(x + 1, y, z - 1) && IsValidVolume(x - 1, y, z - 1) &&
// 		IsValidVolume(x, y + 1, z + 1) && IsValidVolume(x, y - 1, z + 1) && IsValidVolume(x, y + 1, z - 1) && IsValidVolume(x, y - 1, z - 1) &&
// 		IsValidVolume(x + 1, y + 1, z) && IsValidVolume(x - 1, y + 1, z) && IsValidVolume(x + 1, y - 1, z - 1) && IsValidVolume(x - 1, y - 1, z))
// 		)
 	{
		// X		

		//if (CanNavigate(&VolumeAtUnsafe(x + 1, y, z)) && CanNavigate(&VolumeAtUnsafe(x, y, z + 1)))
			Neighbors.Add(&VolumeAtUnsafe(x + 1, y, z + 1));

		//if (CanNavigate(&VolumeAtUnsafe(x - 1, y, z)) && CanNavigate(&VolumeAtUnsafe(x, y, z + 1)))
			Neighbors.Add(&VolumeAtUnsafe(x - 1, y, z + 1));

		//if (CanNavigate(&VolumeAtUnsafe(x + 1, y, z)) && CanNavigate(&VolumeAtUnsafe(x, y, z - 1)))
			Neighbors.Add(&VolumeAtUnsafe(x + 1, y, z - 1));

		//if (CanNavigate(&VolumeAtUnsafe(x - 1, y, z)) && CanNavigate(&VolumeAtUnsafe(x, y, z - 1)))
			Neighbors.Add(&VolumeAtUnsafe(x - 1, y, z - 1));

		//Y
		//if (CanNavigate(&VolumeAtUnsafe(x, y + 1, z)) && CanNavigate(&VolumeAtUnsafe(x, y, z + 1)))
			Neighbors.Add(&VolumeAtUnsafe(x, y + 1, z + 1));

		//if (CanNavigate(&VolumeAtUnsafe(x, y - 1, z)) && CanNavigate(&VolumeAtUnsafe(x, y, z + 1)))
			Neighbors.Add(&VolumeAtUnsafe(x, y - 1, z + 1));

		//if (CanNavigate(&VolumeAtUnsafe(x, y + 1, z)) && CanNavigate(&VolumeAtUnsafe(x, y, z - 1)))
			Neighbors.Add(&VolumeAtUnsafe(x, y + 1, z - 1));

		//if (CanNavigate(&VolumeAtUnsafe(x, y - 1, z)) && CanNavigate(&VolumeAtUnsafe(x, y, z - 1)))
			Neighbors.Add(&VolumeAtUnsafe(x, y - 1, z - 1));

		//Z
		//if (CanNavigate(&VolumeAtUnsafe(x + 1, y, z)) && CanNavigate(&VolumeAtUnsafe(x, y + 1, z)))
			Neighbors.Add(&VolumeAtUnsafe(x + 1, y + 1, z));

		//if (CanNavigate(&VolumeAtUnsafe(x - 1, y, z)) && CanNavigate(&VolumeAtUnsafe(x, y + 1, z)))
			Neighbors.Add(&VolumeAtUnsafe(x - 1, y + 1, z));

		//if (CanNavigate(&VolumeAtUnsafe(x + 1, y, z)) && CanNavigate(&VolumeAtUnsafe(x, y - 1, z)))
			Neighbors.Add(&VolumeAtUnsafe(x + 1, y - 1, z));

		//if (CanNavigate(&VolumeAtUnsafe(x - 1, y, z)) && CanNavigate(&VolumeAtUnsafe(x, y - 1, z)))
			Neighbors.Add(&VolumeAtUnsafe(x - 1, y - 1, z));

	}
}

To make things even weirder, here's a screen grab of 2 use cases; one succeeds and one fails. The one that succeeds is a copy of the AI unit that I duped and slightly nudged over a bit towards the goal. It seems like distance from origin to goal is playing a factor, though I have no idea why.

https://drive.google.com/open?id=0B9...l9TY0tyejJYVUk

I don't have time to look into it further tonight, but will try tomorrow. Just wanted to send the new info out in case it triggered something for you

[VSZ]

One thing that's not apparent from your screenshots is the location of the origin and destination volumes. Assuming DrawDebugVolumes is turned on the origin should show up as a white box and the destination as a green box. I'm curious to know where they're placed when the query fails, especially the white origin box.

Here's a theory - maybe your tweak magnitudes are somehow bumping the origin volume somewhere unexpected so even though we see an apparent sea of green voxels from actual origin to actual destination, the effective origin (created by applying the tweak magnitude on your origin) may be somewhere else.

At this stage, a screenshot capturing only the origin, the origin volume and the first 2-3 set of voxel neighbors alone will really help us understand what's going on. You can achieve this by using the existing SolverIterationCount counter in TickNavigationSolver to limit all your drawdebug activity if the SolverIterationCount has exceeded say 5 (for example). That should provide a simple visualization of just origin and the initial set(s) of neighbors with which we should finally be able to solve this puzzle!

Edit: More ideas - Turn collision off on your pawn and then on your entire landscape and see if either makes a difference. Anything to help narrow down which collision entity is involved here may also help us narrow down the issue.

[Ryan Darcey]

Man, thanks for sticking through this with me, [MENTION=14603]VSZ[/MENTION]. I feel like we're getting close to figuring this out!..and then I can start trying to figure out how I'm ever going to be able to reward you for incredible generosity

One thing that's not apparent from your screenshots is the location of the origin and destination volumes. Assuming DrawDebugVolumes is turned on the origin should show up as a white box and the destination as a green box. I'm curious to know where they're placed when the query fails, especially the white origin box.

Here are the origins for the 2 pawns with the debug display you were interested in. The pawn sitting on the left obviously failed and the one that was to the right made it to the goal. As you can see, just empty space between them.

https://drive.google.com/open?id=0B9...nhjcFVIVXpUSnM

Also, here are the voxels surrounding the origins:

https://drive.google.com/open?id=0B9...kFQVm56YlFBMG8

Here's the goal. You can see the pawn that had a successful query is chillin' and the green voxel is slightly sticking out.

https://drive.google.com/open?id=0B9...FZYRGJsQlQ2Qm8

Also, voxels around goal:

https://drive.google.com/open?id=0B9...k1vak1UVExPR2s

Here's a theory - maybe your tweak magnitudes are somehow bumping the origin volume somewhere unexpected so even though we see an apparent sea of green voxels from actual origin to actual destination, the effective origin (created by applying the tweak magnitude on your origin) may be somewhere else.

I tried reducing my tweak magnitudes all down to 100, still same result.

At this stage, a screenshot capturing only the origin, the origin volume and the first 2-3 set of voxel neighbors alone will really help us understand what's going on. You can achieve this by using the existing SolverIterationCount counter in TickNavigationSolver to limit all your drawdebug activity if the SolverIterationCount has exceeded say 5 (for example). That should provide a simple visualization of just origin and the initial set(s) of neighbors with which we should finally be able to solve this puzzle!

Here are the results. Dude on the left just doesn't want to leave his home!

https://drive.google.com/open?id=0B9...1hrSEhScXNYcEE

Edit: More ideas - Turn collision off on your pawn and then on your entire landscape and see if either makes a difference. Anything to help narrow down which collision entity is involved here may also help us narrow down the issue.

Turning off collision on the landscape results in both pawns succeeding with a direct path sweep. Turning off collision on the pawns has no impact on the result.

OK...

...with this last test I just did I am 99% convinced there's something about the distance between the origin and goal that's the culprit here. I slightly nudged the goal towards both the origins, and now they both succeed!

https://drive.google.com/open?id=0B9...1pzWTJ6dVZ6NVE

This seems to tell me that there's nothing inherently wrong with the origins or goals. We have examples where both pawns are able to leave their origin to pursue the goal, and the goal is always able to be reach by at least one of the pawns. I've been looking but haven't found anything...are there any other numbers that would be sensitive to distances other than tweak magnitudes? Like, is the scale of my map breaking some assumption in code about the max distances the pawns might want to travel?