Hi everyone.
My game levels contain minecraft-like 3D voxel terrain and obstacles. Terrain consists of procedurally generated meshes without mesh colliders. I need to add bot navigation system to it.
I need to set nodes and connections manually. Connections are based on height difference between neighbour nodes. I’m not sure what graph type to pick, could you help me?
Hi
Sounds like the LayeredGridGraph might be your best option.
If you want to do this without any colliders, then you’ll have to write a custom grid graph rule to populate the graph with the voxel data: Writing Custom Grid Graph Rules - A* Pathfinding Project
However, I’d recommend that you prototype it using colliders first.
Thanks for pointing to Grid Graph Rules. I fill nodes in BeforeCollision pass and it seems correct. However I get strange behaviour in AfterConnections pass when I try to connect nodes through IConnectionFilter: neighborDataIndex exceeds nodes.positions length.
using System.Linq;
using Core.Extensions;
using MeshGeneration;
using Pathfinding.Graphs.Grid;
using Pathfinding.Graphs.Grid.Rules;
using Terrain;
using UnityEngine;
namespace LevelObjects.Move
{
public class VoxelGridGraphRule : GridGraphRule
{
private ConnectionFilter _connectionFilter;
public override void Register(GridGraphRules rules)
{
rules.AddMainThreadPass(Pass.BeforeCollision, AddNodes);
rules.AddMainThreadPass(Pass.AfterConnections, SetConnections);
}
private void AddNodes(GridGraphRules.Context ctx)
{
var owner = ctx.graph.active.GetComponent<TerrainDataOwner>();
var terrainHeight = owner.Terrain.ToDictionary(p => new Vector2Int(p.x, p.z), p => p.y + 1);
for (var i = 0; i < ctx.data.nodes.positions.Length; i++)
{
var worldPos = ctx.data.nodes.positions[i];
var nodesPosition = LevelTerrain.GetWorldBlockPos(worldPos).XZ();
if (terrainHeight.TryGetValue(nodesPosition, out var height))
{
ctx.data.nodes.positions[i] = worldPos.WithY(height);
}
ctx.data.nodes.walkable[i] = true;
}
}
private void SetConnections(GridGraphRules.Context ctx)
{
_connectionFilter = new ConnectionFilter(ctx);
GridIterationUtilities.FilterNodeConnections(ctx.data.nodes.bounds, ctx.data.nodes.connections, true, ref _connectionFilter);
}
private struct ConnectionFilter : GridIterationUtilities.IConnectionFilter
{
private readonly GridGraphRules.Context _ctx;
public ConnectionFilter(GridGraphRules.Context ctx)
{
_ctx = ctx;
}
public bool IsValidConnection(int dataIndex, int dataX, int dataLayer, int dataZ, int direction, int neighbourDataIndex)
{
var position = _ctx.data.nodes.positions[dataIndex];
var neighbourPosition = _ctx.data.nodes.positions[neighbourDataIndex];
return neighbourPosition.y - position.y <= 1.1f;
}
}
}
}
Could you pls tell how to connect nodes in Grid Graph Rules? I don’t see any GraphNode in GridGraphRules.Context so I could call Connect on them.
Hi
Note that your current connection filter is identical to the built-in connection filter. You can control it using the Max Step Height setting in the grid graph inspector. I’d recommend relying on that instead of writing your own.
The grid graph rules operate on native unmanaged data, and the node classes are not even created at the point when they run.
Not sure why that happens… Are you sure you are using a layered grid graph and not a normal grid graph?
Yes, it’s layered grid graph. I solved connection issue with connecting nodes in AddWorkItem after scan
private void CreateAStar()
{
var nodesCache = Terrain.ToDictionary(t => new Int3(t.x, t.y, t.z), t => (LevelGridNode)null);
var (path, graph) = EnsureGraph();
graph.Scan();
path.AddWorkItem(() =>
{
path.data.GetNodes(n =>
{
var gn = (LevelGridNode)n;
var position = Vector3Int.FloorToInt((Vector3)gn.position);
nodesCache[new Int3(position.x, position.y, position.z)] = gn;
});
foreach (var (position, graphNode) in nodesCache)
{
if (graphNode == null)
{
continue;
}
graphNode.ClearConnections(true);
for (var x = -1; x <= 1; x++)
{
for (var y = -1; y <= 1; y++)
{
for (var z = -1; z <= 1; z++)
{
if (x == 0
&& y is 0 or 1
&& z == 0)
{
continue;
}
TryConnect(nodesCache, graphNode, position + new Int3(x, y, z));
}
}
}
}
});
AstarPath.active.FlushWorkItems();
}
private void TryConnect(Dictionary<Int3, LevelGridNode> nodesCache, LevelGridNode nodeFrom, Int3 nodeToPosition)
{
if (nodeFrom == null || !nodesCache.TryGetValue(nodeToPosition, out var nodeTo) || nodeTo == null)
{
return;
}
GraphNode.Connect(nodeFrom, nodeTo, (uint)(nodeFrom.position - nodeTo.position).costMagnitude);
}
How to add bridge to my layered grid graph? I can move node position in rule, and I couldn’t find any way to add nodes in different layer, it has only one layer.
Hi
This is a bit tricky. A node existing is defined by the normals array having a non-zero value for that particular node (usually (0,1,0)). So you’ll need to modify the positions, connections normals, walkable, walkableWithErosion arrays to create the node.
If you need to add another layer, then you’ll need to call ctx.data.nodes.ResizeLayerCount.