How do I make pathfinding look more natural?

[saucy_saint]

Godot Version

v4.2.1.stable.mono.official [b09f793f5]

Question

Hi, this is my first time posting! I’ll try to make this as descriptive as possible, but please bear with me if you need me to provide more info.

I’m trying to make a sim with a lot of NPCs moving around a building to perform tasks. While my implementation of pathfinding “works”, I’ve run into the issue that the paths NPCs take are very unnatural looking and usually cause the character to rub against walls (since it’s technically the shortest distance). The main aspect of this I’d want to address is to have the NPC walk close to the center of the hallway if they’re the only one there.

Here’s what I’d like the pathfinding to look like

Here’s what it ends up looking like in practice

And here’s a screenshot of the game itself to illustrate the problem. Note how the characters never go through the center of the doorway and are constantly hugging the wall.

This is the NPC I’m using to troubleshoot pathfinding

I have two vague ideas on how to improve this, but don’t know enough about pathfinding in Godot to understand how I would begin to implement them.

• Have some kind of “personal space” collision shape that only interacts with walls. Somehow this would need to not be so solid that it would prevent the character from passing through doorways or standing in corners, but solid enough to cause them to set their path at least a few feet away from the wall. Also this would need to not cause any kind of actual friction that would effect the NPC’s speed, and only prevent their path from being drawn too close.

• Use an AStarGrid2D with the tilemap. While I don’t want grid-based movement for my game, reducing the amount of possible coordinates might lead to somewhat cleaner looking paths. I’d like to avoid this though, since it might not look right when I scale up the amount of NPCs in the level.

If anyone’s ever had to deal with a similar problem like this or have any suggestions on how I could do the personal space idea, I’m all ears. Honestly if there’s a good-enough solution that only involves tweaking the navigation agent settings, I’d settle for that! At this point in time, I don’t really care how resource intensive the solution would be. I’ve watched a lot of the tutorials that are out there on pathfinding, but they’re mostly about simple enemy movement, so they never address having the NPC avoid sliding off walls in the first place.

[notcampeur]

Hello !

Interesting question, I don’t use these things myself so I’m going to approach them from a strictly algorithmic point of view as the implementation is a mystery to me:

Heuristic adjustment

You could tell your algorithm that contacting walls is slightly more expensive.

This will mean that entities will naturally take a path further away from the walls.
While allowing passage in certain cases (blocked environment, group of entities pushing each other, sharp bend where it’s more interesting to stick to the wall).

But this heuristic approach works if you can control the algorithm.

Improving the AI

Another way is to enhance your NPC script, I think that’s what you meant with ‘personal space’, this would allow you to have finer tuning on behaviour but could result in more cumbersome code.

I feel like I’ve given you the wrong answer but I hope it helped you in some way and gave you some ideas.

Best of luck to you!

[saucy_saint]

Oh no worries, this actually gives me a good place to start! Your first suggestion got me thinking about how I could interact with the navigation server, so that definitely helps get the ball rolling.

In the meantime, I’ve actually found a few tweaks that have helped a bit:

• I went into the Navigation 2D section in the Project Settings menu, enabled Advanced Settings, then disabled Use Edge Connections. I don’t know what this did exactly, but it’s helped the paths have less abrupt changes.

• I altered the tiles themselves by making sure there’s a small gap of empty space between the navigation layer and the physics layer.

• I’ve set the CharacterBody2D’s Safe Margin to 3px. This has done a pretty decent job of making sure the NPCs don’t get stuck on corners.

There’s a few more tileset-specific things I’m going to try out which should further reduce contact with walls in the first place.

Something I noticed while studying the paths themselves is that it looks like the Navigation Server is placing the points at corners of the tiles. If I could offset the A* grid so that it’s placing the points in the centers, that actually might solve the problem somewhat.

If I find a substantial improvement, I’ll make sure to give an update!