How to get Navigation2D to respect Tilemap Navigation Polygons?

Question

When calculating paths on a tilemap, Navigation2D only uses the provided Polygons as indicators, and not as hard constraints on where the path can be. When trying to use a Tilemap with more complex tiles, this can lead to characters phasing though walls, because Navigation2D simply ignores that the navigation polygon dictates that a region is inaccessible.

Here is a basic example:

This Screenshot is the navigation Polygon for a tile. For humans looking at it, a character that wants to get from the top to the bottom would need to follow the specified zig-zag path. Godot however will determine, that the polygon provides some connection between the top and the bottom, therefore the resulting path is a straight line from top to bottom, ignoring the zig-zag pattern. Now my question is:

How can I make sure that Godot will respect the specified polygon?

The only solution I came up with is to divide each Tile into n*n smaller tiles, which each have their own polygon. That would include large refactorings to my map generation (instead of single tiles being placed, n*n tiles must be placed (in correct config), which also has performance implications).

Ideally, I would like the resulting paths to respect the polygons (I know this has performance implications, but caching would solve most of them).

Comments

Personally, I wouldn't really consider the navigation you drew on that tile to be suited for a tile. Your solution makes more sense for that because that's what I think of when I see that: it's a TileMap. That being said, you could try to add collision polygons where the navigation isn't filled in and see if your characters will follow the zig zag pattern. Edit: you could also try calling get_simple_path(start: Vector2, end: Vector2, optimize: bool = true) with false as the third argument and see if that helps.

However, I think you might be trying to solve a simpler problem in a needlessly complex way. I'm not trying to be mean with these questions, I'm trying to get an understanding for the necessity of that particular navigation.

1. "When trying to use a Tilemap with more complex tiles, this can lead
   to characters phasing though walls" can you expand on that? I see no
   walls in that tile. Could you provide a better example with walls?
2. Why is there a zigzag for navigation?
3. Why is it so important that units follow that zigzag?
4. What specifically does it contribute to the mechanics of your game?

---

To be fair, the zig-zag is an extreme example, and I only used that to give a very simple to understand Tile, where navigation2D ignores the given Navigation. There is no such extreme zigzag in my game.

For a real example, consider this apartment tile. The tile is boxed in by walls and only has an opening, the door, at the bottom.

The simplest navigation polygon that respects the walls would be something like this:
(I turned off the snapping lines to give better visibility of the tiles. The Polygons are therefore guaranteed to reach the border)

However, Godot is not able to tell, that the little door at the bottom could serve as a connection to other tiles. Therefore characters are not able to enter/leave this tile. To let Godot know that there is an entrance, the whole side must be inside the navigation polygon, which leads to this workaround:

And now the problem is that Navigation paths just ignore the bottom wall and let characters walk straight through the wall.

Now to answer some questions:

Why is a whole apartment a single tile?

• I am building a Simulator that is set in a generated city. To reduce the number of tiles necessary to place and limit the complexity of the map generation, I chose to use single tiles for whole apartments. Switching to n*n smaller Tiles would be a lot of work, especially for the streets, which currently use auto tiling to be laid out.

Why is it so important that units follow that zigzag / What specifically does it contribute to the mechanics of your game?

• Seeing the people and the own character just phase through walls is bad for immersion and it just looks wrong. So it's a visual thing.

Why not just use collisions on the walls?

• This would require each character to process collisions, which, given the number of characters is 500+, is not an option simply because of performance.

What about using optimize: bool = false?

• I have already tried that. Just upfront: This does not solve the problem itself. When using non-optimized paths, the units will always enter/exit tiles at the halfway point of a tile border. This means there are only 4 points at which they can enter/leave tiles. This "solves" the problem, by forcing all characters that enter the apartment to enter through a point that happens to align with the door. However, this also means that all characters walking along the streets are forced onto these paths and it just looks wrong. As mentioned, this also does not solve the underlying problem of navigation2D ignoring the polygons.

---

I've had navigation setup similarly to the first demonstration, albeit with an exit out the top as well and Godot recognized that as a valid path. I think your issue might have been with the tile connecting to it. Navigation is very finicky - if you're not on the edge of the tile with all of your collision polygons they won't connect.

"To reduce the number of tiles necessary to place and limit the complexity of the map generation, I chose to use single tiles for whole apartments."
You're using a hammer where you want to be using a multi-tool. When I think of a room built using a TileMap I think of something along the lines of this:

You are trying to make your TileMap function something like this where buildings and entire parks occupy entire tiles:

TileMaps can work for either situation but not both at the same time. You want a tile set that allows you to have the map movement of a the second image with the navigation precision of building a room like the first image. Those are two conflicting goals.

I think at the very least you want to make the tiles you've shown me be a set of 3x3 tiles to get the functionality you desire. Or deal with the phasing in and out of walls.

I mean my park visitors in roller coaster tycoon phased through things all the time but I didn't care because I was too busy enjoying the other mechanics of the game. Let other people play it and don't tell them about your worries and ask them what they think of it. A lot of the stuff I thought was stupid and needed to be changed in my games turned out to be a hit when I got people to play test them.

---

In both cases you mentioned, the tiles do not really have navigation polygons. In both cases, a tile can either be accessed via the navigation, or it cannot. But Godot has navigation polygons so why are they ignored when defining anything with even the slightest complexity? The current implementation could work just as fine with a boolean for each side that specifies if characters can enter/leave through this side. But Godot provides the possibility to define these arbitrarily complex polygons, so I hope there is a way to actually use them.

---

I see what you're getting at. They use polygons and not booleans because it's designed to let you have n-sided polygons be your tiles. I think they designed the Navigation2D being used with a TileMap with the first image I linked you in mind. You would have tiles that basically connect to each other thinking that your characters will treat the each tile as a step with no sub-tile navigation. The thought being that if you want sub-tile navigation that you would just make your tiles smaller.

If you add a NavigationPolygonInstance as a child of the Navigation2D node the paths you get will absolutely follow the intricacies of the paths you define via your polygon as demonstrated in this video: https://www.youtube.com/watch?v=Ad6Us73smNs

I still agree with their design choice with how the Navigation2D node works with a TileMap child since I think that's how most people think TileMaps should work. I can absolutely see how it could lead to confusion since it's not very well spelled out.

---

So I did some more reading on that, and I am a bit confused on why this behavior occurs. The way I understand it is that each Tile basically has its own little NavigationPolygonInstance and the TileMap then passes all those to the Navigation2D node. (At some point they will be combined into a single "big" NavigationPolygon Instance).

From what I can tell the pathfinding then takes some shortcuts, by assuming that if the target point and the entry point are both in the polygon, there must be a straight path connecting them.

I'll try to find the implementation of that in hopes to get more clarity on this. But in my opinion, there should be some option to allow sub-tile navigation to behave properly.

---

I have found some related Issues on Github, see this comment on Github

---

Neat, that's good information. I'm not a fan of using the Navigation2D node for navigation on TileMaps I use the AStar2D node instead. Unfortunately, that won't help your situation since it doesn't offer sub-tile navigation either. The get_simple_path() function is a bit janky like you said. I don't like how it returns straight line navigation as 2 points regardless of the distance between them. It also cuts corners instead of always going through the center of the tile (if you have your TileMap setup to do that). You get the path tile-to-tile back from the AStar2D node so you can position in the tile where ever you want per tile.

It seems like you'll have to wait until 4.0 is out for sub-tile navigation. It should be out this year.