Distance between two tiles / get_simple_path (?) for NPC on whole tilemap

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By BakouKai

Hi everyone,

I am currently working on a tilemap, bigger than screen where I manage to move my player thanks to many existing tutorials.

What I am also trying to do, is to have NPCs moving using the same process from specific points (I do not want them to just wander everywhere, but let say, from cities to cities).

I believe I face two problems :

  • I need to create path for every character even when the player is not on the tilemap
  • I want them to move while my tilemap scene is off (Player is not on the world map)

For this matter, I created a dictionary on a one-shot effort (but it can be updated) that is supposed to provide for each cities, the distance with the other existing cities.

Nonetheless, it seems I am facing some troubles with the get_simple_path between two cities.
I tried to use it between tilemap cells coordinate. Between map_to_world coordinate and alway get an empty path…

I am certainly doing something wrong here… but I am wondering if the get_simple_path is actually able to calculate a path/distance or if I should determine the distance between to cities in a whole different fashion…

if it is of any use, I am doing the following :

This function search for a city on my map. When it finds one, it launches another function looking for relatives distances between this city an all other “visitable” ( = cities) tiles.

func city_distances():
	var origin_cell = Vector2()
	for x in range(map_size.x):
		origin_cell.x=x
		for y in range (map_size.y):
			origin_cell.y=y
			if $Navigation2D/TileMap.tile_dic[origin_cell].visitable == true:
				Global.dic_cities_distances[$Navigation2D/TileMap.tile_dic[origin_cell].name]=all_cities_distance(origin_cell)

The following function is called whenever a cities is found, it crawls the tilemap in search for any other cities, and is supposed to provide a path between the first city and any other cities. The path lenght (which my be a bad idea) is supposed to give me an idea regarding the distances between the two said cities:

func all_cities_distance(origin_cell): #from one cell, crawl the tile_dic to find distances for all cities
	var temp_city_dist={}
	var target_cell = Vector2()
	for i in range(map_size.x):
		target_cell.x=i
		for j in range (map_size.y):
			target_cell.y=j
			var path = PoolVector2Array()
			if $Navigation2D/TileMap.tile_dic[target_cell].visitable == true && target_cell!=origin_cell:
#path = $Navigation2D.get_simple_path(origin_cell,target_cell,false) #attempt with cell coordinate
				path = $Navigation2D.get_simple_path($Navigation2D/TileMap.map_to_world(origin_cell),$Navigation2D/TileMap.map_to_world(target_cell),false) #attempt with map to world ..
				temp_city_dist[$Navigation2D/TileMap.tile_dic[target_cell].name]={"Distance":path.size()}
	return temp_city_dist

Result is a nice dictionary with Distance:0 between all cities… (path remains empty while debugging).

At this point, I am considering all options :smiley: Including different ways to get the distance between two tiles from a tilemap…

Many thanks for your help/questions/hints.

Best regards,

Bk

:bust_in_silhouette: Reply From: timothybrentwood

(path remains empty while debugging).

That indicates to me that your Navigation2D node isn’t set up properly. It seems to me that you are calling get_simple_path() with the correct arguments. Maybe try calling it with global positions and see if that gets you a path?

var tmap = $Navigation2D/TileMap
var origin_local = tmap.map_to_world(origin_cell)
var target_local = tmap.map_to_world(target_cell)
path = $Navigation2D.get_simple_path(tmap.to_global(origin_local), tmap.to_global(target_local),false)

Here is a video demonstrating using a Navigation2D node on a tilemap: https://www.youtube.com/watch?v=0fPOt0Jw52s

Here is a video on general path finding that also shows the alternative AStar node path finding: https://www.youtube.com/watch?v=Ad6Us73smNs
The video is a bit older, since it was created Godot added a AStar2D node where you can work entirely with Vector2’s instead of converting to Vector3’s. It’s very easy to download the code from that video and update it to use AStar2D.

Hi,

Thank you for the suggestion. Actually as the Navigation2D was working fine for my player, I did not question its set up in the first place.

It looks like a good place to start. Thank you for pointing it out. I check the videos and your code suggestion tomorrow and I give you feedbacks.

Best regards,

Bk

BakouKai | 2021-04-29 22:18

Hi again,

I managed to check the videos links you gave me. The first one is the one I referred to when I wanted my player to be able to move on the tilemap. What it described there is basically what I tried to replicate from player to “non player” characters.

I integrated the to_global() on my path definition with little success. All distances remains to 0.

So I wanted to see the value used in the $Navigation2D.get_simple_path().
Basicall, it seems that the map_to_world() is already giving me global coordinates as shows my output :

