NavigationAgent2D ignoring tile map collision and pathing through non-navigable grid cells

[stoic dome]

I am learning about navigation and have set up my tileset to have the floor tiles marked as navigable as seen by the highlighted tiles during debug gameplay. As my enemy entity starting in the corridor I have a simple node (denoted by _self) with the following code running when I press a key:

_navigationAgent.TargetPosition = _player.Position;
if (_navigationAgent.IsNavigationFinished()) return;
var direction = _self.Position.DirectionTo(_navigationAgent.GetNextPathPosition());
_self.Position = (_self.Position + direction * TileSize).Snapped(Vector2.One * TileSize);

What's noticeable is that the computed path by Godot clips through the non-navigable wall and cuts diagonally at times. For the time being I have the following questions:

1. How can I adjust the behavior of the path finding to not take the paths through walls? Are there parameters to ensure this behavior or do I have setup my own instance of the AstarGrid2D algorithm? If possible I'd like to use most of the out of the box features where possible.
2. For the beginning I want to disallow diagonal movement which probably means having to change the heuristic of the algorithm. Can this be achieved with the built-in NavigationAgent2D node?
3. Once everything works as expected I'd like to allow diagonal movement only if it doesn't cut corners. I can imagine this will require some more custom code to alter the path finding behavior.

[sonic pivot]

1. Check your naviguation polygon meshes and try increasing deadzones.
2. I've mostly used the 3D version. But, you might be able to disallow diagonal movements by changing your move code to only Have One axis not be zero at a time. However this might mess the pathfinding since these Grid based movements were intended to be used with Astar2D classes.
3. You can calculate distance and check for collisions in your move code. This is how I would see it work

[stoic dome]

1. The navigation area is not created manually, it's just automatically deduced from the floor tiles by the engine which works fine since the entity doesn't try to cross the non-navigable walls before reaching the top corridor.

re 2. and 3. Yes, you're right, I have been slightly changing the initial code to obtain the next path position from the agent as a "hint" rather than the guaranteed tile to move to and instead have been applying a few checks. The current logic is this

• Map the "hint" to the nearest cardinal direction one tile away and check collision using a RayCast2D.
• If there is a collision, rotate the direction by 90 degrees clockwise and repeat the same check until either one of the directions is navigable or all four directions are blocked.

All of this is just hacked together and needs some more love in terms of code but it seems to be working and will allow me later to enable diagonal movement once I check diagonals to prevent cutting corners. At its core though this looks like a reasonable approach for now.

[sonic pivot]

Can you show me an exemple of the issue?

[stoic dome]

The video in the original post shows how the entity moves through the wall when taking the left turn out of the corridor despite only the brown floor tiles being navigable.

Or have you been referring to something else?

The wall tiles aren't part of any navigation layer and are marked using a physics layer for collision which seems to be ignored during pathfinding using the agent.

[stoic dome]

NavigationAgent2D ignoring tile map collision and pathing through non-navigable grid cells

[stoic dome]

My "solution" I have come up with so far is not robust enough and I'd be curious if others have experience with restricting movement to the actual navigable areas.

[stoic dome]

From browsing few more resources and tutorials I stumbled upon this: https://www.youtube.com/watch?v=1-f4WEy0GBg
This guy mentioned how the NavigationAgent2D is designed more for open spaces and their nav meshes rather than discrete grid-based maps. Using the AStarGrid2D class as described in the video definitely helped me to cover most of my desired features, being able to tweak heuristics as well as adjust the behavior of cutting corners (or rather preventing that).
The most notable difference of my current code to his in the tutorial is that I am supplying the grid with values from the navigation layer of my map using this:

foreach (var tileId in _tileMapLayer.GetUsedCells())
    if (_tileMapLayer.GetCellTileData(tileId)?.GetNavigationPolygon(0) == null)
        _aStar.SetPointSolid(tileId);

I will need to tweak some minor details to improve certain special cases unique to my desired behavior, but other than that it works really fine and I can recommend this for grid-based and turn-based path finding over other scenarios.

[sonic pivot]

Good to know it's working! Astar2D is the recommended way for grid based game. I've never really used the new AstarGrid2D. But, I've got some exemple(gd script) of making pathfinding with Astar2D classes. You could make connections between diagonal tiles with it aswell.

[stoic dome]

AStarGrid2D doesn't work by definining connections, it works by outlining whether cells in a grid are solid and will deduce connections from this. As such there are ambiguous cases that need custom handling. Most notably the attached examples where the first is a wall that should not allow to cut corners while the second example shows water that should allow to cut corners since it's not blocking by moving diagonally over it. I can see that defining the connections manually with AStar2D would make it possible to distinguish this, but AStarGrid2D is designed differently. As far as I can tell from reading the docs, this would need custom implementations of _ComputeCost and _EstimateCost which I'll will look into in the future.

[sonic pivot]

AstarGrid2D seems pretty basic. I would recommend Astar2D if you intend to have mote custom behaviors.

However, if it fits your case. Then it's all good

[stoic dome]

Short update: Astar2D is better. You can more easily set up teleporters for AI to use and add custom routes at the cost of some minor setup that is less trivial than the grid.