Seeking Advice on Pathfinding/Obstacle Avoidance/Navigation: How to Account for Allies?

Help
, ,
1

Godot Version

4.2.2

Question

Scene Description:
A → B :crossed_swords: Enemy
As shown in the diagram, ally B is engaged in combat with the enemy, and I need ally A to also attack the enemy, but A is blocked by B.

Expected Outcome:
A should bypass B to attack the enemy, similar to the behavior in games like Warcraft or StarCraft.

Problem:

  • Both A and B have obstacle avoidance enabled. If B can move, it will actively avoid A.
  • However, since B is attacking and cannot move, A gets stuck trying to move straight ahead.

Attempts:

  • I’ve watched numerous videos and tutorials on pathfinding, but they all discuss situations where both A and B are moving and avoiding each other. I’ve never seen anyone address how to consider B as an immovable object in A’s pathfinding.
  • Tried adding a NavigationObstacle2D to B, but since B also uses pathfinding, it conflicts with itself, and A doesn’t seem to bypass B.

Thank you very much if you can provide an answer.

1 Like
2

What if you disable avoidance while attacking/not moving?

3

I tried this, disable B’s avoidance, but A is still blocked by B, A didn’t bypass B.

4

i’m sorry, i don’t understand the question. Maybe because you’re using the nav mesh system (which i hate, for reasons similar to this one)? i use AStarGrid and can’t imagine a situation like the one you’re describing. Would you mind giving some examples?

i built the following situations in my pathfinding demo:
image image

Rufus (orange) is fighting Ash (white). In scenario A, you can’t reach Ash because there’s physically no room. In B you can, you just have to move around Rufus.