Origin Cell : (2, 16) - Local : (280, 1680)
target Cell : (18, 16) - Local : (2520, 1680)
tmap.to global for locals(o&t) : (281, 1680) & (2521, 1680)
Origin Cell : (2, 16) - Local : (280, 1680)
target Cell : (24, 6) - Local : (3360, 630)
tmap.to global for locals(o&t) : (281, 1680) & (3361, 630)
Origin Cell : (2, 16) - Local : (280, 1680)
target Cell : (28, 20) - Local : (3920, 2100)
tmap.to global for locals(o&t) : (281, 1680) & (3921, 2100)
Origin Cell : (2, 16) - Local : (280, 1680)
target Cell : (30, 28) - Local : (4200, 2940)
tmap.to global for locals(o&t) : (281, 1680) & (4201, 2940)
Origin Cell : (4, 3) - Local : (630, 315)
target Cell : (2, 16) - Local : (280, 1680)
tmap.to global for locals(o&t) : (631, 315) & (281, 1680)
Origin Cell : (4, 3) - Local : (630, 315)
target Cell : (11, 7) - Local : (1610, 735)
tmap.to global for locals(o&t) : (631, 315) & (1611, 735)

Seeing this, I believe I can easily compute the distances with basic Pythagorean stuff like sqrt((origin.x-target.x)²+(origin.y-target.y)²)

So that solves one part of my problem (getting distances between tiles of the map).

Now I believe it drops me with the other problem : if I cannot build a path between two points, in the very same script I manage to make my player move, I will not be able to make the NPC move…

I believe there should be no limitations regarding $Navigation2D (can be used many times right ? by different nodes…?)

To illustrate, here is the “working” code I am using to make my player move (in the very same script) :

func _unhandled_input(event):
	if event is InputEventMouseButton:
		if event.button_index == BUTTON_LEFT and event.pressed:
			var pos = cam_2D.get_global_mouse_position() #get the cliqued pixel, relative to portview I believe
			$HUDdebug.update_debug_HUD(event.global_position.x,event.global_position.y) #display on my debug HUD
			goal = pos
			var targetcell = $Navigation2D/TileMap.world_to_map(goal)
			print("Cellule visée : ", targetcell)
			var modified_goal = $Navigation2D/TileMap.map_to_world(targetcell) + $Navigation2D/TileMap.cell_size/2 #the player has to move to the center, so adding half a cell to the cell position.
			print("Changing goal from ", pos, "to ", modified_goal)
			print(" Cell Id : ", $Navigation2D/TileMap.get_cell(targetcell.x,targetcell.y))  #id of the targeted cell
			goal = modified_goal
			path = $Navigation2D.get_simple_path($Character.global_position,goal,false) #create the path toward the target
			#print("New Path is",path)
			$Line2D.points = path
			$Character.path = path #provide character with path
			$Line2D.show() #drawing the path

I fail to see huge differences…
The $Navigation2D is, I believe, set otherwise I would get an error because of non-instantiated object.
The path works for player on click.
I am not drawing the path for NPC (no line2D no nothing)

What do you think ?

BakouKai | 2021-04-30 07:45

Ho and just to be clear, here is how I changed the code to get the output :

if tmap.tile_dic[target_cell].visitable == true && target_cell!=origin_cell:
				var origin_local = tmap.map_to_world(origin_cell)
				var target_local = tmap.map_to_world(target_cell)
				print("Origin Cell : ",origin_cell," - Local : ",origin_local)
				print("target Cell : ",target_cell," - Local : ",target_local)
				print("tmap.to global for locals(o&t) : ",tmap.to_global(origin_local)," & ",tmap.to_global(target_local) )
				path = $Navigation2D.get_simple_path(tmap.to_global(origin_local), tmap.to_global(target_local),false)

BakouKai | 2021-04-30 07:48

Another idea : maybe I should just use a Path2D/PathFollow node ?

To be honest, I do not know when it is a viable solution…but based on the tutorials I have seen, it might just do the trick…

BakouKai | 2021-04-30 09:52

modified_goal = $Navigation2D/TileMap.map_to_world(targetcell) + $Navigation2D/TileMap.cell_size/2 
goal = modified_goal
path = $Navigation2D.get_simple_path($Character.global_position,goal,false)

You are calling get_simple_path() here with a point in the center of the tile whereas before you were calling it from whatever point the TileMap gives you (i would assume top left) Try this:

var tmap = $Navigation2D/TileMap
var half_cell = tmap.cell_size/2
var origin_pos = tmap.map_to_world(origin_cell) +  half_cell
var target_pos = tmap.map_to_world(target_cell) + half_cell 
path = $Navigation2D.get_simple_path(origin_pos, target_pos,false)

This modification may give you results, I’m a lot more hopeful for this than my suggestion of using a global position. If this doesn’t work, the next step is to record an origin point and destination point that are known to give you a path and just hard code those values into a get_simple_path() call in you func all_cities_distance(origin_cell): and make sure they still give you a path there. If they don’t, I think it would be your node structure causing it not to work.

I personally prefer using the AStar2D node for my path finding. It’s a little more front loaded effort to get it set up, but it’s a lot more robust and usable - for me at least.

