RichAI: Erratic behaviour

[Wildcard]

This is a follow up to AStar - RecastGraph, RichAI - Performance?

I’m seeing some very erractic behaviour from agents. Agents find and take the correct path, but at some point along the path they circle back for a bit before continuing on their path. This can happen 0-4 (give or take) times in the same spot before they continue on their path.

I currently have it set so that SearchPath() is called 1x when the agent starts. WallForce/Dist are set to 0 (but the problem also happens with those set to default). But the same behavior is visible when the agents are set to “Dynamic, at least every 10s, Sensitivity 10”. I’ve taken a video with this setting:

pathfinding

According to the gizmos, there’s nothing visibly wrong in this spot:

This isn’t tied to the fact that the agents are very close to their destination (in terms of line of sight) at that point. Neither is it tied to the complexity of the path. I can replicate it (less reliably) when their path is a very very long straight line as well, where they issue happens when the agents are still about 20 units away from the destination.

Since it also isn’t a matter of the agents re-calculating their path (again, it also happens when they calculate a path only 1x, when they start out), or an issue with local avoidance (as you can see, the first agent exhibits this behavior alone) I am at a loss.

The issue goes away if I set the agents to recalculate their path every 2 seconds.
If I set it to every 4 seconds, then the issue appears, in a “milder” form. The agents either stop in that spot for half a second, or they turn around and go back half the distance that they would at 10 seconds.

[Wildcard]

FYI, I’m using 4.3.48. I just upgraded to 4.3.61 with no change in the behavior (and then rolled back to 4.3.48).

[Wildcard]

I tested some more. This is the last calculated path before the agent starts tripping over its feet. Of interest are the three points that are very close together:

I visualized them by adding spheres at these locations, so you can see how extremely close they are:

This is exactly the spot where the agent trips up. So it seems the agent reaches the first spot, but can’t hit the second one, then turns around, misses it again, eventually hits it and then the same thing again for the third point.

That explains why setting the recalculation really low fixes the issue - once we’re past the first point we calculate a new path that doesn’t take us back to those three bunched up points, and we’re golden.

So the questions are: Why are there 3 points so close together? And why can’t the agent hit them?

I tried increasing the rotation speed of the agents (default is 360, I had it at 250, I tried 1080 for the sake of this issue), thinking that maybe the agent can’t turn quick enough to hit the next point, but that didn’t change anything.

I also tried increasing the agent radius (from 0.2 to 0.5) because the cell size of the graph is quite small (0.1), but that didn’t change anything.

I have also tried “Funnel Simplification” and “Prevent Moving Backwards”, neither of which made a difference.

End Reached Distance is already very high (2), playing with this value didn’t make a difference either.

I tried changing the Cell Size of the graph from 0.1 to 0.5, again, no change in the behavior (but the agents got really creative with their paths).

Another thing I tried is add a FunnelModifier and/or a SimpleSmoothModifier to the agents. While I can see them do their job, that doesn’t change the behavior either (as was to be expected I suppose).

I think this is where the three close points come from (outline of the recast graph):

Here is the same situation with the some of the barricades (which are NavMeshCuts) removed:

Is there anything I can do in this situation?

[Wildcard]

I tried to use a RaycastModifier. I have tried different settings, here’s the result with physics raycast (all layers), one meter off the ground (0/1/0 offset) at the highest quality:

This seems to change/simplify the path at first glance, but makes no difference to my actual problem.

Having said that, I set it to only use the default layer, which results in this:

Oddly enough, the agents still behave exactly the same as before - they don’t cut through obstacles, and they still get stuck in the same spot. So by now, I have no clue what the RaycastModifier even does, or how the green debug lines have any relevance :-/

[Wildcard]

I have now tried to use AIPath instead of RichAI. The good news: This issue is gone!

The bad news: The pathfinding is all over the place. The agents follow the green line perfectly, making them zig-zag all over the place:

Now I know what you’ll say: that’s what modifiers are for!

So I added a SimpleSmoothModifier as wells a FunnelModifier. This makes my agents run off grid, and through NavMeshCuts:

Even when using only the FunnelModifier (high quality), the agents run through my NavMeshCuts:

When I only use the SimpleSmoothModifier, it looks a little bit better, but the agents still run through my NavMeshCuts:

On top of that, there’s some very … creative path finding going on:

I will now revert everything and go back to RichAI, and go with dynamic path recalculating at 2.5s max interval. This destroys a good bit of the performance gains that I have, but 2.5s is just enough to cover up the issue the agents run into.

I’m still very much looking forward to ideas why the three points are that close together, and why they’re not “crossed off” because the agents are close enough, which means they have to circle back repeatedly. This can’t be intentional.

[aron_granberg]

Hi

This happens when the agent “misses” a section of the path it wanted to move through. Around those three triangles that you mentioned, it can either move through them (blue line), or through the larger triangle adjacent to them (red line).

If the path was generated like the blue line, but the agent actually moved like the red line, then it gets confused and tries to turn back (unless its path is recalculated so that how it moves matches the path).

