Does get_available_point_id in AStar is usefull ?

m21-cerutti

Hello, does get_available_point_id is useful in AStar in general ?

I am currently doing a template for hexagonal TileMap and pathfinding (2D), but it seems I need to create my own function to calculate the id from a position, because otherwise there is no way to have a bijection from tilemap coordinates (Vector2i) and index (int). On all example I see it use a map_size, like a hashing function, to get point id from coordinates, but seems very fishy to me, since I don't care about id value, I just want to access to the point I created.

func astar_add_walkable_cells():
	var cell_array = []
	for coords in get_used_cells(0):
			var position_cell = to_global(map_to_local(coords))
			var id = astar_node.get_available_point_id()
			
			var tile_data:TileData = get_cell_tile_data(0, coords)
			cell_array.append(id)
			astar_node.add_point(id, position_cell, 1.0)
			
	return cell_array


func astar_connect_walkable_cells(cell_array):
	for id in cell_array:
		var point = astar_node.get_point_position(id)
		for coords_neighbor in get_surrounding_cells(point):
			# Here no idea how to retrieve the id from position without closest_point (that would be algorithmically wrong) 
                        ...
			astar_node.connect_points(id, neighbor_id, false)

Seems so get_available_point_id is useless, and I would want to know in which context it can be useful ?

xyz

m21-cerutti Why simply not use AStar2D::get_closest_point() to get the point id from coordinates. That way you don't need to care about id or hashing. Let the astar object handle it.

m21-cerutti

xyz Because it is false, could be self or an other already connected node. We could check for those two cases but hell why do we need to check inside connection list for this ? It's not efficient. A closest_within_radius could maybe work (or check distance on the node get).

xyz

m21-cerutti Umm what do you mean by "false"? And what do you mean by "already connected node"? It's supposed to just return the closest point id. If all points are at tile centers and you pass it a tile center, you should get the id of that point. And how do you know it's not efficient? Have you profiled it?

m21-cerutti

xyz Maybe I need to profile it on a big map to see (but it is less efficient I would think than a hash function, haven't see yet implementation).
But my point is what if the point doesn't exist (borders) ? Or if there are holes in the map ? I said "false" because conceptually I don't want the nearest point, which could be 1km away, but effectively the node at the coordinates (x,y), within a certain epsilon maybe, or nothing at all. Maybe it's too picky for a general purpose astar graph, but seems to me using the hack get_available_point_id and get_closest_point is not safe when it comes to create connections. You don't have the security the node have been created at this position (and hard to debug without proper debug tools displaying the graph).

xyz

m21-cerutti It's trivial to check if the point position is approximately equal to the input position.

I'm not sure what get_available_point_id() has to do with your described problem though.

You seem to be creating a point for each tile. So just increment the id from 0 onwards when adding points. If you create a point at each tile center and query the id only via used cell coordinates, then it cannot possibly happen that you ask for a non existent point.

But even if you do ask for it, the proximity check can handle that.

m21-cerutti

Made recently a pull request inside godot demo we could use as base (I am not currently using get_available_point_id).
https://github.com/godotengine/godot-demo-projects/pull/1085