How to implement pathfinding with a Tilemap?

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By Zylann
:warning: Old Version Published before Godot 3 was released.

I see there is an example of NavigationPolygon, but how should I proceed with TileMaps?
Also, I have dynamic elements such as lockable doors, moving crates etc…

I have tried this with an isometric tilemap for some time now but I cannot just get it to work. I have my navpolygon snapped to grid at 32x32 and rotated 45 deg. when exporting. Tilemap is 64x64 isometric.

It works perfectly with square tilemap. Can someone help me out on what I’m doing wrong?
Dropbox - File Deleted - Simplify your life

Or is it possible to get the polygon from the navpoly at runtime in order to see how it is drawn? It could make debugging easier since i think it is some overlap problem.

patrik | 2016-04-12 20:42

:bust_in_silhouette: Reply From: PixelWizzard

I am currently working on a project using pathfinding with a tilemap. If I can create a more simple version of what I currently have, I will try to upload and link it here.

Okay, you now can download a simple demo here. I tried to strip down a game of mine, so there could be some small pieces of code left, that aren’t needed…

PixelWizzard | 2016-03-21 15:26

I know this was posted a long time ago, but I still want to point out that the repository linked in the comment does no longer exist and leads to a 404 page. Which is sad because I was looking forward to have a look … : )

Noël | 2017-09-25 12:02

:bust_in_silhouette: Reply From: batmanasb

I was wondering the same exact thing a few days ago and found this: https://github.com/FEDE0D/godot-pathfinding2d-demo

Basically what you do is create a tileset the alternative way (recommended on docs) which is to convert a scene into a tileset. So basically make a new scene and add sprites the way you normally make a tileset, then you can attach NavPolyInstances to each tile. Then in your map scene, make the TileMap a child of a Navigation2D and all the NavPolyInstances on the tiles will combine.

I’m pretty sure this works dynamically, so if you change the tilemap thought code it will update the navigation. However I have yet to figure out how to make the navigation avoid moving objects, such as a RigidBody2D.

I’ll test this as soon as I can :slight_smile:
But, am I forced to put the tilemap as child of Navigation2D? Because I’ll have to update lots of paths to the tilemap, while it’s not related to navigation. Also, my world is made of rooms, and each room is made of a tilemap. Should Navigation2D be on top of all of them?

Zylann | 2016-03-21 18:09

All I know (haven’t had the chance to make my own TileMap yet) is that Navigation2D to a NavigationPolygonInstance is like a StaticBody2D to a CollisionShape2D, but maybe a dirty little trick such as changing the root node of the scene from the usual Node2D or Node, to a Navigation2D might work… maybe.

batmanasb | 2016-03-21 18:16

I just tested with two tilemaps in the example, and it works! This is wonderful! I love this game engine <3

Zylann | 2016-03-21 19:17

Awesome! But just to clarify, what works? What exactly did you do? I’m curious :stuck_out_tongue:

batmanasb | 2016-03-21 19:20

I just wanted to see if having multiple tilemaps works too, and it does :slight_smile:
But now, I realize that my levels are built the opposite way: instead of placing tiles AIs can walk on (those with NavPolys), I usually place tiles that can’t be walked (walls). I even have one tilemap for the ground, and another for walls because they are blended together (so I don’t have to update wall tiles if I change the ground).
I wonder how I should adapt the example to my game. Place invisible tiles on the Walls tilemap just to build the navigable part?
EDIT: this is discussed here: Need to occlude NavigationPolygon set in TileSet at runtime · Issue #3821 · godotengine/godot · GitHub

Zylann | 2016-03-21 19:29

Multiple TileMaps is less efficient, but if that works for you then that’s fine. But wait, I’m not sure how you are building the the navpoly. You can’t place walls to block off a navpoly, blocking off navpoly only works if you draw shapes inside shapes in a single NavigationPolygonInstance. I think a good approach would be to just add square NavigationPolygonInstances to the floor/ground tiles or make another TileMap and then place NavPolyonInstances over the ground, and nothing on the wall tiles.

batmanasb | 2016-03-21 20:08

What I’ll do for now is to dedicate a tilemap to nav polys, or have two versions of ground tiles (one with, one without). Actually it would be easier if I could build navigation with occluders instead of “walkable” polys.

Zylann | 2016-03-21 20:39

I don’t think you can build navigation with occluders. Only way of occluding navpolygons is when you draw polygons within polygons in a single NavigationPolygonInstance, which wouldn’t work because each tile has a separate NavigationPolygonInstance. At least not yet…

batmanasb | 2016-03-21 21:00

I have tried this, see here for a screenshot: https://drive.google.com/file/d/1lsXUFawmC-GvstA3wmnaCfKauLyEQ8k5/view

but it is not working in godot 3. Have I done something wrong?

supagu | 2018-09-13 10:56

can we add something like floyd-warshall on godot?

c21james | 2019-08-25 14:30

:bust_in_silhouette: Reply From: Migoun

The easiest way I can think of, is Smart Tilemap 2D

This is a paid product and should be disclosed as such.

nightblade9 | 2020-10-19 23:48