I have solved this in my dev version with a completely new movement script, which simplifies paths much better. However, this is unlikely to be available for some time.

However. You can also mitigate this issue by not using any tiling for your recast graph. It looks like your world is pretty small. So maybe you can disable tiling in the recast graph settings?

[Wildcard]

Hi Aron,

Thank you for the reply. I saw that you’re away so I didn’t expect a reply for a while (which makes it even more appreciated).

Not using tiles doesn’t seem to work, when I scan the graph this happens:

The exception happens in a gizmo method, so I switched gizmos off. The graph scan completes with no exceptions, but when running the game, no graph is found.

So I tried to simply use a bigger tile size than the default 128 (with the idea that a huge tile size results in just one tile and is probably the same as not using tiles at all). Anything over 2048 leads to exceptions when scanning the graph. 2048 scans the graph with no errors (although the result doesn’t look 100% the way I’d expect it), but when I attempt to save it (generate cache) it doesn’t save it (no error either).

At a tile size of 1024, everything seems to work fine. The issue I’m having is no longer appearing. But I have no way of knowing whether there is still more than 1 tile in use right now (do I?). If I understand it correctly, the issue can happen at the edge of tiles, so maybe by changing the tile size these seams/edges are now simply at a different spot and the issue can still happen.

My graphs are generally in the ballpark figure of 250x250 units (meters). At a cell size of 0.1 units, this results in a graph of 2500x2500 voxels. So a tile size of 1024 will not cover everything in 1 tile. Which means I still have seams/edges that can produce the issue (if I understand everything correctly).

[s.khan]

I have the same issue, but my maps are kinda bad for using it without tiling. Maybe I’m doing something wrong, but without tiles my AI still gets stuck

---

Without tiling

---

With tiling

---

Also sometimes I have AI rotating in one place instead of running back and forth

RichAI spin

[Wildcard]

Right… after some more testing:

1024 as tile size doesn’t work all the time. Sometimes only part of the graph calculates (no error message), and either it doesn’t save (generate cache) or the pathfinding gets extremely weird.

512 seems to be a safe value, anything above can work, but maybe doesn’t.

Even at these values, the root issue can easily be replicated with a test case that (presumably) ends up using a path that goes over a critical spot between two tiles.

I also tested some more with a recalculation interval of 2.5 seconds, and sadly that’s not low enough. Agents still go in circles. I’ll probably have to got 1 second or lower.

To be honest, I’m starting to become a little bit frustrated. I only went down this rabbit hole because A* uses tons of CPU on the main thread which tanks the performance of my game.

So then I changed the recalculation interval from 0.5 seconds to 10 seconds (or even to “once”), which works great because my world is static (between agent instantiation and death). Except agents need to recalculate their path all the time, because even though the path they have is correct, it’s possible that points on that path or so close together they can’t hit them, so they end up going in circles.

To sum it up:

• Multithreading doesn’t work properly, because even with MT on a 12 Core system, a few dozen agents hog the main CPU thread
• Path calculation doesn’t manage to merge three points that are practically on top of each other.
• Funnel modifiers don’t manage to merge these points either
• Funnel and simple smooth modifier used with the AIPath script result in my agents violating the constraints of the graphs and run over surfaces they shouldn’t
• The movement logic is unable to comprehend that “now that I have hit point 17, and points 18 and 19 are a hair’s breadth away from me, I can cross these off my list as well”. I have no idea how A* handles these things (that’s why I’m using an asset) and there might be a good reason for this behavior, but I can’t see it.
• Scanning the graph with a tile size set too high can result in a graph that looks ok at first glance (scene view) but isn’t complete and doesn’t save, but no error is written.

The only thing I can do right now is experiment with the recalculation value and set it as high as I can without too much impact, and I suspect it’s going to be somewhere between 0.5 and 1 seconds.

[Wildcard]

I tried one more thing and created my own modifier. The idea: If the distance between two points in the path is less than X, remove that point. I found out after a bit that RichAI ignores the vectorPath and instead uses the .path, and I thought I sorted that as well.

Here’s the originally calculated path:

And here’s the “corrected” path, where you can see the two points at index [7] and [8] have been removed. Please note that the corresponding parts of the .path property have also been removed.

Here’s my visualization by placing 0.1 sized spheres:

So that looks great, right? In the middle where we had 3 points/nodes/steps we now only have 1, so it should work. But it doesn’t, my agents still turns around as soon as it hits that middle node.

I tried to look into what richPath does with the path supplied, and noticed that it keeps a list of nodes (the correct one with the nodes in question removed) as well as a list of vectors for “left” and “right”. Looking at these lists, a lot of subsequent values look completely the same.

I think at this stage I have to admit that I’m at my wits end. I will for the moment reduce the recalculation time to 1s - this still uses loads of CPU (but at least it’s better than the 0.5 I used to have) and still (!) isn’t enough to get rid of agents stopping/turning completely, but it’s the best compromise for the moment.

[Wildcard]