For scenario A you do a pathfind operation, determine there is no valid path and do what you do in that state (find a new target, switch to ranged, queue up behind and wait, etc.). In scenario B you pathfind to Ash and… Okay, here might be a problem. Options:

  1. Rufus (in my AStarGrid situation) is registered on the blocker map so you pathfind around him automatically (ex: https://www.youtube.com/watch?v=qJKBT3KOLiY)
  2. You know nothing about Rufus but because you don’t his Rufus perfectly opposite Ash, calling move_and_slide() causes you to slide around Rufus. This works 30% of the time in my case so it’s not great.
  3. You start using influence maps. Which is a bigger topic and not radically different than option 1 so i’ll drop it unless you’re really interested.
  4. Don’t navigate to Ash. Define 8 points around Ash, pick one at random and pathfind to it. On no path, pick another. This causes you to move to points around Ash.
  5. Use steering for path following. Raycasts (function or node) give feedback on how to move around obstacles. Steer around Rufus, arrive with an X margin to Ash that is greater than (target.size/2+1) and less than (target.size+rufus.size) (so 1 tile away in tilemap terms). There are lots of steering videos but none that i know of for Godot 4. i used GDQuest’s Godot 3 tutorial without much problem (https://www.youtube.com/watch?v=fnkgBaWKZNU)

Not sure if any of that is useful to you but hopefully it helps. The ideal solution is one where Godot has the behavior built in and you just have to find the magic word to use it. But if it’s not there, there are options to work around it. i’ve had a lot of problems with the navmesh stuff so i switched to grid-based navigation and it’s made a lot of things easier for me.

5

Thanks for your answer.
I tried your demo, and the same problem occurred in your demo. A Rufus was stucked by other Rufus.
GIF
Is there a way to make him aware of his allies, so he bypasses them?

6

Yeah, that’s awful, right? It bugs me so much. In that demo it happens because Rufus isn’t registered in BlockersTileMapLayer. Which is why i mentioned Retrobright’s video. He registers them in AStarGrid. i do the same thing in my pathfinding article (section 4: Pathfinding in Godot with AStarGrid2D – baylor does game stuff)

astar_grid.set_point_solid(ally_position)

The bad news is that you have to do this every time the agent switches tiles - if Rufus moves from tile (5,5) to (5,6) you have to unset his previous position and set his new one. But it works. i’ll try to make a demo showing that but i probably won’t get to it any time soon (especially since the correct answer is steering, but that will take me a lot longer to get to) which is why Retrobright’s video is probably the best example i know to look at.

(off the top of my head, a solution might look like:

func _physics_process(delta):
    current_coord_tile = coordinate_global_to_map(position)
    if current_coord_tile != previous_coord_tile:
        astar_grid.set_point_solid(previous_coord_tile, false)
        astar_grid.set_point_solid(current_coord_tile )
        previous_coord_tile = current_coord_tile

func coordinate_global_to_map(coordinate_global : Vector2i) -> Vector2i:
	var coordinate_local = to_local(coordinate_global)
	var coordinate_map   = terrain_tilemap.local_to_map(coordinate_local)
	return coordinate_map

)

Marking spots as occupied is quick and easy but on bigger, fancier, better funded games it’s probably not what you’d do. For example, in No One Lives Forever pathfinding was done with navcubes with occupancy-based cost, meaning the cost of traversal goes up as more people take it, which at a certain density causes groups to flow into multiple paths and approach from multiple angles. But that’s a lot more work than i think either of us want to do right now. For now marking tiles as occupied (by an enemy, ally, treasure chest, tree stump, etc.) works pretty well.

1 Like
7

I’ve been using NavigationAgent2D until now, but after watching Retrobright’s video and reading your article, I’m going to try to refactor my code using AStarGrid2D, try to mark tiles as occupied. This might take some time. Once it’s successful, I’ll be very grateful to you.

8

In professional games almost everything is navmesh based. There’s no reason not to start there in Godot. i did. But Godot doesn’t currently have a great and simple way to dynamically modify navmeshes at runtime. There are smarter people than me on Godot navmeshes and maybe they have a solution. i tried for a while without luck and switched to the AStarGrid.

9

Warcraft 3 uses a grid where units register themself for the pathfinding, they occupy cells. That is why it is so stupidly simple in Warcraft3 to block units from pathfinding. You just step one units toe into the neighbor cell and the entire cell gets blocked, the other unit needs to make a huge detour. Starcraft1 uses a worse grid version of Warcraft3.

Starcraft2 instead uses a regular navmesh system because they needed the surface detail and performance of navmesh compared to small resolution grids. The navmesh keeps a static geometry copy of the level and rebuilds on building placement.

sc2-navgrid
sc2-navgrid1024×738 158 KB

Because back in 2010 memory was a huge problem and StarCraft2 had so many different sized units they went with 1 navmesh for everything, and made the units only keep a path for the next 2-3 polygons. The units would offset their movement path by their radius to not get stuck on all corners. This did work for Starcraft2 because all the buildings are placed on a grid with a lot of cell spacing. So if there is space for a unit to move through there is almost always enough space to halfradius offset the path. Outside of this specific context doing the pathfinding with radius offset is not feasible for both performance and reliability as everything will get stuck on smaller passages if you dont force a minimum size for passages, e.g. by forcing a grid placement. It is also very performance costly that is why they never did full paths and only 2-3 polygons outside debug that you can see here.

sc2_pathfing
sc2_pathfing963×644 89.7 KB

As you can see here the small SpaceMarine radius (yellow) offsets the path on every corner. While buildings are placed on the grid their actual shape for the navmesh baking is not necessarily a grid cell size. That is why smaller radius units like e.g. zerglings can slip through the corners of bunkers as their navmesh shape is not a full square and the zergling radius is small enough to fit through.

The navmesh does not rebuild for units, those are only affected by a custom avoidance system.

The avoidance in Starcraft2 is a complex beast with a lot of internal rules, e.g. small units get pushed by large units, friendly units can push friendly units, standing friendly units move away from moving friendly units, friendly units that all move in the same direction ignore each other, … it is a long list. While you can do a near 1:1 copy of the navmesh system for the avoidance system you would need to do a custom version. The existing RVO avoidance in Godot has options like layers and priorities but you would need to shuffle those all the time manually for similar effects. It is way “easier” to do a custom avoidance instead to get all those rules in. The StarCraft2 avoidance system is also heavily tied to the other systems, e.g. it uses both the collision system and the navmesh geometry for its own calculations.

4 Likes
10

Although I don’t use NavigationAgent2D, allies can no longer actively avoid each other, but I’ve implemented obstacle avoidance similar to that in Warcraft III. Thank you very much.