timothybrentwood | 2021-04-30 14:07

hmmm good point.
I was actually trying your next step on my own, make it “spawn” on my “working” player to see if I could get a path but I am not done with it yet as it required some set up…

I try the middle of cell thing and come back at you.

I quickly took a look at AStar2D. As it seemed to be a completed different thing I will probably use it as a last resort solution. I did not knew there was an other way when I started this…

BakouKai | 2021-04-30 16:55

Ok, so I tried while adding half cells but failed to get results. (path.size() always == 0)

What I am actually trying is to get a path for npc at the same moment I get one for the player. Trying to send it in a random location from there.
It requires a little bit of set up as I want to be able to switch back to a more desirable setting once I get what is wrong.
I might get a good run tomorrow…

BakouKai | 2021-04-30 17:07

A little bit more on this.

I hard coded “local coordinates” and tried to see if I could get a path.

here is the chunk of code (it is ugly but I want to solve this ^^') :

	var vector1 = Vector2()
	vector1.x = 650
	vector1.y = 400
	var vector2 = Vector2()
	vector2.x=800
	vector2.y=600
	var temp_path = $Navigation2D.get_simple_path(vector1,vector2,false)
	print("temp path : ", temp_path)

In the same script, are my player movement on click and my paths generator.
Went if copy this in my player movement event I get something :

temp path : [(650, 400), (736, 437.5), (806, 542.5), (800, 600)]

While my loop in the path_generator just…gives nothing :

temp path : path : temp path : path : temp path : path
: temp path : path :

I am starting to feel there is something awkward and/or not ready when I call the path generator. So I will try to call it at the same moment I move my player to see if it changes anything…

BakouKai | 2021-04-30 17:26

ok so it worked when I called the city_dstances() at the end of the player movement func.

temp path : [(650, 400), (736, 437.5), (806, 542.5), (800, 600)] path
: [(351, 1732.5), (316, 1697.5), (246, 1592.5), (246, 1487.5), (316,
1382.5), (386, 1277.5), (456, 1172.5), (526, 1067.5), (596, 962.5), (596, 857.5), (596, 752.5), (666, 647.5), (666, 542.5), (666, 437.5),
(701, 367.5)] temp path : [(650, 400), (736, 437.5), (806, 542.5),
(800, 600)] path : [(351, 1732.5), (421, 1750), (526, 1697.5), (596,
1592.5), (666, 1487.5), (736, 1382.5), (806, 1277.5), (876, 1172.5), (946, 1067.5), (1051, 1015), (1156, 962.5), (1226, 857.5), (1331,
805), (1471, 805), (1611, 805), (1681, 787.5)] temp path : [(650,
400), (736, 437.5), (806, 542.5), (800, 600)]

I was initially calling city_distances() at the end of the _ready():

func _ready():
	$Character.show()
	$floating_Label.hide()
	map_size=Global.map_size
	is_hovering = false
	if Global.dic_cities_distances.size()==0: #if it has not previously been done, populates the city_distances dictionary. Has to be reperformed if a new city is added
		 city_distances()

I do not get it as my code is not preparing anything fancy nor initiates things for the $Navigation2D to work on click.

I would like to understand this…

BakouKai | 2021-04-30 17:34

From my understanding, the nodes at the bottom of the hierarchy have their _ready() functions called first then it goes up the tree from there. I would bet that Navigation2D nodes need to have their _ready() functions called before they will work properly. You can test which node is ready first pretty easily. Add this code to the node where you were calling city_distances() from _ready() (replacing the node path in get_node() to match yours, you can drag and drop the path from the scene tree on the left):

extends Node2D

var my_cool_var

func _ready() -> void:
	my_cool_var = 'node'
	print('nav is inside tree: ',  get_node("../Navigation2D").is_inside_tree())
	print('nav is ready: ', get_node("../Navigation2D").my_cool_var != null)

and add this code to your Navigation2D script (again replacing the node path in get_node() to match yours):

extends Navigation2D

var my_cool_var

func _ready() -> void:
	my_cool_var = "nav"
	print('node is inside tree: ',  get_node("../Node2D").is_inside_tree())
	print('node is ready: ', get_node("../Node2D").my_cool_var != null)

timothybrentwood | 2021-04-30 20:42

Hi, I am a little bit confused about what this is supposed to achieve.

I think I have enought material to get around my problem, but when I tried you thing is crashes stating I cannot call is_inside_tree" on a null instance from my navigation2D.

There is nothing (no script) in my navigation2D so I added just this.

Is it a cross checking variable (navigation calls node’s variable and tries to display it, while the node tries to call navigation’s variable ?)

I will try to just go with distance calculus and check that on a given timer, my NPC movements func manages to get paths. Hope it works!

Sincerely thank you for you time and help !

BakouKai | 2021-05-08 13:42