FYI here’s the custom modifier code:

using UnityEngine;
using System.Collections.Generic;
using Pathfinding.Util;

namespace Pathfinding {
	[AddComponentMenu("Pathfinding/Modifiers/Remove Close Parts Modifier")]
	[System.Serializable]
	public class RemoveClosePartsModifier : MonoModifier {

		public float MinimumDistance = 0.25f;
		public bool LogDebugInfos = false;

#if UNITY_EDITOR
		[UnityEditor.MenuItem("CONTEXT/Seeker/Add Remove Close Parts Modifier")]
		public static void AddComp (UnityEditor.MenuCommand command) {
			(command.context as Component).gameObject.AddComponent(typeof(FunnelModifier));
		}
#endif

		public override int Order { get { return 10; } }

		public override void Apply (Path p) 
		{
			ModifyPath(p, MinimumDistance, LogDebugInfos);
		}

		public static void ModifyPath(Path p, float minimumDistance, bool logDebugInfos)
		{
			if (p.path == null || p.path.Count == 0 || p.vectorPath == null || p.vectorPath.Count == 0)
			{
				return;
			}

			List<Vector3> correctedVectorPath = new List<Vector3>();
			List<GraphNode> correctedPath = new List<GraphNode>();

			Vector3 last = p.vectorPath[0];
			for (int i = 0; i < p.vectorPath.Count; i++)
			{

				// Very first part
				if (i == 0)
				{
					correctedVectorPath.Add(p.vectorPath[i]);
					correctedPath.Add(p.path[i]);
				}
				// Middle part
				else if (i < p.vectorPath.Count - 1)
				{
					Vector3 current = p.vectorPath[i];

					if (DistanceGreater(current, last, minimumDistance))
					{
						correctedVectorPath.Add(p.vectorPath[i]);
						correctedPath.Add(p.path[i]);
						last = p.vectorPath[i];
					}
				}
				// Very last part
				else
				{
					correctedVectorPath.Add(p.vectorPath[i]);
					correctedPath.Add(p.path[i]);
				}
			}

			if (correctedVectorPath.Count > 1 && correctedVectorPath.Count != p.vectorPath.Count)
			{
				if (logDebugInfos)
				{
					Debug.Log($"Path simplified, {p.vectorPath.Count - correctedVectorPath.Count} parts removed.");
				}
				p.vectorPath = correctedVectorPath;
				p.path = correctedPath;
			}
		}

		private static bool DistanceGreater(Vector3 point1, Vector3 point2, float distance)
		{
			// Vector3.Distance is slow, this is better
			return ((point1 - point2).sqrMagnitude > distance * distance);
		}

	}
}

[Wildcard]

Hi there.

I have tried AIPath instead of RichAI (results see above) and experimented with every single setting on RichAI (also documented above).

[s.khan]

You have done an amazing work, @Wildcard

I guess that modifier solution didn’t work because the problem lies somewhere deeper. It feels like something is broken in RichFunnel, how it advances to next point.

In video below it’s clearly shown that steering target is switching back and forth - indefinitely

What helps a little - I lowered acceleration. I think that by lowering rate at which character decelerates I aid him to overshoot broken point and go by it’s real path. But this solution just barely works, AI still breaks and makes 1-3 turnarounds.

Unfortunately I don’t have both time and expertise to figure out how to fix asset itself and I’m still hoping that Aron can provide solution.

RichAI steering target

[Wildcard]

The modifier doesn’t work because RichAI (by design) doesn’t use modifiers. I only found that out afterwards

I’ll try playing with the acceleration, thanks for the suggestion.

[aron_granberg]

Hi

As I mentioned earlier, I have been working on a new movement script. It’s not available in the beta version. It should manage to handle these kinds of issues a lot better. You can try it out if you want.

[dakl1]

Hi

I am encountering the same problems as described above. In addition sometimes my characters are just getting stuck with no apparent reason. They seem to try to cut through navMeshCuts and can’t.

I am using RichAI without any modifiers.
The yellow arrow represents the starting point and orientation when startPath was called initially. The target is the red dot on the right side. The character then moved towards the big red X and got stuck because there is a navMeshCut.
The green path would be ideal.

I’d like to try out the new movement script. @aron_granberg Where can I find it in the beta version? (I need to try it out in version 4.2.18 because I can’t upgrade my com.unity.entities version)

[aron_granberg]

@dakl1

I’d like to try out the new movement script. @aron_granberg Where can I find it in the beta version? (I need to try it out in version 4.2.18 because I can’t upgrade my com.unity.entities version)

You can find it here: A* Pathfinding Project, but it does require com.unity.entities.

[dakl1]

So it is still the RichAI script?

[dakl1]

Here is another one. Green line is the optimal path and the red one is the chosen one even though there is a straight line without any obstacles or cuts available from start to end. (I guess the RichAI funnel algorithm doesn’t work as intended)

[aron_granberg]

@dakl1

So it is still the RichAI script?

No. The new movement script is called FollowerEntity (name pending).