Download

AI Pathfinding - Nav-Links for large areas?

I’m exploring different options for AI path-finding in my game, but currently I feel like I’m running into limitations of the AI engine. Currently everything seems entirely geared towards characters who can start, stop and spin on the spot. While the movement for my game is pretty simple, my pawns have a lot more ‘freedom’ of movement than characters.

My pawns have a lot of freedom of movement:

Pawns in my game can jump, force-drop to the floor and sprint. Most of these things they can do whenever they want, but getting AI to decide when to do it seems to be a minefield. My first port of call was using Nav Links to let the path component know when it can jump or drop, but navlinks seem to be specified to ‘points’ rather than an area. In this image, my pawns should be able to jump from one area to another from almost anywhere.

Now in theory my pawn can jump from anywhere to reach the top section - but the navlink requires them to reach a very small, very specific location first. I want AI to know they can jump up there from almost anywhere in the level - so how can I use navlinks to set that up without creating literally thousands of them?

I basically want to say that a pawn can jump from one ‘area’ to another, not one ‘point’ to another.

I had a similar issue in our game where we wanted Wrestler AI to get in and out of the ring on the 3 sides. Initially, I setup a service in the BT which checked whether the Opponent is in the ring with the AI and if not, it would walk towards the opponent until it reached the ropes. At which point the enter/exit ring logic would trigger. I later setup a handful of navlinks to restrict where the AI can enter/exit, primarily to help position the Wrestler better…

Don’t know if that is of any use in your case, but I do agree with the AI being a bit too focused on conventional character design (as you said on twitter).

Right so, I’m working on this properly now and after studying UT’s source code in ridiculous detail, I think I’ve found a way to do this (based on a similar method).

The idea is to create additional data and store it in the RecastNavMesh Actor. This data essentially clusters polygons of the navmesh together, first based on whether or not NavAgents of the same size can traverse each polygon, then based on whether or not each polygon of a cluster can reach another cluster. You then create ‘Path Nodes’ (as UT calls them, probably a throwback to UDK) - and store that path link data there.

I have an early version working in terms of the NavMesh generation, but I will have to alter the way valid paths are actually generated from NavMesh in order for the AI to start using them. I tried doing this with NavLinks first, but Links are a bit rubbish to be honest, and aren’t useful for connecting ‘area’s’, so much as specific world locations. It’s also ridiculously difficult to place these dynamically, so any kind of procedural or moving level stuff won’t work with it.


This is where I’m at so far:

Essentially you generate the NavMesh first, then add an additional loop for constructing your own data once the Mesh has been generated. I haven’t yet figured out how to force-rebuild the paths when only moving a segment of the world, so at the moment I have to manually hit ‘Build Paths’ in the editor to generate the paths properly for the whole level.



void AECGame_RecastNavMesh::OnNavMeshGenerationFinished()
{
	// If a path build is in progress, do nothing
	if (bPathsAreRebuilding) { return; }

	if (bPathsNeedRebuilding)
	{
		// Once Polygon building has completed, start building the paths
		StartPathBuild();
	}
	else
	{
		// Polys and Paths should have finished building, we can clean up now.
		Super::OnNavMeshGenerationFinished();
	}
}


Then, you select an island in the Navmesh, and create a Path Node for it. Each PathNode knows which Nav Polygons it’s responsible for (NavNodeRef). If a polygon in that island can be traversed by a same sized agent as the other polygon, then you link them to that node. The idea is to have as few nodes as possible, since later for pathfinding you’ll need to iterate nodes to generate the cheapest paths.

This is the islands linked to each other. I used Debug Arcs to show the linked polygons because it’s easier to see what’s going on.

Recast generates NavMesh inside world geometry, so you need to filter out those islands from the traversable islands by testing for collision. I just do an overlap test with a 1UU sphere at that Polygons world location, which seems to be a good enough test for now. There are islands inside the geometry, which only link to themselves and not other nodes. In future I want to stop generating nodes inside geometry at all really…

I still have a few steps to go, but I think this is the right route:

1 - Link together nodes that can be ‘jumped’ to from other nodes, or ‘sprint-jumped’ to for extra distance. This part is a bit more complicated, since you need to check the Jump Arc for collisions.
2 - Allow NavArea’s to affect Node / Link generation to give me some way to block off some areas entirely (or change the traversal type)
3 - Figure out a way to make the AI pathing choose routes using the Path Node data.
4 - Ensure the AI tells the pawn to ‘Jump’ and ‘Crouch’, based on the path it’s traversing.


UT does quite a few things I don’t want to do, like it’s own custom pathing and using AI state machines instead of BT’s - so the path generation side of things will probably be quite challenging…

Alright… made some progress today. First thing I fixed was the busted drawing for Nav Polygons. I do something similar to UT now and draw the polygons coloured by connection region.

2f67d2d504b7b3fbe16b16ca2289c7a83ca2a525.jpeg

Since my pawns change radius and can ‘drop’ to the floor at the players / AI’s will - I’m also separating out polygons based on the properties required to traverse them, then linking them together (the purple lines indicate navigation nodes that can be navigated to one another. The pawn should eventually be able to get the current node it’s traversing , and grab some flags from it to work out if it can traverse that segment, and if so what input does it need to apply.

dc400412001a8b3046bef73e7f70e1f1e3ae01f5.jpeg

Small steps…

This is almost a dev blog now…

I got “crouch” (Force-Drop) links working today, so the Nav Links now know if an AI has to crouch when travelling between two polygons. Radius is also checked, so smaller orbs should now be able to travel through narrower gaps…

Jump-Links next. This shouldn’t be too hard, the trick is to just iterate over all the polys and check if it’s possible to jump to another one. The tricky part is that my pawns have accelerating movement rather than discrete velocity, so I guess I can’t guarantee that orbs can always make jump distances…

Next step is to place Nav Links for all of the polygons that can be linked together.

Most of them seem to work (though I need to configure direction still) - but many don’t - particularly ones in shallow areas.

Any ideas? The Agent Properties are definitely small enough to fit in these gaps.

Hi, I know its an old thread. Is there any progress with this method of generating the navLinks automatically?