Diagonally entering a sinkhole but not leaving it again

[ath-software]

We are using an AIPath movement script on a GridGraph.
The bug happens with and without a RVOController.

There is some sort of sinkhole in the GridGraph, see the screenshot:

I read that units on a GridGraph should not be able to pass diagonally unless there is at least one horizontal or vertical adjacent reachable gridnode:

Diagonal connections in a simple Grid Graph

My 8 direction grid graph is missing a diagonal connection (the green line drawn into the screenshot below). [image] It seems as if a node doesn’t actually check its 8 neighbour nodes, but rather checks its 4 neighbour nodes (up,down,left,right) and then creates diagonal connections in between nodes that are joined by a vertical and a horizontal connection. How can I make my graph find its missing diagonal connection? I think I might have misunderstood something very basic here, any help is …

But if I send this unit to move into the sinkhole, the unit will move to the closest point,
then stand there briefly, then decide that it can actually progress to the original path goal.

I guess what happens is that the unit arrives exactly at the corner of the gridnode, or perhaps some effect like rounding / floating point imprecision of the position then makes the unit pop out on the other side of the corner, so that it can continue the path on the other side.

It’s not so much a problem that the unit can pop out, the problem is that it can’t get back anymore.

We can very easily create such a situation when creating levels and its almost impossible to avoid. We had the bug in both of our demo levels.

[aron_granberg]

Hi

Sorry for the late reply.
Yes, this can be an issue. And yes, it is caused by floating point errors when the agent is exactly at the corner.
If possible, you can set the ‘erosion iterations’ setting on the grid graph to 1. This will make it effectively impossible for this case to occur. But you might need to tweak other grid settings to make sense for your game.

[ath-software]

Is it true that it will make it effectively impossible for the case to occur?
It would depend on the implementation.

Consider this example where white is walkable, black is obstructed, and gray is eroded:

Or if erosion only expands horizontally or vertically, not diagonally:

If the erosion mechanism is trivial and only appends a margin of 1 everywhere, this graph could appear and it wouldn’t really make it more or less likely to get these situations with arbitrary grid graphs I would guess.

An approach in deterministically avoiding these “diagonal entrances” could be when scanning the graph or a graph subset, to detect such “diagonal entrances” and erode only there / block the diagonal entrance.

Our current workaround is to find these sinkholes with manual inspection and add a manual obstruction over it, but that won’t work with dynamic obstructions (such as buildings built during the gametime).

[ath-software]

Actual example with erosion iterations = 1

[aron_granberg]

Oh right. I forgot erosion doesn’t expand diagonally.

You could try to attach the NavmeshClamp script to the agent. It’s not used much these days, and it’s not mentioned by the docs, but it might just solve this problem if we are lucky.

[ath-software]

Even with diagonal erosion the bug can occur, see first image.

A Linecast each frame for each unit sounds quite expensive.

The most elegant, robust and performant solution would be to detect these cases in the grid and mark both tiles at the “epsilon-passage” as obstructed (perhaps only if a new option in the grid graph is enabled).

Example:

Black are obstructed tiles.
Red is the path that a unit CAN take but SHOULDN’T be able to.
Blue are tiles that the algorithm could insert after having detected such a checkerboard pattern.

The catch with this algorithm is that the introduction of the two new tile obstructions (blue) in turn might open up yet another “epsilon-passage” nearby:

Example 2:

So each time the two obstructed tiles would be inserted, one would have to scan the surrounding tiles as well (and potentially the surrounding tiles of the surrounding tiles etc.)

But then it would cover all cases without agents having to do more work or needing any code modifications.

[aron_granberg]

Hi

Sorry for the late reply. I’ve been quite sick the last few weeks.

It’s possible to implement such a filter quite easily using grid graph rules (available in the beta version).
See Writing Custom Grid Graph Rules - A* Pathfinding Project

using UnityEngine;
using Unity.Burst;
using Unity.Collections;
using Unity.Jobs;
using Unity.Mathematics;
using Pathfinding;

// Mark with the Preserve attribute to ensure that this class is not removed when bytecode stripping is used. See https://docs.unity3d.com/Manual/IL2CPP-BytecodeStripping.html
[Pathfinding.Util.Preserve]
public class RuleFilterDiagonals : GridGraphRule {

	public override void Register (GridGraphRules rules) {
		// The Register method will be called once the first time the rule is used
		// and it will be called again if any settings for the rule changes in the inspector.
		// Use this part to do any precalculations that you need later.

		// Hook into the grid graph's calculation code
		rules.AddJobSystemPass(Pass.BeforeConnections, context => {
			// This callback is called when scanning the graph and during graph updates.
			// Here you can modify the graph data as you wish.
			// The context.data object contains all the node data as NativeArrays
			// Not all data is valid for all passes since it may not have been calculated at that time.
			// You can find more info about that on the documentation for the GridGraphScanData object.

			// Get the data arrays we need
			var nodeWalkable = context.data.nodeWalkable;
			var nodePositions = context.data.nodePositions;

			var size = context.data.bounds.size;

			// Run the filter multiple times until everything converges
			var changed = true;
			while(changed) {
				changed = false;

				var newWalkable = new Unity.Collections.NativeArray<bool>(nodeWalkable, Allocator.Temp);
				for (int z = 0; z < size.z - 1; z++) {
					for (int x = 0; x < size.x - 1; x++) {
						// C D
						// A B
						var ia = (z+0)*size.x + (x+0);
						var ib = (z+0)*size.x + (x+1);
						var ic = (z+1)*size.x + (x+0);
						var id = (z+1)*size.x + (x+1);
						var wa = nodeWalkable[ia];
						var wb = nodeWalkable[ib];
						var wc = nodeWalkable[ic];
						var wd = nodeWalkable[id];

						if ((wa && !wb && !wc && wd) || (!wa && wb && wc && !wd)) {
							changed = true;
							newWalkable[ia] = false;
							newWalkable[ib] = false;
							newWalkable[ic] = false;
							newWalkable[id] = false;
						}
					}
				}

				for (int i = 0; i < nodeWalkable.Length; i++) {
					nodeWalkable[i] = newWalkable[i];
				}
			}
		});
	}
}

Before:

After 1 iteration:

After convergence: