Pick a path based on a "wider" agent width

Alright, this is going to take some explaining and I’m already almost sure the answer is “this won’t work”, but I’ll try it anyway.

My game is a tower defense game. Agents (enemies) spawn in a few locations and need to find their way to a target (the base). There are existing obstacles on the map (e.g. buildings) and the player can build additional ones (walls/turrets). Anything the player can build is placed on a fixed grid of 1.5x1.5m cells and has a NavMeshCut attached.

This is all working 100% and as intended, with one small issue that I’m trying to explain.

My game is using two recast graphs. One with a character radius of 0.5, one with a character radius of 1.25. That’s the only difference. The one with the bigger character radius of 1.25 is used to check to make sure the player leaves a valid path of at least 2 cells (of 1.5m width each) open for the enemies to walk through. I want 2 cells width so the enemies don’t step on each others toes so much. If I only had 1 cell, it would be really tight.

The other graph with 0.5m character width is the one the enemies actually use for navigation. I’m not using the other graph, because I don’t want all my enemies to walk in the middle of the “wide” gap when there’s more space.

Here’s the graph I used during construction: As you can see, even though there are 2 1.5m cells in between the obstacles the player placed (the barrel stacks), he couldn’t place another one in between without making this spot impassable (therefore I don’t let him do that):

And here’s the same spot with the graph the agents use for navigation. They have a wide gap to go through and to go past each other:

So far, so good. This is working great, except in situations when there are multiple paths.

Imagine a level like this:

Now the player can place his walls/turrets down like this (green):

It’s perfectly ok, he leaves a gap of 2 squares at the top, satisfying my check with the 1.25m radius graph. All is well.

Except the agents of course take the more direct path with the gap of only 1 cell.

I could of course simply have the enemies use the 1.25m radius graph as well, but then they run in single file and get in each others way. If an enemy stops (they do that for certain actions), the others can’t go around them, as their available path isn’t wide enough.

The only thing I can think of doing is using the 1.25m graph for navigation as well, and completely disable local avoidance / RVO. The enemies would still just run in the middle and essentially through each other, but at least the game behaves the way I want to.

Another thing I could do is have some enemies use one graph, and others the other. That would mean the player can’t game the system too much.

Do you have a better idea?

TDLR: I want enemies to ignore 1.5m wide gaps in their path finding, while still fully utilising the width that’s available when passing through a wider gap (and now that I’m writing this down, I’m 100% there is no solution for it…).

I think there is a pro feature that causes your characters to try to avoid each others’ paths, but I don’t remember what it was exactly as I use the free version
even if I’m wrong, I’m fairly certain you can easily make something similar by getting the .path attribute of the Path object your character is using and loop through it and add penalty to each node (though make sure to reduce the penalty again once the character reaches each node or before it calculates a new Path)

After leaning back a bit, I’m going down a completely different route now.

Whenever the player adds or removes something to my grid, I now perform a check on all my empty “squares” that are nearby.

The check involves a cross-shaped detector right on top of my square. This cross-shaped detector has a total of 4 colliders, one for each of its ends. I then rotate that detector by a full 360° (step size not determined yet) and check all 4 colliders hit something at the same time.

If they do, I consider this empty square impassable, and activate a navmesh cut on top of it.
So, essentially, I turn my empty square into an occupied square.

As you can see from the example here:
A) No matter how long I rotated the detector, no more than 3 of the crosses ends will hit something. This square is safe to pass.
B) When rotating the detector, eventually all 4 of the ends will hit something. This square is not safe to pass. It will receive a nav mesh cut.
C) Same as B).

The system needs a wee bit of fine tuning but works great. And no messing with the agents.

1 Like